Deck 3: A: Algorithms

Question 1

Express a brute-force algorithm that finds the second largest element in a list a1, a2, . . . , an 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.

Answer 1

procedure secondmax(a1, a2, . . . , an : integers)

Question 2

Describe in words how the binary search works.

Answer 2

To search for x in an ordered list a1, . . . , an, find the "midpoint" of the list and choose the appropriate half of the list. Continue until the list consists of one element. Either this element is x, or else x is not in the list.

Question 3

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.

Answer 3

The greedy algorithm first chooses a 12-foot-long board, and then three one-foot-long boards. This requires four boards. But only three boards are needed: each five feet long.

Question 4

Use the definition of big-O to prove that

Question 5

Describe an algorithm that takes a list of n integers and finds the location of the last even integer in the list, and returns 0 if there are no even integers in the list.

Question 6

Describe an algorithm that takes a list of integers a1, a2, . . . , an 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 7

List all the steps that the naive string matcher uses to match the pattern xy in the text yxyxxy.

Question 8

List all the steps that insertion sort uses to sort 8, 20, 13, 16, 9

Question 9

Use the definition of big-O to prove that

Question 10

Use the definition of big-O to prove that

Question 11

Prove or disprove that the cashier's 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.

Question 12

Use the definition of big-O to prove that is

Question 13

Describe an algorithm that takes a list of n integers and finds the average of the largest and smallest

Question 14

Prove or disprove that the cashier's 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 15

List all the steps that bubble sort uses to sort 8, 20, 13, 16, 9

Question 16

List all the steps the binary search algorithm uses to search for 27 in the following list: 5, 6, 8, 12, 15, 21, 25, 31.

Question 17

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 18

Let

Question 19

Use the definition of big-O to prove that

Question 20

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 21

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

Question 22

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

Question 23

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

Question 24

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

Question 25

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

Question 26

Show that

Question 27

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

Question 28

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

Question 29

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

Question 30

Find the best big-O function for

Question 31

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

Question 32

Find the best big-O function for

Question 33

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

Question 34

Prove that

Question 35

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

Question 36

Show that

Question 37

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

Question 38

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

Question 39

Prove that

Question 40

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

Question 41

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 A1, A2, A3 of sizes 10 × 50, 50 × 10, 10 × 40?

Question 42

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

Question 43

find the "best" big-O notation to describe the complexity of the algorithm. Choose your
answers from the following:
An iterative algorithm to compute n!, (counting the number of multiplications)

Question 44

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

Question 45

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

Question 46

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 A1, A2, A3 of sizes 20 × 5, 5 × 50, 50 × 5?

Question 47

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 48

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

Question 49

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

Question 50

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

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

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

Question 53

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

Question 54

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