Question

In: Computer Science

def sequentialSearch(theList, item): #**** to be changed: # counts the iterations of the while...

def sequentialSearch(theList, item):
    #**** to be changed:
    # counts the iterations of the while loop and returns this value
    found = False
    index = 0
    while index < len(theList) and not found:
        if theList[index] == item:
            found = True
        index = index + 1
    return found

def binarySearch(theList, item):
    #**** to be changed:
    # counts the iterations of the while loop and returns this value
    startIndex = 0
    endIndex = len(theList)- 1
    found = False
    while startIndex <= endIndex and not found:
        middleIndex = (startIndex + endIndex)//2
        if item == theList[middleIndex]:
            found = True
        elif item > theList[middleIndex]:
            startIndex = middleIndex + 1
        else:
            endIndex = middleIndex - 1
    return found

# program for testing the search algorithms
dataSet = [-200, -190, -180, -170, -160, -110, -105, -74, -30, -17, -12, -1, 4, 5, 13, 26, 37, 42, 62, 96, 100, 110, 120,130]

print("\nSuccessful sequential search - all elements of the data set")
totalComparisons = 0
#**** to be completed:
#     list traversal on the dataSet list:
#     for each item: perform a sequential search and
#                    display the number of comparisons,
#     count the total number of comparisons
print("Average number of comparisons: "+str(totalComparisons/len(dataSet)))

print("\nUn-successful sequential search")
target = 196                 # target not in the dataSet
comparisons = 0 #**** to be changed: perform a sequential search for target
print ("target " + str(target), "\t comparisons used " + str(comparisons))

print("\nSuccessful binary search - all elements of the data set")
totalComparisons = 0
#**** to be completed:
#     list traversal on the dataSet list:
#     for each item: perform a binary search and
#                    display the number of comparisons,
#     count the total number of comparisons
print("Average number of comparisons: "+str(totalComparisons/len(dataSet)))

print("\nUn-successful binary search")
target = 196 # target not in the dataSet
comparisons = 0 #**** to be changed: perform a binary search for target
print ("target " + str(target), "\t comparisons used " + str(comparisons))

make some change to the python according to the comment line and complete the following question.

Sequential Search Algorithm		Binary Search Algorithm
Successful searches		Successful searches
Average number of comparisons		Average number of comparisons
Maximum number of comparisons found at index _____________		Maximum number of comparisons found at index _____________
Minimum number of comparisons found at index____________		Minimum number of comparisons found at index____________
Un-Successful search		Un-Successful search
Number of comparisons		Number of comparisons

What is the size n of the data set used?
What is the worst case for sequential search?
What is the best case for sequential search?
Is the worst case for sequential search O(n)?

What is the best case for binary search?

What is the worst case for binary search?

Is the worst case for binary search O(log n)?

Expert Solution

Sequential Search Algorithm		Binary Search Algorithm
Successful searches	24	Successful searches	24
Average number of comparisons	12.5	Average number of comparisons	3.9166666666666665
Maximum number of comparisons found at index (assuming index starts at 1) 24	24	Maximum number of comparisons found at index (assuming index starts at 1) 2,5,8,11,14,17,20,22,24	5
Minimum number of comparisons found at index______1______	1	Minimum number of comparisons found at index (assuming index starts at 1) 12	1
Un-Successful search	1	Un-Successful search	1
Number of comparisons	24	Number of comparisons	5

What is the size n of the data set used? -> 24
What is the worst case for sequential search? ->O(n) (for the above case O(24))
What is the best case for sequential search? ->O(1)
Is the worst case for sequential search O(n)? ->Yes

What is the best case for binary search? -> O(1)

What is the worst case for binary search? -> O(log n) (with base 2)

Is the worst case for binary search O(log n)? ->Yes

Below is the modified program to get the number of comparisons in each case as required.

