CPSC 420 Advanced Algorithm Design and Analysis Spring 2018

Hu Fu hufu@cs.ubc.ca ICCS X539, 827-4222, www.fuhuthu.com Office hours: Friday 3-4pm, ICCS X539.

Teaching Assistants:
Ben Chugg ben.chugg@alumni.ubc.ca Office hours: Thursday 2:30-3:30pm, DLC Table 6.
Sikander Randhawa sikander_94@alumni.ubc.ca Office hours: Tuesday 2-3pm, DLC Table 3.
Artem Tsikiridis artemt@cs.ubc.ca Office hours: Wednesday 3-4pm, DLC Table 2.
Sharon Yang L5w8@ugrad.cs.ubc.ca Office hours: Monday 10-11am. DLC Table 2.

We will be using Piazza for class discussions. This allows you to get help from other students, the TAs, and me much faster than if you just emailed questions to the teaching staff. Find our class page at: piazza.com/ubc.ca/winterterm22017/cpsc420/home

MWF 14:00 - 15:00 DMP 310

The first part of the course focuses on developing a few general conceptual and mathematical frameworks that help design algorithms. We will see some of their applications and occasionally delve into interesting specific algorithms (that are better than generic algorithms) for these applications. In the second part of the course we will look at algorithms and data structures that cater to the needs in some modern applications.

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.

There are several good references for the material covered in this course.

Course Work
The following is the approximate contribution of different aspects of the course to your grade. I might change it slightly: Problem sets/written assignments (40%) + Two Midterms (30%) + Final (30%).

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 Sets:
Problem set 0 due 12 Jan 2017 at 9pm.

Supplementary Reading

[Spring Break] Feb 19, 21, 23.