Exam 1 Topics

Review materials covered from the slides, assigned reading, homework, plicker questions, and in-class questions. You should be able to sufficiently justify why any algorithm or data structure operation has the time complexity it does.

• Algorithm analysis
  • Definition of \(O, \Theta, \Omega, o, \omega\).
  • Show that \(f(n) = O(g(n))\)
  • Express and justify the runtime of any algorithm in \(O\)-notation (existing algorithms, or ones you create)
• How each data structure is implemented, any characteristic properties or definitions of the data structure, what operations an be performed on it, and the complexity of those operations. Data structures include:
  • Stacks
  • Queues
  • Linked lists
  • Trees and binary trees
  • Heaps (including definition and height)
  • Hash tables (including hash functions and collision handling strategies)
• Algorithms include
  • Execution of any data structure operation (e.g., push into a stack, dequeue, insert into a list, insert into a heap, extract maximum from a heap, find an item in a hash table using linear probing or double hashing, etc.).
  • Tree traversals (preorder, postorder, inorder, Euler tour)
  • Sorting (definition of stable sort, in-place algorithm, divide and conquer paradigm, lower bounds on comparison-based sorting)
    • Insertion sort
    • Heap sort
    • Merge sort (including sub-routine of merging two sorted lists)
    • Quick sort (including pivot selection, its affect on performance, and sub-routine of partitioning two lists)
    • Counting sort and radix sort

Exam 2 Topics

• All content from prior exams
• Binary search on an array
• Binary search trees (properties, height)
• Red black trees (properties, height)
• Design techniques: definition, general approach, when it’s used
  • Greedy method; greedy choice property
  • Divide and conquer; master theorem. I won’t ask you about induction nor integer multiplication.
• Algorithms include
  • Binary search on an array
  • Insert, find, delete from a BST
  • Insert, find from a RBT. I won’t ask you about deleting from a RBT
  • Making change (greedy)
  • Fractional Knapsack (greedy)
  • Activity Selection (greedy)

Topics are cumulative, both implicitly and explicitly. That is, many exam 2 topics depend on content we previously covered. For example, you’ll need to understand asymptotic notation as we continue to use that to represent the run time of an algorithm. It is also expected you understand and can use previous data structures and algorithms. While the explicit focus is primarily on most recently covered material, I may ask one or two questions from earlier topics covered.

Review materials covered from the slides, assigned reading, homework, plicker questions, and in-class questions. You should be able to sufficiently justify why any algorithm or data structure operation has the time complexity it does.

Types of questions

There is one page for each problem (which may consist of sub-problems).

Try to work as many problems as possible. If you get stuck, briefly write down your ideas and then move on to the next problem – you can come back later if there’s time. The last problem is a challenging bonus problem, which is worth less points. Save the last bonus question for last; it is entirely optional. Be concise and give well-organized explanations. Long, rambling, or poorly written/organized explanations, which are difficult to follow, will receive less credit.

Expect questions of the following form:

• A series of short answer / fill-in / multiple-choice questions. For example, I may ask you to provide a definition or indicate run time complexity using $O$-notation.

• Work through some algorithm on a given input. I’ll pick the algorithm at random because I want you to learn them all. For some more complex algorithms (e.g., insert into a heap, insert into a red black tree), I may ask you to do only a few operations.

• Design and analyze simple algorithms. These are much more unpredictable. I try to ask questions that involve a very simple modification to an algorithm we have seen before (in class or in homework), so be sure you understand the solutions to all the homework problems.

• One challenging (optional) bonus problem. Save this problem for last. Don’t be upset if you cannot solve this problem. (But, at least be sure to read it, since sometimes the problem is not as challenging as I think it is and there may be a very simple solution). If you cannot see how to solve the problem, feel free to write down your wild ideas or observations. You might get some partial credit if your idea is good.