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.
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.
[Spring Break] Feb 19, 21, 23.