CPSC 420 requires CPSC 320 as a pre-requisite. We will review some basic algorithms, such as the greedy algorithms for minimum spanning trees, as we develop more general conceptual frameworks. Some other basic techniques and topics that are covered in CPSC 320, however, are not covered in this course. In particular, we will not cover divide-and-conquor, dynamic programming and NP-completeness. Written assignment 0 tests your knowledge in these prerequisites. If you have difficulty understanding the questions or coming up with ideas to start with, you may consider either reviewing materials from CPSC 320 or, if you have not done so, taking CPSC 320 instead.

The types of problems we'll consider may include: greedy algorithms and matroids, matching and matroid intersections, linear program and network flows, approximation algorithms, data structures (hasing, splay trees...), "big data" algorithms (streaming and dimension reduction). We may do a subset or superset of these topics, depending on the pace of the lectures and interest of the class.

• Jon Kleinberg and Eva Tardos. Algorithm Design, Addison-Wesley, 2005.
  The CPSC 320 textbook.
• Dexter Kozen. The Design and Analysis of Algorithms.
  A very well exposited book on more advanced topics in the form of "bite-sized" lecture notes.
• Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani. Algorithms, McGraw-Hill, 2008.
  An excellent, concise text.
• Jeff Erickson's online course notes.
  A glorious, detailed, funny, scholarly online book.

We will have written assignments roughly every week or two. No late solutions will be accepted; conditioning on that, by the end of the semester, the majority of your assignments are typeset with LaTeX, I will drop your lowest assignment mark from the calculation of your course grade.
Here is a LaTeX template for your reference.
You may work together discussing problems and course material, but you should write up and hand in your own solutions. Do not write up your solutions while looking at a reference or working with another person. If you do, you risk copying someone else's work. Plagiarism (the submission of work of another person as your own) is not allowed. For futher clarification see the department's policy on Collaboration and Plagiarism. If you have any questions concerning what constitutes acceptable behaviour, ask me. If you do work with someone or use some outside source, you must acknowledge them in your write-up.

Problem set 1 due 26 Jan 2018 at 9pm.

Problem set 2 due 9 Feb 2018 at 9pm.

Problem set 3 due 23 Feb 2018 at 9pm.

Problem set 4 due 2 March 2018 at 9pm.

Problem set 5 due 16 March 2018 at 9pm.

Problem set 6 due 30 March 2018 at 9pm.

Additional exercises. There is no due time for the last set of exercises.

Review exercises for the session on April 6. There is no due time for this.

Sample final.

• 1/3, 5, 8, 10: Greedy algorithms and matroids
  
  • Chapters 2.1 and 3 of Kozen's book contains a superset of the material we coverered in the lectures.
  • For a somewhat similar treatment, see lecture notes by Bobby Kleinberg.
  • The lecture notes by Michel Goemans are also a very good reference, the style being slightly more abstract and mathematical. We cover mostly Sections 4.1 and 4.2. The rest is excellent material for supplementary reading and exercise.
  • Chapter 4.5 of Kleinberg - Tardos explains the optimality of Kruskal's and Prim's algorithms.
  • Slides from lecture.
• 1/10, 12, 15, 17, 19, 22: Matching
  
  • Chapters 19 and 20 of Kozen's book contain a nice treatment of bipartite unweighted matching.
  • The first section of these lecture notes by Bobby Kleinberg covers roughly the same material in a different light.
  • The slides we used in class (these only contain the skeleton (definitions, lemma/theorem statements etc.) of the lectures, and should not substitute a careful reading of at least one of the supplementary readings.
  • Scanned copy of scribes from class.
• 1/24, 26, 29, 31; 2/2, 7: Max Flow Min Cut
  
  • Chapter 7.1-7.3, 7.5 and 7.12 of Kleinberg and Tardos contains a good subset of the material we cover. The other sections of the chapter are extremely good supplementary reading.
  • The lecture notes by Bobby Kleinberg is a very clear illustration of a superset of the material we cover.
  • Chapters 16-18 of Kozen's book is a concise and accessible treatment of the materials.
  • Slides from lectures.
  • Scribe notes from lectures.
• 2/7, 9, 12, 14, 16, 26, 28; 3/2: NP-completeness
  
  • Chapter 8 of Kleinberg and Tardos has a great coverage of the material.
  • The list of Karp's 21 NP-complete problems.
  • Slides from lectures.
  • Scribe notes from lectures.
• 3/5 - 21: Linear Programming
  
  • These lectures by Michel Goemans is a great illustration of the geometry of linear programs (although somewhat more abstract than our treatment in class). For a more detailed presentation of the Simplex algorithm, see these other notes by Goemans.
  • Chapter 7 of the book by Dasgupta, Papadimitriou and Vazirani contains presents max flow and matching problems as instances of linear programming.
  • For von Neumann's Min-Max Theorem, see these lecture notes by Costis Daskalakis.
  • Slides from lectures. To be updated as we go.
  • Scribe notes from lectures. To be updated as we go.
• 3/21 - 3/28: Advanced Data Structures
  
  • To review the very basics of probability theory, you may read Chapter 1 of these lecture notes by Matousek and Vondrak. (If you have never studied probability thoery, this could be a tough read; but you may still be able to glean some basic ideas.)
  • Chapter 13.3 of Kleinberg and Tardos reviews some basics on random variables and their expectations.
  • Chapter 13.6 of Kleinberg and Tardos has a discussion of universal hash functions. Alternatively, see these lecture notes by David Wagner. These lecture notes by Erik Demaine are more concise (and less detailed) but cover lots more ground --- read them if you'd like to see more.
  • For Bloom filters, see these lecture notes by Dana Randall.
  • Slides from lectures.
  • Scribe notes from lectures.
• 4/4: The secretary problem
  
  • For a derivation of the optimal algorithm, see these lecture notes, Section 9.1 by Ashish Goel and Reza Zadeh.
  • For the optimality proof using a linear program, see these notes, Section 2.1 by Nikhil Bansal. (This approach also contains a derivation of the optimal algorithm.
  • Slides from the lecture.