CSE 101 Assignment 2

Due date, July 14, 2003, 9:30 AM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant at the beginning of class on the due date.
There will be a 10% penalty if the homework is turned in during office hours on the due date. Homework turned in later than that will not be accepted.
  1. Work Exercise 2 on page 126 of your textbook.
  2. Consider the queue-based algorithm which visits all the vertices of the graph G (here is the eps version) reachable from s in breadth-first order. Show the queue at each step.
  3. Apply quicksort to sort the list D,I,V,I,D,E,A,N,D,C,O,N,Q,U,E,R. Show the array at each step.
  4. Solve the single source minimum path problem for the weighted directed graph G, using Dijkstra's algorithm. Show the subgraph at each iteration of the algorithm.
  5. What sorting algorithm do you think would be best in each of the following situations? Explain.
    1. You are given many thousands of lists, each of which is very small. In fact, their average size is 1. (You need to sort each list separately.)
    2. You have a list of donors that you want to alphabetize. This list was formed by concatenatinglists of donors from each of the 50 states. Each state list was sorted. The total number of names is approximately 100,000.
  6. What are the disadvantages of radix sort? (One or two sentences should be enough.)
  7. We will implement a heap of letters as an array, as shown in class. Start with an empty heap, and perform the following operations:
    Insert(G);
    Insert(N);
    Insert(B);
    Insert(H);
    Insert(M);
    Insert(R);
    Insert(V);
    Insert(C);
    DeleteMin;
    DeleteMin;
    DeleteMin;
    What will the array be after those operations? Show the array at each step.
    9. Describe the algorithm which adds n-bit numbers in O(log n) time in parallel. Do not turn it in. (This should be about two pages.)

Back to Course Page