Here are resources to help you prepare for exams. You may also want to see the class notes, class code, and the recordings of class sessions on Microsoft Stream.
Exam 2 will follow a similar format to Exam 1. The exam will open at 8 AM EDT on Thursday, April 8 and will close at 11:59 PM EDT on Friday, April 9.
What is the maximum height of a binary tree with n nodes? The minimum height?
Which has a more strict property, a binary heap or a binary search tree?
Which of the following is most likely to have the minimum possible height: a binary heap, a binary search tree, or a red-black tree?
What is the time complexity of searching for a key in a binary search tree?
If you recursively traverse all of a tree’s nodes, are you performing a breadth-first search or a depth-first search?
What problem does memoization solve?
What do greedy and dynamic programming strategies have in common? How do they differ?
Say you want to use Huffman codes to represent a string made from an alphabet that contains 16 characters, and it turns out every character appears with the same frequency. How will the encoding look compared to a fixed width encoding?
If an operation has an amortized time complexity of O(1), what is the upper bound on the time complexity of that operation when examined in isolation?
This exam will consist of multiple choice questions, short essay-style questions, and problems that require showing your work. For the latter category you will upload a scan of your work.
The exam will take place on Moodle here. The exam will open at 8 AM EST on Monday, February 22 and will close at 11:59 PM EST on Tuesday, February 23. Once you have begun the exam you will have a 2 hour time limit to complete it. The length of the exam will be the same as an exam that I would give during the length of our normal class period, so I anticipate that most students should be able to complete the exam within 1 hour and 20 minutes.
Write an algorithm for the the following problem, using the style of pseudocode from the book:
The input is an array of integers \(A\), and a “run length” \(r\). The algorithm preserves subsequences in the array that are part of non-negative increasing “runs” of length \(r\) or greater, and replaces any integer that is not part of a run with -1. We define a “run” to be a subsequence of length \(r\) or greater where each element in the subsequence is non-negative, and after the first element of the subsequence each subsequent element is one greater than the last.
For example, if given the following input:
\(A = \langle 1, 3, 4, 5, 3, 10, 11, 12, 13, 6 \rangle\)
\(r = 3\)
the algorithm should manipulate the array in-place so that it becomes this:
\(\langle -1, 3, 4, 5, -1, 10, 11, 12, 13, -1 \rangle\)
In addition to writing an algorithm in pseudocode, find the time complexities of the best and worst cases for your algorithm.
Algorithm A runs in time \(\Theta(n)\) and algorithm B runs in time \(\Theta(n^2)\). Does this mean that A is faster than B on all inputs? Explain your answer both intuitively in written form and mathematically by using the definition of \(\Theta\).
Consider the following question:
Which sorting algorithm is best: insertion sort, quicksort, or counting sort?
Is there a “right” answer to this question? Explain.