Recent Changes

Today

  1. page home edited Announcements May 24: Next Thursday's (5/31) and Friday's (6/1) classes will take place in 1127…

    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.
    ...
    announcements follow:
    Please enroll in piazza using the following link: piazza.com/columbia/summer2018/summer2018analysisofalgorithms. We look forward to questions and discussions!
    ...
    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.
    (view changes)
    9:29 am
  2. page home edited Announcements ... 24: Reminder: Makeup makeup class TOMORROW May 20: Several important ann…

    Announcements
    ...
    24: Reminder: Makeupmakeup class TOMORROW
    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!
    ...
    Teaching Assistants and Office Hours:
    Daniel Gomez, daniel.gomez@columbia.edu, Office Hours: Saturdays, 2-4pm, Mudd 122A (CS TA room)
    ...
    Office Hours: Thursdays, 7-9pm,Sundays, 2-4pm, Mudd 122A
    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.
    (view changes)
    8:41 am
  3. page home edited Announcements May 24: Reminder: Makeup class TOMORROW 11:30-2:40pm in 524 Mudd. The class will …

    Announcements
    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!
    (view changes)
    8:38 am

Yesterday

  1. page home edited ... Office Hours: Tuesdays, 4:15-6pm (or by appointment), Mudd 414 Teaching Assistants and Office…
    ...
    Office Hours: Tuesdays, 4:15-6pm (or by appointment), Mudd 414
    Teaching Assistants and Office Hours:
    MidhunDaniel Gomez, daniel.gomez@columbia.edu, Office Hours: Saturdays, 2-4pm, Mudd 122A (CS TA room)
    Midhun
    Gundapuneni, g.midhun@columbia.edu, Office Hours: TBD,Thursdays, 7-9pm, Mudd 122A
    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.
    (view changes)
    6:23 am

Tuesday, May 22

  1. page home edited ... Office Hours: Tuesdays, 4:15-6pm (or by appointment), Mudd 414 Teaching Assistants and Office…
    ...
    Office Hours: Tuesdays, 4:15-6pm (or by appointment), Mudd 414
    Teaching Assistants and Office Hours:
    Daniel Gomez, dg3001@columbia.edu,Midhun Gundapuneni, g.midhun@columbia.edu, Office Hours: TBD, CSMudd 122A (CS TA roomroom)
    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.
    (view changes)
    9:13 am

Sunday, May 20

  1. page Summer 2017 edited ... Jun 19: Solutions to the midterm exam are now available on courseworks. Jun 19: Reminder: no …
    ...
    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 {HW4.pdf} ishw4 is now available.
    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.
    ...
    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 {HW3.pdf} ishw3 is now available.
    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 {HW2.pdf} ishw2 is now available.
    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: 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 {HW1.pdf} ishw1 is now available.
    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).
    ...
    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 {HW1.pdf} :hw1: Out: Friday,
    ...
    June 5
    Homework 2 {HW2.pdf} :

    hw2:
    Out: Friday,
    ...
    June 12
    Homework 3 {HW3.pdf} :

    hw3:
    Out: Friday,
    ...
    June 19
    Homework 4 {HW4.pdf} :

    hw4:
    Out: Saturday,
    x-Announcements-Preliminary syllabusPreliminary 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 {insertionsort.pdf} , Sections 1.1, 2.1, 2.2, mergesort {mergesort.pdf} , mastertheorem {mastertheorem.pdf} , Sections 3.1, 2.3, 4.0]
    ...
    {moredivideandconquer.pdf} , quicksort {quicksort.pdf} ,
    ,
    randQS-ballsinbins {randQS-ballsinbins.pdf}
    ...

    Fri, 5/26: HW1 {HW1.pdf} outhw1 out
    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 {randQS-ballsinbins.pdf} , hashing {hashing.pdf} , 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, {huffman.pdf} 16.3, cache {cachemaintenance.pdf} , 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)]
    Makeup class (full) Fri, 6/2, 12-3:10pm, 1024 Mudd: Graphs, graph representation, Breadth-First Search and applications: connected components, testing bipartiteness; Depth-First Search and applications: cycle detection, topological sort [ graphsandBFS {graphs-BFS.pdf} , optional reading: Appendix B, Sections B.4, B.5, pp. 1168-1179, Sections 22.1, 22.2, dfs-toposort {DFS-toposort.pdf} , optional reading: Sections 22.3, 22.4]
    Fri, 6/2: HW2 {HW2.pdf} outhw2 out
    Mon, 6/5: HW1 due
    Tue, 6/6: Dynamic programming principle: segmented least squares, sequence alignment, iterative and memoized implementations [ datasegmentation {datasegmentation.pdf} , sequencealignment {sequencealignment.pdf} , recommended reading: Chapter 15, Section 15.4],
    Thu, 6/8: Matrix-chain multiplication; [ matrixchainmultiplication {matrixchainmult.pdf} , Sections 15.0, 15.2, 15.3 without the discussion on shortest/longest simple path]; strongly connected components [ stronglyconnectedcomponents {SCCs.pdf} , optional reading: Section 22.5]; single-source shortest paths in weighted graphs (non-negative edge weights): Dijkstra's algorithm [ shortestpaths-negativeweights {BelmanF-FW.pdf} , optional reading: Sections 24.0-24.3]
    Makeup class (short) Fri, 6/9, 12-1:30pm, 1024 Mudd: Single-source shortest paths in weighted graphs (negative edge weights): Bellman-Ford; [ shortestpaths-negativeweights {BelmanF-FW.pdf} , optional reading: Sections 24.0-24.3, Section 25.2]
    Fri, 6/9: HW3 {HW3.pdf} outhw3 out
    Mon, 6/12: HW2 due
    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 {flows.pdf} , 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)
    ...
    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
    Sat, 6/17: HW4 {HW4.pdf} outhw4 out
    Mon, 6/19: HW3 due
    Tue, 6/20: no class (makeup class on Friday, 6/2)
    (view changes)
    7:05 am

