Overview

Instructor: Sasha Golovnev

Teaching Assistants: Sam King and Sidhant Saraogi

Class Meetings:                                    MW 12:30pm–1:45pm, Reiss, Room 264

Office Hours by Sam and Sidhant:      Tu 11:00am–12:00pm, St. Mary's Hall, Room 342C

Office Hours by Sasha:                        Th 2:00pm–3:00pm, St. Mary's Hall, Room 354

Email: alexgolovnev+algo@gmail.com

Description:

This course explores various techniques used in the design and analysis of computer algorithms. Starting with the divide-and-conquer technique, the course covers various general approaches such as the greedy method and dynamic programming. The course will also cover online algorithms and fundamental algorithms on graphs. Finally, the course will introduce algorithmic techniques used in other areas including cryptography and computational complexity.

Prerequisites:

COSC-2010 or COSC-160 (Data Structures).
Familiarity with mathematical proofs and discrete mathematics.

Canvas page:

https://georgetown.instructure.com/courses/193304.

Textbooks:

Primary textbook:
[CLRS] Cormen, Leiserson, Rivest, Stein. Introduction to algorithms, 4th Edition. 2022.
Additional textbooks:
[DPV] Dasgupta, Papadimitriou, Vazirani. Algorithms. 2008.
[KP] Kulikov, Pevzner. Ace Your Next Coding Interview by Learning Algorithms through Programming and Puzzle Solving. 2022.
[KT] Kleinberg, Tardos. Algorithm Design. 2006.
[Eri] Erickson. Algorithms. Online Draft.

Grading:

Grading will be based on five or six homework problem sets (50%), midterm (25%) and final (25%) exams, with extra credit for in-class participation.

Tentative Schedule

Class Date Topic References
Algorithmic Thinking
1 8/28 One-pass Algorithms Slides. Missing Elements: [Mut05, Sec 1.1]; Majority: [wiki], [KP, Sec 7.4].
2 9/3 Asymptotic notation Slides. [CLRS, Sec 3.1], [DPV, Sec 0.2--0.3], [KT, Sec. 2.1--2.2], [KP, Sec 2.2--2.3].
Divide and Conquer
3 9/4 Binary Search, SelectionSort and MergeSort, Lower Bound [CLRS, Sec 2.2--2.3, 8.1], [DPV, Sec 2.3], [KT, Sec 5.1], [KP, Sec 7.1, 3.5]
4 9/9
5 9/11
6 9/16
7 9/18
Dynamic Prograpmming
8 9/23
9 9/25
10 9/30
11 10/2
12 10/7
Greedy Algorithms
13 10/9
14 10/16
15 10/21 Midterm Exam
16 10/23
17 10/28 Midterm Review
18 10/30
19 11/4
Graph Algorithms
20 11/6
21 11/11
22 11/13
23 11/18
24 11/20
Advanced Topics
25 11/25
26 12/2
27 12/4
28 12/9
12/13 Final Exam

Course Policies

Academic Honesty:

We encourage you to discuss the homework assignments with your classmates in groups of no more than three people, however you must explicitly list all collaborators and materials that you used, and you must write up your own solution to every problem. See Georgetown University Honor System. When in doubt, ask the instructor what is allowed.

Late Submissions:

Late submissions of homework solutions are graded with a 10% penalty per day of late submission.

No AI Tools Permitted:

The use of AI text generating tools at any point when working on the assignments will be treated as academic dishonesty.

Disability Disclosure Statement:

If you have a disability that may affect your academic work or well-being and for which accommodations may be necessary, please inform us and contact the Academic Resource Center.

Title IX:

We are committed to supporting safe and hospitable environment for all members of the community. For details of University resources, consult Georgetown University Sexual Misconduct Reference Guide.

Religious Observance:

Any student who is unable to attend a class because of the observance of a major religious holiday will be provided with the opportunity to make up for the class.