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:           Tu 11:00am–12:00pm, St. Mary's Hall, Room 342C

Office Hours by Sidhant:      Th 4:00pm–5:00pm, St. Mary's Hall, Room 328

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 four 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 Counting Sort, QuickSort. [CLRS, Sec 8.2, 7], [DPV, Ex 2.20, Ex 2.24 ], [KP, Sec 3.6, 7.5], [KT, Sec 13.5].
5 9/11 Maximum Subarray Problem, Investment Problem. [CLRS 3rd Ed, Sec 4.1], [Wys24, Sec 1--3], [KT, Chapter 5 Solved Ex 2], [KP, Sec 7.17].
6 9/16 Karatsuba Algorithm, Master Theorem. [Eri, Sec 1.9] and [CLRS, Sec 4.5]; or [KP, Sec 7.1].
7 9/18 Local Maximum, Red-Blue Pair, Fixed Point, Duplicates, Anagrams.
Homework 1
Greedy Algorithms
8 9/23 Largest Number, Car Charging, Money Change, Fractional Knapsack. [CLRS, Sec 15.1--15.2], [KP, Sec 6.1--6.4].
9 9/25 Maximum Inner Product, Activity Selection, Hitting Intervals. [CLRS, Sec 15.1--15.2], [Eri 4.2--4.3], [KT Sec 4.1], [KP Sec 6.5--6.6, 3.2].
10 9/30 Huffman Codes. [CLRS, Sec 15.3], [DPV Sec 5.2], [Eri Sec 4.4], [KT Sec 4.8], [KP Sec 6.14].
11 10/2 Stable Matchings. [Eri, Sec 4.5], [KT Sec 1.1].
12 10/7 Distinct Summands, Bulb Switching, Minimum Unchangeable Amount.
Homework 2
Dynamic Programming
13 10/9 Money Change, Rod Cutting, Nim. [CLRS, Sec 14.1], [DPV Sec 6.1], [Eri Sec 3.1], [KP Sec 8.1--8.2, 3.3], [KT Sec 6.2].
14 10/16 Midterm Review.
15 10/21 Midterm Exam.
16 10/23 Longest Common Subsequence. [CLRS, Sec 14.3].
17 10/28 Edit Distance. [Eri, Sec 3.7], [DPV, Sec 6.3].
18 10/30 Subset Sum, Knapsack. [Eri, Sec 3.8], [DPV, Sec 6.4], [KT, Sec 6.4], [KP, Sec 8.7].
Homework 3
19 11/4 MinCost Stairs Climbing, Longest Palindromic Subsequence, Longest Repeating Subsequence, Splitting Loot, Coins Game.
Graph Algorithms
20 11/6 Graph Representations, Depth-first Search. [CLRS, Sec 20.1, 20.3], [Eri, Chap 5].
21 11/11 Depth-first Search. [CLRS, 20.3], [DPV, Sec 3.3], [Eri, Sec 6.1--6.2].
22 11/13 Topological Sort. [CLRS, Sec 20.4], [DPV, Sec 3.3], [Eri, Sec 6.3], [KT Sec 3.6].
23 11/18 Breadth-first Search and Dijkstra. [CLRS, Sec 20.2, 22.3], [DPV, Sec 4.2--4.2], [Eri, Sec 8.4, 8.6], [KT, Sec 3.2, 4.4].
24 11/20 Bellman-Ford and Floyd-Warshall. [CLRS, Sec 22.1, 23.2], [DPV, Sec 4.6, 6.6], [Eri, Sec 8.7, 9.8].
25 11/25 Floyd-Warshall, Number of Islands, Rotting Tomatoes.
Homework 4
Advanced Topics
26 12/2 Streaming Algorithms. Missing Elements: [Mut05, Sec 1.1]; Majority: [wiki]; Distinct Elements: [And17, Sec 3] or [Nel20, Sec 2.2].
27 12/4 Approximation Algorithms. k-center [WS10, Sec 2.2]; TSP [WS10, Sec 2.4].
28 12/9 Final Review
12/14 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.