Saturday, May 19

  1. page home edited ... Announcements May 20: Several important announcements follow: ... forward to questions/d…
    ...
    Announcements
    May 20: Several important announcements follow:
    ...
    forward to questions/discussions!
    I will hold a makeup
    questions and discussions!
    Makeup
    class onthis Friday May 25 (tentative(May 25, tentative time: 11:30-2:40pm)
    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.
    ...
    week (May 30).29).
    x-Announcements---General course informationx-Announcements---General course informationGeneral course information
    Time: TTR, 1-4:10pm, Location:1-4:10pm
    Location:
    524 Mudd
    Instructor: Eleni Drinea, eleni@cs.columbia.edu
    ...
    Hours: Tuesdays, 4:15-5:50pm4:15-6pm (or by
    Teaching Assistants and Office Hours:
    Daniel Gomez, dg3001@columbia.edu, Office Hours: TBD, CS TA room
    ...
    Analysis of Algorithms, I-HomeworksHomeworks
    General: There will be four homework assignments to help you better assimilate the course material.
    ...
    be due ~1010 days later
    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!
    ...
    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
    ...
    on Wed, 6/6 and6/6, thus useusing 2 of
    Homework 2: 10am on Wed, 6/13 (if you do so, you will use 0.5 late days)
    Homework 4: 11am7pm on Wed, 6/27Tue, 6/26 (if you
    ...
    will use 1.50.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
    Homework 1: Out: Friday, May 25, Due: 10pm on Monday, June 4
    ...
    (HARD deadline: 10am on Wednesday, June 13 at 10am)13)
    Homework 3: Out: Friday, June 8, Due: 10pm on Monday, June 18
    ...
    (HARD deadline: Wednesday,5pm on Tuesday, June 27 at 10am)26)
    x-Announcements-Preliminary syllabusPreliminary 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 {insertionsort.pdf} , Sections 1.1, 2.1, 2.2, mergesort {mergesort.pdf} , mastertheorem {mastertheorem.pdf} , Sections 3.1, 2.3, 4.0]
    ...
    Fri, 6/8: hw3 out
    Tue, 6/12: no class (makeup class on 5/25)
    ...
    by 10pm (HARD deadline: 10am on Wed 6/13)
    Thu, 6/14: midterm exam
    Midterm exam information
    ...
    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 {reductions.pdf} , Sections 34.0, 34.1 up to and including p. 1056, 34.3 up to p. 1073, SAT {SAT.pdf} , optional reading: Section 34.4, 34.5.2, more NP-complete problems {moreNPcomplete.pdf} , optional reading: 34.2 up to and not including Verification Algorithms, 34.5.4, p. 1118]
    Mon, 6/26: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 {LP_part1.pdf} , optional reading: Sections 29.0, 29.1 (without the slack form), Theorem 29.13 on p. 892 (just the statement, no proof), duality {LP-part2.pdf} , 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 {IP-SetCover.pdf} , Section 11.4]
    Thu, 6/28: Final exam
    (view changes)
    2:44 pm
  2. page Spring 2018 edited ... Instructor: Eleni Drinea, eleni@cs.columbia.edu Office Hours: Tuesdays, 2-4pm (or by appointm…
    ...
    Instructor: Eleni Drinea, eleni@cs.columbia.edu
    Office Hours: Tuesdays, 2-4pm (or by appointment), 414 Mudd
    ...
    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
    Daniel Gomez, daniel.gomez@columbia.edu, Office Hours: Saturdays, 2-4pm, Mudd 122A (CS TA room)
    Gaurav Singh, gs2938@columbia.edu, Office Hours: Fridays, 6-8pm, Mudd 122A (CS TA room)
    ...
    Mon, 3/5: hw3 due
    Tue, 3/6: Single source shortest paths, non-negative edge weights: Dijsktra's algorithm
    Thu, 3/8: midtermmidterm exam
    Midterm exam information:
    Time: 4:10-5:25pm (regular time)
    (view changes)
    2:25 pm
  3. page Spring 2018 edited ... Mon, 3/5: hw3 due Tue, 3/6: Single source shortest paths, non-negative edge weights: Dijsktra…
    ...
    Mon, 3/5: hw3 due
    Tue, 3/6: Single source shortest paths, non-negative edge weights: Dijsktra's algorithm
    Thu, 3/8: midterm midterm exam
    Midterm exam information:
    Time: 4:10-5:25pm (regular time)
    (view changes)
    2:23 pm

More