Homework 8 (due 6/2)
CSC 321

We talked about a dynamic program for coin changing. It differs from the two-dimensional solution in the book (Section 8.2), see Advanced Algorithms Lecture Notes, for example. As a matter of fact, we made the point that the coin changing algorithm is yet another case of the shortest path algorithm for dags: let V be the set {1, 2, ..., n}, and let there be an edge (i,j) if j-i is a valid denomination in our currency. Each edge has unit weight. Then the length of a shortest path from 1 to i for any i <= n is the smallest number of coins needed to make change for i cents.

We also talked about various text searching algorithm, including naive text-searching (9.1), and Rabin-Karp Search (9.2). I also went into the intuition behind Knuth-Morris-Pratt (9.3), and mentioned Boyer-Moore-Horspool (9.4) and regular expression matching (9.6). We've started surveying some NP-complete problems (Section 10.2).

: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns. You do not need to include the code (or any executables).

1. (Reading Assignment) Read Sections 9.1, 9.2, and Advanced Algorithms Lecture Notes on the coin changing algorithm.

2. (Rabin-Karp Search, 30pt) Implement the following three text-searching algorithms:

You can follow the book implementations, or implement these directly. Test-run these algorithms with a long text (e.g. innocents.txt, or roughing.txt), and text patterns p of various lengths (chosen as random subsequences of the long text, so that they will always match the text). Gather, display and analyze data on your algorithm to test the following claims:

  1. While simple text search takes worst-case time O(mn), it's closer to O(n) in practice (that is for real texts and real patterns, not artificially constructed ones), in particular as m gets larger.
  2. Monte-Carlo Rabin Karp search virtually never gives false positives, in particular for very long texts (that is, if n is large)
  3. Rabin-Karp search is not much slower than Monte-Carlo Rabin Karp search.

where m = |p| and n = |t|.

For each of these three claims clearly state whether your data supports or refutes the claim, and explain why that is so. Note: you can use the nextprime(m) function in prime.py to find the smallest prime greater than or equal to m. The implementation is primitive, but for small values of m (up to 10**10 or so) it should work just fine.

Marcus Schaefer
Last updated: May 28th, 2015.