/Algorithms-Design-and-Analysis-Part-2

Solutions to Programming Assignments of Coursera's Algorithms: Design and Analysis, Part 2 by Prof. Tim Roughgarden

Primary LanguageC++

Algorithms: Design and Analysis, Part 2 - Codes for Programming Assignments in C++

Week 1

  • Question 1 (Greedy Scheduling 1) - Compile and run greedyjob1.cpp
  • Question 2 (Greedy Scheduling 2) - Compile and run greedyjob2.cpp
  • Question 3 (Prim's algorithm) - Compile and run primheap.cpp

Week 2

  • Question 1 (max spacing k-clustering) - Compile and run firstproblem.cpp
  • Question 2 (Hamming distance and k-clustering) - Compile and run secondproblem.cpp

Week 3

  • Question 1 (Knapsack problem) - Compile and run problem1.cpp
  • Question 2 (Knapsack problem on a larger input) - Compile and run problem2.cpp

Week 4

  • Question 1 (All Pairs Shortest Path algorithm (Floyd Warshall algorithm) - shortest shortest path) - Compile and run fwalgo.cpp (Run the program for graph1.txt, graph2.txt and graph3.txt)

Week 5

  • Question 1 (TSP problem) - Compile and run tsp.cpp - This program is a direct DP implementation and hence requires atleast 2 GB of RAM

Week 6

  • Question 1 (2 SAT problem) - Compile and run 2sat.cpp for 2sat1.txt, 2sat2.txt, 2sat3.txt, 2sat4.txt, 2sat5.txt and 2sat6.txt.