A binary search ____ a linear search.

Question options:

	can't be compared to
	generally has a similar running time to
	is generally faster than
	is generally slower than
Question 3		0 / 1 point

Which sorting algorithm has better than O(n²) behavior, even in the worst case?

Question options:

	Insertion sort
	Merge sort
	Quicksort
	Selection sort
Question 4		0 / 1 point

Consider the selection sort function shown below:

def selectionSort(values) :

for i in range(len(values)) :

minPos = minimumPosition(values, i)

swap(values, minPos, i)

The function works correctly in its current form. What would happen if the line calling swap was replaced with: swap(values, i, minPos)?

Question options:

	The list would still be sorted, but it would take one less iteration
	The list would still be sorted, using the same number of iterations
	The list would still be sorted, but it would take one more iteration
	A runtime error would occur
Question 5		0 / 1 point

Consider the following function for performing a binary search:

def binarySearch(values, low, high, target) :

if low <= high :

mid = (low + high) // 2

if values[mid] == target :

return mid

elif values[mid] < target :

return binarySearch(values, mid + 1, high, target)

else :

return binarySearch(values, low, mid - 1, target)

else :

return -1

How many elements will be visited when values is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], low is 0, high is 9, and target is 2?

Question options:

	1
	3
	5
	10
Question 6		0 / 1 point

In the textbook, we found that the number of element visits for merge sort totaled n + 5nlog₂n. Lets consider sorting 1024 elements. How many visits are needed?

Question options:

	1,024
	6,144
	51,200
	52,224
Question 7		0 / 1 point

Binary search is an ____ algorithm.

Question options:

	O(n)
	O(n2)
	O(log n)
	O(n log n)
Question 8		0 / 1 point

Consider the following function for performing a linear search:

def linearSearch(values, target) :

for i in range(len(values)) :

if values[i] == target :

return i

return -1

How many elements will be visited when values is [1, 5, 7, 6, 2, 4, 9, 3, 8, 0] and target is 2?

Question options:

	0
	2
	5
	10
Question 10		0 / 1 point

How many times can an list with 729 elements be cut into three equal pieces?

Question options:

	4
	5
	6
	7

In the textbook, we found that the number of element visits for merge sort totaled n + 5nlog₂n. Which of the following is the appropriate big-Oh notation for merge sort?

Question options:

	5nlog2n
	n + log2
	n + 5n
	nlog2n
Question 2		0 / 1 point

In big-Oh notation, when we consider the order of the number of visits an algorithm makes, what do we ignore?

I. Power of two terms

II. The coefficients of the terms

III. All lower order terms

Question options:

	I only
	II only
	I and II only
	II and III only
Question 3		0 / 1 point

Consider the following variation of the selection sort algorithm:

def sort(values) :

for i in range(len(values)) :

maxPos = i

for j in range(i + 1, len(values)) :

if values[j] > values[maxPos] :

maxPos = j

temp = values[maxPos]

values[maxPos] = values[i]

values[i] = values[maxPos]

If this algorithm takes 5 seconds to sort 15,000 elements, how long would you expect it to take to sort 30,000 elements?

Question options:

	5 seconds
	10 seconds
	25 seconds
	50 seconds
Question 6		0 / 1 point

The checklist function is shown below:

def checklist(lst) :

if(lst[0] >= lst[len(lst)-1] :

return True

return False

What can you conclude about the running time of this function?

Question options:

	Its running time will be O(n).
	Its running time will be O(n2).
	Its running time will be O(log n).
	Its running time will be O(1).
Question 8		0 / 1 point

Consider the following function, which correctly merges two lists:

def mergeLists(first, second, values) :

iFrist = 0

iSecond = 0

j = 0

while iFirst < len(first) and iSecond < len(second) :

if first[iFirst] < second[iSecond] :

values[j] = first[iFirst]

iFirst = iFirst + 1

else :

values[j] = second[iSecond]

iSecond = iSecond + 1

j = j + 1

while iFrist < len(first) :

values[j] = first[iFirst]

iFirst = iFirst + 1

j = j + 1

while iSecond < len(second) :

values[j] = second[iSecond]

iSecond = iSecond + 1

j = j + 1

What is the big-Oh complexity of this algorithm, where n is the total number of elements in first and second?

Question options:

	O(1)
	O(log(n))
	O(n)
	O(n2)
Question 9		0 / 1 point

The following program is supposed to time the performance of the selectionSort function. Right now it is missing the code, startTime = time(), which records the starting time. Where should the missing code be inserted?

# Line 1

values = []

# Line 2

for i in range(10000) :

values.append(randint(1, 100))

# Line 3

selectionSort(values)

# Line 4

endTime = time()

Question options:

	Line 1
	Line 2
	Line 3
	Line 4
Question 10		0 / 1 point

Selection sort has O(n²) complexity. If a computer can sort 1,000 elements in 4 seconds, approximately how many seconds will it take the computer to sort 1,000 times that many, or 1,000,000 elements?

Question options:

	16
	1,000
	1,000,000
	4,000,000

An algorithm that cuts the work in half in each step is an ____ algorithm.

Question options:

	O(n)
	O(n2)
	O(log n)
	O(n log n)
Question 4		0 / 1 point

Consider the following function for performing a binary search:

def binarySearch(values, low, high, target) :

if low <= high :

mid = (low + high) // 2

if values[mid] == target :

return mid

elif values[mid] < target :

return binarySearch(values, mid + 1, high, target)

else :

return binarySearch(values, low, mid - 1, target)

else :

return -1

How many elements will be visited when values is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], low is 0, high is 9, and target is 10?

Question options:

	0
	2
	4
	10
Question 5		0 / 1 point

Suppose you have a phone number and need to find the address that it corresponds to. If there are 2,000,000 entries, how many do you expect to search in a printed phone directory before finding the address you are looking for?

Question options:

	Approximately 50,000 records
	Approximately 75,000 records
	Approximately 1,000,000 records
	Approximately 1,200,000 records
Question 6		0 / 1 point

Consider the selection sort function and function call shown below:

def selectionSort(values) :

for i in range(len(values)) :

print(values)

minPos = minimumPosition(values, i)

swap(values, minPos, i)

data = [1, 2, 3]

selectionSort(data)

print(data)

What is displayed when this code segment executes?

Question options:

	[]
	[1, 2, 3]
	[3, 2, 1]
	[1, 2, 3] [1, 2, 3] [1, 2, 3] [1, 2, 3]
Question 9		0 / 1 point

Which of the following statements about running times of algorithms is correct?

Question options:

	An algorithm that is O(1) means that only one comparison takes place.
	When determining the running time, constants are not taken into consideration.
	When determining the running time, lower-order terms must be taken into consideration.
	An algorithm that is O(n) means that the number of comparisons does not grow as the size of the list increases.