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.