CISC-235 Data Structures W21

Assignment 1

January 19, 2021

How to Submit: Important!

You need to prepare a folder which contains your answer and code. For question 1-3, write your answers in a text file and submit in the pdf format. You need to submit your python code for question 3 and 4. One for each question. You must comment your code. Name your folder as your netid-A1, zip the folder and upload it to OnQ.

1   Discuss the Complexity of a Program: 5*4 points

Line 1: def average(inputList):

Line 2: n = len(inputList)

Line 3: total = 0

Line 4: for i in range(n):

Line 5: total += inputList[i]

Line 6: return total / n

Analyze the time complexity of the above program. Your analysis should contain 1) a discussion on how many operations used per line, line 1 excluded. 2) what is the final representation of the complexity of this program, 3) what is the Big-O of the program, and 4) prove it following the formal definition of Big-O, 5) is your provided Big-O in answer to 3) the tighest upper bound? Why? provide a short discussion.

2   Big-O, Big-Ω, and Big-Θ Analysis and Proofs: 5+10 points

Prove following the formal definitions:

1) Proof that if 

2) Let  T(n) represents the general form of polynomials, where a0, a1, . . . akk 1 are real numbers with ak > 0. Does T(n) have a Big-Θ estimation? If it has, what is the Big-Θ of T(n)? Proof your claim.

3   Binary Search or Linear Search? 10+40 points

Let us analyse the runtime complexity of two algorithms, i.e., linear search (Algorithm A) and binary search (Algorithm B) using experimental method.

Algorithm A: Store the list S in an array or list, in whatever order the values are given. Search the list from beginning to end. If S[i] == x for any value of i, stop searching and return True (i.e., found), otherwise return False.

Algorithm B: Store the list S in an array or indexed list (such as the Python list). Sort the list. Use binary search to determine if x is in S. Return True or False as appropriate.

When using Algorithm A, searching for a value that is in the list will require an average of n/2 comparisons, while in the worse case, searching for a value that is not in the list will require n comparisons. When using Algorithm B, searching for any value will require an average of about logn comparisons. However, sorting the list will take O(nlogn) time.

If we are doing a very small number of searches, Algorithm A is preferable. However if we are doing many searches of the same list, Algorithm B is preferable since the time required to sort the list once is more than offset by the reduced time for the searches. This is what complexity theory tells us.

Your task is to conduct experiments to explore the relationship between the size of the list and the number of searches required to make Algorithm B preferable to Algorithm A. See the detailed requirement below:

1) Implement two algorithms using Python. When implementing Algorithm B, you must write your own sort function and your own binary search function. You may use any sort algorithm that has complexity in O(nlogn).

2) For n = 1000, 5000, and 10000, conduct the following experiment:

     - Use a pseudo-random number generator to create a list S containing n integers.

     - For values of k ranging from 10 upwards:

     - Choose k target values, make sure half of which are in S and half are not in S, i.e., modeling the average case

     - Use Algorithm A and B seperately to search the k target values in S.

     - Design and conduct experiements to determine the approximate smallest value of k for which Algorithm B becomes faster than Algorithm A. Provide a short description on how you determine the smallest value k.

Hints: To easily create a list of search values, half of which are in S and half of which are not:

• when generating the list S, use only even integer values. You can use step=2 in randrange function to control the interval of considered numbers. For instance odd_rand_num = random.randrange(2,20,2) will return any random number between 2 to 20, such as 2, 4, 6, . . . 18. It will never select 20.

• randomly choose some elements of S as the first half of the search list

• randomly choose odd integer values as the second half of the search list

4   Implementing Stack: 5*2*1 +5 points

Implement Stack using array-based list and linked list. Your stack should support the following functions:

• isEmpty, this function checks whether the current Stack instance is empty. It should return true if the Stack is empty.

• push, this function should takes a data item as input and add it into the Stack.

• pop, this function should return the data item on the top of the current Stack and remove it from the Stack.

• top, this function should return the data item on the top of the current Stack without modifying the Stack.

• size, this function should return the number of data items in the Stack.

Write a test code for validating the behavior of fifive functions. Comment your test code. You can write your test code in the main, i.e., after if __name__ == "__main__":

Hints: you need to write a Linked List class first in order to implement Stack. You can create two python files. One for the implementation of Stack using build-in list in Python. The rest for the implementation of Stack using an inner class linkedlist. ref: https://www.datacamp.com/community/tutorials/inner-classes-python