CPSC500 Reading Project
2017 Winter Term 1
The course project is a chance for you to dig deeper on a topic of interest to you,
learn about interesting algorithms or data structures that may fall outside the scope of the class, or to relate the course
material to a problem in your research area. You may want to dig deep into one paper, or
delve into more than one paper on the topic of your choice.
I've included some suggestions below. Some are classical papers in the
field, others quite recent. Don't feel limited by these - if you
have a different paper you'd like to study, run it by me before
commiting to it.
I recommend small groups of size 2 or 3 for the project.
It can be a lot more productive and fun to work
with someone else, particularly if the material is dense.
Send me an emil by Friday, October 13, stating what paper you will read, and who is in your group.
One email per group is sufficient, cc'ing all group members. You are welcome to come and talk to me
beforehand about your ideas.
Once you have chosen a project topic, please stop by to discuss how it's going.
I'll be happy to talk with you as you make progress or get stuck, and
I'm sure that others in the department will be happy to help
also. Make sure to stop by at least once - just ask or email me to
set up a time.
You'll share what you've learned from reading the paper in a class
presentation. Make sure that everyone has a chance to shine in the
presentation, and help each other prepare. The length of a
presentation will depend on the group size, roughly between 15 and 20
In your presentation, motivate your choice of algorithm, give an overview
of the main ideas, and insight to the underlying technigues. Share
ideas for future work. Provide illustrative examples; use the board,
slides, or both.
Use this as a chance to give good presentations! Practice with your
friends. Find simple examples to illustrate the more complicated
concepts. Don't try to squeeze in too much material, but rather try to
get the important ideas across. If you have a draft of your
presentation ready at least 48 hours before your presentation date,
I'll be happy to provide feedback one on one. We'll schedule
presentation times outside of regular class hours, most likely in
early December (in lieu of classes cancelled in September), or during
the last week of class (in which case I'll give make-up lectures at
Your grade will be based primarily on your presentation.
Paper Suggestions (don't feel limited by these):
Some of these were suggested by Chris Thachuk (Caltech) and others by Valerie King (UVic).
Navarro, G. (2012). Constant-time array initialization in little space. Manuscript: University of Chile, Santiago, Chile.
Question: What if you need an array of N words, that you can read and write to in O(1) time, and need every element of the array to have some initial value, for example '0'? Can you allocate and initialize such an array in o(N) time? Sections 1-3 of this paper (1.5 pages) detail the folklore solution to this problem which nicely demonstrates that "every problem in computer science can be solved by another level of indirection" [David Wheeler I think said that]. No need to read the 'succinct' solution in the subsequent sections.
Jacobson, G. (1989, October). Space-efficient static trees and graphs. In Foundations of Computer Science, 1989., 30th Annual Symposium on (pp. 549-554). IEEE.
Jacobson's work, followed by later work of Munro and others, kicked off the field of 'succinct' data structures. Most every succinct representations that can answer queries about combinatorial objects (such as sequences, points on a grid, trees, permutations) relies on 'rank & select' data structures. This seminal paper shows the basic solution for rank & select data structures on binary sequences which already is applicable to a number of applications.
Navarro, G. (2014). Wavelet trees for all. Journal of Discrete Algorithms, 25, 2-20.
Generalizing beyond binary strings to arbitrary alphabets for rank & select can be solved using wavelet trees. Navarro's paper is a very approachable overview. One you are here, you can start answering geometric queries efficiently (dependent on query size, not index size) such as "how many points are contained in this rectangle".
Ferragina, P., & Manzini, G. (2000). Opportunistic data structures with applications. In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on (pp. 390-398). IEEE.
This paper introduces one of the most elegant data structures, the FM-index, which builds upon the Burrows Wheeler Transform for text, rank & select data structures, and demonstrates how compressed text can be efficiently searched.
One of Nick Harvey's papers
See Nick's website. For example, Nick has recently given an algorithmic proof of the Lovasz Local Lemma, and also has done some lovely systems-oriented work on managing storage workloads.
A survey of approximation schemes for NP-hard geometric optimization problems
by Sanjeev Arora.
Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs by Goel, Kapralov and Khanna.
One of Bruce Shepherd's papers, e.g. his celebrated proof of the VPN (Virtual Private Network) conjecture.
See Bruce's website.
One of Valerie King's papers, e.g., on dynamic graph algorithms. See
Papers by other researchers whose resources or papers we'll cover in this class:
For other ideas, see the papers on the Highlights of Algorithms