Welcome.
- why study this course:
- theoretical elegance, insight on hardness of problems
- ability to research in any area of algorithms
- ability to recognize problems that arise, apply past techniques, and develop new ones
- broad sense of “what is algorithms”. Not deep---other courses follow.
- I no longer research algorithms, but the algorithmic perspective often gives new insights on applied problems.
- Varieties of problems and algorithms
- numerical analysis/linear algebra
- number theoretic. drives cryptography
- combinatorial---focus of this course.
- things involving permutations (sorting), graphs (shortest paths) and subsets (linear programming).
- many optimization problems---find the best possible solution
- almost always, finitely many solutions. brute force always works. we want something better.
- combinatorial optimzation: major subarea, but not all we cover (vempala course)
- aspects of all will arise in others
- some problems/algorithms draw from multiple areas---eg comp. geom.
- Variety of models---sequential, parallel, online, streaming, etc.
- Goals:
- recognize an algorithmic opportunity (theory or practice)
- know how to formulate an algorithmic question
- including suitable computational model
- know where to seek previous solutions
- be able to read and understand past work
- know how to adapt it to problem variants
- some ability to extend it to accomplish new things
- some ability to invent new algorithms
- course summary sheet
- Requirements
- psets: wednesdays
- project
- grading
- collaboration:
- have to fully reconstruct the answer yourself.
- Cheating is often detected and consequences are severe for both receiver and giver
- ethics homework problem on pset 1
- if I have to speak to you, we'll have your pset 1 answers.
- Experiments
- live zoom lecture
- pre-recorded lecture with realtime Q\&A
- pre-recorded lecture with Q\&A after
- flipped classroom learning exercises
- swap collaborators requirements
- I will teach fast. Slow me down with questions.
- Course is time consuming and hard.
- Collaboration is essential but should not be overused.
- A strong background in undergraduate algorithms is too
- Cheating policy on psets. downgrade if caught.