Total #problems: ~6, potentially with multiple parts

Past final exam problems: see review session

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

Reductions

IPs/LPs

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

May 4: Solutions to hw5 and hw6 except for problem 4 are available on canvas; hw6 problem 4 which will be added tomorrow.

May 2: The instructor's OH are moved to Thursday, May 4, 1-3pm.

May 1: As announced in Thursday's class, Raymond and Kevin will hold a review session this Thursday, 5/4 at 4:10pm in Math 312. They will cover several problems on using reductions and linear programming.

Apr 19: Updated due date for HW6: 8pm on Monday, May 1.

Apr 19: Xinwei's OH are moved to Fridays, 7:30-9:30pm until the end of the semester.

Apr 19: Updated HW4 (includes the clarification for problem 2.a posted on piazza). HW6 is due 8pm on Friday, April 28.

Apr 14: HW6 is now available. It is due by 8pm on Monday, April 10.

Apr 10: Since we haven't yet covered much of the material that will appear in the last assignment, I will post HW6 this Friday. It will be due two weeks later (4/28) by 8pm.

Mar 20:HW5is now available. It is due by 8pm on Monday, April 10.

Mar 21: Midterm exams will be returned at the end of today's class. If you have questions about your exam, please stop by during the instructor's OH this week or next. Solutions will be posted early next week.

Mar 8: Solutions to HW3 are now available on canvas.

Mar 6: HW4 is now available. It is due 8pm on Monday, March 27.

Mar 3: Solutions to the practice problems session on 2/26 and HW2 are now available on canvas.

Mar 1: midterm information

Material: all lectures up to and including Mar 2, without Dijkstra's algorithm (if we cover it on Mar 2)

Total #problems: ~6, potentially with multiple parts

Past midterm problems:

HW1: problem 5.1, parts a and b;

HW1 optional: problems 1, 3, 4a and 4b

HW2: problem 1;

HW3: problems 1, 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

Mar 1: Raymond will hold a review session this Saturday, 3/4 at 4:30pm in Mudd 833. He will cover several greedy and DP algorithms. Everyone is encouraged to attend and ask questions!

Feb 28: The instructor's OH today are canceled due to a conflicting event. Instead I will hold extended OH 1-2:30 on Thursday.

Feb 22: As mentioned in class yesterday, we will hold an optional Practice Problems session this Sunday (2/26) 1-5pm in the CS lounge. We will propose a few problems and offer an estimate for their difficulty; you will design algorithms to solve (some of) these problems and then code up your algorithms in a language of your choice (Java, C++ and Python are preferred). Many problems will require a DP solution so this session should also help towards solving the problems in HW3.
Pizza and refreshments will be served. Please vote by tomorrow (Thursday) night in the poll I created on piazza to indicate whether you're coming to the event so we can have an accurate estimate for the amount of food needed. If you have any suggestions about this event, please post them on piazza publicly or privately --we look forward to your thoughts. More details about the structure of the event will be posted by Friday.

Feb 20: HW3 is now available. It is due by 8pm on Monday, March 6. Please note that you may only submit your solutions as a pdf file on canvas.

Feb 9: There will be no extension for HW2. You can solve all problems in HW2 after reviewing the definitions of SAT and 3SAT from my slides on NP-completeness. Please do so soon --and definitely before Tuesday's lecture-- and post any questions on piazza (preferred) or email the teaching staff directly.

Feb 9: Today's class is canceled because of the weather. For the same reason, all OH today are canceled.

Feb 7: Two changes in Thursday's (2/9) OH: the instructor's OH is canceled due to a conflicting event. Jisong's OH are moved to 8-10pm. These changes are for this week only.

Feb 6: HW2 is now available. It is due by 8pm on Monday, February 20. Please note that you may only submit your solutions as a pdf file on canvas.

Jan 26: As mentioned in Tuesday's class, here are a few recommended exercises to work on. These exercises are optional so please do not return your solutions. Solutions to these problems will be posted after Monday, February 6.

Jan 26: In Tuesday's class, there was a question whether Karatsuba's algorithm may be improved and if yes, how much. For a detailed discussion of the Toom-Cook algorithm I mentioned, see this article at wikipedia.

Jan 23:HW1 is now available. It is due by 8pm on Monday, February 6. Please note that you may only submit your solutions as a pdf file on canvas.

Jan 17: Office hours will start next week (January 23).

General course information

Time: TTR, 4:10-5:25pm, Location: 312 Math Building

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 within

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.

Collaboration 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

Tue, 1/31: Analysis of randomized Quicksort; balls-in-bins problems, the coupon collector problem [randQS-ballsinbins, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]

Thu, 2/2: Greedy algorithms: Huffman coding for data compression [huffman, Section 16.3]

