Overview
CSCI 140 is an introduction to algorithm design and analysis techniques. The course covers basic techniques used to analyze algorithms, basic techniques used in designing algorithms, and important classical algorithms. The goal is to learn how to apply all of the above to designing solutions to new problems (a skill that you will practice throughout the semester). Grades will be based on problem sets, exams, and participation. The prerequisite for this class is CSCI62.
Resources
Instructor: Dr. Dave
e-mail: David.last_name@pomona.edu
office hours: Edmunds 224
Monday: 10:30am-12
Wednesday: 10:30am-12
Thursday: 2:30-3:30pm
and by appointment
Mentor hours (Edmunds 227):
Friday: 1-3pm (Emily), 4-6pm (Aidan)
Saturday: 9:30-11:30am (Millie), 10am-12 (Jiahao)
Sunday:7-9pm (Carl), 8-10pm (Alan)
Learning Community Meetings:
Thursday: 8-9pm (Emily & Carl, Edmunds upstairs)
Friday: 9-10am (Millie, Edmunds downstairs)
2-3pm (Jiahao & Aidan, Edmunds downstairs)
3-4pm (Jiahao, Edmunds downstairs)
4-5pm (Millie, Edmunds downstairs)
Assignment submission: Gradescope
Discussion/questions: Slack
Textbook: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, and Stein (CLRS). We will have some copies in the Edmunds lab library.
If you need accommodations please contact the Disability Coordinator on your home campus. The process for Pomona students is available here.
Logistics
The basic flow each week will be as follows:
You will be assigned to a small group of approximately 4 students the first week of classes. Your group will work together for the entire semester; your first task will be to find a time when you can all meet for an hour on either Thursday or Friday. The plan is for each group to have an assigned TA who will attend the meetings to answer questions, talk through concepts, etc. Each week there will be a low-stakes assignment to work on during your group meeting; this will be turned in on Friday evening on Gradescope.
In addition, there will be a weekly problem set. The assignments will mostly be done and submitted in pairs and will also be submitted on gradescope. The pairs will be by assignment for the first few weeks and then at your discretion after that. Problems on the assignment will ask you to apply concepts in new ways. As with the practice problems you may discuss the problems with anyone else currently taking cs140 (or with the TAs or myself), but each pair must write up their own solution.
Finally there will be checkpoints approximately every 4 weeks
The breakdown of grades will be as follows:
Calendar
This is a high-level outline of the planned syllabus. Note that the calendar is subject to change. Unless otherwise specified, the readings are in CLRS.
| Week | Day | Date | Topic | Reading | Due |
|---|---|---|---|---|---|
| 1 | T | 8/30 | introduction, proofs (ppt - other notes) | Ch 1, 2 | |
| Th | 9/1 | big-O (ppt) | Ch 3 | Assign 1 (.tex) due 11:59pm 9/4 | |
| 2 | M | 9/6 | recurrences (ppt) | Ch 2, 3 | |
| W | 9/8 | more recurrences (ppt) | Ch 7 | Group assign 2 due 11:59pm 9/9 Assign 2 (.tex) due 11:59pm 9/11 |
|
| 3 | T | 9/13 | sorting concluded (ppt) | Ch 8 | |
| Th | 9/15 | order statistics (ppt), basic data structures (ppt) | Ch 9, 10 | Group assign 3 due 11:59pm 9/16 Assign 3 (.tex) due 11:59pm 9/18 |
|
| 4 | T | 9/20 | hashtables (ppt) | Ch 9, 10 | |
| Th | 9/22 | |
Group assign 4 due 11:59pm 9/23 Assign 4 (.tex) due 11:59pm 10/2 test files |
||
| 5 | T | 9/27 | binary search trees (ppt) | Ch 12, 13 | |
| Th | 9/29 | heaps, heapsort, amortized analysis (ppt) | Ch 6, 17 | Group assign 5 due 11:59pm 9/30 | |
| 6 | T | 10/4 | graphs, traversals (ppt) | Appendix B.4-5, Ch 22, 24 | |
| Th | 10/6 | dynamic programming (ppt) | Ch 15 | Group assign 5.2 due 11:59pm 10/7 Assign 5 (.tex) due 11:59pm 10/9 |
|
| 7 | T | 10/11 | dynamic programming 2 (ppt) | ||
| Th | 10/13 | dynamic programming 3 (ppt) | Group assign 6 due 11:59pm 10/14 Assign 6 (.tex) due 11:59pm 10/16 |
||
| 8 | T | 10/18 | |
||
| Th | 10/20 | greedy algorithms (ppt) | Group assign 7 due 11:59pm 10/21 (solutions) Assign 7 (.tex) due 11:59pm 10/30 |
||
| 9 | T | 10/25 | |
||
| Th | 10/27 | minimum spanning trees, disjoint sets (ppt) | Group assign 7.2 due 11:59pm 10/28 | ||
| 10 | T | 11/1 | more graphs (ppt) | ||
| Th | 11/3 | single source shortest paths (ppt) | Group assign 8 due 11:59pm 11/4 Assign 8 (.tex) due 11:59pm 11/6 |
||
| 11 | T | 11/8 | all pairs shortest paths (ppt) | ||
| Th | 11/10 | network flow (ppt) | Group assign 9 due 11:59pm 11/11 Assign 9 (.tex) due 11:59pm 11/13 |
||
| 12 | T | 11/15 | flow applications (ppt NP (ppt) |
||
| Th | 11/17 | |
Group assign 10 due 11:59pm 11/18 Assign 10 (.tex) due 11:59pm 11/22 |
||
| 13 | T | 11/22 | |||
| Th | 11/24 | Thanksgiving | |||
| 14 | T | 11/29 | NP completeness (ppt) example reduction (.tex) |
||
| Th | 12/1 | linear programming | Group assign 11 due 11:59pm 12/2 Assign 11 (.tex) due 11:59pm 12/7 |
||
| 15 | T | 12/6 | review (ppt) |