CPSC 490 - Student Presentations

For your student presentation, you must either

choose one problem below and present its solution
choose an algorithm/problem we have not talked about in class and introduce it

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, email me (at paul.liu.ubc@gmail.com) or PM me on Piazza. Problems go by first come first serve :)

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

Presentation Dates

Monday, March 30th.
Wednesday, April 1st.
Wednesday, April 8th.
Friday, April 10th.

Update: The schedule for the first set of presentations is out! See here
Wednesday, Feburary 4th.
Friday, Feburary 6th.
Wednesday, Feburary 11th.
Friday, Feburary 13th.

Problem List (more to be added)

★★ Let G be an undirected graph. Give an algorithm to colour each node of G black or white, so that every white node has at least half its neighbours coloured black, and every black node has at least half its neighbours coloured white. The algorithm must run in O(V+E) time. Presenter: Farzad Fallahi
★★★★ 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. Presenter: Angus Lim
★★★ 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. Presenter: John He
★★★ 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: Mark Leyfman
★★★ Let P and Q be two nested convex polygons with n and m vertices respectively. Let T be a convex polygon nested between P and Q with the minimum number of vertices possible. Give an O((n+m)^2) algorithm or better to find a convex polygon nested between P and Q with at most c|T| vertices (where |T| is the number of vertices in T). It can be done in O(n+m) time with a very simple (but possibly hard to prove) algorithm.
★★ 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). Presenter: Kuba Kapierz
★★ 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. Presenter: Jared Kim
★★★★★ Let P be a convex polygon with n vertices. Give a data structure to compute two types of queries: (1) Given a point q, reassign P to be the convex hull of the old P and q. (2) Given a line l, determine if l intersects P. Your data structure must cost O(sqrt(q)log(n+q)) per query or better (averaged over the q queries). It can be done in O(log^2(n+q)).
★★ 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. Presenter: Akshat Divekar

Suggested algorithms (more to be added)

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: Bo Gong
Edmond’s Blossom Algorithm. Presenter: Kristina Nelson
Lazy propagation (range updates) in Segment Trees. Presenter: Jason Chiu
Computing a 3D Convex Hull (Any algorithm running in O(n^3) or better. A simpler algorithm may be easier to present.) Presenter: Michael Moritsugu
Generalization of Segment Trees and BITs to 2D (and above) for sum queries. Presenter: Carolyn Shen
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).
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. Presenter: Jeremy Goh
The Hopcroft-Karp matching algorithm. Presenter: Kyle Malong
Any algorithm for constructing a rectilinear convex hull with minimum area.
Overview of heavy-light decomposition on a tree, and example problem(s) to go with. Presenter: Nathan Chow
Any efficient algorithm to intersect two simple polygons. It should run in O(n^2 log n) time or better, where n is the number of vertices in both polygons combined.

Topics from previous presentations

Problem List

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: Bo Gong
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: Farzad Fallahi
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: Kristina Nelson
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. Presenter: Jason Chiu
Let G be an undirected graph. Two paths A and B in G are called edge-disjoint if A and B have no edges in common. Pair up vertices of odd degree arbitrarily so that each vertex is in one pair. Give a polynomial time algorithm to find paths between each pair of vertices so that each path is edge disjoint with all the other paths. Presenter: Carolyn Shen
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: Kuba Karpierz
Facebook Hacker cup round 1 question 3 (question statement too long). Presenter: Mark Leyfman

Algorithms

Johnson’s algorithm. Presenter: Nathan Chow
Suurballe’s algorithm. Presenter: Michael Moritsugu
Solving Longest Increasing Subsequence with Patience Sorting. Presenter: Akshat Divekar
Tarjan’s bridge and articulation vertex detection algorithm. Presenter: Kyle Malong
Any linear time algorithm to find an euler tour (or report that no tour exists). Presenter: Angus Lim
Any dynamic programming parsing algorithm for context-free grammars (e.g. the CYK algorithm). Presenter: John He
Applications of hashing and the Rabin-Karp algorithm. Presenter: Jeremy Goh
The KMP string searching algorithm. Presenter: Jared Kim