CSC 344
Homework 4

Assigned 7 Apr, due 3 May

Note: will not be accepted late!

Problems from the Levitin textbook

• Do problem 5.2.3 in the textbook (note that the graph is undirected).

• Do problem 5.2.6 in the textbook (note that the graph is directed).

• Do problem 5.6.10 in the textbook (sorting a stack of pancakes by flipping substacks).

• Do problem 6.1.6 in the textbook (you'll need the formula on p. 126 for the number of comparisons in a merge sort).

• Do problem 6.4.2 in the textbook (checking whether a given array, when viewed as a binary tree, is a heap).

• Do problem 6.5.10 in the textbook. By "discuss which is more convenient," I mean

  • for each of the two representations, give a pseudocode algorithm to solve the problem;
  • for each of the two representations, analyze your pseudocode algorithm; and
  • tell which representation makes the problem easier.

• Do problems 7.2.1, 7.2.2, and 7.2.3 in the textbook (Horspool string matching).

• Read problem 8.1.9 in the textbook, then do the following:

  1. Set up a recurrence relation for P[i,j] that can be used to solve the problem.
  2. Write a working program that solves the problem, recursively and top-down, using the recurrence relation. The input to the program is the probability p of Team A winning any given game, and the number of games in the series (you may assume this number is odd); the output is the probability of Team A winning the series (i.e. winning a majority of the games). Test and time your program on a variety of series sizes and probabilities.
  3. Modify this program to use "memo-ization" to avoid re-computing answers to common sub-problems. Test and time the modified program on the same test cases.
  4. Write pseudocode for a bottom-up, dynamic-programming algorithm to solve the same problem.
  5. Implement this bottom-up algorithm in real code. Test and time it as before.
  6. Compare the running times of the three versions of the program.

A problem out of my head

You're a network administrator concerned about terrorist attacks, either on computers in the network or on cables between computers. You want to know whether

1. the network is currently connected, i.e. a message can get from any computer to any other; and if so, whether
2. there is a single computer which, if destroyed, would leave the network no longer connected; or
3. there is a single cable which, if cut, would leave the network no longer connected.

1. re-phrase it in graph terminology
2. give a pseudocode algorithm for solving it
3. analyze the running time of your algorithm