Someone has recently moved into an office with two bookshelves of equal length and wants to work out whether they can fit all their books into the bookshelves, in their intended orientation, without splitting individual books. Once they have checked that the height and depth of each book is such that it will fit into the bookshelves, they only need to consider the widths of the books and the lengths of the bookshelves. For example, if the shelves were each of length 3, then even though the total shelf length is 6, 3 books each of length 2 would not fit without splitting an individual book.

When they measured the length of each bookshelf, they discovered them to be of length 12 units. They have 5 books, and when they measure the widths of them, in the same units, they discover them to be of widths 3, 4, 4, 5 and 8 (in the order in which they measure them). As these values sum to 24, they realize that if they can fit some books exactly into one shelf, the other books will fit exactly into the other shelf, so they want to check whether it is possible to select some books such that the sum of book widths is 12.

A dynamic programming approach can be used to work out whether this is possible. The approach would construct a table, with one column for each book, (considering the books in the order of measuring), and one row for each possible sum of book widths from 0 up to 12. Each entry in the table would be either T (for true) to indicate that it is possible to obtain that sum of book widths by selecting from the books up to and including the book of the column, or F (for false) to indicate that it is not. (Note that a selection may be none, some, or all, of the relevant books.)

Starting with the table below, which of the following formulae would give the correct entry (True or False) for the table cell T[r][c]? (where r is the row corresponding to a given length, and c is the column corresponding to a book, W[c] is the width of the book at column c)

Width of Shelf	Book 1 (width 3)	Book 2 (width 4)	Book 3 (width 4)	Book 4 (width 5)	Book 5 (width 8)
0	T	T	T	T	T
1	F
2	F
3	T
4	F
5	F
6	F
7	F
8	F
9	F
10	F
11	F
12	F

Question 1 options:

T[r][c] = (T[r-W[c]][c-1] || T[r][c-1])

T[r][c] = (T[r-W[c]][c-1] && T[r][c-1])

T[r][c] = (T[r-W[c]][c-1] || T[r-1][c])

T[r][c] = (T[r][c-W[c]] || T[r][c-1])

T[r][c] = (T[r][c-W[c]] && T[r][c-1])

Question 2 (1 point)

What is the algorithm design technique utilized by the binary search algorithm?

Question 2 options:

Search

Greedy

Dynamic Programming

Divide and Conquer

Question 3 (1 point)

Whats it the algorithm design strategy utilised by Prim's algorithm?

Question 3 options:

Greedy

Divide and Conquer

Dynamic Programming

Search

Question 4 (1 point)

What is the algorithm design technique utilized by the Floyd Warshall all-pairs shortest path algorithm?

Question 4 options:

	Greedy
	Divide and Conquer
	Dynamic Programming
	Search