Your All-in-One AI-Powered Toolkit for Academic Success.

Available 24*7 on WhatsApp / Email

Unlock your academic potential

© 2024 | Zucol Services PVT LTD | All rights reserved.

Added on 2019/09/16

|2

|959

|64

Project

AI Summary

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.

Your contribution can guide someone’s learning journey. Share your
documents today.

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

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

Need help grading? Try our AI Grader for instant feedback on your assignments.

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.

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.

1 out of 2