def sequentialSearch(theList, item):
    #**** to be changed:
    # counts the iterations of the while loop and returns this value
    found = False
    index = 0
    compare_count=0
    while index < len(theList) and not found:
        compare_count+=1
        if theList[index] == item:
            found = True
        index = index + 1
    return compare_count

def binarySearch(theList, item):
    #**** to be changed:
    # counts the iterations of the while loop and returns this value
    startIndex = 0
    endIndex = len(theList)- 1
    found = False
    compare_count=0
    while startIndex <= endIndex and not found:
        middleIndex = (startIndex + endIndex)//2
        compare_count+=1
        if item == theList[middleIndex]:
            found = True
        elif item > theList[middleIndex]:
            startIndex = middleIndex + 1
        else:
            endIndex = middleIndex - 1
    return compare_count

# program for testing the search algorithms
dataSet = [-200, -190, -180, -170, -160, -110, -105, -74, -30, -17, -12, -1, 4, 5, 13, 26, 37, 42, 62, 96, 100, 110, 120,130]

print("\nSuccessful sequential search - all elements of the data set")
totalComparisons = 0
#**** to be completed:
#     list traversal on the dataSet list:
#     for each item: perform a sequential search and
#                    display the number of comparisons,

for num in dataSet:
    comparisons = sequentialSearch(dataSet,num)
    print("target " + str(num), "\t comparisons used " + str(comparisons))
#     count the total number of comparisons
    totalComparisons= totalComparisons + comparisons

print("Average number of comparisons: "+str(totalComparisons/len(dataSet)))

print("\nUn-successful sequential search")
target = 196 # target not in the dataSet
comparisons = 0 #**** to be changed: perform a sequential search for target
comparisons= sequentialSearch(dataSet, target)
print ("target " + str(target), "\t comparisons used " + str(comparisons))

print("\nSuccessful binary search - all elements of the data set")

totalComparisons = 0
#**** to be completed:
#     list traversal on the dataSet list:
#     for each item: perform a binary search and
#                    display the number of comparisons,

for num in dataSet:
    comparisons = binarySearch(dataSet,num)
    print("target " + str(num), "\t comparisons used " + str(comparisons))
#     count the total number of comparisons
    totalComparisons= totalComparisons + comparisons

print("Average number of comparisons: "+str(totalComparisons/len(dataSet)))

print("\nUn-successful binary search")
target = 196 # target not in the dataSet
comparisons = 0 #**** to be changed: perform a binary search for target
comparisons= binarySearch(dataSet, target)
print ("target " + str(target), "\t comparisons used " + str(comparisons))

Please find below attached the schreeshot of the program and console output.

venereology answered 2 weeks ago

The counts per second (cps) changes when the spot size is changed. Why? The counts per...

The counts per second (cps) changes when the spot size is changed. Why? The counts per second (cps) also changes when kV is changed. Why? In general, which parameter would you change, spot size or kV, to increase the counts per second? Why? This is when using an Scanning Electron Microscopy (SEM) or Energy Dispersive Spectroscopy (EDS).

def hiCount(iterable): rtnVal = 0 most = '' for item in iterable: num = iterable.count(item) if...

def hiCount(iterable): rtnVal = 0 most = '' for item in iterable: num = iterable.count(item) if num > rtnVal: most = item rtnVal = num return tuple(most, rtnVal) lyric = "you don't own me" print(hiCount(lyric)) does all the for then the return Python

What would have to be changed in the code if the while statement were changed to:...

What would have to be changed in the code if the while statement were changed to: while (menu == 5); Code is as follows #include <stdio.h> void printHelp () { printf ("\n"); printf ("a: a(x) = x*x\n"); printf ("b: b(x) = x*x*x\n"); printf ("c: c(x) = x^2 + 2*x + 7\n"); printf ("d: shrink(x) = x/2\n"); printf ("q: quit\n"); } void a(float x) { float v = x*x; printf (" a(%.2f) = %.2f^2 = %.2f\n", x, x, v); } //...

