June 27: Solutions to hw4 are now available on courseworks.

June 25: Solutions to hw3 are now available on courseworks. Solutions to hw4 will be posted around 11am on Wednesday.

June 22: Solutions to the midterm exam are posted on courseworks under Files.

June 22: Final exam information

Date: Thursday, June 28

Time: 1-2:30 (tentative)

Location: 524 Mudd

Material: all lectures from 6/7 (Belman-Ford and Floyd-Warshall) up to and including all NP-complete problems from 6/26; makeup lecture on 6/1 is also part of the final.

Algorithm design questions: you must argue correctness (even if you do so briefly) and analyze the running time of all algorithms you give; you must clearly described your algorithm in English; only give pseudocode if time permits. Think carefully which algorithm design technique (recursion, greedy, DP, reduction) is appropriate for each problem.

If you give a reduction:

describe the inputs to the two problems

clearly give the reduction transformation and argue that it takes polynomial time

prove equivalence of instances

Final is closed books, no calculators, no cheat sheet

June 17: Reminder: there will be no class this Tuesday. The instructor's OH are moved to Thursday June 21 4:15-6pm.

June 16: hw4 is now available. It is due by 10pm on Tuesday June 26 (hard deadline: 10am on Wednesday June 27).

June 11: Solutions to hw1 were posted this morning on courseworks under Files. Solutions to hw2 will be posted around 11am on Wednesday.

June 9: hw3 is now available. It is due by 10pm on Tuesday June 19.

June 7: Makeup class TOMORROW (Friday) 1-4:10pm in 524 Mudd followed by instructor's OH 4:15-6. The instructor's OH on 6/12 are canceled.

June 5: Reminder: makeup class this Friday (June 8) 1-4:10pm in 524 Mudd (please note the slight change in time). The class will be recorded.

June 4: Midterm exam information

Date: Thursday, June 14

Time: 1-2:30

Location: 524 Mudd

Material: all lectures up to and including 6/7, without the Belman-Ford and Floyd-Warshall algorithms; also, makeup lecture on 6/1 is not part of the midterm.

Total #problems: ~7, potentially with multiple parts

True/false questions

Multiple choice questions

Past midterm questions:

HW1: problems 3, 4, 5a and 5b, 6a and 6b; recommended exercise 1.

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

If you give a dynamic programming algorithm:

clearly describe the subproblems

state the recurrence

give boundary conditions

analyze the running time of your algorithm

analyze the space

explain how to fill in the DP table, if applicable

Midterm is closed books, no calculators, no cheat sheet

June 2:hw2 is now available. It is due by 10pm on Tuesday June 12. HARD deadline: 10 am on Wednesday June 13.

May 31: Reminder: makeup class TOMORROW (Friday) 12-1:30pm in 1127 Mudd. The class will be recorded.

May 28: Few announcements about this week follow.

Office hours start this week (May 29).

Short makeup class this Friday (June 1) 12-1:30pm in 1127 Mudd. The class will be recorded. There will be no class on Thursday, June 14 after the midterm exam.

Thursday's regular class will also take place in 1127 Mudd.

May 26:hw1 is now available. It is due by 10pm on Tuesday June 5. For a description of the SAT problem in question 4, please review slides 23-32 from slide set SAT. We will also go over this in Thursday's class.

May 25: As discussed in class today, the release dates and deadlines for submitting homework assignments have been moved by one day (see homework section below).

May 24: Next Thursday's (5/31) and Friday's (6/1) classes will take place in 1127 Mudd due to construction work next to our regular classroom.

May 24: Reminder: makeup class TOMORROW 11:30-2:40pm in 524 Mudd. The class will be recorded.

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

Homeworks

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

Homework assignments will be out on Saturdays (late in the evening). They will be due 10 days later by 10pm. 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---make sure the quality of your scanned document is good and your handwriting very neat!

Late homework policy: No homework extensions will be granted. However you have 5 late days for all assignments: for example, you may submit Homework 1 at 9:59pm on Thu, 6/7, thus using 2 of your 5 late days. Note the following hard deadlines for Homework 2 and Homework 4:

Homework 2: 10am on Wed, 6/13 (if you do so, you will use 0.5 late days)

Homework 4: 10am on Wed, 6/27 (if you do so, you will use 0.5 late days)

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

Homework 1: Out: Saturday, May 26, Due: 10pm on Tuesday, June 5

Homework 2: Out: Saturday, June 2, Due: 10pm on Tuesday, June 12 (HARD deadline: 10am on Wednesday, June 13)

Homework 3: Out: Saturday, June 9, Due: 10pm on Tuesday, June 19

Homework 4: Out: Saturday, June 16, Due: 10pm on Tuesday, June 26 (HARD deadline: 10am on Wednesday, June 27)

