Deck 3: Algorithms

Question 1

Use the definition of big_ to prove that is https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/.

Answer 1

Question 2

Prove or disprove that the greedy algorithm for making change always uses the fewest coins possible when the
denominations available are 1-cent coins, 8-cent coins, and 20-cent coins.

Answer 2

False The algorithm gives change of 25 using 20, 1, 1, 1, 1, 1 (a total of six coins), but it can be done using
8, 8, 8, 1 (a total of only four coins).

Question 3

Use the definition of big- to prove that 1.2+2.3+3.4+...+ . is

Answer 3

Question 4

Use the definition of big- to prove that is

Question 5

Describe an algorithm that takes a list of n integers (n ≥ 1) and finds the location of the last even integer in the list. and returns 0 if there aer no even integers in the list .

Question 6

Show how the binary search algorithm searches for 27 in the following list: 5 6 8 12 15 21 25 31.

Question 7

Express a brute-force algorithm that finds the second largest element in a list a1, a2, . . . , an (n ≥ 2) of distinct integers by finding the largest element, placing it at the beginning of the sequence, then finding the largest element of the remaining sequence.

Question 8

In questions find the best big-O function for the function. Choose your answer from among the following:
1,

Question 9

Express a brute-force algorithm that finds the largest product of two numbers in a list a1, a2, . . . , an (n ≥ 2) that is less than a threshold N .

Question 10

Let . Show that f(n) is https://d2lvgg3v3hfg70.cloudfront.net/TB5530/.find C and k from the definition.

Question 11

In questions find the best big-O function for the function. Choose your answer from among the following:
1,

Question 12

Describe in words how the binary search works.

Question 13

Describe an algorithm that takes a list of integers a1, a2, . . . , an (n ≥ 2) and finds the second-largest integer in the sequence by going through the list and keeping track of the largest and second-largest integer encountered.

Question 14

Use the definition of big- to prove that is

Question 15

Prove or disprove that the greedy algorithm for making change always uses the fewest coins possible when the
denominations available are pennies (1-cent coins), nickels (5-cent coins), and quarters (25-cent coins).

Question 16

Use the definition of big- to prove that is

Question 17

Describe an algorithm that takes a list of n integers (n ≥ 1) and finds the average of the largest and smallest integers in the list.

Question 18

You have supplies of boards that are one foot, five feet, seven feet, and twelve feet long. You need to lay pieces
end-to-end to make a molding 15 feet long and wish to do this using the fewest number of pieces possible.
Explain why the greedy algorithm of taking boards of the longest length at each stage (so long as the total
length of the boards selected does not exceed 15 feet) does not give the fewest number of boards possible.

Question 19

In questions find the best big-O function for the function. Choose your answer from among the following:
1,

Question 20

Describe an algorithm that takes a list of n integers a1, a2, . . . , an and finds the number of integers each greater
than five in the list.

Question 21

Arrange the functions and in a list so that each function is big- of the next function .

Question 22

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
A binary search of n elements.

Question 23

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
An algorithm that prints all bit strings of length n.

Question 24

Show that

Question 25

In questions find the best big-O function for the function. Choose your answer from among the following:
1,

Question 26

Find the best

Question 27

Arrange the following functions in a list so each is big- of the next one in the list:

Question 28

Find all pairs of functions in this list that are of the same order: ,

Question 29

Find the

Question 30

Prove that is https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/.

Question 31

Show that

Question 32

In questions find the best big-O function for the function. Choose your answer from among the following:
1,

Question 33

Prove that

Question 34

Suppose you have two different algorithms for solving a problem. To solve a problem of size the first algorithm uses exactly operations and the second algorithm uses exactly log operations. As grows, which algorithm uses fewer operations?

Question 35

Prove that

Question 36

Arrange the following functions in a list so each is big- of the next one in the list: log , log log log

Question 37

In questions find the best big-O function for the function. Choose your answer from among the following:
1,

Question 38

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
A linear search to find the smallest number in a list of n numbers.

Question 39

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
The number of print statements in the following:

Question 40

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
An algorithm that lists all ways to put the numbers 1, 2, 3, . . . , n in a row.

Question 41

assume that the number of multiplications of entries used to multiply a p × q and a q × r matrix is
pqr.
Whatand 7 ×is 3,therespbestectivorderely?to form the product ABC if A, B and C are matrices with dimensions 2 × 5, 5 × 7

Question 42

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
An algorithm that finds the average of n numbers by adding them and dividing by n.

Question 43

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,

Question 44

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
The number of print statements in the following:

Question 45

assume that the number of multiplications of entries used to multiply a p × q and a q × r matrix is
pqr.
What is the most efficient way to multiply the matrices

Question 46

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
An algorithm that prints all subsets of size three of the set {1, 2, 3, . . . , n}.

Question 47

assume that the number of multiplications of entries used to multiply a p × q and a q × r matrix is
pqr.
Whatand 6 ×is 12,therespbestectivorderely?to form the product ABC if A, B and C are matrices with dimensions 8 × 3, 3 × 6

Question 48

Give a big-O estimate for the number of operations (where an operation is an addition or a multiplication)
used in this segment of an algorithm:

Question 49

assume that the number of multiplications of entries used to multiply a p × q and a q × r matrix is
pqr.
What is the most efficient way to multiply the matrices

Question 50

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
The best-case analysis of a linear search of a list of size n (counting the number of comparisons).

Question 51

Give a big-O estimate for the number of operations (where an operation is an addition or a multiplication)
used in this segment of an algorithm:

Question 52

In questions find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
1,
The worst-case analysis of a linear search of a list of size n (counting the number of comparisons).