Jun 13: Reminder: HW4 is due by 11am on Wednesday.

Jun 25: final exam information

Material: all lectures from 6/8 up to and including 6/27, WITHOUT linear programming

NB: any material on the slides that was not covered in class is not part of the final; exception: Floyd-Warshall algorithm, for which you should know (a) which problem it solves (all-pairs shortest paths in weighted graphs) and (b) its time/space complexity (O(n^3) and O(n^2) respectively)

Time: 1:10-3:10pm (the duration of the exam might change but will not exceed 2h)

Location: regular classroom

Total #problems: ~7, potentially with multiple parts

T/F questions

Short explanation/counterexample questions

Reductions: clearly describe the reduction transformation and argue it is polynomial time; then prove carefully equivalence of the original and the transformed instances.

Past final exam problems:

HW3: problems 1, 5; recommended exercises 3, 4.

HW4: problem 1, 3, 4b; recommended exercises 1, 3.

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 and give pseudocode only if time permits

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

Jun 25: Solutions to HW3 are now available on courseworks.

Jun 19: Solutions to the midterm exam are now available on courseworks.

Jun 19: Reminder: no class/instructor's OH tomorrow (6/20).

Jun 17: HW4 is now available. It is due by 8pm on Monday 6/26 and no later than 11am on Wednesday 6/28.

Jun 14: Solutions to HW2 are now available on courseworks.

Jun 13: Reminders: HW2 is due by 11am tomorrow (Wednesday); there will be no class after the midterm exam on Thursday.

Jun 13: Midterm exam information

Material: all lectures up to and including 6/8, without Dijkstra's algorithm

Total #problems: ~7, potentially with multiple parts

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 and give pseudocode only if time permits

Midterm is closed books, no calculators, no cheat sheet

Jun 9:HW3 is now available. It is due by 8pm on Monday, June 19.

Jun 6: A reminder that there will be three classes this week, including the class on Friday 12-1:30pm in 1024 Mudd.

Jun 2:HW2 is now available. It is due by 8pm on Mon 6/12 and no later than 11am on Wed 6/14. Please read carefully the collaboration policy for this assignment.

Jun 2: Reminder: class today at 12pm in 1024 Mudd.

Jun 1: Recommended reading: Chapter 6 from your textbook (the binary min heap data structure)

May 30: A reminder that there will be three classes this week, including the class on Friday 12-3:10pm in 1024 Mudd.

May 30: Office hours start this week (May 30).

May 26: Piazza: if you haven't enrolled in piazza yet, please take a moment to do so by using the following link: piazza.com/columbia/summer2017/csors4231_002_2017_2. We look forward to questions/discussions!

May 26:HW1 is now available. It is due by 8pm on Monday, June 5. Please note that you must submit your assignment as a pdf file on canvas.

May 26: Lecture videos are now available to everyone.

May 25: Please note that there will be two makeup classes: one full-length class on Fri, 6/2, 12-3:10pm and one half class on Fri, 6/9,12-1:30pm. Both classes will be in 1024 Mudd and will be recorded. There will be no classes on 6/20, and 6/15 after the midterm exam (see also preliminary syllabus below).

May 23: Office hours will start next week (May 30).

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 Fridays (late in the evening). They will be due 10 days 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. However you have 5 late days for all assignments: for example, you may submit HW1 at 7:59pm on Wed, 6/7 and thus use 2 of your 5 late days. Note the following hard deadlines for hw2 and hw4:

HW2: 11am on Wed, 6/14 (if you do so, you will use 1.5 late days)

HW4: 11am on Wed, 6/28 (if you do so, you will use 1.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: Friday, May 26, Due: Monday, June 5

Homework 2: Out: Friday, June 2, Due: Monday, June 12

Homework 3: Out: Friday, June 9, Due: Monday, June 19

Homework 4: Out: Saturday, June 17, Due: Monday, June 26

Tue, 5/31: 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, 6/1: 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/13: All-pairs shortest paths: Floyd-Warshall; 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/15: Midterm exam (no class after the exam: makeup class on Friday, 6/9)

Midterm exam information

Time: 1-2:30pm (regular time)

Location: 1024 Mudd (regular classroom)

Material: all lectures up to and including 6/8, without Dijkstra's algorithm

Midterm is closed books, no calculators, no cheat sheet, no external aids

Thu, 6/22: 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]

Mon, 6/26:HW4 due

Tue, 6/27: 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)]; Approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4]

Thu, 6/29: Final exam

Final exam information:

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

Location: 1024 Mudd Building

