CPSC 490 - Student Presentations 2

For your student presentation, you must either

The presentation should be 8-10 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 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 29th (Wednesday)
March 31st (Friday)
April 3rd (Monday)
April 5th (Wednesday)

Problem List (more to be added)

  1. ★★ Let G be an undirected graph. Give two algorithms 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: Edward Choi

  2. ★★ Given an undirected tree, in O(n) or O(n log n) find a vertex such that when removed, it disconnects the tree into multiple pieces each with fewer than half of the vertices of the original tree. If you do this recursively into those pieces, what is the maximum depth of recursion and total run time? Justify your answer. Presenter: David Chong

  3. ★★ Give an algorithm to compute the intersection of two convex hulls in O(n log n) or better. Presenter: Peter Siemens

  4. ★★★ Give an algorithm to find the minimum distance between two polygons in O(n log n) or better. Presenter: Bob Yang

  5. ★★★ Find maximum perimeter triangle out of a point set in O(n^2) or better. Presenter: Alex Gonzalez

  6. ★★★ 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. Presenter: Michael Wagler

  7. ★★★ 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.

  8. ★★★★ 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.

  9. ★★★★ Find the number of permutations of size n such that the longest increasing subsequence does not have length 3, in polynomial time.

  10. ★★★★ We learned in class that a bit-indexed tree is an efficient data structure that supports range update + point query, or point update + range query for the sum operation. Modify it to support both range update and range query in O(log n).

  11. ★★★★★ 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.

  12. ★★★★★ 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

  1. 2D segment tree or 2D binary-indexed tree. Presenter: Andrew Kim

  2. K-d tree and nearest neighbor queries. Presenter: Joey Lee

  3. Quad tree / oct tree / binary space partition tree and their applications. Presenter: Rohin Patel

  4. Randomized incremental convex hull construction Presenter: Radu Nesiu

  5. Orthogonal convex hull

  6. Delaunay triangulation Presenter: Jack Li

  7. Voronoi diagram Presenter: Vaastav Anand

  8. Line arrangement Presenter: Cathy Leung

  9. Topological line sweep

  10. Triangulating a non-convex polygon

  11. O(n^2) construction of visibility graph

  12. Arbitrary polygon intersection and union

  13. Arbitrary dimensional minimum enclosing ball

  14. Any convex optimization algorithm with applications Presenter: Paul Cernek

  15. Chinese Remainder theorem: solving simultaneous equations of x = a_i mod n_i Presenter: Jack Mandeville

  16. Primality testing Presenter: Alfred Xing

  17. Karatsuba multiplication Presenter: Joseph Hsu

  18. Strassen multiplication Presenter: Derek Zhang

  19. Numerical integration

  20. Dinic's algorithm for maximum flow Presenter: Kanghee Park

  21. Push-relabel algorithm for maximum flow Presenter: Leo Cho

  22. Gomory-Hu Tree and all-pairs min cut Presenter: David Zheng

  23. Hungarian algorithm for maximum weight bipartite matching Presenter: Eugene Xie

  24. Blossoms algorithm for general matching Presenter: Daniel Du

  25. Topological Skeleton Presenter: Harlin Brandvold

  26. Page Rank Presenter: Coulter Beeson