FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 3: Searching, Sorting, and Complexity Analysis

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 21

True/False

Review LaterAdd Note

Review Later

In the average case, where many items in a list are out of order, an insertion sort is linear.

A) True
B) False

Correct Answer

verified

Show Answer

Question 22

Multiple Choice

Review LaterAdd Note

Review Later

What should the missing code be in the following insertion sort algorithm? i = 1 While i < len(myList) : ItemToInsert = myList[i] J = i - 1 While j >= 0: If itemToInsert < myList[j]: MyList[j + 1] = myList[j] J -= 1 Else: Break < missing code > I += 1

A) myList[ i + 1 ] = itemToInsert
B) myList[ j ] = itemToInsert
C) myList[ j + 1 ] = itemToInsert
D) myList[ i ] = itemToInsert

E) All of the above
F) B) and C)

Correct Answer

verified

Show Answer

Question 23

Multiple Choice

Review LaterAdd Note

Which of the following is a method to estimate the efficiency of an algorithm that predicts the amount of work an algorithm performs regardless of the platform?

Which type of algorithm is analogous to how many people organize playing cards in their hands?

The bubble sort has a complexity of O( n ²).

In terms of complexity, what is the average case for an insertion sort?

Using a binary search, a list of 1 million items requires only 20 comparisons.

What is the best case performance of a sequential search?

A bubble sort always requires approximately n² comparisons.

Algorithms with linear behavior do more work than those with quadratic behavior.

Which method of determining the efficiency of algorithms allows you to rate them independently of timings or instruction counts?

This bubble sort has the effect of bubbling the largest items to the end of the list.

How can the performance complexity of the following algorithm be described? For x in range(numIterations) : Value = value * x Print(value)

In the following code, what is the algorithm's complexity? minIndex = 0 CurrentIndex = 1 While currentIndex < len(lyst) : If lyst[currentIndex] < lyst[minIndex]: MinIndex = currentIndex CurrentIndex += 1 Return minIndex

The sequential search algorithm does more work to find a target at the beginning of a list than at the end of the list.

In terms of complexity, what is the worst-case scenario for an insertion sort?

In a binary search of an ascending order list, where does the search algorithm begin the search?

What should the missing code be in the following algorithm if the goal is to determine how many seconds the algorithm runs? start = time.time() MyCount = 1 For x in range(100) : MyCount *= x Elapsed = time.time() - < missing code >

In the first step of the quicksort, you begin by selecting the item at the list's midpoint.

How many loops are found in a typical insertion sort?