Friday, August 21, 2015 (10:50 am11:50 am, EEB 026)
Final Details
Exam Policies
You will have 60 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, closed notes. 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 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
Concurrency and Synchronization:
Race Conditions
Bad Interleavings
Synchronizing your code
Mutexes
Deadlock
Graphs:
Graph Definitions
Directed/Undirected
Weighted/Unweighted
Simple/Multi
Walks, paths, cycles
Connectedness
Trees, DAGs
Graph Definitions
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
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
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.
You will have 60 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, closed notes. 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
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 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.