Mon, 2/6: HW1 due, HW2 out

Tue, 2/7: More greedy: cache maintenance, online algorithms [cache, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg]

Thu, 2/9:canceled due to snowstorm

Tue, 2/14: Dynamic programming principle: segmented least squares, iterative and memoized implementations [datasegmentation]

Thu, 3/23: Minimum spanning trees: Prim's and Kruskal's algorithms [msts, optional reading: Sections 21.1, 21.2, 21.3]; a first Union-Find data structure using linked lists: MakeSet, Find in worst-case O(1) time, a sequence of n Union operations in O(nlogn) time [Sections 21.1, 21.2] Recommended reading: Union-Find data structure using trees; union by rank and path compression; amortized analysis [Union-Find, Sections 17.0, 17.1, 17.2, 17.4 (without the potential method), 21.1, 21.2 (optional), 21.3]

Mon, 3/27: HW4 due, HW5 out

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

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

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

Thu, 4/13: 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]

Fri, 4/14: HW5 due, HW6 out

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

Thu, 4/20: 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)]

Tue, 4/25: Approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4]

Thu, 4/27: Hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins; hashing for saving space: fingerprints, Bloom filters [hashing]

Mon, 5/1: HW6 due

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

Tue, 5/9: Final exam

Final exam information:

Day/Time: Tuesday, May 9, 4:10-5:40pm

Location: 312 Math Building

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

AnnouncementsMay 5:Solutions to hw6 have been updated.May 4:Final exam informationMay 4: Solutions to hw5 and hw6 except for problem 4 are available on canvas; hw6 problem 4 which will be added tomorrow.May 2: The instructor's OH are moved to Thursday, May 4, 1-3pm.May 1: As announced in Thursday's class, Raymond and Kevin will hold a review session this Thursday, 5/4 at 4:10pm in Math 312. They will cover several problems on using reductions and linear programming.Apr 14: HW6 is now available. It is due by8pm on Monday, April 10.Apr 10: Since we haven't yet covered much of the material that will appear in the last assignment, I will post HW6 this Friday. It will be due two weeks later (4/28) by 8pm.Mar 20:HW5is now available. It is due by8pm on Monday, April 10.Mar 21:Midterm exams will be returned at the end of today's class. If you have questions about your exam, please stop by during the instructor's OH this week or next. Solutions will be posted early next week.Mar 8:Solutions to HW3 are now available on canvas.Mar 6:HW4is now available. It is due8pm on Monday, March 27.Mar 3: Solutions to the practice problems session on 2/26 and HW2 are now available on canvas.Mar 1:midterm informationMar 1:Raymond will hold a review session thisSaturday, 3/4 at 4:30pm in Mudd 833. He will cover several greedy and DP algorithms. Everyone is encouraged to attend and ask questions!Feb 28:The instructor's OH today are canceled due to a conflicting event. Instead I will hold extended OH 1-2:30 on Thursday.Feb 22:As mentioned in class yesterday, we will hold an optional Practice Problems session thisSunday (2/26) 1-5pm in the CS lounge. We will propose a few problems and offer an estimate for their difficulty; you will design algorithms to solve (some of) these problems and then code up your algorithms in a language of your choice (Java, C++ and Python are preferred). Many problems will require a DP solution so this session should also help towards solving the problems in HW3.Pizza and refreshments will be served. Please

vote by tomorrow (Thursday) nightin the poll I created on piazza to indicate whether you're coming to the event so we can have an accurate estimate for the amount of food needed. If you have any suggestions about this event, please post them on piazza publicly or privately --we look forward to your thoughts. More details about the structure of the event will be posted by Friday.Feb 20: HW3is now available. It is due by8pm on Monday, March 6. Please note that you may only submit your solutions as apdf fileon canvas.Feb 9:There will be no extension for HW2. You can solve all problems in HW2 after reviewing the definitions of SAT and 3SAT from my slides on NP-completeness. Please do so soon --and definitely before Tuesday's lecture-- and post any questions on piazza (preferred) or email the teaching staff directly.Feb 9:Today's class is canceled because of the weather. For the same reason, all OH today are canceled.Feb 7:Two changes in Thursday's (2/9) OH: the instructor's OH is canceled due to a conflicting event. Jisong's OH are moved to 8-10pm. These changes are for this week only.Feb 6: HW2 is now available. It is due by8pm on Monday, February 20. Please note that you may only submit your solutions as apdf fileon canvas.Jan 26:As mentioned in Tuesday's class, here are a few recommended exercises to work on. These exercises are optional so please do not return your solutions. Solutions to these problems will be posted after Monday, February 6.Jan 26:In Tuesday's class, there was a question whether Karatsuba's algorithm may be improved and if yes, how much. For a detailed discussion of the Toom-Cook algorithm I mentioned, see this article at wikipedia.Jan 23:HW1is now available. It is due by8pm on Monday, February 6. Please note that you may only submit your solutions asa pdf fileon canvas.Jan 17: Office hours will start next week (January 23).General course informationTime:TTR, 4:10-5:25pm, Location: 312 Math BuildingInstructor:Eleni Drinea, eleni@cs.columbia.eduOffice Hours:TTR, 1-2pm (or by appointment), Mudd 414Teaching Assistants and Office Hours:Teaching staff mailing list:w4231-s2017@googlegroups.comTextbook: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.PrerequisitesCourse descriptionThis 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.

