91Ó°ÊÓ

Exercises 41 and 42 deal with the problem of scheduling the most talks possible given the start and end times of \(n\) talks. Find the complexity of a brute-force algorithm for scheduling the talks by examining all possible subsets of the talks. [Hint: Use the fact that a set with \(n\) elements has \(2^{n}\) subsets. \(]\)

Write the selection sort algorithm in pseudocode.

Big- \(O,\) big-Theta, and big-Omega notation can be extended to functions in more than one variable. For example, the statement \(f(x, y)\) is \(O(g(x, y))\) means that there exist constants \(C\) , \(k_{1},\) and \(k_{2}\) such that \(|f(x, y)| \leq C|g(x, y)|\) whenever \(x>k_{1}\) and \(y>k_{2} .\) Define the statement \(f(x, y)\) is \(\Theta(g(x, y))\)

List all the steps the naive string matcher uses to find all occurrences of the pattern \(\mathrm{FE}\) in the text COVFEFE.

Show that if there were a coin worth 12 cents, the cashier's algorithm using quarters, 12 -cent coins, dimes, nickels, and pennies would not always produce change using the fewest coins possible.

(Requires calculus) Show that if \(c>b>1,\) then \(b^{n}\) is \(O\left(c^{n}\right),\) but \(c^{n}\) is not \(O\left(b^{n}\right) .\)

a) Prove that the Boyer-Moore majority vote algorithm outputs the majority element of a sequence, if it exists. Brove or disprove that the majority candidate of the Boyer-Moore majority vote algorithm will be a mode of the sequence (that is, its most common element) even when no majority element exists.