CSE 202: Resources

Algorithm Design Techniques

• 1. Techniques for analyzing algorithms

Problems and Sample Solutions

• 2. Problems with linear or sublinear complexity

  3. Divide and conquer method, searching and sorting

     1. Solution for the maximum weight connected subgraph of a tree

  4. Greedy method

  5. Dynamic programming

  6. Algorithms on graphs

  7. Network flows

  8. NP-completeness and approximation algorithms

General resources

• 1. Guidelines for writing solutions

Notes

• 1. Correctness proof for Dijkstra's shortest-path algorithm

  2. Scheduling events to minimize the number of rooms

  3. Makespan problem --- approximation algorithm

  4. Weighted vertex cover --- approximation algorithm using layering method by Yatharth Saraf