Note: memoization means storing previously done computations to save in future computations
Write a recursive program to compute Fibonacci numbers. Notice that it is trash. (What’s it’s running time?) Imrpove it a bit by using memoization.
Write a program that does binary search. That is, given some sorted data, it can answer the query “what is the index of X / does X occur in the array” in time logarithmic in the array length.
The powerset of a set is the set of all subsets of that set. More plainly, \[\mathcal{P}(A) = \{ B: B \subset A \}.\] Write a recursive function and a non-recursie function to compute the powerset of a given set.
The “edit distance” between 2 strings is the minimum number of deletions, insertions, and substitutions that it takes to transform one string into the other. Write a program that computes the minimum edit distance between two input strings.
Download a list of the most common english words from the internet, and write a python script that replaces every word in some input text with a random word that is of minimal edit distance to it, but not of zero edit distance.
There are 7 cents coins, 6 cents coins, and 8 cents coins. What is the fewest number of coins that you can use to get 692 coins?
Write a program that determines the minimum distance between 2 vertices in a weighted graph.