CPSC 320: Analysis of Algorithms Spring 2026

Research project

Project proposal: due Monday, March 30
Oral presentation: due April 20, 22 or 27

During the second half of the term, you are expected to pair up with another student and study on your own an original research paper on an advanced topic in algorithms not covered in class. Your project topic must be selected from the list given below. During the last two weeks of the term, you and your partner are expected to give a 15-minute oral presentation on your project.

Project proposal. You are first expected to choose your partner and write up together a one-page summary of what you plan to study for your project. You should first select a project topic that suits your interest from the list given below. The goal of this project should be to study and present the original research paper given below in your chosen area. If your paper is long and/or deep, then it may not be appropriate to cover the entire paper. In such a case, it may be appropriate to study and present only part of the paper. Be sure to choose a specific topic with specific algorithms (for example, a project on greedy algorithms is not specific enough, but a project on Dijkstra's algorithm is). Your proposal should at least state (i) what your topic is in, (ii) what specific algorithms you will be learning from the given source.

Oral presentation. On April 20, 22 or 27, you and your partner are expected to give a 15-minute oral presentation on your project, using slides. The date of your presentation will be assigned by the instructor after you submit your proposal. An ideal presentation first invites the audience with an informal overview, sets up formalization, gives precise descriptions of algorithms and then ends with discussions on correctness and runtime.

Final deliverable. For this project, there is no paper to submit. You are expected to just submit copies of your slides on the day of your presentation.

Project topics. Choose one topic from the following list. No two pairs may select the same topic. Topics will be assigned on the basis of first come, first served. Before you start working on your proposal, you should reserve which topic you would like to work on. Topics that are taken will be crossed off below. Some of the articles (such as those of Springer) are proprietary; to access them, you must be on the Trinity network.

1. Greedy algorithms. This paper formalizes notions of greedy and greedy-type algorithms:
A. Borodin, M. N. Nielsen and C. Rackoff, (Incremental) priority algorithms, Algorithmica 37 (2003), 295–326.
2. Finding shortest paths. This paper evaluates a number of shortest paths algorithms:
B. V. Cherkassky, A. V. Goldberg and T. Radzik, Shortest paths algorithms: theory and experimental evaluation, Math. Program. 73 (1996), 129–174.
3. The latest breakthrough in finding shortest paths. This paper proposes the fastest algorithm to date, combining Dijkstra's algorithm and the Bellman–Ford algorithm:
R. Duan, J. Mao, X. Mao, X. Shu and L. Yin, Breaking the sorting barrier for directed single-source shortest paths, STOC ’25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, Praha, June 23–27, 2025, ACM, New York, 2025, pp. 36–44.
4. The Ford–Fulkerson algorithm. A classic algorithm to solve the maximum-flow problem. This is discussed in §7.1. Originally published in:
L. R. Ford, Jr., and D. R. Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956), 399–404.
5. The preflow-push maximum-flow algorithm. Another well-known approach to the maximum flow problem. This is discussed in §7.4. Originally published in:
A. V. Goldberg, É. Tardos and R. E. Tarjan, Network flow algorithms, Path, Flows, and VLSI-Layout (B. Korte, L. Lovász, H. J. Prömel and A. Schrijver, eds.), Algorithms and Combin., vol. 9, Springer, New York, 1990, pp. 101–164.
6. Baseball elimination. A maximal-flow technique to determine which team is eliminated in a divisional race in baseball. This is discussed in §7.12. Originally published in:
K. D. Wayne, A new property and a faster algorithm for baseball elimination, SIAM J. Discrete Math. 14 (2001), 223–229.
7. Coloring circular arcs. While NP-complete in general, it is in polynomial time for a fixed number of colors. This is discussed in §10.3. Originally published in:
M. R. Garey, D. S. Johnson, G. L. Miller and C. H. Papadimitriou, The complexity of coloring circular arcs and chords, SIAM J. Algebraic Discrete Methods 1 (1980), 216–227.
8. Greedy algorithms and bounds on the optimum. A greedy approach to the load balancing problem. This is discussed in §11.1. Originally published in:
R. L. Graham, Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math. 17 (1969), 416–429.
9. The center selection problem. Another problem to allocate work across multiple servers. This is discussed in §11.2. Originally published in:
D. S. Hochbaum and D. B. Shmoys, A best possible heuristic for the k-center problem, Math. Oper. Res. 10 (1985), 180–184.
10. Linear programming and load balancing. An approximation algorithm for the generalized load balancing problem. This is discussed in §11.7. Originally published in:
J. K. Lenstra, D. B. Shmoys and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Math. Program. 46 (1990), 259–271.
11. Finding Nash equilibria. A fundamental problem in game theory. This is discussed in §12.7. For more in-depth study, see:
C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou, The complexity of computing a Nash equilibrium, SIAM J. Comput. 39 (2009), 195–259.
12. A randomized approach to the minimum cut problem. A randomized method that is simpler than all previous methods. This is discussed in §13.2. Originally published in:
D. R. Karger and C. Stein, A new approach to the minimum cut problem, J. ACM 43 (1996), 601–640.
13. Randomized caching. A randomized cache maintenance algorithm. This is discussed in §13.8. Originally published in:
A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator and N. E. Young, Competitive paging algorithms, J. Algorithms 12 (1991), 685–699.
14. Machine learning. A seminal paper in computational learning theory to propose a formal notion of efficient learning in the form of the probably approximately correct (PAC) learning model:
L. G. Valiant, A theory of the learnable, Comm. ACM 27 (1984), 1134–1142.
15. Link analysis and web searching. This paper is about what is now called the HITS (Hyperlink-Induced Topic Search) algorithm:
J. M. Kleinberg, Authoritative sources in a hyperlinked environment, J. ACM 46 (1999), 604–632.
16. Quantum computation. A seminal paper in quantum computation:
D. R. Simon, On the power of quantum computation, SIAM J. Comput. 26 (1997), 1474–1483.

* CPSC 320 home page
Valid HTML 4.01!