CSE 326

HW 5

Related reading: Chapters 7 & 9

Due date: Friday, May 25, 2001 in class

Total points: 40 points

Homework #5

  1. Topological Order
    1. Describe an algorithm to determine whether a directed graph has exactly one topological order.
    2. What is the time complexity of your algorithm?

 

  1. Kruskal’s algorithm relies on the Union-Find algorithm to identify disjoint sets and union them. Show the trees or linked lists (your choice) resulting from applying the union-find algorithm at each step of Kruskal’s algorithm on the following graph. Initially, each tree or linked list consists of a unique node in the graph.

 
  1. Determine the running time of mergesort for
  1. sorted input
  2. reverse-ordered input
  3. random input
  1. Construct a permutation of 20 elements that is as bad as possible for quicksort using median-of-three partitioning and a cutoff of 3.