Test 1

Question 1

When confronted with a new ___________ , there may be several possible solutions.

Answer 1

problem

Question 2

A __________ is a question which requires an answer.

Answer 2

problem

Question 3

A problem usually includes variables, called __________.

Answer 3

parameters

Question 4

What is an algorithm?

Answer 4

A step - by- step procedure to solve all instances of a problem.

Question 5

What are problems of an algorithm?

Answer 5

Difficult for complex algorithms

Hard to translate to a programming language

Question 6

It is possible for sequential search to examine _______ element before solving the problem . It can be used whether the array is sorted or not.

Answer 6

every

Question 7

A much faster algorithm is available if the array is sorted:

Answer 7

Binary Search

Question 8

works by comparing x with the middle of the array. The algorithm then “ discards” either the first or second half of the array .

Answer 8

Binary search

Question 9

It can be shown by mathematical induction that the recursive version performs approximately _________ operations.

Answer 9

2 ^ (n / 2)

Question 10

The iterative version if recursion performs ____ operations.

Answer 10

n + 1

Question 11

when the basic operation is done the same number of times for every instance of size n. In algorithm 1.2 (sum of array values), T(n) = n

Answer 11

Every-Case Time Complexity

Question 12

when the amount of work performed by the algorithm depends on the values of other parameters. W(n) is the largest number of times the basic operation will be performed for an instance of size n. In algorithm (sequential search) W(n) = n

Answer 12

Worst-Case Time Complexity

Question 13

When analyzing the Complexity of an algorithm, it is useful to observe some simplifying abstractions:

Answer 13

Do not worry about actual CPU time

Determine the number of times a basic operation is done as a function of n (the size of the input)

The total amount of work done by the algorithm is proportional to the number of times the basic operation is performed .

Question 14

Once we determine the number of operations performed as a function of n(T (n) or W(n)) , we are interested in classifying algorithms according to their ________ or ____________ class.

Answer 14

order

complexity

Question 15

Algorithms with time complexities such as n,100n, and 50n + 10 are called ____________ algorithms

Answer 15

linear -time

Question 16

Algorithms with time complexities such as n ^ 2, 0.5n ^ 2 , and n ^ 2 + 10n + 1 are called _____________ algorithms

Answer 16

quadratic-time

Question 17

Any linear -time algorithm is ______________________ than any quadratic-time algorithm.

Answer 17

eventually more efficient

Question 18

In order to define order formally, it is useful to define a similar concept:

Answer 18

Big O notation.

Question 19

Big notation is used to establish an _____________ on the growth of a function .

Answer 19

upper bound

Question 20

Big Theta is defined in a similar way as Big O, except that it provides both _______ (big O ) and ______ (big Omega) bounds on the growth of the function

Answer 20

upper

lower

Question 21

What is wrong with an algorithm such as Exchange ( Bubble ) Sort?

Answer 21

Usually, the least efficient of all sorting algorithms , because of the excessive number of swap operations

Exchange sort requires n - 1 major loop iterations, and up to n - 1 swaps in each iteration, resulting in a worst case of sim n^ 2 element swaps!!

Question 22

This sorting causes each iteration, selection sort. Finds the smallest entry in the unsorted portion of the array , and Swaps it with the element in the corresponding position.

Answer 22

Selection sorting

Question 23

This type of sorting works by extending the length of the sorted portion one step at a time:
After zero iterations, A[1] is sorted After one iteration, A[1..2] is sorted After two iterations, A[1..3] is sorted After three iterations A[1.4] is sorted, and so on, until A[1..N] is sorted .

Answer 23

Insertion sorting

Question 24

For a list of length n, an average selection sort makes about key comparisons and exactly ______ swap operations .

Answer 24

n - 1

Question 25

Selection sort is not affected by the __________ of the array elements.

Answer 25

original order

Question 26

The insertion sort is particularly appropriate for small arrays that are _____________

Answer 26

nearly sorted

Question 27

The divide -and-conquer strategy solves a problem by:

Answer 27

1. Breaking it into subproblems that are themselves smaller instances of the same type of problem
2. Recursively solving these subproblems
3. Appropriately combining their answers

Question 28

Finds the middle element, if one exists If target is equal to middle element Target found , return location

Answer 28

Recursive binary search

Question 29

What do you do if the recursive binary search hits an else?

Answer 29

1. DIVIDE the array into two smaller subarrays . Choose either left or right subarray , AND
2. CONQUER by recursively applying binary search to the smaller subarray .
3. OBTAIN overall solution from subarray result.

Question 30

Let ____ be the number comparisons performed by recursive binary search for an array of size n. ____ can be expressed with a recurrence relation:

Answer 30

W(n)-worst case time complexity

Question 31

Given an array with n items, Mergesort involves three steps:

Answer 31

1. Divide the array into two subarrays each with n / 2 items
2. Conquer (solve) each subarray by sorting it.
3. Unless the array is sufficiently small, use recursion to do this Combine the solutions to the subarrays by merging them into a single sorted array

Question 32

Mergesort uses additional storage: an array of the _______ as the one being ________

Answer 32

same size

sorted

Question 33

Quicksort is another sort based on the ______________ pattern .

Answer 33

divide-and-conquer

Question 34

Quicksort the most efficient general sorting algorithm in existence for _____________.

Answer 34

random arrays

Question 35

Quicksort worst-case time complexity is:

Answer 35

O(n ^ 2)

Question 36

For Quicksort, the worst-case time complexity of Theta(n ^ 2) occurs when the array is:

Answer 36

already sorted!!

Question 37

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist ). This algorithm offers guaranteed n log (n) performance .

Answer 37

Collections.sort()

Question 38

The sorting algorithm is a tuned quicksort , adapted from Jon L. Bentley and M. Douglas Mcllroy. This algorithm offers n^ * log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance .

Answer 38

Arrays.sort()

Question 39

In a _________________ solution, the “basic operationsto be counted are usually performed as part of recursive calls.

Answer 39

Divide-and-Conquer

Question 40

It is essential to formulate a recursive definition to “_______” basic operations :

Answer 40

count

Question 41

A useful alternative in estimating Big theta complexity is to use the _________________ whenever we have a recurrence relation of the form:

Answer 41

Master Theorem

Question 42

The master theorem is:

Answer 42

T(n) = a * T(n/b) + f(n)