Spring 2016

Analysis of Algorithms, I


Announcements

  • May 5: Solutions to HW5 and HW6 are now available on canvas.
  • Apr 29: Drishan will hold a review session this Thursday, 5/5 at 4:30pm in Mudd 833. Everyone is encouraged to attend.
  • Apr 27: final exam information
    • Date/Time: Tuesday, May 10, 7:10-9:10pm
    • Duration: 2h
    • Location: Mudd 833
    • Material: all lectures from 3/3 up to and including 4/26, only up to taking the dual of set cover (approximation algorithms will not be part of the exam); algorithm design techniques such as recursion, greedy and DP are part of the final exam.
    • Total #problems: ~8, potentially with multiple parts
    • Types of problems: True/False questions; multiple choice questions; algorithm design questions (you must argue correctness and analyze the running time of all algorithms you give); reductions (clearly give the reduction transformation, explain time to compute it, prove equivalence of instances; if the reduction is to show NP-completeness, you should also prove that the problem is in NP, that is, admits an efficient certifier); formulating linear or integer prorgams
    • Past final exam problems: HW4, problem 5; HW5: problems 6, 7 and 8; HW6: problems 1 and 5
    • Final exam is closed books, no calculators, no cheat sheet
  • Apr 25: HW6, problem 2: although a dominating set is defined in directed graphs in this problem, you may show that the dominating set problem in NP-complete for undirected graphs since the reduction is slightly cleaner.
  • Apr 25: Solutions to optional problems have been posted on canvas.
  • Apr 14: HW6 is out. It is due 8pm on Thursday, April 28.
  • Apr 13: HW6 will be out tomorrow (4/14) in the afternoon. It will be due in two weeks from tomorrow.
  • Apr 10: The instructor's office hours this week are moved to Monday, 4/11, 3-5. This change is for this week only.
  • Apr 8: As announced in class yesterday, you should not solve part i of Problem 6 in HW5.
  • Apr 4: Midterm solutions are now available on canvas.
  • Mar 30: Unfortunately I now have a conflict tomorrow 3-5. If you wish to discuss your midterm grade you may do so on Tuesday (4/5) during my regular office hours. Solutions to the exam will be posted on 4/4.
  • Mar 30: HW5 is out. It is due 8pm on Wednesday, April 13.
  • Mar 29: Solutions to the midterm will be posted tomorrow (3/30) on canvas. If you have questions about your exam, you may stop by the instructor's office on Thursday (3/31), 3-5.
  • Mar 29: HW5 will be out tomorrow (3/30) (and due in two weeks from tomorrow) to avoid overlap with HW4.
  • Mar 21: HW4 is out. It is due 1pm on Tuesday, March 29.
  • Mar 8: The instructor's OH today will start at 2:50.
  • Mar 4: midterm information
    • Material: all lectures up to and including March 3
    • Total #problems: 6-8, potentially with multiple parts
    • Past midterm problems: HW1: problems 1 and 3; HW2: problems 3 and 6; HW3: problem 1
    • True/false questions
    • Multiple choice questions
    • Algorithm design questions: you must argue correctness and analyze the running time of all algorithms you give
    • Midterm is closed books, no calculators, no cheat sheet
  • 2/29: Drishan will hold a review session this Sunday, 3/6 at 4pm in Mudd 833.
  • 2/26: Yesterday's slides have been reposted (a couple of theorems were labelled incorrectly).
  • 2/25: Reminder: we will hold the hackathon tomorrow (Friday, 2/26), 6-9pm in the CS lounge (view directions ). Pizza and soft drinks will be provided!
  • 2/24: There was a typo in Problem 5, HW3 ("end" and "then" should be swapped in the right tree). The pdf has been corrected.
  • 2/23: HW3 is out. It is due 1pm on Tuesday, March 8. No extensions will be granted for HW3 so that we can post solutions on time for your midterm exam. Please start working on this problem set early!
  • 2/22: We will hold the hackathon this Friday, 2/26, 6-9pm in the CS lounge.
  • 2/22: HW3 will be posted by 1pm tomorrow.
  • 2/18: Please vote for your preferred date to hold the "hackathon" in the poll on piazza by 2pm tomorrow (Friday). As mentioned in class, the hackathon is a 3h optional event aiming to bridge theory with practice. You will solve 3-4 problems and code up your solutions in C, C++, Java or Python, so please bring your laptops. Bo, Dev and Rajan will be there to assist you with thinking through a solution and/or coding it up, if needed. Food and soft drinks will be available. Once we have a date/time, I'll follow up with a location.
  • 2/16: HW2, Problem 3ii: if you're using a randomized algorithm/data structure, it should return the correct answer with probability 1. Also, you should use as little extra space as possible (see related comment on piazza).
  • 2/9: Yiyang will offer a recitation session on the binary min-heap (the data structure we used to improve the running time of Huffman's algorithm) on Sunday, 2/14, 4-5pm in Mudd 833. You are encouraged to attend and take notes, as this is a very useful data structure that we will encounter several times in our course.
  • 2/9: The instructor's OH today are cancelled. I will hold OH on Thursday, 2/11, 4-5, instead.
  • 2/8: HW2 is out. It is due 8pm on Monday, February 22.
  • 2/2: Please make sure you sign up for Piazza on Canvas.
  • 2/2: Drishan's OH are moved to Fridays, 10am-12pm, permanently.
  • 1/27: Drishan's OH tomorrow are moved to Friday, 10am-12pm. This change is for tomorrow only.
  • 1/25: HW1 is out. It is due 8pm on Monday, February 8.
  • 1/20: Office hours will start next week. However, as mentioned in class yesterday, you may stop by the instructor's office tomorrow (1/21) 2-3pm, if you have any questions about the class.

General course information
  • Time: TTR, 5:40-6:55pm, Location: 833 Mudd-Seeley
  • Instructor: Eleni Drinea, eleni@cs.columbia.edu
  • Office Hours: Tuesdays, 2:30-4:30pm (or by appointment), Mudd 414
  • Teaching Assistants and Office Hours:
  • Teaching staff mailing list: w4231-s2016@googlegroups.com
  • 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 some knowledge of discrete math and basic probability is required.


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
  • Network flows
  • Hashing: Bloom filters, count-min sketch
  • Greedy algorithms: huffman coding, minimum spanning trees & clustering
  • Dynamic programming: matrix multiplication, sequence alignment
  • Integer and linear programming
  • Reductions and NP-completeness
  • Randomized algorithms: median selection, min cut
  • Approximation and online algorithms
  • Heuristics: the metropolis algorithm, simulated annealing


Homeworks

  • General: There will be six biweekly homework assignments to help you better assimilate the course material.
    1. 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 refer to the end of this section.
    2. You may submit your homework assignment online (through courseworks) or use the drop box labelled "CSOR W4231.002, Analysis of Algorithms, I", in the CS TA room.
  • 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
    1. 6 hours past the submission deadline, 25% of the final score will be reduced;
    2. 6 and 24 hours past the submission deadline, 50% of the final score will be reduced;
    3. 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 (4-5) 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: Jan 25, Due: Feb 8
  2. Homework 2: Out: Feb 8, Due: Feb 22
  3. Homework 3: Out: Feb 23, Due: Mar 8
  4. Homework 4: Out: Mar 8, Due: Mar 28
  5. Homework 5: Out: Mar 28, Due: Apr 11
  6. Homework 6: Out: Apr 11, Due: Apr 25


Preliminary schedule

  • Tue, 1/19: Insertion sort, induction, worst-case running time analysis, efficient algorithms [
    File Not Found
    File Not Found
    , Sections 1.1, 2.1, 2.2]
  • Thu, 1/21: Asymptotic notation, divide and conquer principle, mergesort, solving recurrences: recursion trees, master theorem [
    File Not Found
    File Not Found
    , Sections 3.1, 2.3, 4.0, 4.3, 4.4, 4.5, notes on the master theorem]
    • Mon, 1/25: HW1 out
  • Tue, 1/26: More divide & conquer algorithms: binary search, fast integer multiplication, fast matrix multiplication (Strassen's algorithm), Quicksort [
    File Not Found
    File Not Found
    , Sections 4.2, 7.1]
  • Thu, 1/28: Quicksort (cont'd), randomized algorithms, randomized Quicksort [
    File Not Found
    File Not Found
    , Sections 7.2, 7.3, 5.1, 5.2 without the hiring problem]
  • Tue, 2/2: Analysis of randomized Quicksort, balls-in-bins problems [
    File Not Found
    File Not Found
    , Sections 7.4, 5.1, 5.2; Optional reading: 5.4.1, 5.4.2]
  • Thu, 2/4: Greedy algorithms: Huffman coding for data compression [
    File Not Found
    File Not Found
    , Section 16.3]
    • Mon, 2/8: HW1 due, HW2 out
  • Tue, 2/9: More greedy: cache maintenance, online algorithms [
    File Not Found
    File Not Found
    , for more context on this problem, read Section 4.3 from Tardos-Kleinberg]
  • Thu, 2/11: Dynamic programming principle: matrix-chain multiplication [slides2-11, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path
  • Tue, 2/16: Iterative and memoized implementations, segmented least squares [slides2-16]
  • Thu, 2/18: Sequence alignment, graphs [slides2-18, recommended reading: Section 15.4, optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179]
    • Mon, 2/22: HW2 due, HW3 out
  • Tue, 2/23: Graph representation, breadth-first search and applications: connected components, testing bipartiteness [slides2-23, Sections 22.1, 22.2 (optional)]
  • Thu, 2/25: Depth-first search and applications: cycle detection, topological sort [slides2-25, optional reading: Sections 22.3, 22.4, 22.5]
  • Tue, 3/1: Strongly connected components, single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra [slides3-1, optional reading: Section 22.5]
  • Thu, 3/3: Single-source shortest paths in graphs with negative edge weights: Bellman-Ford, all-pairs shortest paths: Floyd-Warshall [slides3-3, optional reading: Sections 24.0-24.3, Section 25.2]
    • Tue, 3/8: HW3 due, HW4 out
  • Tue, 3/8: Minimum spanning trees: Prim and Kruskal [slides3-31, optional reading: Chapter 24]
  • Thu, 3/10: Midterm Exam
    • Midterm information
      • Time: 5:40-6:55pm
      • Location: Mudd 833 (regular classroom)
      • Material: all lectures up to and including 3/3
      • Midterm is closed books, no calculators, no cheat sheet.
  • 3/14-3/18: no class, spring recess
  • Tue, 3/22: The union-find data structure and amortized analysis [slides4-2, optional reading: Sections 21.1, 21.2, 21.3]
  • Thu, 3/24: Hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins [slides3-24, Section 11.4] Hashing for saving space: Bloom filters, count-min sketch [slides3-26]
    • Mon, 3/28: HW4 due, HW5 out
  • Tue, 3/29: Network flows, the Ford-Fulkerson algorithm for max flow [slides4-7, pp. 708-720, 724-726]
  • Thu, 3/31: Applications: maximum bipartite matching, Hall's theorem [slides4-9, pp. 720-724, Section 26.3]
  • Tue, 4/5: Linear programs, weak and strong duality [optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof)]
  • Thu, 4/7: Dualization; interpreting the dual LP [optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)]
    • Mon, 4/11: HW5 due, HW6 out
  • Tue, 4/12: Reductions; complexity classes P, NP [slides4-21, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073]
  • Thu, 4/14: Proving NP-completeness; satisfiability of boolean functions (formulas, circuits) [slides4-23, optional reading: Section 34.4, 34.5.2]
  • Tue, 4/19: TSP, integer programming, set cover and more NP-complete problems [optional reading: 34.2 up to and not including Verification Algorithms, slides4-28.pdf, 34.5.4, p. 1118]
  • Thu, 4/21: Approximation algorithms for set cover, vertex cover
    • Mon, 4/25: HW6 due
  • Tue, 4/26: Heuristics: the metropolis algorithm, simulated annealing
  • Thu, 4/28: Streaming algorithms
  • 5/3-5/8: no class, study week
  • Final exam: TBA
    • Final exam information
      • Time: TBA
      • Location: TBA
      • Final exam is closed books, no calculators, no cheat sheet.