DS 学习 - 打卡贴【欢迎指教】

11-27-2016

Finish Week 4 (all pairs shortest path) in Algorithms: Design and Analysis, Part 2
- Floyd-Warshall algo, Johnson's algo

11-28-2016

Week 5 lecture in Algorithms: Design and Analysis, Part 2
- NP-complete, Vertex cover

11-29-2016

Week 5 lecture in Algorithms: Design and Analysis, Part 2
- TSP

12-3-2016

Finish Week 5 in Algorithms: Design and Analysis, Part 2
- implement TSP, my code using bitarray is very slow. it takes 35 minutes for 25 nodes.     

12-4-2016

Week 6 lecture in Algorithms: Design and Analysis, Part 2
- dynamic programming heuristic for knapsack  

12-5-2016

Week 6 lecture in Algorithms: Design and Analysis, Part 2
- local search algo.

12-6-2016

Week 6 lecture in Algorithms: Design and Analysis, Part 2
- 2-SAT problem, Papadimitriou's algo, 2SAT via SCC

12-7-2016

Week 6 programing assignment in Algorithms: Design and Analysis, Part 2
- implement 2SAT using Tarjun algo. (SCC)

12-9-2016

Finish Week 6 in Algorithms: Design and Analysis, Part 2
- Matching

12-10-2016

read ch15.1-15.2 in "Introduction to algorithms"
- Dynamic programming: rod cutting, matrix-chain multiplication