CMPUT 498/501: Advanced Algorithms

Instructor
 		Mohammad R. Salavatipour
Lectures
 		MW 11:00-12:20
Office hours
 		Mondays 1:00-2:00, U-Comm 6-237

Topics and outcome:

This is a new course that will cover topics in Advanced Algorithms in Theoretical Computer Science (TCS),  targeted for senior undergraduate and graduate students interested in TCS.  The tentative list of topics to be covered in this course are listed below. We cover some classic topics and more recent advances with applications in other areas: streaming and sketching algorithms for big data, online and randomized algorithms, and approximation algorithms.


Tentative topics (could change later):

Outcome:

By the end of this course you should have a basic knowledge of some of the basic techniques used in TCS in design and analysis of algorithms.
You should also learn some tools and tricks to tackle problems that might arise in different settings (such as online setting, streaming setting, or interactable/hard to solve optimization problems).

Prerequisites:

CMPUT204 and MATH125 or MATH225. Also CMPUT 304 is strongly recommended. In general strong undergraduate background in theoretical computer science and mathematics would be required. You must also have basic knowledge of graph theory, basic probability, and complexity theory.

Grading Scheme and course policies.

 This is a theory course (no programming involved).

Note: In order to pass the course you need to obtain at least 50% overall AND at least 40% on your final exam.

Read the detailed policies here carefully!



Lectures:
See the list of resources further down for extra references listed for each lecture below.

  • Minimum Spanning Tree, Minimum Arborescence:
    • Lecture 4: Minimum Spanning Tree (MST), Fredman-Tarjan Algorithm
      Here are the       handwritten notes, and here are the notes.
      Also see 1.1-1.3 from (AG) combined notes and Lec 6 by (SA).
    • Lecture 5: MST in linear time, Minimum Arborescence
      Here are the handwritten notes, and here       are the notes.
       Also 1.4-1.5 from (AG) and Lec 7 by (SA); and 4.9 from (KT).

  • Randomized Algrithms:
    • Lecture 6: Introduction, simple deviation bounds, randomized min-cut
       Here are the notes, here are the scribe notes
       Also, lecture 1-3 from (RA).

    • Lecture 7: Chernoff bound, Hypercube routing
      Here are the handwritten notes, here are scribe notes
      Also Lecture 5 from (RA), and Chapter 10.3 and 10.5 by (AG), and 4.1-4.2 from (MR)

    • Lecture 8: Balls and Bins, power of two choices
      Here are the handwritten notes, here are scribe notes
      Also Lecture 7 from (RA), Lec 5 from (SA), GuptaS21 Lec6

    • Lecture 9: Randomized load balancing, Hashing
      Here are the handwritten notes, here are scribe notes
      Also lecture 16 from (RA), Lec 3 from (SA) and, notes 5 from (JE), and these notes.

    • Lecture 10: Random Walks, resistence graph
       Here are the handwritten notes, here are scribe notes
       Also, Lecturse 12 and 13 from (RA), Chapter 6 from (MR), Lec 23 from (SA)

    • Lecture 11: Finger printing, Polynomial identity testing
      Here are the handwritten notes, here are scribe notes.
      Also Lecture 13 from (RA), Lecture 16 from (SA) and Chapter 7 from (MR), and Chapter 8 from (AG)

      •
  • Integer/Linear Programming and Combinatorial Optimization:
    • Lecture 12: Integer/Linear Programming, Duality
      Here are the handwritten notes, here are scribe notes
      Also see Lec 6 and 7 from (CO) and Lec 8 and Lec 9 by (SA).
      See also these notes by Goemans.

    • Lecture 13: Bipartite Matching, Matching polytope
      Here are the handwritten notes,
      Also see Lecture 1-3 from (CO), Lec 11 by (SA), Chapter 7 from (AG)

    • Lecture 14: Weighted Biparite Matching
      Here are the handwritten notes,
      Also see Lectures 2-4 from (CO), Chapter 9 from (AG)

    • Lecture 15: Bipartite matching (vardinality and weighted) via priam dual methods
      Here are the notes,
      Also see Lecture4 from (CO), Lec 11 by (SA), and Chatpter 9.3 from (AG)

  • Approximation Algorithms
    • Lecture 16: Introduction, Set cover/Max coverage, Set cover rounding
      Here are the notes,
      Also see Lectures 1-3 from (AP), Chapter 24.3-24.4 from (AG), and 1.2, 1.6, 1.7 from (WS)

    • Lecture 17: Approximation Schemes: knapsack, Bin Packing
      Here are the notes,
      Also see Lecture 4,5 from (AP), Chapter 24.5-24-6 from (AG), and 3.1-3.3 from (WS)

    • Lecture 18: Max-SAT
      Here are the notes,
      Also see Lecture 6 from (AP), and 5.1-5.6 from (WS)

    • Lecture 19: Semidefinite Programming, Max-Cut
      Here are the notes,
      Also see Lecture 21,22 from (AP), and 25.1-25.4 from (AG), and 6.1-6.2 from (WS)


  • Streaming and Sketching
    • Lecture 20: Streaming Algorithms, Probabilistic counting
      Here are the notes,
      Also see

    • Lecture 21: Frequencey moments
      Here are the notes,
      Also see

  • Online Algorithms, Learning From Experts
    • Lecture 22: Online algorithms, Paging
      Here are the notes,
      Also see

    • Lecture 23: Secretary Problem, Prophet inequality
      Here are the notes,
      Also see

    • Lecture 24: Learning from experts, Multiplicative weight update,
      Here are the notes,
      Also see

Assignments:

Assignments will be posted on Canvas and submitted there as well.

posted
 Due date
Assignment 1
 Sept 17
 Oct 1
Assignment 2
 Oct 1
 Oct 15
Assignment 3
 Oct 22
 Nov 5
Assignment 4
 Nov 5
 Nov 19
Assignment 5
 Nov 26
 Dec 10




Templates


 Here is a Latex Template file for preparing assignments and/or lecture notes (here is how it looks when compiled).
Here is the style file you may need to compile it.

You can use Overleaf, an excellent online Latex editor/compiler to write your Latex documents and compile it.
It also has many templates with the source to learn various tricks in using Latex.

Resources:


There is no textbook for this course. However, we will use parts of several books and/or lecture notes from other courses offered by the instructor or
similar course offerings in other universities. We will provide lecture (whiteboard) notes as well as links to relevant readings.
The following is a list of most commonly referred to references:


Here are links to offerings of similar courses by other colleagues: