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.