What This Document Is
This document contains detailed solutions to Homework Two for Introduction to Graduate Algorithms (CS 6515) at Georgia Tech, from the Spring 2018 semester. It focuses on applying dynamic programming techniques to solve three distinct algorithmic problems. It’s intended for students who have completed the assignment and are seeking to review correct approaches and understand potential areas for improvement.
Why This Document Matters
This solution set is valuable for students enrolled in CS 6515, or similar advanced algorithms courses. It serves as a check for self-study, clarifies common misunderstandings, and demonstrates effective problem-solving strategies using dynamic programming. It’s most useful *after* a student has attempted the homework independently.
Common Limitations or Challenges
This document provides completed solutions, but it does not offer a tutorial on the underlying concepts of dynamic programming. It assumes a foundational understanding of the technique. It also doesn’t explain the reasoning *behind* the solutions in a pedagogical way – it presents the answers, not a learning path.
What This Document Provides
The full document includes:
* Detailed solutions for Problem 1: Longest Common Substring (with dynamic programming table definition, recurrence relation, pseudocode, and time complexity analysis).
* Solutions for Problem 2: Maximum Product (with table definition, recurrence relation, pseudocode, and time complexity analysis).
* Solutions for Problem 3: Coin Changing Variant (with table definition, recurrence relation, pseudocode, and time complexity analysis).
* Pseudocode for each algorithm.
* Asymptotic time complexity analysis for each algorithm.
This preview does *not* include the actual pseudocode, recurrence relations, or detailed explanations – only a high-level overview of the problems addressed and the solution approach used.
