May 2: The review session problems and solutions have been uploaded on courseworks. These problems are good practice for the final exam; if you did not attend the review session, you might want to attempt solving these problems on your own before looking up the solutions.

May 2: Final exam information

Material: all lectures from 3/1 to 4/26. Since the following slide sets were not covered in their entirety in class, you only need study them as follows:

Union-Find: slides 1 - 22 only

hashing: slides 1 - 30 only

flows: slides 1 - 71 only

more NP-complete problems: slides 1 - 29 only

duality: slides 1 - 19 and 36 - 39 only

Exam duration: ~1.5h

Location: regular classroom

Time: 4:10-5:40 (you should be in the classroom by 4)

Total #problems: ~6, potentially with multiple parts

Past final exam problems:

all problems in the review session

hw4: problems 3, 4

hw5: problems 4, 5b; recommended exercises 1 and 3

hw6: problems similar to 1 and 3; problem 5; recommended exercise 1

True/false questions

Short explanation/counterexample question

Algorithm design questions: you must argue correctness (even if you do so briefly) and analyze the running time of all algorithms you give; give pseudocode only if time permits

Reductions: you should give the input instances, clearly describe the reduction transformation and argue it requires polynomial time, and prove equivalence of instances

LPs/IPs

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

May 1: Reminder: review session today in 833 Mudd at 4pm!

Apr 25: The teaching staff will be holding office hours next week Apr 30-May 4, except for Gaurav and Daniel who will give the review session on May 1 (see below). Any changes in our regular office hours will be posted on the course website and piazza.

From duality, the matrix-vector formulation of an LP, its dual & interpreting the dual LP;

From IP, Set Cover, approximation, Integer Programming and the IP formulation for Set Cover; if time permits, the approximation algorithm for Set Cover.

Apr 25: Daniel and Gaurav will hold a review session on Tuesday May 1 from 4-5pm in 833 Mudd. They will discuss flows, NP-completeness, linear programming and answer questions after the review session. Everyone is encouraged to attend!

Apr 19: A clarification about today's lecture: we will not discuss Integer Programming; instead we will skip to the Set Cover problem after the slide on similar problems with different complexities.

Apr 16: Clarification in problem 2 of hw6: a Hamiltonian cycle is a cycle that visits every vertex in the graph once (except for the start vertex which is the same as the end vertex). Thus a Hamiltonian cycle, if one exists, consists of n edges.

Apr 16: hw6 is now available. It is due by 8pm on Monday April 30.

Apr 10: Part (b) of problem 5 is removed from hw5 (we will not cover linear programs this week). See related discussion on piazza too.

Apr 2: hw5 is now available. It is due by 8pm on Monday April 16.

Mar 19: hw4 is now available. It is due by 8pm on Monday April 2.

Mar 7: Solutions to hw3 have been posted on courseworks.

Mar 1: Aditya and Midhun will hold a review session this Saturday at 4pm. Everyone is encouraged to attend!

Date/Time: Saturday March 3, 4-5pm

Location: 833 Mudd

Material: greedy and dynamic programming examples

Feb 27: midterm information

Material: all lectures up to and including Feb 27 (updated 3/1)

Total #problems: ~6, potentially with multiple parts

Past midterm problems:

hw1: problems 1, 2, 3, 4 and recommended exercise 1;

hw2: problems similar to 1 and 2;

hw3: problem 1, recommended exercises 1 and 2.

True/False questions

Multiple choice questions

Algorithm design questions: you must argue correctness (even if you do so briefly) and analyze the running time of all algorithms you give; give pseudocode only if time permits

Midterm is closed books, no calculators, no cheat sheet

Feb 19: hw3 is now available. It is due by 8pm on Monday March 5.

Feb 10: Solutions to hw1 are now available on courseworks, under Files.

Feb 5: hw2 is now available. It is due by 8pm on Monday February 19.

Feb 5: The instructor's office hours are permanently moved to Tuesdays 2-4pm to accommodate several students with conflicts.

Jan 24: The instructor's office hour tomorrow is canceled due to a conflict. This change is for tomorrow only.

Jan 23: Please signup for Piazza today using this link . Please follow piazza closely: important information about your homework assignments will be posted there, we will assume you have read and are familiar with this information.

Jan 22: hw2 is now available. It is due by 8pm on Monday February 5. Here is a template for hw1 if you're using latex.

Jan 15: Office hours will start next week (January 22).

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 basic knowledge of probability and linear algebra is required.

You might want to refresh your memory on some of the required math background for this class by going over the following sections in our textbook:

Appendix A: pp. 1145-1147, a basic understanding of 1150-1153

Appendix B: B.1, B.3, B.4 (parts of B4 and B5 will be covered in class)

Appendix C: pp. 1183-1186, C.2, C.3, C.4

Appendix D: D.1, D.2

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

Greedy algorithms: huffman coding, minimum spanning trees

Network flows

Dynamic programming: data segmentation, sequence alignment

Linear programming

Reductions and NP-completeness

Hashing: Bloom filters, document similarity

Approximation algorithms

Cryptography fundamentals and primality testing

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 go to the end of this section.

You should submit your homework assignment online (on canvas) as a pdf file. If needed, scan your handwritten assignment and submit the resulting pdf --please make sure the quality of your scanned document is good.

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 withinCollaboration policy: You are allowed to brainstorm and think through solutions with a small number (2-3) 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

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

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

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

Thu, 3/29: Two data structures: the Union-Find data structure [Union Find, only up to and including the pseudocode for path compression; recommended reading: Sections 17.0, 17.1, 17.2, 17.4 (without the potential method), 21.1, 21.2 (optional), 21.3]; the hash table and applications of hashing for saving space: fingerprints, Bloom filters [hashing]

Mon, 4/2: hw4 due, hw5 out

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

