Spring 2015


Announcements

  • May 8: Information regarding your final exams
    • GRADUATING students: you may stop by CEPSR 620 on Thursday, May 14, 5-6:30pm to look at your graded final exams. I will submit your grades for this course on 5/14 by 9pm. I will send out a separate email to each of you today; if you do not receive an email from me by tonight, yet you are a graduating student, please email me ASAP.
    • NON-GRADUATING students: we will release your final exam grades by Sunday, May 17. if you want to take a look at your exam, you may stop by my office on
      • Monday, May 18, 12:30-2:30pm; or
      • Tuesday, May 19, 1:30-4pm.
  • May 5: Solutions to HW6 are now available on courseworks.
  • May 4: You may pick up your graded HW5 during Liang's or Xinyue's OH this week.
  • May 4: Slides for the lecture on 4/28 have been updated (note: LP relaxation is not part of the final exam). For a reduction from Hamiltonian cycle to TSP, and more variants of TSP, see slides for 4/30.
  • May 1: Final exam information
    • Location: regular classroom (Mudd 833)
    • Date & Time: Thursday, May 7, 6-8pm
    • Duration: 2h
    • Material: all lectures up to and including April 28. You should briefly refresh your memory on the problems we studied before the exam and the running time of the solutions. The exam will focus heavily on the material after the midterm, that is, shortest paths, hashing, MSTs, flows, LPs, reductions and NP-completeness. Of course, algorithmic design principles such as recursion, greedy and DP will be part of the exam.
    • Taking the dual: you do not need to remember the 7-step procedure for taking the dual. However you should be able to derive the dual of a small linear program with, say, 3 variables and 3 constraints by using multipliers (as in the chocolatier example), or the matrix-vector form of an LP.
    • You should know what an integer program is and how to form one.
    • You should know what the following problems are: SAT, 3SAT, Independent Set, Vertex Cover, Hamiltonian cycle, TSP, Set Cover.
    • Total #problems: 8, potentially with multiple parts
      • True/false questions
      • Multiple choice questions
      • Algorithm design questions: you should argue correctness and analyze the running time of all algorithms you give
      • Reductions: you should work out all reductions carefully; clearly explain the reduction transformation and prove equivalence of instances
      • Midterm is closed books, no calculators, no cheat sheet.
  • Apr 18: HW6 is now available. It is due Friday, May 1, by 8pm.
  • Apr 3: HW5 is now available. It is due Friday, April 17, by 8pm.
  • Mar 30: Office hours change, this week only: the instructor's office hours on Tuesday are moved to 12:45-2pm.
  • Mar 26: Midterm exams
    • Midterms will be returned in class today.
    • Solutions will be posted on courseworks by 3/29 (in the evening).
    • If you have questions regarding your grade, you can stop by the instructor's office (Mudd 529A) tomorrow, 1-3pm or by appointment.
  • Mar 13: HW4 is now available. PLEASE NOTE UNUSUAL DUE DATE: Wednesday, April 1, by 8pm.
  • Mar 9: Since you are preparing for your midterm exams this week, HW4 will be posted after our midterm (3/13). Its due date will be adjusted accordingly; there will be an overlap of a few days between HW4 and HW5.
  • Mar 4: Midterm information
    • Location: regular classroom
    • Date & Time: Thursday, March 12, 5:40-6:55pm
    • Material: all lectures up to and including March 5
    • Total #problems: 6-8, potentially with multiple parts
      • 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.
  • Feb 28: FINAL EXAM date and time: Thursday, May 7, 6-9pm
  • Feb 26: Hackathon tomorrow (2/27) 6-9pm in CS lounge. Pizzas and soft drinks will be provided! This event is optional; please let us know whether you will be attending by participating in the poll on courseworks (if you haven't done so already) so we can have an accurate estimate for the food needed.
  • Feb 23: HW3 is now available. It is due Mon 3/9 by 8pm.
  • Feb 22: On HW2: in case you have an older print of the 3rd edition of your textbook, Problem 7-2, part c (p. 186) should read as follows. Modify the RANDOMIZED-PARTITION procedure to call PARTITION′, and name the new procedure RANDOMIZED-PARTITION′. Then modify the QUICKSORT procedure to produce a procedure QUICKSORT′(A, p, r) that calls RANDOMIZED-PARTITION′ and recurses only on partitions of elements not known to be equal to each other.
  • Feb 17: HW1 grades are now available. If you have any questions, please see Di by March 3. Di is available at the end of today's class or during OH.
  • Feb 17: The instructor's OH are moved to 1-3pm.
  • Feb 11: Liang and Xinyue will hold a recitation session this Friday, 2/13, 7-8pm, Mudd 833 on binary min-heaps (the data structure we used for the Huffman algorithm).
  • Feb 9: HW2 is now available. It is due Mon 2/23 by 8pm.
  • Feb 9: HW1 will be graded by Di.
  • Feb 5: Typos corrected in HW1, Problem 3: the last two summations are over the first n terms of the series, so their upper limit is n (not infinity).
  • Jan 26: No class tomorrow due to the winter storm.
  • Jan 26: The instructor and the TAs will start holding office hours next week (2/2).
  • Jan 26: HW1 is now available. It is due Mon 2/9 by 8pm.

General course information

  • Time: TTR, 5:40-6:55pm, Location: 833 Mudd-Seeley
  • Instructor: Eleni Drinea, eleni@cs.columbia.edu
  • Office Hours: Tuesdays, 1:30-3:30pm (or by appointment), Mudd 529A
  • Teaching Assistants and Office Hours:
  • Teaching staff mailing list: w4231@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.
  • 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, document similarity
  • Greedy algorithms: huffman coding, minimum spanning trees
  • Dynamic programming: matrix multiplication, sequence alignment
  • Integer and linear programming
  • Reductions and NP-completeness
  • Randomized algorithms: median selection, primality testing
  • Approximation and online algorithms

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 (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.
    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 (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, consulting solutions from the Internet or other textbooks is strictly prohibited.

  1. Homework 1: Out: Jan 26, Due: Feb 9
  2. Homework 2: Out: Feb 9, Due: Feb 23
  3. Homework 3: Out: Feb 23, Due: Mar 9
  4. Homework 4: Out: Mar 13, Due: Apr 1
  5. Homework 5: Out: Apr 3, Due: Apr 17
  6. Homework 6: Out: Apr 13, Due: Apr 27


Preliminary syllabus


  • Tue, 1/20: Insertion sort, induction, worst-case running time analysis, efficient algorithms [, Sections 1.1, 2.1, 2.2]
  • Thu, 1/22: Asymptotic notation, divide and conquer principle, mergesort [, Sections 3.1, 2.3, 4.0]
Mon, 1/26: HW1 out
Tue, 1/27: cancelled due to winter storm
Thu, 1/29: Solving recurrences: recursion trees, master theorem; more divide & conquer algorithms: binary search, fast integer multiplication [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, Sections 4.2, 4.3, 4.4, 4.5]
Tue, 2/3: Fast matrix multiplication (Strassen's algorithm), Quicksort, randomized algorithms, randomized Quicksort [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, Sections 7.1, 7.2]
Thu, 2/5: Analysis of randomized Quicksort [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]
Mon, 2/9: HW1 due, HW2 out
Tue, 2/10: Greedy algorithms: Huffman coding for data compression [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, Section 16.3]
Thu, 2/12: More greedy: cache maintenance, online algorithms [slides2-12, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg]
Tue, 2/17: Dynamic programming principle: matrix-chain multiplication [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]
Thu, 2/19: Iterative and memoized implementations, segmented least squares [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
]
Mon, 2/23: HW2 due, HW3 out
Tue, 2/24: Sequence alignment, graphs [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, recommended reading: Section 15.4, optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179]
Thu, 2/26: Graph representation, breadth-first search and applications: connected components, testing bipartiteness [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, Sections 22.1, 22.2 (optional)]
Tue, 3/3: Depth-first search and applications: cycle detection, topological sort [slides3-3, optional reading: Sections 22.3, 22.4, 22.5]
Thu, 3/5: Strongly connected components, single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra [slides3-5, optional reading: Section 22.5]
Mon, 3/9: HW3 due
Tue, 3/10: Single-source shortest paths in graphs with negative edge weights: Bellman-Ford, all-pairs shortest paths: Floyd-Warshall [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
, optional reading: Sections 24.0-24.3, Section 25.2]
Thu, 3/12: Midterm Exam
Fri, 3/13: HW4 out
Midterm information
Time: 5:40-6:55pm
Location: Mudd 833 (regular classroom)
Midterm is closed books, no calculators, no cheat sheet.
3/17-3/19: no class, spring recess
Tue, 3/24: Hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins [slides3-24, Section 15.4]
Thu, 3/26: Hashing for saving space: hashing-based fingerprints, Bloom filters [slides3-26]
Tue, 3/31: Minimum spanning trees: Prim and Kruskal [slides3-31, optional reading: Chapter 24]
Wed, 4/1: HW4 due
Thu, 4/2: The union-find data structure and amortized analysis [slides4-2, optional reading: Sections 21.1, 21.2, 21.3]
Fri, 4/3: HW5 out
Tue, 4/7: Network flows, the Ford-Fulkerson algorithm for max flow [slides4-7, pp. 708-720, 724-726]
Thu, 4/9: Applications: maximum bipartite matching, Hall's theorem [slides4-9, pp. 720-724, Section 26.3]
Tue, 4/14: 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/16: 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)]
Fri, 4/17: HW5 due, HW6 out
Tue, 4/21: 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/23: Proving NP-completeness; satisfiability of boolean functions (formulas, circuits) [slides4-23, optional reading: Section 34.4, 34.5.2]
Tue, 4/28: 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/30: Approximation algorithms for set cover, vertex cover [
[[image:/i/file_not_found.png width="32" height="32" caption="File Not Found"]]File Not Found
; we followed in part chapter 1 from "The design of Approximation Algorithms" by Williamson and Shmoys]
Fri, 5/1: HW6 due
Thu, 5/7: Final exam
Final exam information
Time: 6-9pm
Location: Mudd 833
Final exam is closed books, no calculators, no cheat sheet.