May 5: Solutions to HW5 and HW6 are now available on canvas.

Apr 29: Drishan will hold a review session this Thursday, 5/5 at 4:30pm in Mudd 833. Everyone is encouraged to attend.

Apr 27: final exam information

Date/Time: Tuesday, May 10, 7:10-9:10pm

Duration: 2h

Location: Mudd 833

Material: all lectures from 3/3 up to and including 4/26, only up to taking the dual of set cover (approximation algorithms will not be part of the exam); algorithm design techniques such as recursion, greedy and DP are part of the final exam.

Total #problems: ~8, potentially with multiple parts

Types of problems: True/False questions; multiple choice questions; algorithm design questions (you must argue correctness and analyze the running time of all algorithms you give); reductions (clearly give the reduction transformation, explain time to compute it, prove equivalence of instances; if the reduction is to show NP-completeness, you should also prove that the problem is in NP, that is, admits an efficient certifier); formulating linear or integer prorgams

Past final exam problems: HW4, problem 5; HW5: problems 6, 7 and 8; HW6: problems 1 and 5

Final exam is closed books, no calculators, no cheat sheet

Apr 25: HW6, problem 2: although a dominating set is defined in directed graphs in this problem, you may show that the dominating set problem in NP-complete for undirected graphs since the reduction is slightly cleaner.

Apr 25: Solutions to optional problems have been posted on canvas.

Apr 14: HW6 is out. It is due 8pm on Thursday, April 28.

Apr 13: HW6 will be out tomorrow (4/14) in the afternoon. It will be due in two weeks from tomorrow.

Apr 10: The instructor's office hours this week are moved to Monday, 4/11, 3-5. This change is for this week only.

Apr 8: As announced in class yesterday, you should not solve part i of Problem 6 in HW5.

Apr 4: Midterm solutions are now available on canvas.

Mar 30: Unfortunately I now have a conflict tomorrow 3-5. If you wish to discuss your midterm grade you may do so on Tuesday (4/5) during my regular office hours. Solutions to the exam will be posted on 4/4.

Mar 30: HW5 is out. It is due 8pm on Wednesday, April 13.

Mar 29: Solutions to the midterm will be posted tomorrow (3/30) on canvas. If you have questions about your exam, you may stop by the instructor's office on Thursday (3/31), 3-5.

Mar 29: HW5 will be out tomorrow (3/30) (and due in two weeks from tomorrow) to avoid overlap with HW4.

Mar 21: HW4 is out. It is due 1pm on Tuesday, March 29.

Mar 8: The instructor's OH today will start at 2:50.

Mar 4: midterm information

Material: all lectures up to and including March 3

Total #problems: 6-8, potentially with multiple parts

Past midterm problems: HW1: problems 1 and 3; HW2: problems 3 and 6; HW3: problem 1

True/false questions

Multiple choice questions

Algorithm design questions: you must argue correctness and analyze the running time of all algorithms you give

Midterm is closed books, no calculators, no cheat sheet

2/29: Drishan will hold a review session this Sunday, 3/6 at 4pm in Mudd 833.

2/26: Yesterday's slides have been reposted (a couple of theorems were labelled incorrectly).

2/25: Reminder: we will hold the hackathon tomorrow (Friday, 2/26), 6-9pm in the CS lounge (view directions ). Pizza and soft drinks will be provided!

2/24: There was a typo in Problem 5, HW3 ("end" and "then" should be swapped in the right tree). The pdf has been corrected.

2/23: HW3 is out. It is due 1pm on Tuesday, March 8. No extensions will be granted for HW3 so that we can post solutions on time for your midterm exam. Please start working on this problem set early!

2/22: We will hold the hackathon this Friday, 2/26, 6-9pm in the CS lounge.

2/22: HW3 will be posted by 1pm tomorrow.

2/18: Please vote for your preferred date to hold the "hackathon" in the poll on piazza by 2pm tomorrow (Friday). As mentioned in class, the hackathon is a 3h optional event aiming to bridge theory with practice. You will solve 3-4 problems and code up your solutions in C, C++, Java or Python, so please bring your laptops. Bo, Dev and Rajan will be there to assist you with thinking through a solution and/or coding it up, if needed. Food and soft drinks will be available. Once we have a date/time, I'll follow up with a location.

2/16: HW2, Problem 3ii: if you're using a randomized algorithm/data structure, it should return the correct answer with probability 1. Also, you should use as little extra space as possible (see related comment on piazza).