Thu, 4/5: Correctness of Ford-Fulkerson, applications of max flow: maximum bipartite matching, Hall's theorem [pp. 720-724, Section 26.3]

Tue, 4/10: Reductions [reductions, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073]

Thu, 4/19: TSP, and more NP-complete problems [more NP-complete problems, optional reading: 34.2 up to and not including Verification Algorithms, 34.5.4, p. 1118]

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

Thu, 4/26: Dualization; interpreting the dual LP [duality, optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)]; approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4];

Mon 4/30: hw6 due

5/1-5/4: no class, study week

Tue, May 8: final exam

Final exam information:

Start time: 4:10pm

Duration: ~1.5h

Location: 501 NWC (regular classroom)

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

## Announcements

## General course information

Time:TTR, 4:10-5:25pm, Location: 501 NWCInstructor:Eleni Drinea, eleni@cs.columbia.eduOffice Hours:Tuesdays, 2-4pm (or by appointment), 414 MuddTeaching Assistants and Office Hours: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 VaziraniGrading: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

## 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

General:There will be six biweekly homework assignments to help you better assimilate the course material.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 withinCollaboration policy: You are allowed to brainstorm and think through solutions with a small number (2-3) 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## Preliminary syllabus

Tue, 1/16:Insertion sort, induction, worst-case running time analysis, efficient algorithms [insertionsort, Sections 1.1, 2.1, 2.2]Thu, 1/18:Asymptotic notation, divide and conquer principle, mergesort, solving recurrences: recursion trees [mergesort, mastertheorem, Sections 3.1, 2.3, 4.0]Mon, 1/22:hw1 out (a template for hw1)Tue, 1/23:Master theorem; more divide & conquer algorithms: binary search, fast integer multiplication [more divide & conquer, Sections 4.2, 4.3, 4.4, 4.5]Thu, 1/25:Fast matrix multiplication (Strassen's algorithm), quicksort [quicksort, balls-in-bins, Sections 7.1, 7.2]Tue, 1/30:Randomized algorithms, randomized Quicksort,analysis of randomized Quicksort [cache, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]Thu, 2/1:Greedy algorithms: Huffman coding for data compression [huffman, Section 16.3]Mon, 2/5: hw1 due, hw2 outTue, 2/6:Occupancy problems; the coupon's collector problem [quicksort, balls-in-bins]Thu, 2/8: More greedy: cache maintenance, online algorithms [cache, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg]Tue, 2/13: Dynamic programming principle: segmented least squares, iterative and memoized implementations [datasegmentation]Thu, 2/15:Sequence alignment [sequencealignment, recommended reading: Section 15.4]Mon, 2/19: hw2 due, hw3 outTue, 2/20:Matrix-chain multiplication [matrix chain multiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]Thu, 2/22:Graphs, graph representation, Breadth-First Search and applications: connected components [graphs and BFS, optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179, Sections 22.1, 22.2]Tue, 2/27: BFS applications: connected components, testing bipartiteness; Depth-First Search and applications: cycle detection [dfs-toposort, optional reading: Sections 22.3, 22.4]Thu, 3/1: Topological sort, strongly connected components [stronglyconnectedcomponents, optional reading: Section 22.5]Mon, 3/5: hw3 dueTue, 3/6:Single source shortest paths, non-negative edge weights: Dijsktra's algorithmThu, 3/8:midterm examMidterm exam information:Time:4:10-5:25pm (regular time)Location: 501 NWC (regular classroom)Material:all lectures up to and including 2/27 (updated on 3/1)closed books, no calculators, no cheat sheet, no external aids.3/12-3/16: no class, spring recessMon, 3/19: hw4 outTue, 3/20:Implementing Dijsktra's algorithm; single-source shortest paths in weighted graphs (negative edge weights): Bellman-Ford [BelmanFord-FloydWarshall, optional reading: Sections 24.0-24.3, 25.2]Thu, 3/22:Detecting negative cycles; all-pairs shortest paths: Floyd-Warshall; sequence alignment as a shortest paths problemTue, 3/27:Minimum spanning trees: Prim's and Kruskal's algorithms [msts, optional reading: Sections 21.1, 21.2, 21.3];Thu, 3/29:Two data structures: the Union-Find data structure [Union Find, only up to and including the pseudocode for path compression; recommended reading: Sections 17.0, 17.1, 17.2, 17.4 (without the potential method), 21.1, 21.2 (optional), 21.3]; the hash table and applications of hashing for saving space: fingerprints, Bloom filters [hashing]Mon, 4/2: hw4 due, hw5 outTue, 4/3: Network flows, the Ford-Fulkerson algorithm for max flow [flows, pp. 708-720, 724-726]Thu, 4/5:Correctness of Ford-Fulkerson, applications of max flow: maximum bipartite matching, Hall's theorem [pp. 720-724, Section 26.3]Tue, 4/10:Reductions [reductions, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073]Thu, 4/12:Complexity classes P, NP (formulas, circuits)Mon, 4/16: hw5 due, hw6 outTue, 4/17:Proving NP-completeness: satisfiability of boolean functions (formulas, circuits) [SAT, optional reading: Section 34.4, 34.5.2]Thu, 4/19:TSP, and more NP-complete problems [more NP-complete problems, optional reading: 34.2 up to and not including Verification Algorithms, 34.5.4, p. 1118]Tue, 4/24:Linear programs, weak and strong duality [LPs, optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof)]Thu, 4/26:Dualization; interpreting the dual LP [duality, optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)]; approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4];Mon 4/30: hw6 due5/1-5/4: no class, study weekTue, May 8: final examFinal exam information:Start time: 4:10pmDuration:~1.5hLocation:501 NWC (regular classroom)closed books, no calculators, no cheat sheet, no external aids.