This is one of the most difficult courses in the CS major if you are not good at Leetcode and are weak in graphs and proofs. This is a graph-heavy course. So understand graph theory well and how to write proofs. The knowledge you gained in COMP210 and COMP283/MATH381/STOR315 will help in this course. Try solving at least 2 new problems every day and post on Campuswire/Piazza to see if it's correct. You can ask unlimited questions on Campuswire/Piazza so make use of it when you don't understand anything. Go to office hours early and a lot.
If you have been doing leetcode for a while, this is the course where that will pay off. The topic that students find most difficult is dynamic programming.
Public proof that COMP550 can be hard.
The below is taken from Professor Kevin Sun's syllabus.
Content
- Array Algorithms
- Max in Array
- Two Sum
- Binary Search
- Selection Sort
- Merge Sort
- Basic Graph Algorithms
- Breadth-First Search
- Depth-First Search
- Minimum Spanning Tree
- Greedy Algorithms
- Selecting Compatible Intervals
- Fractional Knapsack
- Dynamic Programming
- Sum of Array
- Longest Increasing Subsequence
- Knapsack
- Edit Distance
- Independent Set in Trees
- Shortest Paths
- Paths in a DAG
- Dijkstra's algorithm
- Bellman-Ford
- Floyd-Warshall
- Flows and Cuts
- Ford-Fulkerson
- Bipartite Matching
- Vertex Cover of Bipartite Graphs
- NP-Hardness
- Basic Computational Complexity
- 3-SAT to Independent Set
- Approximation Algorithms
- Vertex Cover
- Load Balancing
Notes
You can find Professor Kevin Sun's notes here.
Learning Outcomes
- Summarize, interpret, and present quantitative data in mathematical forms, such as graphs, diagrams, tables, or mathematical text.
- Develop or compute representations of data using mathematical forms or equations as models, and use statistical methods to assess their validity.
- Make and evaluate important assumptions in the estimation, modeling, and analysis of data, and recognize the limitations of the results.
- Apply mathematical concepts, data, procedures, and solutions to make judgments and draw conclusions.
- Synthesize and present quantitative data to others to explain findings or to provide quantitative evidence in support of a position.
Textbook
- Algorithms by Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani
- Algorithms by Jeff Erickson
- Algorithm Design by Jon Kleinberg and Éva Tardos
- Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
Video Playlists
There are people who follow Abdul Bari's YouTube videos. Abdul Bari explains the algorithm but they don't show you how to write the proofs. This is a good video playlist to understand the algorithm. I haven't seen a good video playlist on how to write the algorithm proofs.
Check the Study Strategy.