2/9: Yiyang will offer a recitation session on the binary min-heap (the data structure we used to improve the running time of Huffman's algorithm) on Sunday, 2/14, 4-5pm in Mudd 833. You are encouraged to attend and take notes, as this is a very useful data structure that we will encounter several times in our course.

2/9: The instructor's OH today are cancelled. I will hold OH on Thursday, 2/11, 4-5, instead.

2/8: HW2 is out. It is due 8pm on Monday, February 22.

2/2: Please make sure you sign up for Piazza on Canvas.

2/2: Drishan's OH are moved to Fridays, 10am-12pm, permanently.

1/27: Drishan's OH tomorrow are moved to Friday, 10am-12pm. This change is for tomorrow only.

1/25: HW1 is out. It is due 8pm on Monday, February 8.

1/20: Office hours will start next week. However, as mentioned in class yesterday, you may stop by the instructor's office tomorrow (1/21) 2-3pm, if you have any questions about the class.

Textbook: Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein (3rd edition) will be the main text for this course. Other recommended reading: Algorithm Design, by Kleinberg and Tardos; Algorithms, by Dasgupta, Papadimitriou and Vazirani.

Grading: Homeworks 40%, Midterm 30%, Final 30%. The midterm and final exams will be in-class. The percentage contributions above are approximate and subject to change.

Prerequisites:

COMS 3137/3139: Data Structures and Algorithms and COMS 3203: Discrete Mathematics.

Familiarity with mathematical proofs and how to write one, as well as some knowledge of discrete math and basic probability is required.

Course description

This course focuses on the design and analysis of efficient algorithms. We will discuss general design paradigms as well as specific problems. A preliminary list of topics follows.

Fundamentals: induction, asymptotics, recurrences

Sorting and searching: insertion sort, merge-sort, quicksort, binary search

Heuristics: the metropolis algorithm, simulated annealing

Homeworks

General: There will be six biweekly homework assignments to help you better assimilate the course material.

Homework assignments will be out on Mondays (late in the evening). They will be due 2 weeks later by 8pm. For a tentative schedule of homework assignments and/or to download a homework, please refer to the end of this section.

You may submit your homework assignment online (through courseworks) or use the drop box labelled "CSOR W4231.002, Analysis of Algorithms, I", in the CS TA room.

Late homework policy: No homework extensions will be granted. Exceptions will be made for medical emergencies or similar exceptional circumstances that must be discussed at least a few days in advance with the instructor. Otherwise, if the assignment is submitted within

6 hours past the submission deadline, 25% of the final score will be reduced;

6 and 24 hours past the submission deadline, 50% of the final score will be reduced;

No assignment will be accepted 24 hours past the submission deadline.

Collaboration policy: You are allowed to brainstorm and think through solutions with a small number (4-5) of your classmates. However you must write up your solutions entirely on your own. If you have used collaborators, you must state their names clearly next to your name on your write-up. Finally, copying solutions from the Internet or other textbooks is strictly prohibited. You should adhere to the department's academic honesty policy

Tue, 3/8: Minimum spanning trees: Prim and Kruskal [slides3-31, optional reading: Chapter 24]

Thu, 3/10: Midterm Exam

Midterm information

Time: 5:40-6:55pm

Location: Mudd 833 (regular classroom)

Material: all lectures up to and including 3/3

Midterm is closed books, no calculators, no cheat sheet.

3/14-3/18: no class, spring recess

Tue, 3/22: The union-find data structure and amortized analysis [slides4-2, optional reading: Sections 21.1, 21.2, 21.3]

Thu, 3/24: Hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins [slides3-24, Section 11.4] Hashing for saving space: Bloom filters, count-min sketch [slides3-26]

Mon, 3/28: HW4 due, HW5 out

Tue, 3/29: Network flows, the Ford-Fulkerson algorithm for max flow [slides4-7, pp. 708-720, 724-726]

Thu, 3/31: Applications: maximum bipartite matching, Hall's theorem [slides4-9, pp. 720-724, Section 26.3]

Tue, 4/5: Linear programs, weak and strong duality [optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof)]

Thu, 4/7: Dualization; interpreting the dual LP [optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)]

Mon, 4/11: HW5 due, HW6 out

Tue, 4/12: Reductions; complexity classes P, NP [slides4-21, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073]

Tue, 4/19: TSP, integer programming, set cover and more NP-complete problems [optional reading: 34.2 up to and not including Verification Algorithms, slides4-28.pdf, 34.5.4, p. 1118]

Thu, 4/21: Approximation algorithms for set cover, vertex cover

Mon, 4/25: HW6 due

Tue, 4/26: Heuristics: the metropolis algorithm, simulated annealing

Thu, 4/28: Streaming algorithms

5/3-5/8: no class, study week

Final exam: TBA

Final exam information

Time: TBA

Location: TBA

Final exam is closed books, no calculators, no cheat sheet.

## Analysis of Algorithms, I

AnnouncementsApr 25:HW6, problem 2: although a dominating set is defined in directed graphs in this problem, you may show that the dominating set problem in NP-complete for undirected graphs since the reduction is slightly cleaner.Apr 25:Solutions to optional problems have been posted on canvas.Apr 14: HW6 is out. It is due 8pm on Thursday, April 28.Apr 13: HW6 will be out tomorrow (4/14) in the afternoon. It will be due in two weeks from tomorrow.Apr 10: The instructor's office hours this week are moved to Monday, 4/11, 3-5. This change is for this week only.Apr 8: As announced in class yesterday, you should not solve part i of Problem 6 in HW5.Apr 4:Midterm solutions are now available on canvas.Mar 30: Unfortunately I now have a conflict tomorrow 3-5. If you wish to discuss your midterm grade you may do so on Tuesday (4/5) during my regular office hours. Solutions to the exam will be posted on 4/4.Mar 30: HW5 is out. It is due 8pm onWednesday, April 13.Mar 29:Solutions to the midterm will be posted tomorrow (3/30) on canvas. If you have questions about your exam, you may stop by the instructor's office on Thursday (3/31), 3-5.Mar 29:HW5 will be out tomorrow (3/30) (and due in two weeks from tomorrow) to avoid overlap with HW4.Mar 21: HW4 is out. It is due1pm on Tuesday, March 29.Mar 8:The instructor's OH today will start at 2:50.Mar 4:midterm informationGeneral course information## Prerequisites:

## Course description

This course focuses on the design and analysis of efficient algorithms. We will discuss general design paradigms as well as specific problems. A preliminary list of topics follows.## Homeworks

## Preliminary schedule

File Not FoundFile Not FoundFile Not FoundFile Not FoundFile Not FoundFile Not FoundFile Not Found