Tue, 5/29: Analysis of randomized Quicksort; balls-in-bins problems, the coupon collector problem; hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins; hashing for saving space: fingerprints, Bloom filters [randQS-ballsinbins, hashing, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]

Thu, 5/31: Greedy algorithms: Huffman coding for data compression; cache maintenance, online algorithms [huffman, 16.3, cache, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg; optional reading: Chapter 6 from your textbook (binary min heap)]

Tue, 6/5: Dynamic programming principle: segmented least squares, sequence alignment, matrix-chain multiplication [datasegmentation, sequencealignment, recommended reading: Chapter 15, Section 15.4; matrixchainmultiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]

Tue, 6/5: hw1 due by 10pm

Thu, 6/7: Single-source shortest paths in weighted graphs (negative edge weights): Bellman-Ford; all-pairs shortest paths: Floyd-Warshall [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3, Section 25.2]; the knapsack problem

Fri, 6/8, 1-4:10pm (makeup class 3, full): Network flows, the Ford-Fulkerson algorithm for max flow; correctness of Ford-Fulkerson, applications of max flow: maximum bipartite matching [flows, pp. 708-720, 724-726, pp. 720-724, Section 26.3]

Thu, 6/21: Reductions; complexity classes P, NP, Satisfiability of boolean functions (formulas, circuits); proving NP-completeness, TSP and more NP-complete problems [reductions, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073, SAT, optional reading: Section 34.4, 34.5.2, more NP-complete problems, optional reading: 34.2 up to and not including Verification Algorithms, 34.5.4, p. 1118]

Tue, 6/26: Linear programs, weak and strong duality, dualization; interpreting the dual LP; [LP_part1, optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof), duality, optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)]

Tue, 6/26: hw4 due by 10pm (HARD deadline: 10am on Wed 6/27)

Thu, 6/28: Final exam

Final exam information:

Day/Time: Thursday, June 28, 1-3pm

Location: 524 Mudd Building

Material: all lectures from 6/8 (Belman-Ford & Floyd-Warshall) up to and including 6/26, WITHOUT linear programming

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

## Announcements

June 27:Solutions to hw4 are now available on courseworks.June 25: Solutions to hw3 are now available on courseworks. Solutions to hw4 will be posted around 11am on Wednesday.June 22:Solutions to the midterm exam are posted on courseworks under Files.June 22:Final exam informationreduction:closed books, no calculators, no cheat sheetJune 17:Reminder: there will be no class this Tuesday. The instructor's OH are moved to Thursday June 21 4:15-6pm.June 16: hw4 is now available. It is due by 10pm on Tuesday June 26 (hard deadline: 10am on Wednesday June 27).June 11: Solutions to hw1 were posted this morning on courseworks under Files. Solutions to hw2 will be posted around 11am on Wednesday.June 9: hw3 is now available. It is due by10pm on Tuesday June 19.June 7: Makeup classTOMORROW (Friday)1-4:10pm in 524 Muddfollowed by instructor's OH 4:15-6. The instructor's OH on 6/12 are canceled.June 5:Reminder: makeup class this Friday (June 8) 1-4:10pm in 524 Mudd (please note the slight change in time). The class will be recorded.June 4:Midterm exam informationDate:Thursday, June 14Time:1-2:30Location:524 MuddMaterial: all lectures up to and including 6/7, without the Belman-Ford and Floyd-Warshall algorithms; also, makeup lecture on 6/1 is not part of the midterm.Algorithm design questions:you must argue correctness (even if you do so briefly) and analyze the running time of all algorithms you give; you must clearly described your algorithm in English; only give pseudocode if time permits.dynamic programmingalgorithm:subproblemsrecurrenceboundary conditionstimeof your algorithmspacehow to fill inthe DP table, if applicableclosed books, no calculators, no cheat sheetJune 2:hw2 is now available. It is due by10pm on Tuesday June 12.HARD deadline: 10 am on Wednesday June 13.May 31:Reminder: makeup class TOMORROW (Friday) 12-1:30pm in 1127 Mudd. The class will be recorded.May 28:Few announcements about this week follow.May 26:hw1 is now available. It is due by10pm on Tuesday June 5. For a description of the SAT problem in question 4, please review slides 23-32 from slide set SAT. We will also go over this in Thursday's class.May 25:As discussed in class today, the release dates and deadlines for submitting homework assignments have been moved by one day (see homework section below).May 24:Next Thursday's (5/31) and Friday's (6/1) classes will take place in 1127 Mudd due to construction work next to our regular classroom.May 24:Reminder: makeup class TOMORROW 11:30-2:40pm in 524 Mudd. The class will be recorded.May 20: Several important announcements follow:## General course information

