CS421 - Advanced Data Structures and Algorithm Development - Week 14 & 15 Assignment

(Homework must be submitted electronically to summers_wayne@ColumbusState.edu or hand delivered to my mailbox by noon MST. )
Late assignments will be subject to up to a 25% deduction in points per day. No credit will be given for assignments that are more than one week late.

• DUE April 26, 1999 (12 pts)
  1. Name two different ways graphs can be implemented.
  2. Describe the differences between a queue, mergeable queue, and binomial queue.
  3. There is only one tree each with one, two, and there nodes, and there are two with four nodes. How many trees have five nodes? Draw them.
  4. EXTRA CREDIT: Show that an even number of people will shake hands an odd number of times.
• DUE April 30, 1999 (15 pts) You may pick this up on Monday morning
  1. Find three 5-node simple (undirected) graphs that are:
     1. cyclic, but not a cycle
     2. a cycle
     3. is acyclic
  2. Why is the reduced digraph a dag?
  3. Trace algorithm 5.5 (Breadth-First) on the graph below to arrive at a sequence of nodes visited.
  4. Trace algorithm 5.6 (Depth-First) on the graph below to arrive at a sequence of nodes visited.
     
  5. Given the following graph, find the cheapest spanning tree using algorithm 5.7.
     
  6. Question #12 on page 352.
  7. EXTRA CREDIT: Question #11 on page 352.

Participate in the Collabra discussion group (CS421 on the server cs.nmhu.edu). Discuss sorting techniques.