# 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 solutionalmost 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 questionincluding suitable

*computational model*know where to

*seek previous solutions*be able to

*read and understand past work*know how to

*adapt it*to problem variantssome ability to

*extend it*to accomplish new thingssome 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.