Data Structures and Algorithms Assignment

This assignment focuses on analyzing and implementing various data structures and algorithms. It includes questions on the time complexity of linear and binary search, sorting algorithms like MergeSort and InsertionSort, substring search, and the analysis of bucket sort and quicksort. Additionally, it requires implementing a cycle detection algorithm for singly linked lists and solving a 0-1 knapsack problem using dynamic programming. The assignment also explores the efficiency of different approaches for finding the k largest items in an array. The solutions and analysis provided aim to help students understand these concepts and improve their problem-solving skills.

Please use the file provided for coding.
Note that the beginning of an array or list will have an index of 0. A file called ClassFile.py is
provided containing classes. You should examine the classes so that you are aware of the
attributes and methods available. Do not modify the classes unless asked to do so. All
programming problems will go in the files Ex2Prog.py and ClassFile.py. Fill in the relevant
function or method, do not change the parameters. The imports for these classes are contained at
the top. Do not use these names for variables.
1. Assume that we have an array containing n elements and we will search the array some
number of times in the future. Now consider two possible approaches to searching this array. The
1st approach simply performs a linear search through the array each time. The second approach
sorts the array prior to searching for any element after which a binary search will be used for
each search. Answer the following questions giving justification for your answer.
a) Suppose that we perform O(lgn) searches. What are the worst case running times using
both procedures? Which is better?
b) Suppose that we perform Ω √n searches. What are the worst case running times of the
two procedures? Which is better?
c) If MergeSort is used for the sorting procedure what is the best case running time for the
second approach?
d) If InsertionSort is used for the sorting procedure what is the best case running time for the
second approach?
2. The following function determines whether or not a non-empty string S is a substring of some
target string T. If it is the function returns True otherwise it returns False. The function works by
considering every index for which T [index] == S[0] and index ≤ len(T) - en(S) as a possible
start of a substring which matches S. The function begins at this character and proceeds checking
the characters of T against S until either the entire string is matched or there is a miss at which
point it moves to the next index where T matches the first character of S. Answer the questions
below the following code. Note tm is an abbreviation for total matched. Below let n denote the
length of the string T
def search (S ,T):
first char = S[0]
matches = []len (S)+
for i in range (len(T) 1):
if T[i] == first char:
matches.append(i)
for index in matches:
tm = 0
while tm < len (S) and T[index + tm] == S [tm]:
tm += 1
if tm == len (S):
return True
return False

a) If we restrict S to be a string of length less than 5 show that the worst case running time is
O(n).
b) Show that the worst case running time of the procedure is ?(n2) if we do not restrict the
length of the string S? To establish this you will need to provide string T of length n and
another string S which achieves this worst-case running time as well as showing that the
running time is O(n2).
c) If T has length n what is the best-case running time over all possible inputs of S?
3) Answer the following questions. You may provide justification which may result in partial
credit in the event that your answer is incorrect. Answer true or false for each. For all problems n
gives the size of an input array.
a) Bucket sort will exhibit a worst case running time of O(n) regardless of the input.
b) The worst case running time of quicksort is O(nlgn).
c) There are some arrays for which merge sort will run in time O(n).
d) There are some arrays for which Insertion Sort will run in time O(n).
4) We would like to determine the k largest items in an integer array. We are considering two
methods.
 We sort the array and then take the k largest items
 We create a heap and then remove the largest item k times using the operation Heap-
Extract-Max.
a) Give the worst-case running time for the first procedure.
b) Give the worst-case running time for the second procedure.
c) If k = O(√n) which procedure has the best worst-case running time?
5) Implement the cycle detection algorithm based on singly linked list. Use the singly linked
list class provided. Code goes in Ex2Prog.py.
6) Consider the following instance of the 0-1 knapsack problem. Illustrate how you would
execute a bottom up Dynamic Programming solution to the problem. Code goes in
Ex2Prog.py. Assume that the maximum weight of the knapsack is W = 5 and that we have
the following items given as weight and value: (4; 4); (5; 5); (1; 2); (3; 3); (1; 2); (2; 2:5);
(2; 2:5). You must illustrate the bottom-up approach even if the answer is obvious to you.
Fill in a 2d grid.