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 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)
  • Binary search trees (properties, height)
  • Red black trees (properties, height)
• 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, insert into a red-black tree, etc.). I won’t ask you about removing from a red-black tree.
  • Tree traversals (preorder, postorder, inorder, Euler tour)
  • Binary search on an array
  • Sorting (definition 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. It is also expected you understand and can use previous data structures and algorithms. 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 / concepts include
  • graphs (definition, how many edges (m) in a simple graph compared to number of vertices (n); adjacency list; adjacenecy matrix; which is more memory efficient for sparse vs. dense graph;)
  • DAG (directed acyclic graph; topological order of vertices; topological order is not necessarily unique)
  • tree (connected and acyclic; exactly one unique path between vertices; number of edges)
  • MST (minimum spanning tree; definition; not necssarily unique; )
• 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
  • Making change (greedy)
  • Fractional Knapsack (greedy)
  • Activity Selection (greedy)
  • Matrix chain product (dynamic programming)
  • 0-1 Knapsack (dynamic programming)
  • Graph searching algorithms: BFS & DFS, how they can be expanded to solve other problems
  • Topological order (find one for a graph; property that a graph has a topological order if and only if it is a DAG; is it unique)
  • Kruskal’s algorithm to find MST
  • Prim’s algorithm to find MST
  • Dijkstra’s algorithm to find single-source shortest path tree in graph with positive edge weights
  • Bellman Ford’s algorithm to find single-source shortest path tree in graph with negative edge weights; how to detect a negative weight cycle
  • DAG-based algorithm to find single-source shortest path tree in a DAG

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.