Homework 3.5 -- GraphQuest (Spring 2025) - HedgeDoc

<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; margin-top: 1em; margin-bottom: 1em; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # Homework 3.5: GraphQuest (Spring 2025) **Key Dates** - **Submission deadline:** Friday, March 21, 11:59pm - **Peerceptive Plan deadline:** Friday, March 21, 11:59pm - **Peerceptive Peer Review deadline:** Monday, March 31, 11:59pm  :::success **Background Notes**: For an overview of the homework, check out notes from last semester's gearup, which describes how to start thinking about each component: - [Notes](https://brown-csci0200.github.io/assets/lectures/reviews/pr02-gearup-f24-notes.pdf)   ::: # Overview In lecture so far, we introduced a data structure for representing graphs (e.g. bus routes between cities), and wrote code to check whether routes exists between nodes. In this assignment, you'll further explore how we can use graphs in different contexts, and extend what we've learned to about finding shortest routes to find shortest paths. You'll also *plan* a solution to a different (yet related) graph problem about assigning people to tasks, which you'll implement in the next homework. Concretely, you will: - Work with multiple data structure representations for graphs - Understand key techniques for programming with graphs - Practice with planning and developing test cases ## How this homework works (open collaboration) This assignment has a good bit of conceptual thinking and planning based on the concepts we have learned in lecture, but we've designed it to not require a ton of *implementation*. Working out concepts really benefits from collaboration--we don't have time in the course schedule to make this a full partner project (and we don't want to constrain you to just collaborating with one person), so we're altering the collaboration policy to be more open: - **You may collaborate with others as much as you want.** This means you can do pair programming, work out answers in groups on a whiteboard, and so on. - **When you submit your assignment, you must _list your collaborators_ and how they contributed** (We provide a template file for this in the stencil called `README.md`) - **You still MUST type out your answers on your own**. We want you to benefit from collaboration and not feel restricted, but we also want to make sure that you, individually, build a good conceptual understanding. :::warning Please keep in mind that **there is a code review** for this assignment and that **graphs will appear on the final exam,** so it's in your best interest to make sure you collaborate in such a way that helps you build a good conceptual understanding! If you just copy work from others, you're going to lose out on some important time to practice with the concepts, which will place you at a big disadvantage on the code review and the final. ::: ## Roadmap There are two parts to this assignment: - In **Part 1**: you will build a new representation for graphs that's different from the Node-based version we've seen in lecture. To do this, you'll implement a new type of graph (`EdgeArrayGraph`) that implements a generic interface, `IGraph` - In **Part 2**: you'll explore ways to use breadth-first search (BFS) to find routes in different contexts (similar to what we did in lecture). There are two subparts to this: - **Part 2A**: you'll implement a method to find the shortest path between nodes (building on a working version of BFS that we saw in lecture) - **Part 2B**: you'll make *plans* for using graphs to managing schedule conflicts. In this assignment, you will only do the planning part and submit your plan for peer review by the submission deadline (**Friday, March 21**). After that, you'll submit reviews of each other's plans by **Monday, March 31** (after spring break!), and then you'll do the actual implementation as part of HW4. ## Setup **Assignment Link**: Use this **[GitHub Classroom link](https://classroom.github.com/a/upSa0B6f)** to get the stencil code for this assignment. **Be sure to follow the [Java Stencil setup guide](https://docs.cs200.io/s/java-stencil-setup-guide)** for instructions on how to do this. ## Part 1: Another representation for graphs As we discussed in lecture, there are many different data structures that can be used to represent graphs, depending on the needs of the application and the type of graph. In this assignment, we want to give you some practice working with a graph representation we haven't seen before, and see how we can use interfaces to operate on graphs in a unified way, regardless of the underlying representation. The next few sections will provide some background on the two different graph representations we'll be working with (one of which you've already seen) and introduce you to the relevant parts of our stencil code. :::success **What to expect**: The next few sections introduce the most important classes in the stencil code. **As you read each section, skim over the relevant code in the stencil** to familiarize yourself with what's there and how the pieces fit together. ::: ### Background: Node-based graphs (`NodeEdgeGraph` in the stencil) In lecture, our graphs have used what is typically called a "node-based" implementation, which uses a class to represent each node, and some kind of collection (list, hashmap, set etc.) to keep track of the neighboring nodes. For example, here's our `CityVertex` class from lecture, which represented one City in our travel graph: ```java public class CityVertex { String name; // Name of city List<CityVertex> neighbors; // Neighboring cities } ``` As we've seen, this structure isn't specific to representing routes between cities--instead, we typically just call the vertex a "node", which can refer to any vertex we want to represent: ```java public class Node { String label; // Some label describing this node List<Node> neighbors; // Neighboring nodes } ``` **In the stencil**: We've provided a complete representation for a node-based graph in the stencil (as `NodeEdgeGraph.java`), which is similar to implementations we've seen before--**you shouldn't need to modify it.** You'll use this version to make graphs for testing, and as an example for developing your own graph representation (described in the next section). **The catch**: In a node-based graph representation, we need one Node object for each vertex in the graph. This is generally fine, but graphs can be *very large*: imagine a graph of hundreds of millions of social media users and who they follow--this would require a lot of memory! Can we do better? It turns out we can, read on! ### Background: Array-based graphs (`EdgeArrayGraph` in the stencil) Another very common representation for graphs is to use a two-dimensional array--that is, an array of arrays, which effectively creates 2D grid of rows and columns, like a matrix. In an array-based graph representation, each "cell" of the graph is a boolean value that indicates if one node has an edge to another node. To do this, one dimension of the grid (e.g., rows) represents the "source" of the edge, and the other dimension (e.g., columns) represents the "target". This is called an *adjacency matrix*, in that a true value a cell indicates if there's an edge from one node to another. Here's an example of the adjacency matrix for the graph of bus routes from lecture (we've left out the false values in the blank cells to make it easier to read): <table> <tr><td> ![](https://docs.cs200.io/uploads/475aa8cb-1b78-4b2c-b4f0-0bd10853704c.png) </td><td> | | man | bos | pvd | wor | har | | --------- | ----- | -------- | ------ | ---- | ---- | **man** | | True | | | | | **bos** | | | True | True | | | **pvd** | | True | | | | | **wor** | | | | | True | | **har** | | | | | | *(Note: blank cell == False)* </td></tr> </table> <details><summary>Aside: why is the array-based format useful?</summary> Since every cell is just a boolean value, array-based graphs can be stored using less memory than node-based graphs. It also turns out that the matrix-like format can be very fast for performing certain computations (because computers, specifically GPUs, are very good at matrix math). The details of this are beyond the scope of this course, but we want you to know that this format exists, and that it can have advantages. (You'll learn more about this in AI courses, which use this format frequently!) </details> <br /> With an array-based graph, we can perform the same kinds of operations we've been doing with node-based graphs (e.g. finding neighbors, computing shortest paths, etc.). The only difference is how we "read" the graph from the underlying data, which what you'll do in this part of the assignment! ### `IGraph`: An interface for graphs Before we go building another graph implementation, we have a design issue to consider: Both the node-based and array-based versions are both graphs, and so we'd like to perform the same kind of graph operations (like computing shortest paths) on them. Does having two representations mean we need to write this code multiple times??? This would be annoying, and difficult to maintain. :frowning: Fortunately, we have a tool in our toolbox that can help: **interfaces**! By creating an interface (say, `IGraph`) for the key operations on graphs, and then and write our shortest path code based on it, we can use it with *any* graph representation (so long as it provides the key operations in `IGraph`). :grinning: To take advantage of this, we've defined an `IGraph` interface which looks like this: ```java public interface IGraph { // Add a node to the graph void addNode(String label); // Add edge (A -> B) void addDirectedEdge(String label1, String label2); // Add edges (A -> B) and (B -> A) void addUndirectedEdge(String label1, String label2); // Get the set of neighbors for a node Set<String> getNeighbors(String nodeLabel); // Get the names of all nodes in the graph Set<String> getAllNodes(); } ``` :::info <details><summary>What's a <code>Set</code>? Is it like a <code>HashSet</code>?</summary> Yes. A `Set` is equivalent to a `HashSet`, which just represents an unordered collection of values. In Java, you can add, remove, and iterate over a set just like a `LinkedList` or `ArrayList`. See the second bullet below for more details on why we use them here. **So why not write `HashSet`?** `Set` in Java is an interface, just like `IGraph`! Java has multiple implementations for sets, and it doesn't really matter what underlying representation we're using, so we use the interface name instead--we don't care what representation `getNeighbors` returns, so long as it behaves like a set. This is a common practice for writing good generic code, since it lets our code be more flexible, so we want you to see this. </details> ::: Some key points about `IGraph`: - **Nodes are identified by *labels*, which are strings**: whenever we need to refer to a node, we use its label. This is a bit different from the graphs we've seen in class, where we wrote methods that used `Node` or `CityVertex` objects. Since not all of our graph representations have discrete Node objects (e.g., the array-based graph does not), our interface needs a generic way to refer to nodes that works for all of them. **You may assume that no two nodes have the same label.** - **Graphs can have *directed* or *undirected* (bidirectional) edges**: In lecture, we mostly saw graphs with *directed* edges, which are unidirectional (A -> B). In contrast, *undirected* edges are bidirectional, and are usually drawn them with a double-ended arrow (A <-> B). A bidirectional edge (A <-> B) is equivalent to two directed edges (A -> B), (B -> A). We'll use undirected edges in part 2. - **`getNeighbors` and `getAllNodes` return sets** since we don't want to make assumptions about the *order* of the nodes across graph representations. A Java `Set` (specifically a `HashSet`) behaves similarly to a List, but has no defined order. Sets also have a `contains` method to check if an element is in the set in constant time (similar to a hashmap), as shown in the example. Concretely, our `IGraph` interface lets us make graphs and get their neighbors like this (here, we use a `NodeEdgeGraph`): ```java IGraph g = new NodeEdgeGraph("a graph"); g.addDirectedEdge("a", "b"); // add a->b g.addDirectedEdge("a", "c"); // add a->c Set<String> aNeighbors = g.getNeighbors("a"); Assert.assertTrue(aNeighbors.contains("b")); ``` **Where we go from here**: Now that you've seen the context and the key operations in the `IGraph` interface, you'll implement your version of an array-based graph. In part 2, you'll work with some methods that *use* the `IGraph` interface to do some operations on graphs. ### Task 1.1: Write some tests for `NodeEdgeGraph` We've provided you a complete, working implementation for a node-based graph (in `NodeEdgeGraph.java`), which implements `IGraph`. You should not need to modify this version. To warm up and make sure you understand the behavior `IGraph` interface, **write 2-3 tests for `NodeEdgeGraph` that use `getNeighbors` and `getAllNodes`**. You can write your tests in `GraphUtilsTest.java`. We already provided some example tests in this file; you should make new test methods and write your tests within them. You don't need to be super-comprehensive in your tests yet--just write some examples to make sure you understand how the methods should work. **Since the implementation for NodeEdgeGraph already works, your new tests should pass without writing any code**. This shows you have a good understanding of the specification! ### Task 1.2: Implement `EdgeArrayGraph` Now that you have an understanding of `IGraph`, **implement the methods in `EdgeArrayGraph`** to realize an array-based graph implementation (as described [here](#Background-Array-based-graphs-EdgeArrayGraph-in-the-stencil)). We've started off the implementation for you by defining the underlying array (`edgeArray`), which we implement as a nested `ArrayList` of booleans: ```java private ArrayList<ArrayList<Boolean>> edgeArray; ``` Some things to consider: - You get to decide which dimension of `edgeArray` (e.g., rows or columns) refers to the "source" or "target" of the edge. Feel free to use whatever feels most comfortable! - Since `edgeArray` is based on an array, we need to index into it with integers (0, 1, 2, ...), but our nodes we refer to nodes with labels (`pvd`, `bos`, `wos`, ...), so **you'll need a way to map labels into array indices, and vice versa**. How you implement this is up to you, but **consider adding some extra fields to help**! - As you work on your implementation, consider writing some tests to help check your understanding (which is also Task 1.3 :wink:)  ### Task 1.3: Write some tests for `EdgeArrayGraph` Similar to how you wrote tests for `NodeEdgeGraph` in Task 1.1, write some tests using your new `EdgeArrayGraph` that use the methods in `IGraph`. To do this: - **Use your tests from Task 1.1 as a starting point.** Since both graph representations use the same interface, you should be able to copy your tests and modify them to use `EdgeArrayGraph` with *very* minimal changes--yay, interfaces! - Your test cases don't need to be super-comprehensive (there's no wheat/chaff testing), but try to come up with some edge cases to help you test thoroughly. One you're confident in your tests for `EdgeArrayGraph`, you're done with part 1. Yay! :sunglasses: ## Part 2A: Finding shortest paths on graphs (`getRoute`) :::info If you skipped part 1 and went straight here, be sure to read the following background info, which introduces you to key parts of the stencil code: - [`NodeEdgeGraph`](#Background-Node-based-graphs-NodeEdgeGraph-in-the-stencil): a representation for graphs, similar to what we've seen in lecture - [`IGraph`](#IGraph-An-interface-for-graphs): an interface for working with graphs ::: We'd also like to use our generic interface for working with graphs (`IGraph`, discussed [here](#IGraph-An-interface-for-graphs)) to compute some useful info. In this part, you'll leverage the `IGraph` interface to find shortest paths on graphs, using an existing implementation for breadth-first search (BFS, like we saw in lecture) as a starting point. ### Starting point: `hasRoute` The file `GraphUtils.java` contains some helper functions that operate on graphs. Specifically, we've provided an implementation for `hasRoute`, which uses BFS to determine if a path exists between two nodes. **`hasRoute` is exactly the same as the `canReach` method we saw in lecture on March 5 and 7** (notes [here](https://brown-csci0200.github.io/lectures.html)), just adapted to use `IGraph`: ```java public static boolean hasRouteExample(IGraph graph, String fromNodeLabel, String toNodeLabel) { // See GraphUtils.java for implementation! } ``` In lecture, we discussed how using BFS checks if we can get from the source to target node via the shortest path. However, `hasRoute`/`canReach` **only outputs whether a path exists or not** (a boolean). Your job will be to write a new, similar method that outputs **the path** (ie, a list of nodes) that was used to get to the destination. ### Your goal: `getRoute` Concretely, your goal is to implement `getRoute`: which takes in a a graph and start and end node, and outputs the shortest path (a list of `Strings`) or throws a `NoRouteException` if no route is found: ```java public static LinkedList<String> getRoute(IGraph theGraph, String fromNodeLabel, String toNodeLabel) throws NoRouteException { // You will build this (but read the next part first!) } ``` <details> <summary>What's with the <code>static</code>keyword? </summary> When we first learned Java, we told you that methods are always called on objects. This is generally true, but `static` methods are an exception. Static methods are used to implement helper/utility methods that aren't associated with an object--they're just chunks of related code that live in a class. To call a static method, we use the *name of the class* where we'd usually write the object. For example: ```java NodeEdgeGraph g = new NodeEdgeGraph("a graph"); GraphUtils.getRoute(g, "a", "f"); // GraphUtils is the class name! ``` Since static methods are not associated with an object, they may not use the `this` keyword, since there's no `this` object to access. Otherwise, writing a static method is just like writing any other method. </details> <br /> **As we discussed in lecture, your implementation for `getRoute` will be very similar to `hasRoute`**--you'll use the same general algorithm, but you will need to keep track of some additional information. The next few tasks will guide you in how to approach this. ### Task 2A.1: Write some tests for `hasRoute` and `getRoute` To get started, make some directed graphs to use for testing `hasRoute` and `getRoute` and write some tests using them in `GraphUtilsTest.java`. To do this: - `GraphUtilsTest.java` has some example tests, so take a look at these for a starting point. You should make new test methods and write your tests within them. - You only need to consider *directed* graphs--that is, you should only add edges to your graphs with `addDirectedEdge`. (Undirected edges are for part 2B.) :::warning **Important note**: **For all tests in part 2, you should only test with `NodeEdgeGraph`**. In other words, you don't need to write any tests using `hasRoute` or `canRoute` using your `EdgeArrayGraph` from part 1. While we *could* easily also write tests for these methods using `EdgeArrayGraph`s, we can skip this for the assignment to keep testing simple, and to avoid cases where a bug in part 1 can cause you problems in part 2. :smile: ::: After you have written some test cases, **run your tests.** Your tests for `getRoute` will fail (which is okay, you haven't implemented it yet!), but **your tests for `hasRoute` should pass**. This should help you confirm your understanding and your graphs are correct!   ### Task 2A.2: Implement `getRoute` Now that you've worked out some test cases, implement `getRoute`. To get started on this: - **Copy** the `hasRoute` code into `getRoute`. You will modify this code to build your implementation. - Go back and look at the notes for the lecture on March 10, where we discussed how we could modify `hasRoute` (called `canReach` in lecture) to output the path between nodes. As you consider how your implementation will work, consider the following questions: 1. What data do you need to store as you traverse the graph? (And what data structures would you need?) 2. How can you use this data to reconstruct the path after a destination has been found? :::success Working out these sort of problems really benefits from drawing things out, and from discussing examples. **As you work on this part, please feel free to collaborate with your peers, and/or come talk to us (and your peers) in office hours!** We have opened the collaboration policy on this assignment *specifically* because we want to make sure you're comfortable sharing ideas and talking with others about this. ::: As you build your implementation, use the tests you wrote in the previous part to help check if your work is correct. If you believe you have covered a good set of edge cases in your tests, you should be good to go!  ## Part 2B: Using Graphs to Aid in Scheduling (planning only) :::warning :warning: **Heads up!** In this part, you're going to be planning your design for another graph problem, which has a similar *flavor* to what you just did part 2A. For this assignment, you'll submit your plan to Peerceptiv for peer review, and then **you will implement it in the next homework**. Therefore, you'll want to spend some time thinking about this, so you can get good feedback to help with your implementation. We also *highly* recommend collaborating with others as you work on your plan, to help you get started and so that you hear other perspectives. ::: Oh no! [A series of unfortunate events](https://en.wikipedia.org/wiki/A_Series_of_Unfortunate_Events) have left the TAs unable to run labs next week. The question is whether Kathi and Elijah could cover them all if they dropped all other activities that week. The challenge arises because some lab times overlap (and one person can't run two labs at the same time), and some are so far away on campus that one person can't get from one to the other in time to start it. Is there a schedule that lets two people cover a given set of labs within such constraints? #### **How is this a graph problem?** We can view the set of labs as locations in a graph: **each lab is a node, and an undirected edge between nodes indicates that two labs conflict** (for whatever reason). All of the following are possible lab conflict graphs: <table> <tr> <td> **Example lab conflict graphs**: *In the top left graph, every lab conflicts with every other lab (so we'd need four TAs to cover all of the labs). In the top middle graph, there are two pairs of labs with conflicts, while one lab doesn't conflict with any other lab.*  ![](https://)![](https://docs.cs200.io/uploads/c908e1d7-c433-467d-841a-e0749821e6d0.png) </td> </tr> </table> #### Schedules as graphs A *lab schedule* assigns one of Kathi or Elijah to each lab such that neither one of them is assigned to two labs that conflict (labs that are connected by an edge). Here's how we might schedule a few of the examples from the previous figure: <table> <tr> <td>  ![](https://docs.cs200.io/uploads/317db329-55a4-44a2-b30e-78d0c06665b8.jpg) ***Note**: that these diagrams show one possible schedule, but there are others: Kathi and Elijah could switch which labs they cover. In the middle example below, either Kathi or Elijah could cover the lab that doesn't conflict with any others.* </td> </tr> </table> In this part, you will *plan* two methods that involve lab schedules (stubs for these are in `Scheduler.java`, but you won't implement them): - `checkValidity`: one checks whether a *proposed schedule* for two people indeed respects all of the constraints - `findSchedule` the other computes a valid schedule for two people, if one exists (or throws an exception if none exists) The next tasks describe some steps to start making your plan. At the end of this assignment, you'll submit your plan for peer review. After you receive feedback on your plan, you'll implement these methods in HW4. ## Make a Plan for Scheduler To build your plan, **write your responses to the following questions in a document**. To submit your work, you will upload this doc as `planning.pdf` on Gradescope **and** submit it to Peerceptiv for peer review. :::success **You got this!** This graph problem may seem very different from what we've seen before, but you have all the pieces you need to solve it. For example, certain components might be pretty familiar to Part 2A.... If you are stuck, we highly recommend talking with us or your peers and/or coming to office hours! We want you to collaborate on this, and we are here to help. **Also, remember: your plan does not need to be perfect**: the goal is for you to give it a try, and submit what you have, and get feedback--so it's okay if you don't have everything figured out! ::: ### Task 2B.1: Develop some sample lab-constraint graphs Draw 4-5 lab-constraint graphs (other than the ones we gave you in the handout). Some should have valid schedules, and some should not. For each graph, indicate whether that graph has a schedule. Note that **constraints are not transitive**--for example, consider the following lab schedule: - Lab 1: Mon 8-10 - Lab 2: Mon 9-11 - Lab 3: Mon 10-12 In this example, Lab 1 and Lab 2 confict (9-10), and Lab 2 and Lab 3 conflict (10-11), but Lab 1 and Lab 3 **do not** conflict. Thus, chains of nodes connected by edges do not conflict without direct edges to indicate that they do. **For a picture, see the [gearup notes](https://brown-csci0200.github.io/assets/lectures/reviews/pr02-gearup-f24-notes.pdf), bottom of page 11.** ### Task 2B.2: Plan how to *check* a proposed schedule (`checkValidity`) Imagine that someone gave you a lab-constraint graph and a proposed schedule as a list of two HashSets of Node names (e.g., one HashSet for each of Kathi and Elijah). Develop a plan for a method `checkValidity`, which takes in a graph and the two lists/hashSets for the schedule. To build your plan, you should consider how the method should return true if (and only if) the proposed allocation adheres to the constraints of the graph. Here's the method header from the stencil (you can view it in `sol/Scheduler.java`, and see some example tests in `test/SchedulerExamples.java`): ```=java /** * Method which checks if a given allocation of labs adheres to * the scheduling constraints of the graph * * @param theGraph the graph to try to schedule * @return boolean indicating whether the proposed allocation is valid */ public boolean checkValidity(IGraph theGraph, ArrayList<HashSet<String>> proposedAlloc) { ... } ``` For information on how to plan, [check out this planning guide](https://docs.google.com/document/d/1673PEcn_6ikHpm96T0JR07nDwnOjVtvwEmaytKaZWXw/edit?usp=sharing). To get started, here are some thing to think about: - **To work with the graph, you have all of the methods in the `IGraph` interface available to you.** Think about how you can use these methods to check the constraints. If you want any additional helper methods as part of `IGraph`, you can consider adding these to your plan (just describe what they are), but this should not be necessary. - You should **first consider lab-constraint graphs in which all the nodes are part of one big cluster**, rather than having separate clusters--these are called [*connected graphs*](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Connected_graph). In the grid of 6 examples earlier in the handout, all but the top middle graph is connected. Devise a plan for checking if solutions on these graphs are valid. - In reality, there are likely to be clusters of constrained labs that are not all connected to each other. How would your plan have to change to work more generally, on *all* constraint graphs? ### Task 2B.3: Plan how to *generate* a lab schedule (`findSchedule`) Now let's think about the scheduling problem. Write a plan for `findSchedule`, which will take in a graph and will **generate** allocations like the ones checked by `checkValidity`, or raise a `NoScheduleException` if no allocation exists. Here's the method header for `findSchedule` (view in `sol/Scheduler.java`, examples in `test/SchedulerExamples.java`): ```java /** * Method to compute a valid split of the graph nodes * without violating scheduling constraints, if such a split exists * Throws a NoScheduleException if no such split exists * * @param theGraph the graph to try to schedule * @return an ArrayList of HashSets of node labels that constitute a * valid split of the graph * @throws NoScheduleException if no such split exists */ public static ArrayList<HashSet<String>> findSchedule(IGraph theGraph) throws NoScheduleException { ... } ``` To get started on this: - As before, you have all the methods in the `IGraph` interface available to you. You *may* consider adding extra helper methods, but this should not be necessary. - Once again start with connected graphs. Plan out how you would generate a schedule for Kathi and Elijah, consisting of the collection of labs that each of them should teach. - How would you adapt this plan to work on *all* constraint graphs? :::success <details> <summary>Hint: does this seem familiar?</summary> Think back to `findRoute` and how you implemented `getRoute` in part 2A. To implement `findSchedule`, consider how you could use BFS to help solve this problem, by tracking some extra information as you traverse the graph, like you did in part 2A. You should *not* be calling `getRoute` or `findRoute` in your implementation for `findSchedule`, but you should be able to leverage similar ideas... </details> ::: ### Task 2B.4: Submit your plan (and get ready for peer review) When you are ready, submit your `planning.pdf` with your responses to the tasks in 2B to Peerceptiv (link [here](https://app.peerceptiv.com/course/60daf3a6-a765-4c09-aa06-f344588f04c5/assignment/9c2476c6-846e-459d-be17-72b7efaeceb2/dashboard)), similar to what you did for Decision Tree. Your plan submission is due by **Friday, March 21, 11:59pm**. Similar to Decision Tree, you will be reviewing each other's plans and submitting peer review feedback. Your reviews are due by **Monday, March 31 at 11:59pm**. Due to limitations of the Peerceptiv system, **late reviews cannot be accepted**--we have no way to grant extension on this. To ensure that you and your peers get feedback, please be sure to submit on time!!!  # Handing in (and Peer review) To submit your work: - Submit your `planning.pdf` from Part 2B to **[this Peerceptiv assignment](https://app.peerceptiv.com/course/60daf3a6-a765-4c09-aa06-f344588f04c5/assignment/9c2476c6-846e-459d-be17-72b7efaeceb2/dashboard)** (similar to what you did for Decision Tree). Your document should contain your responses to all the tasks in Part 2B - Fill in your `README.md` file, per [these instructions](#Your-README-file) - Submit the following files to the **Homework 3.5: GraphQuest** submission on Gradescope: - `EdgeArrayGraph.java` - `GraphUtils.java` - `GraphUtilsTest.java` (from the `test` directory) - `README.md` - `planning.pdf` ### Your README file For this and future assignments, we'll ask you to write a `README` file to give us some information about your submission and list your collaborators. In real-world software, `README` files are common way to provide an overview of the code published online, and it's a format that many CS courses use as well, so we want you to learn it! A common format for README files is markdown, which is a way to write a plain text file that can be displayed (or "rendered") with nice formatting (headings, links, etc) on sites like Github. Writing in markdown is just like writing in a text file. To edit your readme and see how this works, do the following: 1. In IntelliJ, open your `README.md` file 2. If IntelliJ may open the file in "preview mode", which shows the formatted text. To edit the file, click on the "Edit mode" button in the top-right, as shown in the figure: ![](https://docs.cs200.io/uploads/0d67170e-9859-486b-8fc0-0cbdafb89f14.png) 3. In the pane on the left, you can edit your README just like any other text file. When you save, you should see a preview of your formatted text on the left. # FAQ See the pinned Homework 3.5: GraphQuest FAQ post on EdStem! _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our_ [_anonymous feedback form_](https://docs.google.com/forms/d/e/1FAIpQLSfe9cDwpzv7xCbbevbrAZacuB4MB8yxer8jiK0SK-CQH3RXuQ/viewform)_!_