# Algorithms and Complexity (Summer 2020)

## Course Description

Introduces paradigms for designing algorithms and fundamental limitations to what algorithms can do. Covers basic algorithm design paradigms of greedy algorithms, divide and conquer algorithms and dynamic programming, as well as a selection of advanced algorithmic topics, such as randomized algorithms, algorithms for distributed systems and basic algorithms for machine learning. Topics related to limitations of algorithms include NP-completeness and undecidability. Coverage includes analyzing algorithms via proofs and programming assignments to implement algorithms.

## General Information

Course Piazza: https://piazza.com/buffalo/summer2020/cse331

Xiangyu Guo

#### Time:

Video lectures will be posted in UBox and UBLearns
Mon-Wed-Fri
9:00 - 9:50 am

#### Location:

The course will be given online

#### Office Hour:

Friday
10:00am - 11:00am

#### Prerequisite

We expect you to have certain levels of mathematical maturity: You should have basic understanding of calculus (e.g., limit, differentiation, integration) and linear algebra (e.g., matrix, vector space, linear transformation); You should be comfortable to read and write mathematical proofs, understanding common proof strategies (e.g., proof by induction, contradication).

We also expect you to have some experience of programming: know what is a computer program, and be able to read and write code. It's best if you have taken CSE250 (data structure) or similar courses before, but this is not a requirement.

There are 4-5 theory homeworks, 1 programming homework, 1 midterm, and 1 final exam. Your final grade will be computed as follows: Theory HW x 40% + Programming HW x 10% + Midterm x 20% + Final x 30%.

## References

### Textbooks

The main textbook we'll use is [KT]; Besides that, [DPV] and [Eric] are usefu supplementaries. [Fleck] and [LLM] are good references for basic concepts.

• [KT] Algorithm Design, by Jon Kleinberg and Eva Tardos
• [DPV] Algorithms , by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
• [Eric] Algorithms , by Jeff Erickson
• [Fleck] Building Blocks for Theoretical Computer Science, by Margaret M. Fleck
• [LLM] Mathematics for Computer Science, by Eric Lehman, F. T. Leighton, Albert R. Meyer

• ### Other References

Some useful references are lecture notes from previous years and similar courses taught in other universities:

• UB CSE431/531 Algorithm Analysis and Design (2020)
• UC Berkeley CS170: Efficient Algorithms and Intractable Problems (2019)
• UIUC CS473: Algorithms (2020)
• Stanford CS161: Design and Analysis of Algorithms (2020)
• Harvard CS121: Introduction to TCS (2019)
• ## News

[May 25, Mon] Course website online.
[Jun 08, Tue] Homework 1 posted. Due in one week later at 11:59 am, Mon, Jun 15.
[Jun 22, Mon] The Midterm is postponed to Fri, Jul 03.
[Jun 24, Wed] Homework 2 posted. Due in one week later at 11:59 pm, Wed, Jul 01.
[Jun 26, Fri] Programming homework posted. Due in one month later at 11:59 pm, Fri, Jul 31.
[Jul 08, Wed] Homework 3 posted. Due in one week later at 11:59 pm, Wed, Jul 15.
[Jul 20, Mon] Homework 4 posted. Due in one week later at 11:59 pm, Mon, Jul 27.
[Jul 27, Mon] The Final Exam is scheduled to Aug 02 - Aug 04.

## Assignments

[Jun 08, Tue][Homework 1] Due: 11:59 am, Mon, Jun 15
[Jun 24, Wed][Homework 2] Due: 11:59 pm, Wed, Jul 01
[Jun 26, Fri][Programming homework] Due: 11:59 pm, Fri, Jul 31
[Jul 08, Wed][Homework 3] Due: 11:59 pm, Wed, Jul 15
[Jul 20, Mon][Homework 4] Due: 11:59 pm, Mon, Jul 27

## Tentative Schedule

[May 26, Tue][slides][handout] Introduction (1): Syllabus
[May 27, Wed][slides][handout] Introduction (2): Asymptotics ([KT] 2.2)
[May 29, Fri][slides][handout] Introduction (3): Example: Fibonacci
[Jun 01, Mon][slides][handout] Graph basics (1): Representation ([KT] 3.1)
[Jun 03, Wed][slides][handout] Graph basics (2): Connectivity ([KT] 3.2)
[Jun 05, Fri][slides][handout] Graph basics (3): Traversal: BFS and DFS ([KT] 3.4)
[Jun 08, Mon][slides][handout] Recitation 1 and release Homework 1: asymptotic notation and graph traversal
[Jun 10, Wed][slides][handout] Greedy alg (1): Interval scheduling: problem def and alg ([KT] 4.1)
[Jun 12, Fri][slides][handout] Greedy alg (2): Analysis of the alg for interval scheduling ([KT] 4.1)
[Jun 15, Mon][slides][handout] Greedy alg (3): Shortest path: Dijkstra's alg ([KT] 4.4)
[Jun 17, Wed][slides][handout] Greedy alg (4): Analysis of Dijkstra's alg ([KT] 4.4)
[Jun 19, Fri][slides][handout] Greedy alg (5): MST: Prim's alg ([KT] 4.5)
[Jun 22, Mon][slides][handout] Greedy alg (6): Analysis of Prim's alg ([KT] 4.5)
[Jun 24, Wed][slides][handout] Recitation 2 and release Homework 2: Greedy alg and graph alg
[Jun 26, Fri][slides][handout] Divide-and-Conquer (1): Merge sort ([KT] 5.1)
[Jun 29, Mon][slides][handout] Divide-and-Conquer (2): Analysis of merge sort. Counting inversions ([KT] 5.3)
[Jul 01, Wed][slides][handout] Divide-and-Conquer (3): Solving recurrence relation: Master Thm ([KT] 5.2)
[Jul 03, Fri] Midterm: Fri Jul 03 - Mon Jul 06
[Jul 06, Mon][slides][handout] Divide-and-Conquer (4): Polynomial multiplication and other examples ([KT] 5.5)
[Jul 08, Wed][slides][handout] Recitation 3 and release Homework 3: Divide and Conquer
[Jul 10, Fri][slides][handout] Dynamic Programming (1): Weighted Interval Scheduling ([KT] 6.1)
[Jul 13, Mon][slides][handout] Dynamic Programming (2): LIS and LCS problem
[Jul 15, Wed][slides][handout] Dynamic Programming (3): Subset sum and knapsack ([KT] 6.4)
[Jul 17, Fri][slides][handout] Dynamic Programming (4): Shortest-path and optimum BST
[Jul 20, Mon][slides][handout] Recitation 4 and release Homework 4: Dynamic Programming
[Jul 22, Wed][slides][handout] NP-completeness (1): P and NP
[Jul 24, Fri][slides][handout] NP-completeness (2): Reduction
[Jul 27, Mon][slides][handout] NP-completeness (3): 3SAT and NP-Completeness
[Jul 29, Wed][slides][handout] NP-completeness (4): Independent-Set is NPC
[Jul 31, Fri][slides][handout] Recitation 5: NP-completeness
[Aug 02, Sun] Final exam: Sun Aug 02 - Tue Aug 04