Time:TTR, 1-4:10pmLocation:524 Mudd BuildingInstructor:Eleni Drinea, eleni@cs.columbia.eduOffice Hours:Tuesdays, 4:15-6pm (or by appointment), Mudd 414Teaching 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 four homework assignments to help you better assimilate the course material.Late homework policy: No homework extensions will be granted. However you have 5 late days for all assignments: for example, you may submit Homework 1 at 9:59pm on Thu, 6/7, thus using 2 of your 5 late days. Note the followinghard deadlinesfor Homework 2 and Homework 4: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 policyHARD deadline: 10am on Wednesday, June 13)HARD deadline: 10am on Wednesday, June 27)## Preliminary schedule of lectures

Tue, 5/22:Insertion sort, induction, worst-case running time analysis, efficient algorithms, asymptotic notation, divide and conquer principle, mergesort, solving recurrences: recursion trees [insertionsort, Sections 1.1, 2.1, 2.2, mergesort, mastertheorem, Sections 3.1, 2.3, 4.0]Thu, 5/24:Master theorem; more divide & conquer algorithms: binary search, fast integer multiplication, fast matrix multiplication (Strassen's algorithm); quicksort, randomized algorithms, randomized Quicksort, balls-in-bins problems [moredivideandconquer, quicksort, balls in bins, Sections 4.2, 4.3, 4.4, 4.5, 7.1, 7.2]Fri, 5/25, 11:30am-2:40pm (makeup class 1, full):Graphs, graph representation, Breadth-First Search and applications: connected components, testing bipartiteness; Depth-First Search and applications: cycle detection, topological sort [graphs and BFS, optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179, Sections 22.1, 22.2, dfs-toposort, optional reading: Sections 22.3, 22.4]Sat, 5/26: hw1 outTue, 5/29:Analysis of randomized Quicksort; balls-in-bins problems, the coupon collector problem; hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins; hashing for saving space: fingerprints, Bloom filters [randQS-ballsinbins, hashing, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]Thu, 5/31:Greedy algorithms: Huffman coding for data compression; cache maintenance, online algorithms [huffman, 16.3, cache, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg; optional reading: Chapter 6 from your textbook (binary min heap)]Fri, 6/1, 12-1:30pm (makeup class 2, short):strongly connected components in directed graphs [stronglyconnectedcomponents, optional reading: Section 22.5]; single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra's algorithm [optional reading: Sections 24.0-24.3]Sat, 6/2: hw2 outTue, 6/5:Dynamic programming principle: segmented least squares, sequence alignment, matrix-chain multiplication [datasegmentation, sequencealignment, recommended reading: Chapter 15, Section 15.4; matrixchainmultiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]Tue, 6/5: hw1 due by 10pmThu, 6/7:Single-source shortest paths in weighted graphs (negative edge weights): Bellman-Ford; all-pairs shortest paths: Floyd-Warshall [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3, Section 25.2]; the knapsack problemFri, 6/8, 1-4:10pm (makeup class 3, full):Network flows, the Ford-Fulkerson algorithm for max flow; correctness of Ford-Fulkerson, applications of max flow: maximum bipartite matching [flows, pp. 708-720, 724-726, pp. 720-724, Section 26.3]Sat, 6/9: hw3 outTue, 6/12:no class (makeup class on 5/25)Tue, 6/12: hw2 due by 10pm (HARD deadline: 10am on Wed 6/13)Thu, 6/14:midterm examMidterm exam informationTime: 1-2:30pm (regular time) (no class after the exam, makeup class on 6/1)Location: 52 Mudd (regular classroom)Material: all lectures up to and including lecture6/7,except for the following:closed books, no calculators, no cheat sheet, no external aidsSat, 6/16: hw4 outTue, 6/19:no class (makeup class on Friday, 6/8)Tue, 6/19: hw3 due by 10pmThu, 6/21: Reductions; complexity classes P, NP, Satisfiability of boolean functions (formulas, circuits); proving NP-completeness, TSP and more NP-complete problems [reductions, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073, SAT, optional reading: Section 34.4, 34.5.2, more NP-complete problems, optional reading: 34.2 up to and not including Verification Algorithms, 34.5.4, p. 1118]Tue, 6/26:Linear programs, weak and strong duality, dualization; interpreting the dual LP; [LP_part1, optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof), duality, optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)](HARD deadline: 10am on Wed 6/27)Thu, 6/28: Final examFinal exam information:Day/Time:Thursday, June 28, 1-3pmLocation:524 Mudd BuildingMaterial:all lectures from 6/8 (Belman-Ford & Floyd-Warshall) up to and including 6/26, WITHOUT linear programmingclosed books, no calculators, no cheat sheet, no external aids.