This is the recitation homepage for Fundamental Algorithms.
The recitation is Fridays, 6:10-7pm in WWH 517.
My office hours are Fridays, 7-8pm in WWH 517.
If you cannot make these office hours due to a conflicting class, email me and we can meet another day.
### Main course page
### Recitation Notes
- Lecture 1, Sep 8: Induction, strong induction, and HW 1 clarifications.
- [Lecture 2, Sep 15](lecture-09-15.html): Asymptotic notation, HW1 problem 1 (c).
- [Lecture 3, Sep 22](lecture-09-22.html): Quick sort review, Hoare's partition algorithm, insertion sort vs quick sort, Towers of Hanoi problem.
- Lecture 4, Sep 29: (Prof Amir covered this one).
- Lecture 5, Oct 6: HW2 Q2, HW3 Q2.
- Lecture 6, Oct 13: HW4 Q2, why BST doesn't use heap property/alternate property, CLRS 12.2-5.
- [Lecture 7, Oct 20](lecture-10-20.html): Dynamic Programming review, word processing problem.
- Lecture 8, Oct 27: Midterm solutions.
- Lecture 9, Nov 3: [Tiling problem](https://www.iarcs.org.in/inoi/online-study-material/topics/dp-tiling.php) (DP), CLRS 16.2-7 (greedy).
- Lecture 10, Nov 10: HW7 Q4, CLRS Section 22.2.
- Lecture 11, Nov 17:
- HW9 Q3(a)
- CLRS Problem 22-2: articulation points (we did until part (b))
- (Optional bonus problem: CLRS 22.1-6: finding a universal sink).
- Lecture 12, Dec 1: Recap of Bellman-Ford, [avoiding trolls problem](lecture-12-01.html).
- Lecture 13, Dec 8: Recap of Dijkstra and Floyd-Warshall algorithms. Problems:
- CLRS 24.3-2 and CLRS 24.3-3
- Why can't we add a positive number to all edge weights to make all edge weights positive and then run Dijkstra's algorithm?
- Challenge: find the shortest path tree with minimum total weight (where the weight of a tree is the sum of the weight of all edges in the tree).
### Interview/Challenge Problems and Resources
Here are some websites with collections of problems and resources that will be useful if you want to prepare for an interview for a software engineering role at Google, Facebook, etc.
- [Topcoder Tutorials](https://www.topcoder.com/community/data-science/data-science-tutorials/)
- [SPOJ tutorial problems](http://www.spoj.com/problems/tutorial/)
- [USACO training program](http://train.usaco.org/usacogate)
- [Codeforces problem archive](http://codeforces.com/contests)
- [CodeChef practice problems](https://www.codechef.com/problems/school)
Many of the sites above also have regular programming competitions, which can be fun once you've learnt the basic algorithms and strategies.