Two Approaches to Searching an Array

This assignment consists of various programming problems related to algorithms and data structures. The main topics covered are searching arrays, string matching, sorting, and cycle detection. The first problem involves two approaches for searching an array: linear search and binary search after sorting the array. The worst-case running times are calculated for both procedures under different conditions. The second problem focuses on a function that determines if a substring is present in a target string, with a time complexity analysis for restricted and unrestricted cases. The third problem deals with the detection of k largest items in an integer array using two methods: sorting and heap extraction. The worst-case running times are calculated for both procedures. Finally, there are problems on implementing cycle detection algorithms based on singly linked lists and solving the 0-1 knapsack problem using a bottom-up dynamic programming approach.

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.