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$. I won’t ask you about little-o ($o$) or little-omega ($\omega$).
  • Show that $f(n) = O(g(n))$
  • Express and justify the runtime of an algorithm in $O$-notation
• 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., 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)
• Concepts related to sorting
  • Definitions of stable sort, in-place algorithm, divide and conquer paradigm
  • Lower bounds on comparison-based sorting
  • Insertion sort
  • Selection 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

Topics are implicitly cumulative, not explicitly. That is, I will not directly ask you questions from exam 1 topics. However, 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. 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.

• Data structures include
  • 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.
  • Dynamic progrmaming
• Algorithms include
  • Execution of any data structure operation (e.g., insert/remove/find in a binary search tree, insert/find in a red black tree). I won’t ask you about removing from a red black tree.
  • Binary search on an array
  • Making change (greedy)
  • Fractional Knapsack (greedy)
  • Activity Selection (greedy)
  • Matrix chain product (dynamic programming)
  • 0-1 Knapsack (dynamic programming)

Instructions

• This is a closed book exam.
• Only one sheet of handwritten notes (both sides) is permitted.
• No cell phones, calculators, nor any other electronics.
• You will have 50 minutes to complete the exam.
• There are 6 questions worth 10 points and a 7th bonus question worth 5 points, for a total of 65 points. Your score will be taken out of 50 points maximum.

Read the first six questions first. Try to work as many of those 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. Save the last bonus question for last; the bonus problem 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 questions. For example, I may ask you to provide a definition, explanation, or run time analysis.
• Work through some algorithm on a given input, showing intermediate results. 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 1-2 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.