What This Document Is
This document contains a complete set of solutions for a final exam in Introduction to Graduate Algorithms (CS 6515) at Georgia Tech, taken in Fall 2017. It showcases a student’s completed exam, including handwritten work and grader annotations.
Why This Document Matters
This resource is valuable for students currently enrolled in or preparing for CS 6515, or a similar graduate-level algorithms course. It provides insight into the expected level of detail, problem-solving approaches, and grading criteria for exams. It’s particularly useful for self-assessment and understanding common pitfalls.
Common Limitations or Challenges
This is a single student’s work and represents one possible approach to solving the exam problems. It does not represent *all* correct solutions, nor does it offer comprehensive explanations of the underlying algorithmic concepts. Relying solely on this document will not guarantee success on the exam.
What This Document Provides
The full document includes:
* A completed exam booklet with answers to seven problems: Word Ladder, Recursion & Master Theorem, NP-Completeness of Subgraph Isomorphism, Shortest Path Linear Program, NP-Hardness of Maximum Clique, Approximation of 3-Matching, and Approximation of Vertex Cover.
* Detailed workings for problems involving recurrence relations and the Master Theorem.
* Grader’s initial and points awarded for each problem.
* Instructions and logistical information from the original exam.
This preview *does not* include the full solutions to all problems, only a portion of the Recursion & Master Theorem section. It does not provide explanations of the algorithms or concepts tested.