HomeworksGeneral:There will be six biweekly homework assignments to help you better assimilate the course material.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 policyHW1:Out: Monday, Jan 23, Due: Monday, Feb 6HW2: Out: Monday, Feb 6, Due: Monday, Feb 20HW3: Out: Monday, Feb 20, Due: Monday, Mar 6HW4: Out: Monday, Mar 6, Due: Monday, Mar 27HW5:Out: Monday, Mar 27, Due: Monday, Apr 10HW6:Out: Friday, April 14, Due: Monday, May 1## Preliminary syllabus

Tue, 1/17: Insertion sort, induction, worst-case running time analysis, efficient algorithms [insertionsort, Sections 1.1, 2.1, 2.2]Thu, 1/19: Asymptotic notation, divide and conquer principle, mergesort, solving recurrences: recursion trees [mergesort, mastertheorem, Sections 3.1, 2.3, 4.0]Tue, 1/24:Master theorem; more divide & conquer algorithms: binary search, fast integer multiplication, fast matrix multiplication (Strassen's algorithm) [moredivideandconquer, Sections 4.2, 4.3, 4.4, 4.5]Thu, 1/26:Quicksort, randomized algorithms, randomized Quicksort [File Not FoundTue, 1/31:Analysis of randomized Quicksort; balls-in-bins problems, the coupon collector problem [randQS-ballsinbins, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]Thu, 2/2:Greedy algorithms: Huffman coding for data compression [huffman, Section 16.3]Tue, 2/7: More greedy: cache maintenance, online algorithms [cache, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg]Thu, 2/9:canceled due to snowstormTue, 2/14: Dynamic programming principle: segmented least squares, iterative and memoized implementations [datasegmentation]Thu, 2/16: Sequence alignment [sequencealignment, recommended reading: Section 15.4]Tue, 2/21: Matrix-chain multiplication [matrixchainmultiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]Thu, 2/23:Graphs, graph representation, Breadth-First Search and applications: connected components [graphsandBFS, optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179, Sections 22.1, 22.2]Tue, 2/28: BFS applications: connected components, testing bipartiteness; Depth-First Search and applications: cycle detection, topological sort [dfs-toposort, optional reading: Sections 22.3, 22.4]Thu, 3/2:Strongly connected components [stronglyconnectedcomponents, optional reading: Section 22.5]Tue, 3/7: Single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra's algorithm and why it fails in graphs with negative edge weights [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3]Thu, 3/9:Midterm ExamMidterm exam information:closed books, no calculators, no cheat sheet, no external aids.3/13-3/17: no class, spring recessThu, 3/23:Minimum spanning trees: Prim's and Kruskal's algorithms [msts, optional reading: Sections 21.1, 21.2, 21.3]; a first Union-Find data structure using linked lists: MakeSet, Find in worst-case O(1) time, a sequence of n Union operations in O(nlogn) time [Sections 21.1, 21.2] Recommended reading: Union-Find data structure using trees; union by rank and path compression; amortized analysis [Union-Find, Sections 17.0, 17.1, 17.2, 17.4 (without the potential method), 21.1, 21.2 (optional), 21.3]Tue, 3/28:Network flows, the Ford-Fulkerson algorithm for max flow [flows, pp. 708-720, 724-726]Thu, 3/30: Correctness of Ford-Fulkerson, applications of max flow: maximum bipartite matching, Hall's theorem [pp. 720-724, Section 26.3]Tue, 4/4: Reductions; complexity classes P, NP [reductions, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073]Thu, 4/6: Satisfiability of boolean functions (formulas, circuits) [SAT, optional reading: Section 34.4, 34.5.2]Tue, 4/11:Proving NP-completenessThu, 4/13: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/18:Linear programs, weak and strong duality [LP_part1, optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof)]Thu, 4/20: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)]Tue, 4/25: Approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4]Thu, 4/27: Hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins; hashing for saving space: fingerprints, Bloom filters [hashing]Mon, 5/1: HW6 due5/2-5/4: no class, study weekTue, 5/9: Final examFinal exam information:closed books, no calculators, no cheat sheet, no external aids.