CSCI 1933 Lab 7 Search Algorithms, Binary Trees, and Binary Search Trees Procedures for Lab Labs...

Transcribed Image Text:

CSCI 1933 Lab 7 Search Algorithms, Binary Trees, and Binary Search Trees Procedures for Lab Labs will be run asynchronously with the exception of those in Section 2. Attendance at your scheduled lab section is strongly encouraged, but not required in order to accommodate for those who may not be comfortable meeting in person. You are strongly encouraged to work with a partner within your lab section. The TAs will assist you in finding one, if needed. Have a TA evaluate your progress on each milestone before you move onto the next. The labs are designed to be mostly completed by the end of the lab. If you are unable to complete all of the milestones by the end of the lab, you will have up until 10:00 p.m. CDT on the Monday following the release of the lab to have any remaining milestones graded (on Discord) by a TA during office hours. We suggest you get your milestones checked off as soon as you complete them since office hours tend to become extremely crowded close to the deadline. You will only receive credit for the milestones you have checked off by a TA. Regrades of a milestone are available but only if submitted before the last office hours on the following Monday. There is nothing to submit to Canvas for this lab. Introduction This lab is made up of three labs from the Spring semester, and as a result covers a wide array of topics. Milestone 1 covers common searching algorithms Breadth First Search (BFS) and Depth First Search (DFS). For this milestone, the file Test.java is provided. BFS and DFS are typically applied to graphs and trees and work in different ways to achieve a similar result. BFS starts from the starting vertex/node and traverses outwards in a level by level fashion (visiting all reachable vertices/nodes on each iteration). DFS starts from the starting vertex/node and traverses as far as possible in one direction then backs up until it can go in another direction as deep as possible. Test.java will be used to make sure your solution to milestone 1 is implemented correctly. Milestones 2-3 focus on the binary tree data structure. You will be provided two files: Node.java and BinaryTree.java. Node.java contains a baseline implementation of a binary tree node. BinaryTree.java contains a code skeleton that you will need to fill out. Both Node.java and BinaryTree.java are implemented using generics that extend Comparable. Milestone 4 introduces Binary Search trees, which define the notion of a "sorted" binary tree. This milestone uses an array implementation of binary trees, and therefore uses a different source file, BinaryTreeArray.java. CSCI 1933 LAB 7 Note: BinaryTree.java's main method contains tests for milestones 2-3 to verify that your solution is correct. Un-comment these tests as you move through each milestone. These tests should not be modified. Likewise, BinaryTreekrray.java's main method contains tests for milestone 4. 1 Color Path While it may not seem immediately obvious, a 2D array/grid problem can be translated to a graph problem. We can imagine each index (row, column) in a given 2D array/grid to be a vertex/node of a graph. Let's explore a problem related to this: Given a positive 2D array of integers, inage, each integer in the array represents a color. Given a row and column index (row, column) and a new color integer (newColor), you must update the given index [row, column] in the color array (image) to the newColor and all reachable neighbors that are same color as image [row, column] to newColor. If a reachable neighbor is not the same color as the original source vertex color, you must NOT update it. Note: A reachable neighbor is one that is in one of the four cardinal directions (left, down, up, or right) from the current index/vertex. For this milestone, you must create a class called ColorPath.java. Within this class you must implement the following three functions: colorPath(), bfs (), and dfs(). The method signature of colorPath should be public static int00 colorPath(int 00 inage, int sourceRow, int sourceCol, int neuColor). You will need to decide what arguments are necessary for the search algorithms, although their implementation is described in detail below. Example Image with row = 1, column= 1, newColor = 2: (left is before, right is after Color Path has been executed) 111 100 000 011 1. COLOR PATH CSCI 1933 LAB 7 All reachable neighbors of the coordinate (1, 1) that were the same as the original color (0) became the new color (2). Also notice that all reachable neighbors of the reachable neighbors that had the original color (0) were modified as well. 111 12 2 2 2 2 211 11100 10011 00111 01123 33000 2 Example Image with row 1, column 1, nowColor 2: (left is before, right is after Color Path has been executed) 11100 12211 2 2 1 11 21123 33000 1. COLOR PATH Similarly, all reachable neighbors of the original coordinate (1, 1) are updated. However, the non reachable vertexes with the original color (0) are not updated since they are not reachable in the context of our problem. Hopefully you notice that the problem involves traversing through reachable neighbors from the starting index and continues on until we reach a stopping point. In this problem, we could define the stopping point as either out of the bounds of the array or at a color that does not match the original. Let's examine each search algorithm in the context of our problem: BFS: A BFS implementation would start from the given index (1, 1) then visit/update each reach- able neighbor that matches the original color (1, 2) and (2, 1) to newColor. Then it would continue to visit each reachable neighbor of these spots and do the same until there are no more valid, reachable neighbors to visit (ex. visit the neighbor above then the right, then bottom, then left; checking if color matches for each visit). DFS: A DFS implementation would start from the given index (1, 1) then visit/update a reachable neighbor and continue following that direction (ex. try to go down as far as possible, then left, then up, then right). There is no requirement on the ordering of the directions as long as you visit all four a single time from each vertex. Note: One important thing that applies to both algorithms is that we need to ensure we do not continue to visit nodes we have already visited. In this problem, we do not have to worry about this since we are updating each new vertex to a new color. Since we have defined a new color as a stopping point, when the algorithm circles around to check the position again, it will not try to revisit this vertex. Consider what would happen if we did continue to revisit vertices. 3 Note: What might happen if we try to update a vertex to a newColor if newColor is the same as the color that is currently there and there is at least one reachable neighbor? Hint: Consider the note above. CSCI 1933 LAB: Now for the fun part. Outlined below are the pseudo code algorithms for how to implement BFS and DFS on a 2D array/grid. Implement both a DFS and BFS solution to solve this Color Path problem. Note that these are pseudo code algorithms that represent general BFS/DFS. You may need to modify the parameters that these algorithms take in in order to accomplish the goal of colorPath. 1: function BFS (arr, row, col) 2: Instantiate an empty queue of index pairs (integer arrays) 3 Add the starting (row, col) pair as an integer array to the queue. 4 Sc 8: 9 10: 11: 12: 13: 15: 16: 17: 18 19 while Queue is notempty do remove current indices from the front of the queue if left indices are in bounds and not visited then add left neighbor indices to queue end if if right indices are in bounds and not visited then add right neighbor indices to queue end if if below indices are in bounds and not visited then add below neighbor indices to queue end if 1. COLOR PATH if above indices are in bounds and not visited then add above neighbor indices to queue end if end while 21: end function Note: BFS: The queue is an interface in Java and should be implemented using one of the classes that implements this interface such as LinkedList: Queue queue = new LinkedList (). This will require the following import statement at the top of your files import java.util."; Note: BFS: You will need to keep in mind that in the context of our problem, you should only add to the queue if the color of that neighbor matches the original color of the starting vertex. 1: function DFS(arr, row, col) 2: if row/column are out of bounds or vertex is visited then stop recursion 3: end if Recursively call DFS() with each directional neighbor 4 & end function CSCI 1933 LAB 7 2. TRAVERSING Note: DFS: You will need to keep in mind that in the context of our problem, you should stop recursion if the color of the neighbor does not match the original color of the starting vertex Milestone 1: After creating ColorPath.java and implementing the methods colorPath(), bra(), and dfa(), need to run the provided test file Test java to show that your functions work correctly. - < CSCI 1933 Lab 7 Search Algorithms, Binary Trees, and Binary Search Trees Procedures for Lab Labs will be run asynchronously with the exception of those in Section 2. Attendance at your scheduled lab section is strongly encouraged, but not required in order to accommodate for those who may not be comfortable meeting in person. You are strongly encouraged to work with a partner within your lab section. The TAs will assist you in finding one, if needed. Have a TA evaluate your progress on each milestone before you move onto the next. The labs are designed to be mostly completed by the end of the lab. If you are unable to complete all of the milestones by the end of the lab, you will have up until 10:00 p.m. CDT on the Monday following the release of the lab to have any remaining milestones graded (on Discord) by a TA during office hours. We suggest you get your milestones checked off as soon as you complete them since office hours tend to become extremely crowded close to the deadline. You will only receive credit for the milestones you have checked off by a TA. Regrades of a milestone are available but only if submitted before the last office hours on the following Monday. There is nothing to submit to Canvas for this lab. Introduction This lab is made up of three labs from the Spring semester, and as a result covers a wide array of topics. Milestone 1 covers common searching algorithms Breadth First Search (BFS) and Depth First Search (DFS). For this milestone, the file Test.java is provided. BFS and DFS are typically applied to graphs and trees and work in different ways to achieve a similar result. BFS starts from the starting vertex/node and traverses outwards in a level by level fashion (visiting all reachable vertices/nodes on each iteration). DFS starts from the starting vertex/node and traverses as far as possible in one direction then backs up until it can go in another direction as deep as possible. Test.java will be used to make sure your solution to milestone 1 is implemented correctly. Milestones 2-3 focus on the binary tree data structure. You will be provided two files: Node.java and BinaryTree.java. Node.java contains a baseline implementation of a binary tree node. BinaryTree.java contains a code skeleton that you will need to fill out. Both Node.java and BinaryTree.java are implemented using generics that extend Comparable. Milestone 4 introduces Binary Search trees, which define the notion of a "sorted" binary tree. This milestone uses an array implementation of binary trees, and therefore uses a different source file, BinaryTreeArray.java. CSCI 1933 Lab 7 Search Algorithms, Binary Trees, and Binary Search Trees Procedures for Lab Labs will be run asynchronously with the exception of those in Section 2. Attendance at your scheduled lab section is strongly encouraged, but not required in order to accommodate for those who may not be comfortable meeting in person. You are strongly encouraged to work with a partner within your lab section. The TAs will assist you in finding one, if needed. Have a TA evaluate your progress on each milestone before you move onto the next. The labs are designed to be mostly completed by the end of the lab. If you are unable to complete all of the milestones by the end of the lab, you will have up until 10:00 p.m. CDT on the Monday following the release of the lab to have any remaining milestones graded (on Discord) by a TA during office hours. We suggest you get your milestones checked off as soon as you complete them since office hours tend to become extremely crowded close to the deadline. You will only receive credit for the milestones you have checked off by a TA. Regrades of a milestone are available but only if submitted before the last office hours on the following Monday. There is nothing to submit to Canvas for this lab. Introduction This lab is made up of three labs from the Spring semester, and as a result covers a wide array of topics. Milestone 1 covers common searching algorithms Breadth First Search (BFS) and Depth First Search (DFS). For this milestone, the file Test.java is provided. BFS and DFS are typically applied to graphs and trees and work in different ways to achieve a similar result. BFS starts from the starting vertex/node and traverses outwards in a level by level fashion (visiting all reachable vertices/nodes on each iteration). DFS starts from the starting vertex/node and traverses as far as possible in one direction then backs up until it can go in another direction as deep as possible. Test.java will be used to make sure your solution to milestone 1 is implemented correctly. Milestones 2-3 focus on the binary tree data structure. You will be provided two files: Node.java and BinaryTree.java. Node.java contains a baseline implementation of a binary tree node. BinaryTree.java contains a code skeleton that you will need to fill out. Both Node.java and BinaryTree.java are implemented using generics that extend Comparable. Milestone 4 introduces Binary Search trees, which define the notion of a "sorted" binary tree. This milestone uses an array implementation of binary trees, and therefore uses a different source file, BinaryTreeArray.java. CSCI 1933 LAB 7 Note: BinaryTree.java's main method contains tests for milestones 2-3 to verify that your solution is correct. Un-comment these tests as you move through each milestone. These tests should not be modified. Likewise, BinaryTreekrray.java's main method contains tests for milestone 4. 1 Color Path While it may not seem immediately obvious, a 2D array/grid problem can be translated to a graph problem. We can imagine each index (row, column) in a given 2D array/grid to be a vertex/node of a graph. Let's explore a problem related to this: Given a positive 2D array of integers, inage, each integer in the array represents a color. Given a row and column index (row, column) and a new color integer (newColor), you must update the given index [row, column] in the color array (image) to the newColor and all reachable neighbors that are same color as image [row, column] to newColor. If a reachable neighbor is not the same color as the original source vertex color, you must NOT update it. Note: A reachable neighbor is one that is in one of the four cardinal directions (left, down, up, or right) from the current index/vertex. For this milestone, you must create a class called ColorPath.java. Within this class you must implement the following three functions: colorPath(), bfs (), and dfs(). The method signature of colorPath should be public static int00 colorPath(int 00 inage, int sourceRow, int sourceCol, int neuColor). You will need to decide what arguments are necessary for the search algorithms, although their implementation is described in detail below. Example Image with row = 1, column= 1, newColor = 2: (left is before, right is after Color Path has been executed) 111 100 000 011 1. COLOR PATH CSCI 1933 LAB 7 All reachable neighbors of the coordinate (1, 1) that were the same as the original color (0) became the new color (2). Also notice that all reachable neighbors of the reachable neighbors that had the original color (0) were modified as well. 111 12 2 2 2 2 211 11100 10011 00111 01123 33000 2 Example Image with row 1, column 1, nowColor 2: (left is before, right is after Color Path has been executed) 11100 12211 2 2 1 11 21123 33000 1. COLOR PATH Similarly, all reachable neighbors of the original coordinate (1, 1) are updated. However, the non reachable vertexes with the original color (0) are not updated since they are not reachable in the context of our problem. Hopefully you notice that the problem involves traversing through reachable neighbors from the starting index and continues on until we reach a stopping point. In this problem, we could define the stopping point as either out of the bounds of the array or at a color that does not match the original. Let's examine each search algorithm in the context of our problem: BFS: A BFS implementation would start from the given index (1, 1) then visit/update each reach- able neighbor that matches the original color (1, 2) and (2, 1) to newColor. Then it would continue to visit each reachable neighbor of these spots and do the same until there are no more valid, reachable neighbors to visit (ex. visit the neighbor above then the right, then bottom, then left; checking if color matches for each visit). DFS: A DFS implementation would start from the given index (1, 1) then visit/update a reachable neighbor and continue following that direction (ex. try to go down as far as possible, then left, then up, then right). There is no requirement on the ordering of the directions as long as you visit all four a single time from each vertex. Note: One important thing that applies to both algorithms is that we need to ensure we do not continue to visit nodes we have already visited. In this problem, we do not have to worry about this since we are updating each new vertex to a new color. Since we have defined a new color as a stopping point, when the algorithm circles around to check the position again, it will not try to revisit this vertex. Consider what would happen if we did continue to revisit vertices. 3 Note: What might happen if we try to update a vertex to a newColor if newColor is the same as the color that is currently there and there is at least one reachable neighbor? Hint: Consider the note above. CSCI 1933 LAB 7 Note: BinaryTree.java's main method contains tests for milestones 2-3 to verify that your solution is correct. Un-comment these tests as you move through each milestone. These tests should not be modified. Likewise, BinaryTreekrray.java's main method contains tests for milestone 4. 1 Color Path While it may not seem immediately obvious, a 2D array/grid problem can be translated to a graph problem. We can imagine each index (row, column) in a given 2D array/grid to be a vertex/node of a graph. Let's explore a problem related to this: Given a positive 2D array of integers, inage, each integer in the array represents a color. Given a row and column index (row, column) and a new color integer (newColor), you must update the given index [row, column] in the color array (image) to the newColor and all reachable neighbors that are same color as image [row, column] to newColor. If a reachable neighbor is not the same color as the original source vertex color, you must NOT update it. Note: A reachable neighbor is one that is in one of the four cardinal directions (left, down, up, or right) from the current index/vertex. For this milestone, you must create a class called ColorPath.java. Within this class you must implement the following three functions: colorPath(), bfs (), and dfs(). The method signature of colorPath should be public static int00 colorPath(int 00 inage, int sourceRow, int sourceCol, int neuColor). You will need to decide what arguments are necessary for the search algorithms, although their implementation is described in detail below. Example Image with row = 1, column= 1, newColor = 2: (left is before, right is after Color Path has been executed) 111 100 000 011 1. COLOR PATH CSCI 1933 LAB 7 All reachable neighbors of the coordinate (1, 1) that were the same as the original color (0) became the new color (2). Also notice that all reachable neighbors of the reachable neighbors that had the original color (0) were modified as well. 111 12 2 2 2 2 211 11100 10011 00111 01123 33000 2 Example Image with row 1, column 1, nowColor 2: (left is before, right is after Color Path has been executed) 11100 12211 2 2 1 11 21123 33000 1. COLOR PATH Similarly, all reachable neighbors of the original coordinate (1, 1) are updated. However, the non reachable vertexes with the original color (0) are not updated since they are not reachable in the context of our problem. Hopefully you notice that the problem involves traversing through reachable neighbors from the starting index and continues on until we reach a stopping point. In this problem, we could define the stopping point as either out of the bounds of the array or at a color that does not match the original. Let's examine each search algorithm in the context of our problem: BFS: A BFS implementation would start from the given index (1, 1) then visit/update each reach- able neighbor that matches the original color (1, 2) and (2, 1) to newColor. Then it would continue to visit each reachable neighbor of these spots and do the same until there are no more valid, reachable neighbors to visit (ex. visit the neighbor above then the right, then bottom, then left; checking if color matches for each visit). DFS: A DFS implementation would start from the given index (1, 1) then visit/update a reachable neighbor and continue following that direction (ex. try to go down as far as possible, then left, then up, then right). There is no requirement on the ordering of the directions as long as you visit all four a single time from each vertex. Note: One important thing that applies to both algorithms is that we need to ensure we do not continue to visit nodes we have already visited. In this problem, we do not have to worry about this since we are updating each new vertex to a new color. Since we have defined a new color as a stopping point, when the algorithm circles around to check the position again, it will not try to revisit this vertex. Consider what would happen if we did continue to revisit vertices. 3 Note: What might happen if we try to update a vertex to a newColor if newColor is the same as the color that is currently there and there is at least one reachable neighbor? Hint: Consider the note above. CSCI 1933 LAB: Now for the fun part. Outlined below are the pseudo code algorithms for how to implement BFS and DFS on a 2D array/grid. Implement both a DFS and BFS solution to solve this Color Path problem. Note that these are pseudo code algorithms that represent general BFS/DFS. You may need to modify the parameters that these algorithms take in in order to accomplish the goal of colorPath. 1: function BFS (arr, row, col) 2: Instantiate an empty queue of index pairs (integer arrays) 3 Add the starting (row, col) pair as an integer array to the queue. 4 Sc 8: 9 10: 11: 12: 13: 15: 16: 17: 18 19 while Queue is notempty do remove current indices from the front of the queue if left indices are in bounds and not visited then add left neighbor indices to queue end if if right indices are in bounds and not visited then add right neighbor indices to queue end if if below indices are in bounds and not visited then add below neighbor indices to queue end if 1. COLOR PATH if above indices are in bounds and not visited then add above neighbor indices to queue end if end while 21: end function Note: BFS: The queue is an interface in Java and should be implemented using one of the classes that implements this interface such as LinkedList: Queue queue = new LinkedList (). This will require the following import statement at the top of your files import java.util."; Note: BFS: You will need to keep in mind that in the context of our problem, you should only add to the queue if the color of that neighbor matches the original color of the starting vertex. 1: function DFS(arr, row, col) 2: if row/column are out of bounds or vertex is visited then stop recursion 3: end if Recursively call DFS() with each directional neighbor 4 & end function CSCI 1933 LAB 7 2. TRAVERSING Note: DFS: You will need to keep in mind that in the context of our problem, you should stop recursion if the color of the neighbor does not match the original color of the starting vertex Milestone 1: After creating ColorPath.java and implementing the methods colorPath(), bra(), and dfa(), need to run the provided test file Test java to show that your functions work correctly. - < CSCI 1933 LAB: Now for the fun part. Outlined below are the pseudo code algorithms for how to implement BFS and DFS on a 2D array/grid. Implement both a DFS and BFS solution to solve this Color Path problem. Note that these are pseudo code algorithms that represent general BFS/DFS. You may need to modify the parameters that these algorithms take in in order to accomplish the goal of colorPath. 1: function BFS (arr, row, col) 2: Instantiate an empty queue of index pairs (integer arrays) 3 Add the starting (row, col) pair as an integer array to the queue. 4 Sc 8: 9 10: 11: 12: 13: 15: 16: 17: 18 19 while Queue is notempty do remove current indices from the front of the queue if left indices are in bounds and not visited then add left neighbor indices to queue end if if right indices are in bounds and not visited then add right neighbor indices to queue end if if below indices are in bounds and not visited then add below neighbor indices to queue end if 1. COLOR PATH if above indices are in bounds and not visited then add above neighbor indices to queue end if end while 21: end function Note: BFS: The queue is an interface in Java and should be implemented using one of the classes that implements this interface such as LinkedList: Queue queue = new LinkedList (). This will require the following import statement at the top of your files import java.util."; Note: BFS: You will need to keep in mind that in the context of our problem, you should only add to the queue if the color of that neighbor matches the original color of the starting vertex. 1: function DFS(arr, row, col) 2: if row/column are out of bounds or vertex is visited then stop recursion 3: end if Recursively call DFS() with each directional neighbor 4 & end function CSCI 1933 LAB 7 2. TRAVERSING Note: DFS: You will need to keep in mind that in the context of our problem, you should stop recursion if the color of the neighbor does not match the original color of the starting vertex Milestone 1: After creating ColorPath.java and implementing the methods colorPath(), bra(), and dfa(), need to run the provided test file Test java to show that your functions work correctly. - <