Grids, graphs and big numbers

Questions 1 to 5 of 7

1. 1. Which statements about a full breadth-first search over an R by C grid, where every cell is reached, are correct?

   Pick every answer that is true.

   The cost is O(R × C)A 3 by 4 grid has 12 cells, and each cell is taken off the queue onceThe cost is O(R + C), because the search only walks one row and one columnEach cell makes four neighbour checks
2. 2. The graph in the lesson has 5 vertices and the edges 0-1, 0-2, 1-2 and 2-3. Which statements about its storage are correct?

   Pick every answer that is true.

   The adjacency list stores 8 entriesThe adjacency matrix stores 25 cellsReading the neighbours of vertex 3 from the list reads 1 entryReading the neighbours of vertex 3 from the matrix reads 2 cells, one for each neighbour
3. 3. Which statements about adding and multiplying two numbers with n decimal digits each, using the digit model from the lesson, are correct?

   Pick every answer that is true.

   Adding them takes about n digit stepsMultiplying them with schoolbook multiplication takes about n digit productsMultiplying them takes about n times n digit productsEvery 64-bit number has at most 20 decimal digits
4. 4. A full breadth-first search over a graph with an adjacency list costs about O(____).

   Type your answer.

5. 5. The growth rate of schoolbook multiplication of two numbers with n digits each is n to the power of ____.

   Type your answer.