CS341: Algorithms
Fundamental course. The goal of this class is not as much about learning different algorithms, but rather focusing on understanding proving the correctness of these algorithms.
I’ve been focusing on the wrong thing. Understand how these algorithms are proven so you know they are correct.
Remember the method
It is more important to remember the method than the result. The result can always be derived again if forgotten.
Lecture notes https://cs.uwaterloo.ca/~lapchi/cs341/notes.html
I fcked up the midterm like really really bad. This is probably due to me not doing leetcode for a few months. I become super washed. And I really suck with coming up with Divide and Conquer algorithms fast. And then the graph question fcked me up. So I just really really messed up.
- got 52% on the midterm after curve
I think the teacher said something pretty inspiring: the reason they need to be so harsh on us is that these algorithms that we’re going to be developing for companies are going to be to deployed at scale. We cannot let them be wrong. We need to guarantee correctness. Else, lives are at risk. This is part of our training as engineers.
Plan:
- Practice on tutorials
- Do leetcode
- Greedy algorithms
- Dijkstra’s
- Minimum Spanning Tree
- DP
- Polynomial Time Reduction
- Grind homework again
- Find past exams and do them past
- MST
- come up with proofs fast
- I can quickly come up with the subproblem for the DP
- However, proving them so that it is correct? Do like longest increasing subsequence
I struggle mostly with the correctness of the algorithm.
- For example, proving that the interval scheduling algorithm is correct
In the exam, you need to come up with these proofs on the fly. You need to be able to think fast.
Concepts
- Divide and Conquer
- White Path Lemma
- Breadth-First Search
- Depth-First Search
- Greedy Algorithm
- Dynamic Programming
- Longest Increasing Subsequence
- Longest Common Subsequence
- Optimal BST
- Bellman-Ford Algorithm
- Polynomial Time Reduction
- NP-Completeness