CPSC 490 - Student Presentations

For your student presentation, you must either

The presentation should be 7-9 minutes long, and will be worth 15% of your grade (everyone will do two presentations this term).

Presentations should describe the problem, present an algorithm, and prove/justify its correctness and running time.

As soon as you choose a problem, post a private message on Piazza. Problems go by first come first serve :)

Also, feel free to ask me (Kuba) for hints/resources to solve any of the problems below.

Presentation Dates

Friday, April 1st
Monday, April 4th
Wednesday, April 6th
Friday, April 8th

Problem List (more to be added)

  1. Let T be a rooted tree with n nodes, and an integer value assigned to each node. Now give a data structure that answers the following queries: (1) Add x to node v. (2) Given a node v, report the sum of node values in v’s subtree. Both operations must be done in O(sqrt(n)) time or better. Natalia Cornwall

  2. Let P be a convex polygon (with n points), give an algorithm to compute the largest quadrilateral using points of P in O(n^2 lg n) time or better (it can be done in O(n) time).

  3. Given a semicircle of radius r centered at the origin, and a simple polygon of n vertices (a polygon that does not self-intersect) that lies completely above y = 0, determine the area of intersection between the polygon and the semicircle. Any algorithm running O(n^3) or better is fine, but be detailed with your answer (i.e. work out the math!). It can be done in O(n) time. Presenter: Michael Hiland

  4. Let P be a point set in R^2, connect all pairs of points with a line segment. Now I give you a pair of real numbers s, and t with s <= t. Give an algorithm report how many line segments have slopes in [s, t] in O(n log n) time or better.

  5. Given a set of points P in R^2, and a radius r, find the maximum number of points in P a circle of radius r can cover. Your algorithm must run in O(n^2 log n) time or better, where n is the number of points in P. It can be done in O(n^2) time.

  6. Given a directed graph, what is the minimum number of edges we need to add, so that every node is in the same strongly connected component? Give an algorithm to compute this in O(VE) time or better (an O(V+E) solution is possible). Presenter: Michael Haaf

  7. Let T be an undirected tree. Give a O(nlogn) or O(n) time algorithm to find a node v such that if v was removed from the tree (creating a forest of trees from v’s children), the remaining subtrees would all have fewer than half the number of vertices from the original tree.

Algorithms

  1. Johnson’s algorithm. Presenter: Alison Clark

  2. Suurballe’s algorithm. Presenter: Lynsey Haynes

  3. Any algorithm for constructing a rectilinear convex hull with minimum area. Presenter: Michelle Findlay-Olynyk

  4. The Hopcroft-Karp matching algorithm. Presenter: Shikib Mehri

  5. Create a data structure S that supports the following operations: (1) Insertion of a interval [s, t] into S (where s and t are real numbers). (2) Given a real number x, report the number of intervals in S that x intersects. Both operations must be done in O(sqrt(n)) time or better.

  6. Any linear time algorithm to find an euler tour (or report that no tour exists). Presenter: Albert Xing

  7. Tarjan’s bridge and articulation vertex detection algorithm. Presenter: Bruno Vacherot

  8. Loop's scheme for mesh subdivision Presenter: Liam Hewitt

  9. Let P be a triangular mesh where each node has degree less than or equal to C (some constant). Given a point q, we want to quickly locate which triangle of the mesh q is in. Describe a data structure which can be built in O(n^2) time or better and handles queries in O(sqrt(n)) time or better (where n is the number of vertices in the mesh).

  10. Computing a 3D Convex Hull Presenter: Kevin Shi

  11. Edmond’s blossom algorithm Presenter: Navpreet Brar

Presentation Dates

Feburary 8th
Feburary 10th
Feburary 12th
Feburary 22nd

Problem List (more to be added)

  1. Given two nodes a and b in a tree, determine the lowest common ancestor between node a and node b. If V is the number of nodes in the tree, and Q is the number of queries (number of a and b pairs), your solution must run in O(V^(3/2) + QV^(1/2)) time or less (an O(V+Q) solution is possible). Presenter: Michael Hiland

  2. Given a directed weighted graph and two nodes s and e, what is the second shortest path from s to e? The algorithm must run in polynomial time in the number of nodes and edges (preferably O((mV)^2)) or better). Presenter: Natalia Cornwall

  3. In class we learned an algorithm for the longest common subsequence problem that ran in O(n^2) time (where both sequences have length n). Suppose you know that the longest common subsequence is upper bounded by n^(1/2). Give an O(n^(3/2)) time algorithm to compute the length of the longest common subsequence. Presenter: Shikib Mehri

  4. Let A[0..n-1] be an array of numbers. You are a frog that starts on index 0 of the array. In one jump, you can jump from your current square i to any square in the interval [i+1, i+d]. As you jump, you collect the numbers located at the squares to jump to. What is the largest sum you can get, over all paths from index 0 to index n-1? Compute this in O(n log n) time or better. O(n) is possible.

Algorithms

  1. Solving Longest Increasing Subsequence with Patience Sorting. Presenter: Alison Clark

  2. Generalization of Segment Trees and BITs to 2D (and above) for sum queries. Presenter: Michelle Findlay-Olynyk

  3. Lazy propagation (range updates) in Segment Trees. Presenter: Daniel Du

  4. Any dynamic programming parsing algorithm for context-free grammars (e.g. the CYK algorithm). Presenter: Michael Haaf

  5. Applications of hashing and the Rabin-Karp algorithm. Presenter: Lynsey Haynes

  6. The KMP string searching algorithm. Presenter: Navpreet Singh Brar

  7. Any algorithm solving 2-SAT in time O(VC) or better (where V is the number of variables and C is the number of clauses). Presenter: Vincent Hui

  8. Four Russians Optimization to Edit Distance Presenter: Kevin Shi

  9. Matrix multiplication in better than O(n^3) time. Presenter: Liam Hewitt

  10. Knuth's word wrapping algorithm Presenter: Albert Xing

  11. In-place Stable Sorting Algorithm Presenter: Bruno Vacherot

  12. Optimal Binary Search Trees Presenter: Raunak Kumar