CPSC 490 - Suggested Topics

Problem List (more to be added)

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

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

  3. ★★★ 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? (Claimed by Manan Mehta)

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

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

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

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

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

  9. ★★★★★ 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. (Claimed by Quintin Moncaster)

  10. ★★★★★ 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 and Data Structures (more to be added)

  1. Johnson’s algorithm.

  2. Suurballe’s algorithm.

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

  4. Applications of hashing and the Rabin-Karp algorithm.

  5. How to implement and when use an LL parser, or recursive descent parser (pick one). (Claimed by Kevin Wong)

  6. Any dynamic programming parsing algorithm for context-free grammars (e.g. the CYK algorithm).

  7. 2D segment trees. (Claimed by Felipe Caiado)

  8. Link-cut tree.

  9. Persistent balanced trees.

  10. Longest common substring of n strings.

  11. Fast Fourier Transform. (Claimed by Alexander Berghholm)

  12. Suffix Arrays/Trees. (Claimed by Steven Shih)

  13. Splay trees.

  14. Heavy light decomposition (HLD).

  15. Persistant segment trees.

  16. Treaps (Cartesian Trees). (Claimed by Clarissa Audrey)

  17. Original map compression techniques used in the first TomTom satnavs.

  18. K-d tree and nearest neighbor queries. (Claimed by John Zou)

  19. Quad tree / oct tree / binary space partition tree and their applications.

  20. Randomized incremental convex hull construction.

  21. Orthogonal convex hull.

  22. Delaunay triangulation.

  23. Voronoi diagram.

  24. Line arrangement.

  25. Topological line sweep. (Claimed by Christopher Hui)

  26. Triangulating a non-convex polygon.

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

  28. Arbitrary polygon intersection and union.

  29. Arbitrary dimensional minimum enclosing ball.

  30. Chinese Remainder theorem: solving simultaneous equations of x = a_i mod n_i. (Claimed by Min-Ji Han)

  31. Primality testing.

  32. Karatsuba multiplication. (Claimed by Dara Nguyen)

  33. Strassen multiplication.

  34. Numerical integration.

  35. Dinic's algorithm for maximum flow.

  36. Hungarian algorithm for maximum weight bipartite matching. (Claimed by Gina Bolognesi)

  37. Blossoms algorithm for general matching.

  38. Topological Skeleton. (Claimed by Brooke Dai)

  39. PID Control / Control Theory. (Claimed by Ben Henaghan)

  40. Gomory-Hu Trees.

  41. Maximum Perimetre Triangle.

  42. A* or ALT. (Claimed by Tommy Zhang)

  43. Dilworth's Theorem.

  44. Linear Programming. (Claimed by Xuhao Chen)

  45. Projective Duality.

  46. Profiling, tutorial, and application to something from class.