Exercise 4.1.5:

Consider the following algorithm to check connectivity of a graph defined by its adjacency matrix.

Algorithm Connected (A[0..n-1,0..n-1]) //Input: Adjacency matrix A[0..n-1,0..n-1]) of an undirected graph G //Output: 1 (true) if G is connected and 0 (false) if it is not if n = 1 return 1 //one-vertex graph is connected by definition else if not Connected (A[0..n-2,0..n-2]) return 0 else for j = 0 to n-2 do if A[n-1,j] return 1 return 0

Does this algorithm work correctly for every undirected graph with N > 0 vertices? If you answer "yes," indicate the algorithm's efficiency class in the worst case; if you answer "no," explain why.

Exercise 4.2.1:

Apply the DFS-based algorithm to solve the topological sorting problem for the following digraphs:

Exercise 4.2.5:

Apply the source-removal algorithm to the digraphs of Exercise 4.2.1.

Exercise 4.2.6:

1. Prove that a dag must have at least one source. Hint: consider proof by contradiction.
2. How would you find a source (or determine that such a vertex does not exist) in a digraph represented by its adjacency matrix? What is the time efficiency of this operation?
3. How would you find a source (or determine that such a vertex does not exist) in a digraph represented by its adjacency lists? What is the time efficiency of this operation?

Exercise 4.4.1:

A stick n inches long needs to be cut into n 1-inch pieces. Outline an algorithm that performs this task with the minimum number of cuts if several pieces of the stick can be cut at the same time. Also give a formula for the minimum number of cuts.
To simplify your analysis, you may assume that n = 2^k.

Exercise 4.4.3:

1. What is the largest number of key comparisons made by binary search in searching for a key in the following array?

   

2. List all the keys of this array that will require the largest number of key comparisons when searched for by binary search.
3. Find the average number of key comparisons made by binary search in a successful search in this array. Assume that each key is searched for with the same probability.

Exercise 4.5.2:

Apply quickselect to find the median of the list of numbers 9, 12, 5, 17, 20, 30, 8.

Exercise 4.5.12:

Flipping pancakes: There are n pancakes all of different sizes that are stacked on top of each other. You are allowed to slip a flipper under one of the pancakes and flip over the whole stack above the flipper. The purpose is to arrange pancakes according to their size with the biggest at the bottom. Design an algorithm for solving this puzzle.