This Spring 2022 course has ended. However, many links below may not be working due to permission settings.

All lecture notes can be found here: https://www.cs.dartmouth.edu/~deepc/cs31-lecture-notes.htm

Please send comments to deeparnab@dartmouth.edu

Schedule

Course schedule by day
28 Mar (Mon)	Introduction
30 Mar (Wed)	The Big-Oh Notation
31 Mar (X-hour)	Big-Oh exercise; Runtime exercise
1 Apr (Fri)	Algorithms with Numbers
4 Apr (Mon)	Divide and Conquer (I) : Merge Sort + Recurrences
6 Apr (Wed)	Divide and Conquer (II) : Counting Inversions
7 Apr (X-hour)	Divide and Conquer Exercise
8 Apr (Fri)	Divide and Conquer (III) : Polynomial Multiplication
11 Apr (Mon)	Dynamic Programming (I) : Smart Recursion
13 Apr (Wed)	Dynamic Programming (II) : Subset Sum
14 Apr (X-hour)	DP exercise
15 Apr (Fri)	Dynamic Programming (III) : Knapsack
18 Apr (Mon)	Dynamic Programming (IV) : Edit Distance
20 Apr (Wed)	Dynamic Programming (V) : Longest Increasing Subsequence
21 Apr (X-hour)	DP Exercise
22 Apr (Fri)	Dynamic Programming (VI) : Conclusion
25 Apr (Mon)	Intro to Graphs + DFS
27 Apr (Wed)	Properties of DFS
28 Apr (X-hour)	Catch up on DFS
29 Apr (Fri)	Topological Sort and Applications
2 May (Mon)	Strongly Connected Components via DFS
3 May (Tue)	Midterm (6pm - 9pm) @MacLean MB01, Zaleski Auditorium
4 May (Wed)	Shortest Paths : BFS
6 May (Fri)	Shortest Paths : BFS Proof
9 May (Mon)	Dijkstra
11 May (Wed)	Bellman-Ford
12 May (X)	Connectivity in Query Model
13 May (Fri)	Flows and Cuts
16 May (Mon)	Weak Duality between Flows and Cuts
18 May (Wed)	Residual Networks
19 May (X)	The Ford-Fulkerson Algorithm
20 May (Fri)	Applications of Flows and Cuts
23 May (Mon)	Applications of Flows and Cuts
25 May (Wed)	Minimum Spanning Trees
27 May (Fri)	Wrap up + AMA
1 Jun (Wed)	Linear Programming
5 Jun (Sun)	Finals @Cummings 100 (usual classroom) 3pm - 6pm

Textbooks

There are no required textbooks. Indeed, the posted lecture notes should be enough. There are many good Algorithms texts out there. Here are some.

a) Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
b) Kleinberg, Tardos: Algorithm Design
c) Dasgupta, Papadimitriou, Vazirani: Algorithms (this is the slimmest one)
d) Erickson: Algorithms (this is freely available here: https://jeffe.cs.illinois.edu/teaching/algorithms/ (Links to an external site.))

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.