Final Details


Exam Policies

You will have 110 minutes to complete the exam. We will distribute the exam early and you can read and fill out the cover page of the exam, but you should not look at the exam questions until you are told to begin. You will not be allowed a calculator, cell phone, or any other electronic device.

Exam Topics

All material from Lecture one up to and including P/NP is fair game. The exam will focus on the material from sorting onwards.
  • Sorting:
    • Quadratic Sorts: Insertion Sort, Selection Sort
    • Faster Sorts: Heap, Merge, Quick
    • Sub Linlog Sorts: Bucket Sort, Radix Sort
    • Understand their runtimes (best and worst case)
    • Understand the lower bound for comparison-based sorting
  • Parallelism:
    • ForkJoin Parallelism, and Associated Terms (Work, Span, etc.)
    • ForkJoin Applications, ex: Parallel Summing of an Array
    • Reduce: parallel sum, multiply, min, find, etc.
    • Map: bit vector, string length, etc.
    • Be able to write Java ForkJoin code
    • Parallel Prefix Sum Algorithm, Filters, etc.
    • Analysis of Parallel Algorithms
    • Parallel Sorting
    • Amdahl's Law
  • Graphs:
    • Graph Definitions
      • Directed/Undirected
      • Weighted/Unweighted
      • Simple/Multi
      • Walks, Paths, Cycles
      • Connectedness
      • Trees, DAGs
    • Graph Representations
      • Adjacency List
      • Adjacency Matrix
      • When to use each representation
    • Graph Searches
      • Breadth-First Search
      • Depth-First Search
      • Minimax
      • Alpha-Beta
    • Other Graph Algorithms
      • Topological Sort
      • Union Find
      • Dijkstra's Algorithm
      • Prim's Algorithm
      • Kruskal's Algorithm
  • Reductions & P/NP:
    • Understand what a reduction is
    • Understand what the complexity classes P/NP/EXP are
    • Be able to explain why a decision problem is in P, NP
    • Understand what NP-Complete and NP-Hard mean
  • Pre-Midterm Material: The exam will focus on the newer material, but there will likely be smaller questions that relate to the earlier material. Additionally, since much of the material builds on itself, it would be unwise to not study things like complexity analysis.

Untested Topics

The following topics will not appear on the exam:
  • Eclipse
  • Generics
  • JUnit Testing
  • Java syntax
  • Concurrency

Miscellaneous

  • Note that you will be required to write Java code (in particular, it will be Fork-Join code), but we will not be sticklers for Java syntax. We will care about edge cases and correctness issues in your code.
  • Writing a simple proof of some sort is a possibility. Any such proof will be intended to show that you know how to prove things. You will not be expected to have a "magic insight" in order to complete the proof.
  • The homeworks thus far are a decent indication of the types of questions that could be asked.

Practice Exams

We strongly suggest that you try to solve all of these problems yourself, on paper without looking at the answer key until you're done. You may also want to time yourself to practice your pacing.

Midterm Details


Exam Policies

You will have 50 minutes to complete the exam. We will distribute the exam early and you can read and fill out the cover page of the exam, but you should not look at the exam questions until you are told to begin. The exam will be closed book. You will not be allowed a calculator, cell phone, or any other electronic device.

Exam Topics

All material from Lecture 1 up to and including Hashing is fair game; Sorting will NOT be on the midterm.
  • Stacks and Queues: implementations, runtimes, when to use them
  • Big Oh (and Omega & Theta):
    • Know the definition
    • Be able to evaluate whether f(x) is O(g(x)), Big Omega, Big Theta
    • Be able to find constants c & n0 to demonstrate Big Oh, Big Omega, Big Theta
    • Examining code to determine its Big O running time.
  • Recurrence Relations:
    • Know closed form for common recurrence relations
    • Given a recurrence relation, solve to closed form
  • Amortized Analysis: Be able to understand and analyze amortized runtime arguments
  • Binary Heaps:
    • Structure & ordering properties
    • Insertion, findMin, deleteMin, increaseKey, decreaseKey, remove, buildHeap
    • Run-times for all the above; including intuition for expected O(1) for insert & O(n) for buildHeap
    • Array representation
    • d-heaps: how different/related to Binary Heaps
  • Dictionary ADT: insert, find, delete
  • Binary Search Trees:
    • Binary property, BST ordering property
    • Inorder, Preorder, Postorder traversals
    • Find, insert & delete
    • Run-times for all the above
  • AVL Trees:
    • BST with stored height & balance property
    • Height bound resulting from balance property
    • Insertions; different rotation cases, no delete
    • Run-time for find & insert
  • B-Trees:
    • Motivation for the B-Tree; how it can minimize disk accesses
    • Structure, ordering; use of M, L; principles behind the selection of M & L
    • Insertion, find, deletion; the rules followed for insertion and deletion will be those shown in lecture
    • Run-times of the above
  • Hash Tables:
    • Basics of good hash function design
    • Collision resolution:
      • Separate Chaining
      • Open Addressing: Linear Probing
      • Open Addressing: Quadratic Probing
      • Open Addressing: Double Hashing
    • Strengths/weaknesses of the above versions
    • Load factor
    • Run-times for the different versions (though you do NOT need to memorize the equations for expected # of probes for a given load factor)
    • Deletion
    • Rehashing

Untested Topics

The following topics will not appear on the exam:
  • Eclipse
  • Generics
  • JUnit Testing
  • Java syntax

Miscellaneous

  • Note that you may be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code
  • Writing a simple proof of some sort is a possibility. Any such proof will be intended to show that you know how to prove things. You will not be expected to have a "magic insight" in order to complete the proof.
  • The homeworks thus far are a decent indication of the types of questions that could be asked.

Practice Exams

We strongly suggest that you try to solve all of these problems yourself, on paper without looking at the answer key until you're done. You may also want to time yourself to practice your pacing.