## 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).

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

- simple text search (Algorithm 9.1.1)
- Rabin Karp search (Algorithm 9.2.5)
- Monte-Carlo Rabin Karp search (Algorithm 9.2.8)

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:

- 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.
- Monte-Carlo Rabin Karp search virtually never gives false positives,
in particular for very long texts (that is, if n is large)
- 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.