Final exam of CS 6363.004 (Algorithms):
Time: Thu, May 9, 11:00 AM-1:00 PM, in the usual classroom.
If room is available, we will start the exam at 10:45 AM.

Format: Closed book, Closed notes, No calculators, No computers. 
Six hand-written, 8.5" x 11" cheat sheets are allowed. 
Write on both sides of the paper, for 12 pages in all. 
You must bring your comet card (UTD Id) to take the exam.

Exam will have 3 parts: A, B, and C.
You need to answer either [Parts A and B], or [Parts B and C]. 
There will be roughly 3 questions in each part.
Section C will be the easiest and Section A is the hardest.

If you answer Parts A and B, all grades from A to F are possible.

If you choose to answer Parts B and C, the maximum grade possible is B+. 
The grading policy is as stated in the syllabus, except for A/A-.
Possible grades: B+ to F.

Note that answering Parts A and C is not an option.
______________________________________________________________________
Detailed topics for each section:

Section A:
All topics discussed in class, homeworks, practice problems, new problems.
Recurrences, code, design of algorithms, correctness, RT analysis, properties.


Section B/C:
Chapter 34:
Definitions: Decision problem, Polynomial-time reduction, P, NP, NP-complete.
Algorithms to find solutions using black-box algorithms for decision problem.
NP-completeness proofs:  Clique, independent set, vertex cover.

Chapter 26:
Description of Ford-Fulkerson, Edmonds-Karp algorithms.
Statement of max-flow min-cut theorem (MFMCT), correctness.
Run Edmonds-Karp algorithm on given inputs.
Find a min-cut of given graph from a maximum flow, based on proof of MFMCT.
Maximum matching in bipartite graphs.

Chapter 25:
Recursion and code for Floyd-Warshall's algorithm.  Run it on given inputs.

Chapter 24:
Structure theorem of shortest paths.
Bellman-Ford algorithm: recurrence, code: Book version (take 3).
Properties of shortest paths.
DAG-shortest-paths algorithm: code, run on given inputs.
Dijkstra's algorithm: code, run on given inputs.
Correctness of DAG-shortest-paths and Dijkstra's algorithms.

Chapter 23,21:
Code for Prim and Kruskal's algorithms for MST, run on given inputs.
Code for Disjoint-set Union/Find algorithms.
Greedy choice theorem of MST: statement and proof.
Generic MST algorithm and its proof of correctness.

Chapter 22:
Depth-first search (DFS): code, run on given inputs.
Statement of parenthesis property and white path theorem.
Classification of edges of a graph by DFS.
DFS algorithm for topological ordering: code, correctness, run on given inputs.
Algorithm for strongly connected components (SCC): code, run on given inputs.
Breadth-first search (BFS): code, run on given inputs, applications.

Chapter 16:
Activity selection (ASP): greedy algorithm, correctness, run on given inputs.
Huffman coding algorithm: code, run on given inputs.

Chapter 15:
Dynamic programming: rod-cutting problem (recurrence and DP code).
Longest common subsequence (LCS): recurrence, code, run and on given inputs.
Longest monotonically increasing subsequence problem: recurrence, code.
Code to find actual solutions (and not just the optimal value).

Chapter 9:
Randomized O(n) algorithm for Select (median): code, RT analysis, applications.

Chapter 8:
Counting/Radix sorts: code, run on given inputs, applications.
Omega(n log n) lower bound for comparison-based sorting.

Chapter 7:
Partition: code, loop invariant, run on given inputs, 3-way partition.
Quicksort: code, running time (without proof).

Divide and conquer:
Merge sort and merge: code, correctness, run-time analysis, run on given inputs.
Binary search: code, correctness, run-time analysis, applications.
Power algorithm to calculate x^n: code, correctness, run-time analysis.
Order notation, run-time analysis of programs.
Recurrences and their solutions (Iteration, Substitution, Special case of MM).
Sums of sequences (arithmetic, geometric, harmonic).