Introduction

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.