About
This course is designed to be a survey of useful algorithms and their applications in competitive programming and coding interviews. Before taking this course, you should have a basic understanding of programming (61A or equivalent) and preferrably some experience with either Python or C++.
This course has some concepts in common with 61B, 70, and 170, but there is a bigger emphasis on implementation and application.
Location
Monday 6:30-8 PM @ Physics Building 2
Book
Schedule
| week | topic | book ch | resources |
|---|---|---|---|
| 1 (jan. 23) | input and output, time complexity | 1.2, 2 | slides pset |
| 2 (jan. 30) | prefix sums | 9.1, 2.4 | slides pset |
| 3 (feb. 6) | greedy algorithms | 6 | slides |
| 4 (feb. 13) | sorting, two pointers | 3.1, 3.2 | slides |
| 5 (feb. 20) | BREAK (PRESIDENT'S DAY) | ||
| 6 (feb. 27) | binary search | 3.3 | slides |
| 7 (mar. 6) | graph representations | 11, 12 | slides |
| 8 (mar. 13) | complete search with recursion | 5 | slides |
| 9 (mar. 20) | dynamic programming | 7 | slides |
| 10 (mar. 27) | BREAK (SPRING RECESS) | ||
| 11 (apr. 3) | more dynamic programming | 7 | slides |
| 12 (apr. 10) | segment trees | 9.3 | slides |
| 13 (apr. 17) | rolling hashes | 26.3 | slides |
| 14 (apr. 24) | wrap-up and final contest | slides |
Policy
Coursework
The class is composed of two components, the lecture between 6:30-8 PM on Mondays introducing concepts and a corresponding weekly assignment due at Sunday midnight. Two homework assignments will be dropped! We expect the homework to take around one hour of work. Some homeworks may have optional challenge problems. Homework will be conducted through Codeforces.
Remote office hours will be available on discord; schedules will be announced later this week.
Grading
| Category | Percent | Criteria |
|---|---|---|
| Homework | 70% | Demonstrated effort, participation |
| Attendance | 30% | Form with password at each lecture |
You receive a P in this class if you receive 70% or higher aggregate score. Late work will get 50% credit. The class shouldn’t be stressful! If you have extenuating circumstances or find yourself falling behind, please reach out to us.
Collaboration
Study groups are allowed and encouraged. Sharing ideas is fine, but sharing code is not allowed.
Course Staff
- Jelani Nelson (advisor)
- Xavier Plourde (lecture/content)
- Nishant Bhakar (OH)
- James Rungsawang (lecture/content)
- Ryan Zhu (lecture/content/OH)
- Chris Liu (content/problem writing)
- Vivek Verma (lecture)
- Youngmin Park (OH)
- Young-jin Park (infra)