Chapters 1-6, which is available online and include interactive programing and lectures

http://interactivepython.org/runestone/static/pythonds/index.html

Assignment 3

1. Searching 25 pts ( Points include the required report portion )

Implement a class named SequentialStringList. In this class implement a method called add, that when given a string, it adds it to an internal list object. You can use the list object from the standard python library for the internal list. Next, implement a find method that takes a string as the argument. Implement the find method using sequential search. If the string is found return it, if not, return None. Create another class called BinaryStringList, that implements the same methods but uses a binary search as the implementation for find. Create a test program called sequential_test.py. Create an instance of your SequentialStringList and add 20 strings to it. Create a timeit test using one of the words in the list and the find method and another timeit test using a word not in the list and the find method. Create another test program called binary_test.py and perform the same tests. Compare the results and write a brief discussion of your findings. In your discussion, include an analysis of the time complexity, i.e Big O.

2. Sorting 25 pts ( Points include the required report portion )

Implement a class named BubbleStringList. In this class implement a method called add, that when given a string, it adds it to an internal list object. You can use the list object from the standard python library for the internal list. Next, implement a sort method that uses a BubbleSort to sort the list when called. Create another class called MergeStringList, that implements the same methods but uses a Merge Sort as the sorting algorithm. Create another class called QuickStringList that implements the same methods but used a QuickSort algorithm. Write a test class for each and use timeit to getting the run times and compare the results. In your discussion, include analysis of the time complexity, i.e Big O.

3. Binary Trees 25 pts ( Points include the required report portion )

Implement a class named BinaryTreeStringList. In this class implement a method called add, that when given a string, it adds it to an internal Binary Tree object. Feel free to use the BinaryTree implementation from the book. Provide a find method on the BinaryTreeStringList class that searches the BinaryTree for the item. Write a test class and a timeit measurement. Write a discussion that compares the find method results in this implementation with the previous implementations from part 2 of this assignment. . In your discussion, include analysis of the time complexity, i.e Big O.

4. Create a Microsoft word document that provides screen captures of running your algorithms with your commentary of the results and your code. At the END of the document, include your python source code at the END of the report for reference and turnitin checking, in TEXT format, NOT screen capture.