CS14 Assignment 5

Posted: May 30th, 2002

Due: June 6th, 2002

 

 

Sorting

 

1.        Given: 22, 36, 6, 79, 36, 45, 75, 13, 36, 62, 27, 79, 3, 16, 62, 47.

 

Trace through sorting these numbers using:

a.     Insertion sort (show the array after each insert; mark a line between the sorted and unsorted sections)

b.     Selection sort (show the array after each swap; mark a line between the sorted and unsorted sections)

c.     Radix sort

d.     Merge sort (bottom-up)

e.     Quicksort (use first element as pivot)

 

2.        A sorting algorithm is stable if it preserves the original order of equal keys, that is, the first 36 in the input is also the first 36 in the output.  This may not seem relevant when sorting numbers, but is relevant when sorting longer records according to a key.  Which of the sorting algorithms are stable?  What property is common to all unstable sorts?

 

3.        Suppose you are to sort a list of numbers consisting in a sorted list followed by a few unsorted elements.  Which sorting algorithms would be especially well suited to the task?

 

Graphs

 

4.        Given the graph:

 

 

                                             A       3       B       

                                5                                       7

                        F                   6                               G

                       1                       4        6

                                                                                            3

                                    E                                  C

                                            3                   2

                                                            D

 

 

 

 

 

 

 

 

a.  Show the adjacency matrix for the graph.

b.  Show an adjacency list for the graph.

c.  Draw a depth-first spanning tree, starting at node A.

d.  Draw a breadth-first spanning tree, starting at node A.

e.  Draw the minimum spanning tree.

 

5.        A graph is connected if it has only one component.  Given a graph, how can you determine if it is connected?   How long (big-O) does this take?