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.

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.

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

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

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

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

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).