Assignment 5 -- Sorting and Searching

Sorting

• Implement Quicksort recursively in python and compare run times of Quicksort and Insertion sort on large data-sets by plotting your results (Time vs listSize).

Searching

• Given a filesystem as a directed acylic graph (i.e., a graph with no cycles) as input in the form of a dictionary (as shown in the class), traverse and print the directory structure in Depth-first search and Breadth-first search. Use the following filesystem as an input:

  fileSystem = {
          "home": ["tmp", "teaching", "documents"]
          "tmp" : []
          "teaching": ["col100", "cov885"]
          "col100" ["practice-sheet"]
          "practice-sheet": [] 
          "cov885":[] 
          "documents":["temp"]
          "temp": []
      }    
  

Sort + Search

• Given an list/array a[0, ..., n-1] of n nonzero integers, develop an algorithm to remove all duplicates by replacing a duplicate with 0 value; An instance of an array before duplicate removal is: |2|2|4|8|8|23|37|37|42|. After the duplicate removal we have the following array: |2|4|8|23|37|42|0|0|0|. Provide correctness argument and timing analysis of your solution.