Recent Changes

Wednesday, June 27

  1. page home edited Announcements ... Solutions to hw44 hw4 are now June 25: Solutions to hw3 are now availabl…

    Announcements
    ...
    Solutions to hw44hw4 are now
    June 25: Solutions to hw3 are now available on courseworks. Solutions to hw4 will be posted around 11am on Wednesday.
    June 22: Solutions to the midterm exam are posted on courseworks under Files.
    (view changes)
    8:07 am
  2. page home edited Announcements June 27: Solutions to hw44 are now available on courseworks. June 25: Solution…

    Announcements
    June 27: Solutions to hw44 are now available on courseworks.
    June 25: Solutions to hw3 are now available on courseworks. Solutions to hw4 will be posted around 11am on Wednesday.
    June 22: Solutions to the midterm exam are posted on courseworks under Files.
    (view changes)
    8:07 am

Monday, June 25

  1. page home edited ... Tue, 6/19: hw3 due by 10pm Thu, 6/21: Reductions; complexity classes P, NP, Satisfiability of…
    ...
    Tue, 6/19: hw3 due by 10pm
    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]
    ...
    min-cost flow/multi-commodity flow)]; Approximation algorithms for set cover, vertex cover [ IP-setcover-approximation {IP-SetCover.pdf} , Section 11.4]flow)]
    Tue, 6/26: hw4 due by 10pm (HARD deadline: 10am on Wed 6/27)
    Thu, 6/28: Final exam
    (view changes)
    6:00 pm
  2. page home edited Announcements June 25: Solutions to hw3 are now available on courseworks. Solutions to hw4 will…

    Announcements
    June 25: Solutions to hw3 are now available on courseworks. Solutions to hw4 will be posted around 11am on Wednesday.
    June 22: Solutions to the midterm exam are posted on courseworks under Files.
    June 22: Final exam information
    (view changes)
    4:40 am

Friday, June 22

  1. page home edited ... Time: 1-2:30 (tentative) Location: 524 Mudd ... and including all NP-complete problems …
    ...
    Time: 1-2:30 (tentative)
    Location: 524 Mudd
    ...
    and including all NP-complete problems
    True/false questions
    Multiple choice questions
    (view changes)
    8:23 am
  2. page home edited ... Time: 1-2:30 (tentative) Location: 524 Mudd ... from 6/26; also, makeup lecture ... 6/1…
    ...
    Time: 1-2:30 (tentative)
    Location: 524 Mudd
    ...
    from 6/26; also, makeup lecture
    ...
    6/1 is also part of
    True/false questions
    Multiple choice questions
    (view changes)
    8:22 am
  3. page home edited ... Homework 3: problems 1, 4, 5; recommended exercise 3. Homework 4: problems 2, 3b, 4, 5; recom…
    ...
    Homework 3: problems 1, 4, 5; recommended exercise 3.
    Homework 4: problems 2, 3b, 4, 5; recommended exercises 1, 3.
    ...
    design technique might be appropriate for each problem (recursion, greedy, DP, reduction).reduction) is appropriate for each problem.
    If you give a reduction:
    describe the inputs to the two problems
    (view changes)
    8:21 am
  4. page home edited ... Homework 3: problems 1, 4, 5; recommended exercise 3. Homework 4: problems 2, 3b, 4, 5; recom…
    ...
    Homework 3: problems 1, 4, 5; recommended exercise 3.
    Homework 4: problems 2, 3b, 4, 5; recommended exercises 1, 3.
    ...
    design technique ismight be appropriate for everyeach problem (recursion,
    If you give a reduction:
    describe the inputs to the two problems
    (view changes)
    8:20 am
  5. page home edited ... Homework 3: problems 1, 4, 5; recommended exercise 3. Homework 4: problems 2, 3b, 4, 5; recom…
    ...
    Homework 3: problems 1, 4, 5; recommended exercise 3.
    Homework 4: problems 2, 3b, 4, 5; recommended exercises 1, 3.
    ...
    time permits. You may use any of theThink carefully which algorithm design techniques discussed in classtechnique is appropriate for every problem (recursion, greedy, DP, reductions).reduction).
    If you give a reduction:
    describe the inputs to the two problems
    (view changes)
    8:19 am
  6. page home edited ... Announcements June 22: Solutions to the midterm exam are posted on courseworks under Files. …
    ...
    Announcements
    June 22: Solutions to the midterm exam are posted on courseworks under Files.
    June 22: Final exam information
    Date: Thursday, June 28
    Time: 1-2:30 (tentative)
    Location: 524 Mudd
    Material: all lectures from 6/7 (Belman-Ford and Floyd-Warshall) up to and including NP-complete problems from 6/26; also, makeup lecture on 6/1 is part of the final.
    True/false questions
    Multiple choice questions
    Past final exam questions:
    Homework 3: problems 1, 4, 5; recommended exercise 3.
    Homework 4: problems 2, 3b, 4, 5; recommended exercises 1, 3.
    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; only give pseudocode if time permits. You may use any of the algorithm design techniques discussed in class (recursion, greedy, DP, reductions).
    If you give a reduction:
    describe the inputs to the two problems
    clearly give the reduction transformation and argue that it takes polynomial time
    prove equivalence of instances
    Final is closed books, no calculators, no cheat sheet

    June 17: Reminder: there will be no class this Tuesday. The instructor's OH are moved to Thursday June 21 4:15-6pm.
    June 16: hw4 {hw4.pdf} is now available. It is due by 10pm on Tuesday June 26 (hard deadline: 10am on Wednesday June 27).
    (view changes)
    8:18 am

More