Assignment 3

 

  1. PART I: Pen-and-paper (PDF) exercises:
    1. Submit pseudocode for In-class Exercise 7.13 in Module 7, as discussed in class. Hint: think about how you could use DFS to determine whether j is reachable from i. Then, use repeated calls to DFS to keep track of reachable nodes, and finally identify the connected components. (Even though you are submitting this for Module 7, repeating that here gives you more points.)
    2. Consider the following problem. We are given a list of courses, and for each course, which other courses are its prerequisites. Suppose this is a text file that looks like this: $$ \scriptsize{ \begin{array}{ll} N: & 13 \\ C_2: & C_1 \\ C_3: & C_1, C_6\\ C_6: & C_5\\ C_7: & C_1, C_2, C_3\\ C_8: & C_2, C_3\\ C_9: & C_4, C_8\\ C_{10}: & C_4, C_9\\ C_{11}: & C_9\\ C_{12}: & C_7, C_{11}\\ C_{13}: & C_7\\ \end{array} } $$ Thus, there are \(N=13\) courses and, for example, course \(C_3\) has courses \(C_1\) and \(C_6\) as prerequisites. We can construct a directed graph out of this data as follows:

      Answer the following questions:

      1. An adjacency-list representation of the graph has an array of linked-lists, where, for example, node \(C_2\) will have \(C_7, C_8\) in its linked-list of "immediately downstream" neighbors. Suppose we wish to construct a dual-adjacency-list where each node has two linked-lists, one for immediately downstream neighbors (outgoing edges) and one for immediately upstream neighbors (incoming edges). Draw the dual-adjacency-list for the above data.
      2. Write pseudocode for constructing the dual-adjacency-list for any data of the kind described above. If there are \(N\) courses, what is the worst-case running-time in terms of \(N\) (along with your reasoning)?
      3. A course is taken in a semester, which means a follow-on course cannot be taken in that semester or earlier. For any course \(C_i\), let \(E(C_i)\) be the earliest possible semester (semesters start from 1) in which the course can be taken. Some examples are shown in red in the picture above. Complete the picture above by calculating \(E(C_i)\) for every node.
      4. Write pseudocode to compute \(E(C_i)\) for each node using the dual-adjacency-list. In addition to the pseudocode, explain through a few steps of execution how it works, and analyze the running time. Your algorithm should not take more than \(O(N^2)\) time.
    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  2. PART II: Implementation: In this part, you will implement an algorithm to find bus connections. The idea is: you'll be given a collection of bus routes, a start point and an end point. Then, your goal is to see if there is a series of buses that will take someone from the start point to the end point. Let's explain with an example:

    • First, we'll assume a rectangular layout of streets with street corners marked with dots. Some of these will be stop points for buses.
    • The grid points will be identified by integer (x,y) coordinates as shown above.
    • The example shows 7 bus routes for buses numbered 0 to 6. Each bus has a start and end point, and one can assume buses ply in each direction. For example, Bus 5 goes from (3,0) to (3,3), stopping at all grid points along the way. That is, stopping at (3,0), (3,1), (3,2) and (3,3).
    • Assume that buses repeatedly go up and down their route. We will not be concerned with timing in this problem.
    • Our goal is, given a start grid point like (1,1) and a destination like (4,2), is there a sequence of buses that will take us from the start to the destination? In this case, we see that there is in fact a solution: take buses 0, 1, 2, 3 and 4 in that sequence. We'll use the term bus journey to denote such a solution.
    • The bus journey is more detailed than a sequence of buses. It must specify where to hop on and hop off. Here, one hops on Bus 0 at (1,1), then hop off at (1,2). Then, hop on Bus 1 at (1,2), hop off at (2,2). Then hop on Bus 2 at (2,2), hop off at (2,4) ... and so on until the final hop off in Bus 4 at (4,2).
    • Initially, for simplicity, you may assume that bus routes are straight-line segments as shown in the example. Later, once you have this working, you should relax this assumption to allow jagged routes. The only really valid assumption is that a bus route will not intersect itself.

    Implementation details:

    • You will need the latest version of algtest.jar for this problem. This has been compiled with JDK 20.0.1 so your install of JDK needs to be at least as recent as that.
    • Call your algorithm BusConnection.
    • Your algorithm will need to implement the BusConnectionAlgorithm interface.
    • Let's first examine the class IntPoint:
      • This is a simple class that holds the x and y for a point (x,y) where both are integers.
      • You can make an instance using the constructor and can set the x and y values directly as in 
                 IntPoint p = new IntPoint (3,4);
         // ... later ...
	 p.x = 5;
      • All grid points are instances of IntPoint.
    • Examine the first method analyzeRoutes():
      • This is given a list of bus routes as an array.
      • Each bus route is specified with an instance of BusInfo.
      • Examine the class BusInfo.
      • The bus number is in the busNumber field.
      • The bus route is simply a list of IntPoint's. This is in the array forwardRoute. Which means the other direction can be inferred as the reverse of this array.
      • To analyze, one only needs this information. What are the other fields for then? They are for constructing a bus journey, as we'll explain below.
    • Now examine the method findConnections():
      • This takes a start of journey (an IntPoint) and an end (also an IntPoint).
      • Notice that the return value is an array of BusInfo instances. It is this array that specifies the bus journey your algorithm will find.
      • Important: if no bus journey is possible (as you'll see in some test cases), then you must return null.
      • A bus journey is a sequence of buses, along with an embarkation point (where to hop on) and a disembarkation point (where to hop off) for each bus. Of course, the disembarkation point for one bus must be the embarkation point for the next bus. And both must be valid for the bus route.
      • If you specify that a particular bus is to be taken, you must also specify the direction: is it in the forward direction or the reverse direction. Use the boolean variable embarkForward for this purpose.
    • Use the busconn.props properties file to run your algorithm in the test environment. There is no performance-testing for this algorithm.

Submission: