CPSC 490 - Student Presentations 2

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 about 10 minutes long, and will be worth 10% 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.

For this set of presentations, a visual aid (e.g. slides) is required. Make a private post on Piazza with a link to your presentation, so we can put them on the course website.

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

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

Presentation Dates

March 28 (Thursday)
April 2 (Tuesday)
April 4 (Thursday)

Problem List (more to be added)

★★ Give an algorithm to compute the intersection of two convex hulls in O(n log n) or better. (Trevin 202)
★★★ Give an algorithm to find the minimum distance between two polygons in O(n log n) or better. (Juan 202)
★★★ Find maximum perimeter triangle out of a point set in O(n^2) or better. (Ben 202)
★★★ Explain how range query and range update can be done in O(log n) on your favorite balanced binary search tree (e.g. a Splay Tree). For example, adding 3 to value of all nodes with key between 10 and 15 and then querying the minimum value out of all nodes with key between 5 and 12. (Ryan 202)
★★★★ A clique is a complete subgraph. Given an undirected graph, partition the vertices into two sets A and B, such that vertices in A forms a clique, and vertices in B have no edges between them, or determine that this is impossible. What is the lowest time complexity you can get for your solution? Hint: it can be done in polynomial time.
★★★★ Find the number of permutations of size n such that the longest increasing subsequence does not have length 3, in polynomial time.
★★★★ Give a data structure that represents an "array" but supports the following operations in O(log n) time: insert/delete/get element at any index, reversing a subarray.
★★★★★ Support two operations on an array in O(log n) time: for each i in [l, r], change A_i to max(A_i, x); query for the sum of A_i from l to r.
★★★★★ A tandem repeat in a string is two adjacent copies of the same substring (e.g. CATCAT). Give an algorithm to detect the presence of at least one tandem repeat in O(n log^2 n) or better.
★★★★★ We learned in class how to solve the path of maximum bandwidth problem and how to efficiently answer many queries. We will turn to the problem of efficient updates. Given an undirected graph, construct a data structure that supports the following queries in O(log V) time: get bandwidth of the path of maximum bandwidth between two nodes, increase the bandwidth of an edge.

Algorithms

Push-relabel maximum flow algorithm (Michelle 202)
Minimum cost maximum flow (Sam 202)
Gomory-Hu Tree and all-pairs min cut (Leif 201)
2D segment tree (Kenny 201)
Any persistent tree data structure (Justin 201 (AVL)), (Rehim 201 (Segment tree))
Mo's algorithm/other square root tricks (Edwin 202)
K-d tree and nearest neighbor queries (Arian 202)
Splay trees (Elad 201)
Treaps (Cartesian Trees) (Barak 201)
Quad tree / oct tree / binary space partition tree and their applications (Andrew 201)
Randomized incremental convex hull construction
Heavy light decomposition (Victor 201)
Orthogonal convex hull
Delaunay triangulation/Voronoi diagram
Line arrangement
Topological line sweep
Triangulating a non-convex polygon
Construction of visibility graph in subcubic time (better than O(n^3)) (Daniel 202)
Arbitrary polygon intersection and union
Arbitrary dimensional minimum enclosing ball
Any convex optimization algorithm with applications
Chinese Remainder theorem: solving simultaneous equations of x = a_i mod n_i
Primality testing (Karan 201)
Integer factorization
Topological Skeleton (Lauren 201)