• Feb 5: hw3 is now available. It is due by 8pm on Monday March 5.
  • Feb 10: Solutions to hw1 are now available on courseworks, under Files.
  • Feb 5: hw2 is now available. It is due by 8pm on Monday February 19.
  • Feb 5: The instructor's office hours are permanently moved to Tuesdays 2-4pm to accommodate several students with conflicts.
  • Jan 24: The instructor's office hour tomorrow is canceled due to a conflict. This change is for tomorrow only.
  • Jan 23: Please signup for Piazza today using this link . Please follow piazza closely: important information about your homework assignments will be posted there, we will assume you have read and are familiar with this information.
  • Jan 22: hw1 is now available. It is due by 8pm on Monday February 5. Here is a template for hw1 if you're using latex.
  • Jan 15: Office hours will start next week (January 22).

General course information
  • Time: TTR, 4:10-5:25pm, Location: 501 NWC
  • Instructor: Eleni Drinea,
  • Office Hours: Tuesdays, 2-4pm (or by appointment), 414 Mudd
  • Teaching Assistants and Office Hours:
  • Teaching staff mailing list:
  • 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.

  • 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
  • Cryptography fundamentals and primality testing

  • 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 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 --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. Otherwise, if the assignment is submitted within
    1. 6 hours past the submission deadline, your final score will be reduced by 25%;
    2. 6 and 24 hours past the submission deadline, your final score will be reduced by 50%;
    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, copying solutions from the Internet or other textbooks is strictly prohibited. You should adhere to the department's academic honesty policy
  1. hw1: Out: Monday, Jan 22, Due: Monday, Feb 5 (a template for hw1)
  2. hw2: Out: Monday, Feb 5, Due: Monday, Feb 19
  3. hw3: Out: Monday, Feb 19, Due: Monday, Mar 5
  4. hw4: Out: Monday, Mar 19, Due: Monday, Apr 2
  5. hw5: Out: Monday, Apr 2, Due: Monday, Apr 16
  6. hw6: Out: Monday, April 16, Due: Monday, April 30

Preliminary syllabus

  • Tue, 1/16: Insertion sort, induction, worst-case running time analysis, efficient algorithms [insertionsort, Sections 1.1, 2.1, 2.2]
  • Thu, 1/18: Asymptotic notation, divide and conquer principle, mergesort, solving recurrences: recursion trees [mergesort, mastertheorem, Sections 3.1, 2.3, 4.0]
  • Tue, 1/23: Master theorem; more divide & conquer algorithms: binary search, fast integer multiplication [more divide & conquer, Sections 4.2, 4.3, 4.4, 4.5]
  • Thu, 1/25: Fast matrix multiplication (Strassen's algorithm), quicksort [quicksort, balls-in-bins, Sections 7.1, 7.2]
  • Tue, 1/30: Randomized algorithms, randomized Quicksort,analysis of randomized Quicksort [cache, Sections 7.3, 7.4, 5.1, 5.2 without the hiring problem]
  • Thu, 2/1: Greedy algorithms: Huffman coding for data compression [huffman, Section 16.3]
    • Mon, 2/5: hw1 due, hw2 out
  • Tue, 2/6: Occupancy problems; the coupon's collector problem [quicksort, balls-in-bins]
  • Thu, 2/8: More greedy: cache maintenance, online algorithms [cache, if you need more context on this problem, read Section 4.3 from Tardos-Kleinberg]
  • Tue, 2/13: Dynamic programming principle: segmented least squares, iterative and memoized implementations [datasegmentation]
  • Thu, 2/15: Sequence alignment [sequencealignment, recommended reading: Section 15.4]
    • Mon, 2/19: hw2 due, hw3 out
  • Tue, 2/20: Matrix-chain multiplication [matrix chain multiplication, Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]
  • Thu, 2/22: Graphs, graph representation, Breadth-First Search and applications: connected components [graphs and BFS, optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179, Sections 22.1, 22.2]
  • Tue, 2/27: BFS applications: connected components, testing bipartiteness; Depth-First Search and applications: cycle detection, topological sort [dfs-toposort, optional reading: Sections 22.3, 22.4]
  • Thu, 3/1: Strongly connected components [stronglyconnectedcomponents, optional reading: Section 22.5]
    • Mon, 3/5: hw3 due
  • Tue, 3/6: Single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra's algorithm; 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, 25.2]
  • Thu, 3/8: Midterm Exam
    • Midterm exam information:
      • Time: 4:10-5:25pm (regular time)
      • Location: 501 NWC (regular classroom)
      • Material: all lectures up to and including 3/1
      • Midterm is closed books, no calculators, no cheat sheet, no external aids.
  • 3/12-3/16: no class, spring recess
    • Mon, 3/19: hw4 out
  • Tue, 3/20: Hashing: hash table, universal hash functions, analysis of chain hashing using balls-and-bins; hashing for saving space: fingerprints, Bloom filters [hashing]
  • Thu, 3/22: Minimum spanning trees: Prim's and Kruskal's algorithms [msts, optional reading: Sections 21.1, 21.2, 21.3]; a first Union-Find data structure using linked lists: MakeSet, Find in worst-case O(1) time, a sequence of n Union operations in O(nlogn) time [Sections 21.1, 21.2] Recommended reading: Union-Find data structure using trees; union by rank and path compression; amortized analysis [Union-Find, Sections 17.0, 17.1, 17.2, 17.4 (without the potential method), 21.1, 21.2 (optional), 21.3]
  • Tue, 3/27: Network flows, the Ford-Fulkerson algorithm for max flow [flows, pp. 708-720, 724-726]
  • Thu, 3/29: Correctness of Ford-Fulkerson, applications of max flow: maximum bipartite matching, Hall's theorem [pp. 720-724, Section 26.3]
    • Mon, 4/2: hw4 due, hw5 out
  • Tue, 4/3: Reductions; complexity classes P, NP [reductions, Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073]
  • Thu, 4/5: Satisfiability of boolean functions (formulas, circuits) [SAT, optional reading: Section 34.4, 34.5.2]
  • Tue, 4/10: Proving NP-completeness
  • Thu, 4/12: TSP, and more NP-complete problems [more NP-complete problems, optional reading: 34.2 up to and not including Verification Algorithms, 34.5.4, p. 1118]
    • Mon, 4/16: hw5 due, hw6 out
  • Tue, 4/17: Linear programs, weak and strong duality [LP_part1, optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof)]
  • Thu, 4/19: Dualization; interpreting the dual LP [duality, optional reading: Section 29.4 up to and including Corollary 29.9, Section 29.2 (without min-cost flow/multi-commodity flow)]
  • Tue, 4/24: Approximation algorithms for set cover, vertex cover [IP-setcover-approximation, Section 11.4]
  • Thu, 4/26: Cryptography fundamentals: extended Euclid's algorithm, the RSA cryptosystem
    • Mon, 4/30: hw6 due
  • 5/1-5/4: no class, study week
  • TBD: Final exam
    • Final exam information:
      • Day/Time: TBD
      • Location: regular classroom
      • Final exam is closed books, no calculators, no cheat sheet, no external aids.