def vend(): a = {'key':'0','item': 'chips', 'price': 1.50, 'stock': 6} b = {'key':'1','item': 'cereal',...

def vend(): a = {'key':'0','item': 'chips', 'price': 1.50, 'stock': 6} b = {'key':'1','item': 'cereal', 'price': 1.25, 'stock': 10} c = {'key':'2','item': 'pop', 'price': 1.75, 'stock': 12} d = {'key':'3','item': 'apple', 'price': 2.50, 'stock': 6} e = {'key':'4','item': 'orange', 'price': 1.95, 'stock': 10} items = [a, b, c, d, e] credit = 0 # cash in machine # show items, prices def show(items): while True: s = input("> ") if s...

Question An item is up for auction. Player 1 values the item at 3 while player...

Question An item is up for auction. Player 1 values the item at 3 while player 2 values the item at 5. Each player can bid either 0, 1, or 2. If player i bids more than player j then i wins the good and pays his bid, while the loser does not pay. If both players bid the same amount then a coin is tossed to determine who the winner is, and the winner gets the good and pays...

I need a C++ program using while loops that counts the number of characters in a...

I need a C++ program using while loops that counts the number of characters in a sentence. The user inputs a sentence and then terminates the input with either '.' or '!'. And then it needs to count and display the number of a's, e's, i's, o's, u's, and consonants. The program should read both lower and upper case. They don't want us using switch statements or string operators, and want us to us if else if statements. I have...

def vend(): a = {'key': '0', 'item': 'choc', 'price': 1.50, 'stock': (2)} b = {'key': '1',...

def vend(): a = {'key': '0', 'item': 'choc', 'price': 1.50, 'stock': (2)} b = {'key': '1', 'item': 'pop', 'price': 1.75, 'stock': 1} c = {'key': '2', 'item': 'chips', 'price': 2.00, 'stock': 3} d = {'key': '3', 'item': 'gum', 'price': 0.50, 'stock': 1} e = {'key': '4', 'item': 'mints', 'price': 0.75, 'stock': 3} items = [a, b, c, d, e] def show(items): cim = 0 for item in items: if item.get('stock') == 0: items.remove(item) for item in items: print(item.get('key'), item.get('item'),item.get('price'),...

import Stack def stack_mystery(myStack): mystery=0 while not myStack.isEmpty(): value=myStack.pop() if v

import Stack def stack_mystery(myStack): mystery=0 while not myStack.isEmpty(): value=myStack.pop() if value> mystery: mystery=value return mystery def main(): s=Stack.Stack() s.push(20) s.push(10) s.push(50) s.push(100) s.push(40) print(stack_mystery(s)) main() Answer the following questions a) What is the output of the print(stack_mystery(s)) statement in the main method? b) What is the task of the stack_mystery function? What does the mystery variable represent?

import os def process_dir(p, indent): for item in os.listdir(path): if os.path.isfile("{0}/{1}".format(path, item)): print("\t"*indent, item) elif os.path.isdir("{0}/{1}".format(path,...

import os def process_dir(p, indent): for item in os.listdir(path): if os.path.isfile("{0}/{1}".format(path, item)): print("\t"*indent, item) elif os.path.isdir("{0}/{1}".format(path, item)): print("\t"*indent, "\x1b[1;31m{}\x1b[0;0m".format(item)) process_dir("{0}/{1}".format(path, item), indent+1) else: print("Not a file or directory") path=input("Enter a valid system path: ") print("\x1b[1;31m{}\x1b[0;0m".format(path)) process_dir(path, 1) 1. Figure out what the program is trying to do. Add meaningful comments that tell what the program is doing. There is a bug in this program that causes it to work incorrectly; find the bug, and fix it c. Put in some...

Interest Expense is treated as an operating activity item in the Statement of Cash Flows while...

Interest Expense is treated as an operating activity item in the Statement of Cash Flows while it is listed as a financing activity item in the Income Statement. Prepare a 1-2 page report listing the reasons why interest should be an operating or financing activity item and recommend your position on how interest should be listed (operating or financing).