Material: all lectures from 6/8 (Dijsktra's algorithm) up to and including 6/29, WITHOUT linear programming

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

AnnouncementsJun 13:Reminder: HW4 is due by11am on Wednesday.Jun 25:final exam informationMaterial:all lectures from 6/8 up to and including 6/27, WITHOUT linear programmingNB:any material on the slides that was not covered in class is not part of the final;exception: Floyd-Warshall algorithm, for which you should know (a) which problem it solves (all-pairs shortest paths in weighted graphs) and (b) its time/space complexity (O(n^3) and O(n^2) respectively)Time:1:10-3:10pm (the duration of the exam might change but will not exceed 2h)Location:regular classroomTotal #problems:~7, potentially with multiple partsAlgorithm 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 and give pseudocode only if time permits*closed books, no calculators, no cheat sheet*Jun 25: Solutions to HW3 are now available on courseworks.Jun 19: Solutions to the midterm exam are now available on courseworks.Jun 19:Reminder: no class/instructor's OH tomorrow (6/20).Jun 17: HW4 is now available. It is due by8pm on Monday 6/26andno later than 11am on Wednesday 6/28.Jun 14:Solutions to HW2 are now available on courseworks.Jun 13:Reminders: HW2 is due by 11am tomorrow (Wednesday); there will be no class after the midterm exam on Thursday.Jun 13:Midterm exam informationJun 9:HW3 is now available. It is due by8pm on Monday, June 19.un 6: A reminder that there will be three classes this week, including the class on Friday 12-1:30pm in 1024 Mudd.Jun 2:HW2 is now available. It is due by8pm on Mon 6/12 and no later than 11am on Wed 6/14.Please read carefully the collaboration policy for this assignment.Jun 2:Reminder: class today at 12pm in 1024 Mudd.Jun 1:Recommended reading: Chapter 6 from your textbook (the binary min heap data structure)May 30:A reminder that there will bethreeclasses this week, including the class on Friday 12-3:10pm in 1024 Mudd.May 30:Office hours start this week (May 30).May 26:Piazza: if you haven't enrolled in piazza yet, please take a moment to do so by using the following link: piazza.com/columbia/summer2017/csors4231_002_2017_2. We look forward to questions/discussions!May 26:HW1 is now available. It is due by8pm on Monday, June 5. Please note that you must submit your assignment as a pdf file on canvas.May 26:Lecture videos are now available to everyone.May 25:Please note that there will betwo makeup classes: one full-length class onFri, 6/2, 12-3:10pmand one half class onFri, 6/9,12-1:30pm. Both classes will be in 1024 Mudd and will be recorded. There will be no classes on 6/20, and 6/15 after the midterm exam (see also preliminary syllabus below).May 23:Office hours will start next week (May 30).General course informationTime:TTR, 1-4:10pm, Location: 1024 Mudd BuildingInstructor:Eleni Drinea, eleni@cs.columbia.eduOffice Hours:Tuesdays, 4:15-5:50pm (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.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 four 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. However you have5 late daysfor all assignments: for example, you may submit HW1 at 7:59pm on Wed, 6/7 and thus use 2 of your 5 late days. Note the following hard deadlines for hw2 and hw4: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 policyHomework 1:Out: Friday, May 26, Due: Monday, June 5Homework 2:Out: Friday, June 2, Due: Monday, June 12Homework 3:Out: Friday, June 9, Due: Monday, June 19Homework 4:Out: Saturday, June 17, Due: Monday, June 26## Preliminary syllabus

Tue, 5/23: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/25: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, randQS-ballsinbins, Sections 4.2, 4.3, 4.4, 4.5, 7.1, 7.2]Fri, 5/26: HW1 outTue, 5/31: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, 6/1: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)]: Graphs, graph representation, Breadth-First Search and applications: connected components, testing bipartiteness; Depth-First Search and applications: cycle detection, topological sort [graphsandBFS, 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]Makeup class (full)Fri, 6/2, 12-3:10pm, 1024 MuddFri, 6/2: HW2 outMon, 6/5: HW1 dueTue, 6/6: Dynamic programming principle: segmented least squares, sequence alignment, iterative and memoized implementations [datasegmentation, sequencealignment, recommended reading: Chapter 15, Section 15.4],Thu, 6/8:Matrix-chain multiplication; [matrixchainmultiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]; strongly connected components [stronglyconnectedcomponents, optional reading: Section 22.5]; single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra's algorithm [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3]: Single-source shortest paths in weighted graphs (negative edge weights): Bellman-Ford; [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3, Section 25.2]Makeup class (short)Fri, 6/9, 12-1:30pm, 1024 MuddFri, 6/9: HW3 outMon, 6/12: HW2 dueTue, 6/13: All-pairs shortest paths: Floyd-Warshall; 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/15:Midterm exam (no class after the exam: makeup class on Friday, 6/9)Midterm exam informationwithout Dijkstra's algorithmclosed books, no calculators, no cheat sheet, no external aidsSat, 6/17: HW4 outMon, 6/19: HW3 dueTue, 6/20:no class (makeup class on Friday, 6/2)Thu, 6/22: 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]Mon, 6/26: HW4 dueTue, 6/27: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)];Approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4]Thu, 6/29: Final examFinal exam information:closed books, no calculators, no cheat sheet, no external aids.