- SOFIs
- Helpful to me in teaching this (or other) courses in future
- Access through myGeneseo/KnightWeb
- Final
- Wednesday, Dec. 16, noon
- Comprehensive, but emphasizing material since 2nd hour exam (e.g., complexity classes, NP completeness)
- Designed for 2 hours,you have 3
- Otherwise similar rules and format to hour exams, particularly open-references rule
- Donuts & cider
- (Section 34.5)
- Traveling salesperson
- Verified by being given k and graph G, certificate = proposed list of edges in cycle, check that certificate hits all vertices and has total cost ≤ k
- Hamiltonian cycle reduces to TSP
- Edges somehow have cost 0 or 1?
- Example of reduction via small adaptation of problem
- Common when problems almost identical
- Edges somehow have cost 0 or 1?
- Subset sum
- Given S and t > 0, does subset of S sum to t?
- Verification: certificate is candidate subset S′, add up elements of S′ and see if sum = t, check that S′ subset of S
- Reduce 3-CNF-SAT to subset sum…?
- “build a machine”
- Want to ensure that every variable either true or false, complements assigned consistently
- Also ensure every clause has ≥ 1 true literal
- Problem set
- Textbook exercises 34.5-1, 34.5-2, 34.5-3
- Handout online now
- Presentations
- Public (i.e., math faculty, friends) invited
- Evaluated against rubric
- Rubric scores consistently in “satisfactory” or “excellent” rows suggest waiving Math 348
- Scores consistently in “unsatisfactory” row suggest not waiving Math 348
- Scores consistently in “almost satisfactory” row are a gray area, outcome probably depends on where other scores are
- Extra credit similar to colloquia for write-ups of talks (except your own if you present); one write-up and extra credit for all talks