CPSC 490 - Student Presentations 1

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

Feburary 8th (Wednesday)
Feburary 10th (Friday)
Feburary 15th (Wednesday)
Feburary 17th (Friday)

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.

  2. ★★ Given an undirected graph, find the edges that are part of ALL minimum spanning trees. For full marks, you can present two or more approaches that run in O(E^2 log E) or one approach that runs in O(E log E). Presenter: David Chong

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

  4. ★★ Given a rooted tree, find a O(n) or O(n log n) algorithm to classify every edge as either heavy or light. A heavy edge is one that points to a subtree at least half the size of the subtree at the parent node; a light edge is any edge that is not heavy. In any path in the tree, what is the maximum number of light edges? Justify your answer. Presenter: Alex Gonzalez

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

  6. ★★★ Consider a gambling game with K types of bets of the following type: for the i-th type of bet, you bet one chip, and you win w_i chips (w_i is an integer) with probability p_i, and you lose the chip you wagered with probability 1 - p_i. Given that you start with n chips, compute the maximum probability that you will eventually make a profit using an optimal betting strategy; you stop playing if you run out of chips. Presenter: Bob Yang

  7. ★★★ We learned in class that the KMP algorithm finds exact matches of one string in another, in linear time. How can we find "fuzzy" matches that contain at most k mismatches? Presenter: Michael Wagler

  8. ★★★★ 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. Presenter: Alfred Xing

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

  10. ★★★★ An alternating permutation of size n is a rearrangement of the array [1, 2, ..., n] that alternates between increase and decrease in adjacent elements (e.g. 15243). Give a dynamic programming algorithm to count the number of alternating permutations of size n that runs in polynomial time. Presenter: Daniel Du

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

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

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

  14. ★★★★★ 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. Johnson’s algorithm. Presenter: Kanghee Park

  2. Suurballe’s algorithm. Presenter: Eugene Xie

  3. Any polynomial time algorithm to find k-th shortest path in graph with non-negative weights. Presenter: Peter Siemens

  4. Disjoint set data structure. Presenter: Leo Cho

  5. Any linear time algorithm to find strongly connected components. Presenter: Joseph Hsu

  6. Any algorithm that solves 2-SAT in O(VC) time or better where V is the number of variables and C is the number of clauses. Presenter: Cathy Leung

  7. Tarjan’s bridge and articulation point detection algorithm. Presenter: Edward Choi

  8. Any linear time algorithm to find an euler tour (or report that no tour exists). Presenter: Jack Mandeville

  9. One of these DP optimization techniques: convex hull Presenter: Joey Lee, divide and conquer Presenter: Andrew Kim, Knuth.

  10. Boyer-Moore string matching. Presenter: Jack Li

  11. Applications of hashing and the Rabin-Karp algorithm. Presenter: Derek Zhang

  12. How to implement and when use an LL parser, or recursive descent parser (pick one).

  13. Any dynamic programming parsing algorithm for context-free grammars (e.g. the CYK algorithm). Presenter: Paul Cernek

  14. 2D segment trees.

  15. Link-cut tree. Presenter: Radu Nesiu

  16. Any persistent tree data structure. Presenter: Rohin Patel

  17. Longest common substring of n strings. Presenter: Vastaav Anand

  18. Graph coloring. Presenter: Harlin Brandvold

  19. Fast Fourier Transform. Presenter: David Zheng

  20. Burrows-Wheeler Transform. Presenter: Coulter Beeson