EECS281-Lab 9 Solved

Part A: Graphs and Searching Algorithms  
 

 

For questions 1-2, use the graph below:

 

9.1 - Running Prim’s Algorithm  
 

What is the sequence of vertices added to the MST for the graph above when running Prim’s algorithm, if you start with vertex 7?

A. 7, 2, 0, 5, 1, 3, 4, 6 B. 7, 2, 0, 5, 3, 1, 6, 4 C. 7, 2, 0, 3, 5, 1, 6, 4 D. 7, 2, 5, 4, 0, 1, 3, 6

            E.      7, 2, 5, 4, 0, 3, 1, 6

 

9.2 - Running Kruskal’s Algorithm  
 

What is the sequence of edges added to the MST for the graph above when running Kruskal’s algorithm? Use the edges’ weights as their label for this question.

A. 1, 4, 9, 2, 3, 5, 7 B. 1, 2, 4, 5, 3, 9, 7 C. 1, 2, 4, 3, 5, 7, 9

D.     1, 2, 3, 4, 5, 7, 9

E.      1, 2, 3, 4, 5, 6, 7, 8, 9 

9.3 - Finding Your Flight  
 

You currently have a graph that represents several airports (vertices) and the flights that connect these airports (edges), weighted by the distance of each flight. You decide to implement this graph using an adjacency list. Let ​V represent the number of vertices in this graph, and let ​E represent the number of edges. If you are given an airport ​X​, what is the worst-case time complexity of determining if ​any​ flights depart from airport ​X​?

A.     Θ(1)

B.      Θ(E​​ ​)

C.      Θ(V​​ ​)

D.     Θ(1 + ​E​/​V​ ​)

E.      Θ(V​​ ​2)​

 

9.4 - Stacks and Queues
 

Which of the following statements is/are ​true​? ​Select all that apply. 

A.     a stack is a good data structure to use for a depth-first search (DFS)

B.      a stack is a good data structure to use for a breadth-first search (BFS)

C.      a stack is a good data structure for conducting a level-order traversal of a binary tree

D.     a queue is a good data structure to use for a depth-first search (DFS)

E.      a queue is a good data structure to use for a breadth-first search (BFS)

F.      a queue is a good data structure for conducting a level-order traversal of a binary tree

 

9.5 - Memory Trees  
 

Suppose you have a binary tree of height 281, where leaf nodes have height 1, and you want to search for an element ​k​. You know that ​k exists as a distinct element in this tree, and that it is a leaf node. Which of the following statements is/are ​true​? Select all that apply.

A.     if you conduct a depth-first search for ​k​, you’ll never have to store more than 281 nodes in memory

B.      if you conduct a breadth-first search for ​k​, you’ll never have to store more than 281 nodes in memory

C.      if you are concerned about the memory efficiency of the search, you should use a queue to conduct this search instead of a stack

D.     the path from the root to the element ​k returned by a breadth-first search will always be shorter than the path returned by a depth-first search

E.      while a breadth-first search will always find the element ​k​, it is possible that a depth-first search may fail to find ​k​ since depth-first searches do not always visit every element 

 

  

Part B: Coding Assignment  
9.6 - Number of Islands  
 

In this problem, you will be implementing the ​number_of_islands() function, as shown below:​      

 

   int​ number_of_islands​(​std​::​vector​<​std​::​vector​<char>​>&​ grid​);

 

This function takes in a 2-D grid map filled with land (represented using the character ​'o')​ and water (represented using the character ​'.')​ and ​returns the number of islands that exist in the map. ​An island is formed by connecting adjacent land characters either horizontally or vertically. In other words, if two land characters are adjacent to each other horizontally or vertically, then they are a part of the same island.  

 

Example: ​Given the following 2-D map:

 

o...oo.ooo.ooooo. .ooo.oo..oo..oooo ...o.o.ooo.....oo oo.ooo..oooo..o.. 

o....o....ooooo.o ooo....oooo....oo ....ooooo...ooo.o ooo.oo.oooo.o.ooo .ooo....oo......o 

...oooooo...oo.oo 

 

           the ​number_of_islands() function should return 7, since there are 7 islands in this map:​       

 

o​...​oo​.​ooo​.​ooooo​. .​ooo​.​oo​..​oo​..​oooo ...​o​.​o​.​ooo​.....​oo oo​.​ooo​..​oooo​..​o​.. o​....​o​....​ooooo​.​o ooo​....​oooo​....​oo ....​ooooo​...​ooo​.​o ooo​.​oo​.​oooo​.​o​.​ooo 

.​ooo​....​oo​......​o ...​oooooo​...​oo​.​oo