Note: This lab assignment contains a multiple choice quiz and a coding portion. Submit your quiz answers to the lab 9 Canvas quiz and your code to the autograder. You will have three attempts on the quiz.

You MUST include the following assignment identifier at the top of every file you submit to the autograder as a comment. This includes all source files, header files, and your Makefile (if there is one). If there is no autograder assignment, you may ignore this.

Assignment Identifier: 472D3C8289DE4915774A47683EC45FFBA373B980

Part A: Graphs and Searching Algorithms (3 points)

For questions 1-2, use the graph below:

9.1 Running Prims Algorithm (0.5 points)

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

1. 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
2. 7, 2, 5, 4, 0, 3, 1, 6

9.2 Running Kruskals Algorithm (0.5 points)

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

1. 1, 4, 9, 2, 3, 5, 7 B. 1, 2, 4, 5, 3, 9, 7 C. 1, 2, 4, 3, 5, 7, 9
2. 1, 2, 3, 4, 5, 7, 9
3. 1, 2, 3, 4, 5, 6, 7, 8, 9

9.3 Finding Your Flight (0.5 points)

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?

1. (1)
2. (E )
3. (V )
4. (1 + E/V )
5. (V ²)

9.4 Stacks and Queues (0.75 points)

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

1. a stack is a good data structure to use for a depth-first search (DFS)
2. a stack is a good data structure to use for a breadth-first search (BFS)
3. a stack is a good data structure for conducting a level-order traversal of a binary tree
4. a queue is a good data structure to use for a depth-first search (DFS)
5. a queue is a good data structure to use for a breadth-first search (BFS)
6. a queue is a good data structure for conducting a level-order traversal of a binary tree

9.5 Memory Trees (0.75 points)

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.

1. if you conduct a depth-first search for k, youll never have to store more than 281 nodes in memory
2. if you conduct a breadth-first search for k, youll never have to store more than 281 nodes in memory
3. if you are concerned about the memory efficiency of the search, you should use a queue to conduct this search instead of a stack
4. 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
5. 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 (10 points)

9.6 Number of Islands (10 points)

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:

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

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

oooooooo.oo

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

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

.ooo.ooo oooooooo.oo

Implement your solution in the islands.h starter file provided. You can download the file on either Canvas or GitLab. To submit to the autograder, create a .tar.gz file containing just islands.h by running the following command:

tar -czvf lab9.tar.gz islands.h ( you can also run make fullsubmit using the Makefile we provide)

If you are working with a partner, both partners must submit to the autograder. Only students who submit code to the autograder will receive points. Its fine if both of you submit the same code for this assignment. If you do end up working with a partner, make sure to put both of your names at the top of the file you are submitting.

Hints (try to work the problem on your own before you look at this)

The purpose of this exercise is to give you practice with graph searching algorithms (BFS and DFS) before the final exam. There are two primary methods that you can use to solve this problem: either by using a breadth-first search (BFS) or a depth-first search (DFS). A summary of the algorithm is as follows:

1. Initialize a counter to keep track of the number of islands.
2. Iterate over every cell of the 2-D vector (a double for loop is okay).
3. If the cell you are currently visiting is a land character (o):

Increment your counter by one.

Mark the cell as visited. (You do not need to create a separate container to keep track of whether a cell has been visited or not! Hint: you can directly modify the values in the map.)

Complete a BFS or DFS of the entire island you are on. To do this, push any adjacent land locations into a queue or stack (make sure that you arent accessing out of bounds). In other words, you would push into a queue or stack the coordinates directly to your north, east, south, and west, as long as they are also land locations. Mark any coordinates as visited, if necessary. If you are doing a DFS, you can either explicitly initialize a std::stack or use recursion, which utilizes the program stack.

After the BFS or DFS is complete, continue iterating the 2-D vector. Keep on repeating steps 2 and 3 until the entire 2-D vector is processed.

You do not need to solve this problem using both BFS and DFS, but you are encouraged to practice both algorithms for the exam (since you may get a problem that can only be solved using one method and not the other).