Discussion Topics

Week of Feb 12th

Given the following array:

and for each of the following sorts:

• Bubble sort (early terminating)
• Insertion sort
• Selection sort
• Merge sort
• Quick sort
• Radix sort (LSD)

do the following:

1. Show the list after each pass of the sort.
2. Indicate graphically the knowledge we have gained after each pass (the elements we now know are sorted, are the largest, etc.
3. Give the big-Oh or big-Theta complexity of the sort, whichever is more specific.
4. If different, give the average-case complexity of the sort.

Consider the task of searching a UNIX filesystem for a file. Suppose you have access only to the commands ls and cd. How could you find the file, making sure you search every directory?

(Hint: assume the file is named cheese.txt).

When you have found the file, how could you trace a path through the filesystem back to the root directory? Suppose you were halfway back to the root. Given the choices of moving to fred, .., or alice, which would be the best choice?