Simply put, an algorithm is a clear, step-by-step set of instructions for solving a computational problem. In this course, we will study algorithms rigorously. At the end of the course, the student should be able to design algorithms for problems, reason about these algorithms both in terms of correctness and efficiency, and communicate the algorithm and its analysis.

Class time and venue: 10 hour (M,W,F: 10:10am - 11:15am) + 10X (Thu: 12:15pm - 1:05pm). Cummings 100 (Spanos Audi)

Policies

Deliverables

Honor Principle : Must Read

Instruction Team & Office Hours

Textbooks and Resources

Tentative Schedule

Course schedule by day
12 Sep (Mon)	1. Introduction
14 Sep (Wed)	2. Big-Oh Notation	PSet 0 Due
15 Sep (X-hour)	3. More Big-Oh + Runtime Analysis
16 Sep (Fri)	4. Algorithms with Numbers
19 Sep (Mon)	5. Divide and Conquer (I) : Merge Sort + Recurrences
21 Sep (Wed)	6. Divide and Conquer (II) : Counting Inversions	PSet 1 Due
22 Sep (X-hour)	7. Divide and Conquer (III): Closest Points on a Plane
23 Sep (Fri)	8. Divide and Conquer (IV) : Polynomial Multiplication	APSet 1 Due
26 Sep (Mon)	9. Dynamic Programming (I) : Smart Recursion
28 Sep (Wed)	10. Dynamic Programming (II) : Subset Sum	PSet 2 Due
29 Sep (X-hour)	11. Dynamic Programming (III) : Knapsack
30 Sep (Fri)	12. Dynamic Programming (IV) : Edit Distance	APSet 2 Due
2 Oct (Sun)		CA1 Due
3 Oct (Mon)	13. Dynamic Programming (V) : Longest Increasing Subsequence
5 Oct (Wed)	14. Dynamic Programming (VI) : Conclusion	PSet 3 Due
6 Oct (X-hour)	15. Graph Algorithms: Introduction
7 Oct (Fri)	16. DFS	APSet 3 Due
9 Oct (Sun)		CA 2 Due
10 Oct (Mon)	17. Properties of DFS + Applications
12 Oct (Wed)	Spill over from Monday	PSet 4 Due
13 Oct (X-hour)	18. Topological Sort
14 Oct (Fri)	19. Top Sort Appl. + Strong Connected Components (SCC)	APSet 4 Due
17 Oct (Mon)	20. SCCs in linear time via DFS
18 Oct (Tue)	Test 1 (Big-Oh, Divide & Conquer, Dynamic Programming)	6pm - 9pm, Cummings 100
19 Oct (Wed)	21. Shortest Paths : BFS
20 Oct (X-hour)	22. Shortest Paths : BFS Proof
21 Oct (Fri)	No Class
24 Oct (Mon)	23. Shortest Paths: Finish up BFS proof + Dijkstra
26 Oct (Wed)	24. Shortest Paths: Finish up Dijkstra + Bellman Ford	PSet 5 Due
27 Oct (X-hour)	No X-hour. Instead DeepC's office hour moved to 12noon - 1pm
28 Oct (Fri)	25. Shortest Paths: Finish up Bellman-Ford	APSet 5 Due
30 Oct (Sun)		CA 3 Due
31 Oct (Mon)	DeepC out of town: Problem solving with Ankita.
2 Nov (Wed)	DeepC out of town: Extra office hour with Ankita.	PSet 6 Due
3 Nov (X-hour)	DeepC out of town.
4 Nov (Fri)	26. Flows and Cuts (over zoom) (scribbles)	APSet 6 Due
7 Nov (Mon)	27. Weak Duality (over zoom) (scribbles)
8 Nov (Tue)	Test 2 (DFS, BFS, Dijkstra, Bellman Ford)	6pm - 9pm, Cummings 100
9 Nov (Wed)	28. Res. Nets & Ford-Fulkerson (over zoom) (scribbles)
10 Nov (X-hour)	29. Applications of Flows
11 Nov (Fri)	30. Application of Cuts
13 Nov (Sun)		CA 4 Due
14 Nov (Mon)	31. Wrap up + Looking ahead + AMA
15 Nov (Tue)		PSet 7 + APSet 7 due

Accessibility Needs

Let me know before the end of the second week of the term if you will need a disability-related accommodation or service. In order for accommodations to be authorized, students are required to consult with Student Accessibility Services ("SAS" <student.accessibility.services@dartmouth.edu>; SAS websiteLinks to an external site.; phone: 603-646-9900) and to email me their SAS accommodation form. We will then work together with SAS if accommodations need to be modified based on the online learning environment. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

Wellness

We recognize that the academic environment at Dartmouth is challenging, that our terms are intensive, and that classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including: your undergraduate deanLinks to an external site., Counseling and Human DevelopmentLinks to an external site., and the Student Wellness CenterLinks to an external site.. I encourage you to use these resources and come speak with me to take care of yourself throughout the term.

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations.

To assist with calendar planning and awareness of our diverse religious and spiritual community, the list of holy days for 2020/2021 can be found at https://students.dartmouth.edu/tucker/spiritual-life/about-spiritual-life/holy-day-calendarLinks to an external site.. The list represents major holy days which may impact accommodation of campus events in general, as well as student course attendance, exams, Commencement and participation in activities 2020-2021. Thank you for your consideration. If you have any questions about these dates or other concerns, please contact Rabbi Daveen Litwin, Dean and Chaplain of the Tucker Center for Spiritual and Ethical Life.