Homework 3

Due Thursday, July 8th @ 8pm

1. Assuming a computer can perform roughly 2 billion operations per second, and that each permutation on a 4ⁿ exhaustive search problem takes 10000 operations to compute, how large can n be if you want an answer within an hour, worst case?
2. Give the Huffman encoding for the following letter/frequency pairs: {a: 50, b: 33, c: 12, d: 4, e: 3, f: 2}.
3. The 0, 1 Knapsack problem (described in lecture and in the text) is usually solved with each cell in the dynamic programming table holding the best value possible for the subproblem that cell represents. Give an algorithm for constructing the actual set of items to be taken when given such a table.
4. You've been given an opportunity to engage in a strange form of gambling. Each square of an m X m chess board is given a value between $-100 and $100. You are given a marker to place on any edge space on the board, except the corners. At each round you must advance once space toward the opposite side, but may move diagonally instead of straight if that doesn't take you off the edge of the board. When you move off the other edge of the board (by going a full m moves), you "earn" the sum of the values of every square your marker was on (including the first space.) This game costs some amount, n to play, but thankfully you get to know n and the board layout before accepting. Give an algorithm that determines whether this is a good bet (that is, profitable for you) or not. It should run as fast as possible.