Announcements

  • 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:
    • Please enroll in piazza using the following link: piazza.com/columbia/summer2018/summer2018analysisofalgorithms. We look forward to questions and discussions!
    • Makeup class this Friday (May 25, tentative time: 11:30-2:40pm) in 524 Mudd. The class will be recorded. There will be no class on Tuesday, June 12.
    • Homework 1 will be out on Friday May 25 and due by 10pm on Monday, June 4. Please note that you must submit your assignment as a pdf file on courseworks.
    • Lecture videos will be available to every student. Please be patient while I work this out with CVN.
    • Office hours will start next week (May 29).

General course information

  • Time: TTR, 1-4:10pm
  • Location: 524 Mudd Building
  • Instructor: Eleni Drinea, eleni@cs.columbia.edu
  • Office Hours: Tuesdays, 4:15-6pm (or by appointment), Mudd 414
  • Teaching 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 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
  • Graph algorithms: depth-first search, breadth-first search, shortest paths
  • 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.
    1. Homework assignments will be out on Fridays (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.
    2. 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 Wed, 6/6, 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: 7pm on Tue, 6/26 (if you do so, you will use 0.75 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

  1. Homework 1: Out: Friday, May 25, Due: 10pm on Monday, June 4
  2. Homework 2: Out: Friday, June 1, Due: 10pm on Tuesday, June 12 (HARD deadline: 10am on Wednesday, June 13)
  3. Homework 3: Out: Friday, June 8, Due: 10pm on Monday, June 18
  4. Homework 4: Out: Friday, June 15, Due: 10pm on Monday, June 25 (HARD deadline: 5pm on Tuesday, June 26)

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 [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]
    • Fri, 5/25: hw1 out
  • 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)]
  • 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 [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3]
    • Fri, 6/1: hw2 out
    • Mon, 6/4: hw1 due by 10pm
  • Tue, 6/5: Dynamic programming principle: segmented least squares, sequence alignment, iterative and memoized implementations [datasegmentation, sequencealignment, recommended reading: Chapter 15, Section 15.4],
  • Thu, 6/7: Matrix-chain multiplication; [matrixchainmultiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]; single-source shortest paths in weighted graphs (negative edge weights): Bellman-Ford; [shortestpaths-negativeweights, optional reading: Sections 24.0-24.3, Section 25.2]; all-pairs shortest paths: Floyd-Warshall
  • Fri, 6/8, 12-3: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]
    • Fri, 6/8: hw3 out
  • Tue, 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 exam
    • Midterm exam information
      • Time: 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 lecture 6/7, except for the following:
        • makeup lecture 6/1;
        • Belman-Ford & Floyd-Warshall from lecture 6/7
      • Midterm is closed books, no calculators, no cheat sheet, no external aids
    • Fri, 6/15: hw4 out
    • Mon, 6/18: hw3 due by 10pm
  • Tue, 6/19: no class (makeup class on Friday, 6/8)
  • 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]
    • Mon, 6/25: hw4 due by 10pm (HARD deadline: 5pm on Tue 6/26)
  • 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)]; Approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4]
  • 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.