Homework Page for Design and Analysis of Algorithms

Homework #1

Due Monday, 9/13

Prove that if the starting position of a 15-puzzle has even parity, then the puzzle can be solved. You may want to do this by giving an algorithm for solving the puzzle.
The puzzle to the right is dodecahedral in shape, with 20 corner pieces and 30 edge pieces altogether. Each of its 12 sides has a different color. A move consists of rotating one of the 12 faces through a 72 degree turn.

Suppose I remove one edge and put it back flipped. Prove that the resulting configuration cannot be solved.
Suppose I swap two edge pieces in an otherwise solved puzzle. Show that the resulting configuration cannot be solved
Suppose I swap a pair of edges and a pair of corners in an otherwise solved puzzle. Can the resulting configuration be solved?

We discussed in class how any sequence of moves which swaps two adjacent edge pieces of the Rubik's Revenge (picture to the right) must have an odd number of ninety-degree middle slice moves and an even number of 90 degree face turns.

Find a sequence on the Internet that does this, and verify our calculation
Show that such a sequence cannot leave all center pieces unmoved, assuming that we could tell where each center piece started and ended

Given a permutation of n elements which consists of c cycles, prove that the least number of swaps necessary to restore it to home position is exactly n - c. Then prove that the following algorithm will achieve this bound: "Select an element x which is not where it belongs and swap it with the element which is currently occupying the position where x belongs. Repeat until the permutation is in home position.

Homework #2

Due Monday, 9/27

Does an algorithm with propertiies A and B necessarily generate all permutations with equal probability?

Some Definitions:

Here are three properties which may or may not be had by algorithms which purport to generate a random permutation on n elements:

Property A: For each element x, and each integer i, 1 <= i <= n, P[x is sent to the ith spot] = 1/n.

Property B: For each pair of elements xand y, P[xand y are inverted] = 1/2.

Property C: Even and odd permutations are generated with equal probability

We observed that any algorithm which generates permutations uniformly must have properties A, B and C.

Homework #3

Due Wednesday, 10/13

Does an algorithm with Properties A, B and C necessarily generate all permutations with equal probability
From the book, page 86, questions 4 and 5 (I think...I'll check and correct this if it's wrong. It's the problems that I mentioned in class.)

Some Algorithms:

Here are some algorithms which attempted, not always successfully, to generate a random permutation on n elements:

Algorithm 1: Flip a coin. On H, do n - 1 random swaps, on T do n - 2 random swaps.
This algorithm worked for n =1, 2 and 3, but failed to generate permutations uniformly for n = 4.

Algorithm 2: Start with the array A[i] = i for i = 1..n. Select a random r in the interval [1..n] and send each element i to (i + r) (mod n).
This algorithm had property A, but generates only n different permutations, not n!.

Algorithm 3: Flip a coin. If it's H, return the identity permutation. If it's T, return the reverse permutation.
This algorithm had property B, but generates only 2 different permutations, not n!.

Algorithm 4:

Extra Credit

From Car Talk, the syndicated NPR radio call-in show.

RAY: You're one of a hundred people standing in line to get onto an airplane that has 100 seats. There's a seat for every person who's in line, and each of you has a boarding pass for your assigned a seat. The first person to walk onto the plane drops his boarding pass and, instead of picking it up, decides, "I'm just going to sit anyplace." He takes a seat at random.

Now, every other passenger will take either his assigned seat or, if that seat is taken, that passenger will take any seat at random.

TOM: I've been on that flight!

RAY: Because you are such a kind, generous, and accommodating person, you are the last passenger to walk onto the plane. Obviously, there's going to be one seat left, because everyone else is sitting in his correct seat, or not.

The question is: What are the chances that you get to sit in your assigned seat?

Homework #4

Due Wednesday, 11/10

First some problems from this problem set:

Problems 3, 6 and 11
Problems 8, 9 and 13.

And then a problem from the problem set at the end of this document.

Problems 9 and 10

In the second problem 9, you are asked to find an optimal local alignment using the scoring matrix from the previous problem. In this scenario, there is not a single score for matched letters and another single score for mismatched letters. Each pair alignment has its own score, and that is what is given in the table. For example, if one aligns T with T, it contributes a score of +4, and if one aligns A with D, it contributes a score of -2.

Homework #5
Due Monday, 11/22 15.2-1 and 15.2-4, pg 338 15.4-1, pg 355 (please draw the c and b tables) 15-3, pg 364 22.3-1 and 22.3-4, pg 547 22.3-11, pg 549

Homework #6
Changes are in bold/red

Due Wednesday, 12/8

Prove that if T is a minimum weight spanning tree in some connected graph G, then T is also a bottleneck spanning tree for G. Give an example of a bottleneck spanning tree which is not also a MWST. (Such an example exists on a graph with as few as 4 vertices.)
Prove that if G is a connected, weighted graph with no two edges having the same weight, then G has a unique MWST. (Note that the problem does not ask you to prove that Kruskal's algorithm has only one possible output.)
A certain messaging system has 8 characters, with the i'th character appearing with frequency i/36 for 1 <= i <= 8. Use Huffman coding to devise an efficient prefix-free binary code for these 8 characters. What is the expected number of bits needed in your code to send a random message of length 10000?
Prove that even if a tree has multiple maximum-length paths, its middle still consists of just a single vertex or a single edge. Then devise a linear-time algorithm for finding the middle of a tree.
Prove that a minimum weight Hamilton Circuit in a connected graph must have greater total weight than that of a MWST in that graph.

A bottleneck spanning tree of a connected graph G is a spanning tree of G whose maximum weight edge is as small as possible.
The length of a simple path in a graph is the number of edges along that path. Consider a tree and let P be a longest path in that tree. Define the middle of a tree to be the middle of any one of its longest paths. If P has an even number of edges, then the middle consists of a single vertex. If P has an odd number of edges, then the middle consists of a single edge.
A Hamilton Circuit in a graph is a simple circuit which contains all the vertices of the graph.