Question 1:

A search algorithm iSearchand a variableilisthave been defined as follows:

def iSearch(target, lyst): left = 0 right = len(lyst) - 1 while left <= right: midpoint = (left + right) // 2 if target == lyst[midpoint]: return midpoint elif target < lyst[midpoint]: right = midpoint - 1 else: left = midpoint + 1 return -1  iList = [11, 20, 29, 33, 41, 55, 56, 62, 66, 74, 88] 

a)If the target element is11, trace the values of the variablesleft,right, andmidpointafter applying theiSearchalgorithm to theiListstructure.

b)Repeat the tracing process inQ1afor target element55.

c)Why does the iSearch algorithm run faster inQ1bscenario than inQ1ascenario?

d)Modify theiSearchalgorithm, so it can run inQ1ascenario as fast as it does inQ1bscenario.

e)For a problem of size?if algorithmXperforms?^4instructions, and algorithmYperforms2^ninstructions. At what point does one of the algorithms begin to be more efficient and perform better than the other? Justify your answer.

Question 2:

Emulate the stack behaviour using the list data structure.

a)Complete the methods of the followingStackclass according to their description

class Stack: def __init__(self): """ Initialize a new stack """ self.elements = [] def push(self, new_item): """ Append the new item to the stack """ ## CODE HERE ### def pop(self): """ Remove and return the last item from the stack """ ## CODE HERE ### def size(self): """ Return the total number of elements in the stack """ ## CODE HERE ### def is_empty(self): """ Return True if the stack is empty and False if it is not empty """ ## CODE HERE ### def peek(self): """ Return the element at the top of the stack or return None if the stack is empty """ ## CODE HERE ### 

b)Use theStackclass that you defined inQ2ato complete the code of theis_valid()function, which checks whether the order of the brackets of an arithmetic expression is correct. Some examples are given below:

exp1 = "(2+3)+(1-5)" # True exp2 = "((3*2))*(7/3))" # False exp3 = "(3*5))]" # False 

def is_valid(exp): """ Check the order of the brackets Returns True or False """ opening = ['(', '[', '{'] closing = [')', ']', '}'] ## CODE HERE ## return ## CODE HERE ## is_valid(exp1) is_valid(exp2) is_valid(exp3) 

c)Use theStackclass that you defined inQ2ato complete the code of thecount_pairs()function, which returns the number of the valid bracket pairs of an arithmetic expression. Some examples are given below:

exp1 = "(2+3)+(1-5)" # 2 pairs exp2 = "((([()])))" # 5 pairs exp3 = "[([])" # 2 pairs 

def count_pairs(exp): """ Count the valid number of brackets Returns the total number of valid brackets in the string """ opening = ['(', '[', '{'] closing = [')', ']', '}'] ## CODE HERE ## return ## CODE HERE ## count_pairs(exp1) count_pairs(exp2) count_pairs(exp3)