Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #10 -- Due Thu 05 August 1999 : Midnight

• Question 1. [2 points each part] Suppose you have a set S of N integers, where N can be very large but not infinite. If you wanted to determine whether an integer x was in the set, which would be the
  (a) most space-efficient and time-efficient data structure for representing S? Explain your answer in detail, stating all assumptions.

  (b) worst-choice data structure (in terms of efficiency) to represent S? Again, explain your answer in detail.

• Question 2. [2 points each part] Given a telephone book with N names, addresses, and phone numbers, what is the most space- and time-efficient data structure for storing and retrieving the
  (a) address given the name,

  (b) phone number given the name or address.

  Explain all answers in detail to get full credit.

• Question 3. Suppose you are trapped in a burning building, in a room that has two doors. Each door leads to a distinct room that has one or two windows and one door, each of which leads outdoors to safety. You can exit through the windows or doors.
  (a) [1 point] What specific data structure would best represent this situation? Hint: Draw a diagram of the problem and its associated decision tree.

  (b) [3 points] Suppose only one of the windows could be blocked at any given time (and none of the doors could be blocked). What kind of data structure would you use to most efficiently enumerate (or list) all the probabilities of encountering a blocked exit? List the probabilities, to show that your answer is correct.

• Question 4. Consider the Towers of Hanoi problem on p. 277 of your text (Sahni, 1999).
  (a) [1 point] Assuming that each disk is labelled with a unique number according to the size of the disk, what data structure would be most efficient for finding the optimal choice of disks?

  (b) [3 points] Write pseudocode for an algorithm that finds the solution to a given instance of the Towers of Hanoi problem, using the data structure chosen in Question 4a).

• Question 5. Suppose you are designing a computer program to play a game such as chess. At the i-th move, you have n_i choices for the (i+1)-th move, where n_i > 1 for all 0 < i < m+1.
  (a) [1 point] What specific type of data structure would you use to represent the organization of your strategy for playing the game? Hint: A special kind of tree.

  (b) [1 point] Draw a diagram of this data structure for m = 4 and 1 < i < m+1.

  (c) [2 points] For prespecified (integer) values of m and k, such that 1 < n_i < k, what is the upper bound on the total number of choices of moves (i.e., the largest number of objects in the tree)? Express your answer theoretically, as a function of m and k.

• Question 6. Assume that you are in charge of a large communications network N that is sparsely connected.
  (a) [2 points] Which algorithm would you use to find the shortest path from Station A to Station B in N? Explain your answer in detail.

  (b) [2 points] What algorithm that we discussed in class should you use to determine if N is sparsely or densely connected? Explain your answer in detail.

Copyright © 1999 by Mark S. Schmalz.