CISC 3220 - Homework #6

Due: Wednesday, November 16.

    Selection (Chapter 5) (These exercises include some more review of Max-heaps.)

  1. Page 244, Exercise 5.10 Explain how you derived your answer.

    You are asked to find the k largest keys in an UNsorted array. You can repeatedly find the max k times. How much time would this take? Here is an alternative idea:
    --------------------------------------------------
    Build a heap H out of the n keys in the array.
    for (i=1;i <=k; i++)
    {
    extractMax(H)
    fixheap(H)
    }
    --------------------------------------------------

    How large can k be (as a function of n) for this algorithm to remain linear in n?
  2. Page 245, Exercise 5.21 Suppose that you had a computer with small memory and you are given a sequence of n keys on a disk. Keys can be read in exactly once for processing.

    (1). What is the minimum number of storage cells needed in memory for finding the max of an array of n elements?

    (2) What is the minimum number of memory cells needed for finding the median?

    3. Graph Traversals (Chapter 7)

  3. Exercise 7.4 b

    Show, using the stack and the node ordering, how the Depth-First search algorithm would run for the directed graph that we used in class (with nodes A,B,C,D,E,F,G): if each adjacency list in the graph's representation is in reverse alphabetical order.

  4. Exercise 7.5 b (same as previous exercise just for BFS.)

  5. 7.8 The transpose of a directed graph is the graph that results from reversing the direction of each edge in the original graph.

    (1) What is the relationship between the adjacency matrix of a graph G=(V,E) and the adj matrix of the transpose of graph G?

    (2) Give an algorithm that would compute the transpose of the adjacency lists of a given graph.
  6. Exercise 7.17

    You want to determine whether a given directed graph has a cycle. Consider using DFS and BFS. Which is preferable and why?