This class contains 6 large project, which was conducted in a group of 4. We where the only group to score highest in our class. Bellow is a general overview of what each project topic was about, and their respeictive problem titles.
Project 1: Backtracking and Heuristics
- Problem 1: Solving Sudoku Puzzles: Backtracking and Deductive Strategies
- Problem 2: Knight's Tour Problem with Backtracking and Accessibility Heuristic
- Problem 3: Magnets Puzzle with Backtracking and Search Space Reduction
- Problem 4: N-bit Grey Codes Generation: Backtracking vs Greedy Algorithm
Project 2: Grammatical Inference
- Problem 1: String Generation and Labeling with DFA Incidence Matrix
- Problem 2: Minimum DFA Construction using the Trakhtenbrot-Barzdin Algorithm
- Problem 3: DFA Labeling and Merge: Backtracking and Stack Implementation
Project 3: Search and Sort using Divide and Conquer
- Problem 1: MergeSort
- Problem 2: QuickSort
- Problem 3: Binary Search of an ordered list
- Problem 4: Optimal Binary Search Tree
Project 4: Greedy and dynamic programming
- Problem 1: Travelling Salesperson (TSP)
- Problem 2: Minimum spanning tree
- Problem 3: Huffman coding
- Problem 4: Job scheduling
- Problem 5: Knapsack
Project 5: Implementing Heapsort algorithm
Project 6: NP
- Problem 1: Polynomial-Time Verification Algorithm for the Clique Decision Problem
- Problem 2: Polynomial-Time Reduction of CNF-Satisfiability to the Clique Decision Problem
- Problem 3: NP-Completeness of Problem B Given Polynomial-Time Many-One Reduction from Problem A
- Problem 4: Establishing NP Membership for Problems in Examples 9.2 to 9.5