ICS 46 Spring 2022, Exercise Set 6

Getting started

First of all, be sure that you've read the Reinforcement Exercises page, which explains everything you'll need to know, generally, about how the reinforcement exercises will work this quarter. Make sure you read that page before you continue with this one.

Before you begin work on these reinforcement exercises, there's a chore that you'll need to complete on your ICS 46 VM to get it set up to proceed.

Refreshing your ICS 46 VM environment

Even if you previously downloaded your ICS 46 VM, you will probably need to refresh its environment before proceeding with these exercises. Log into your VM and issue the command ics46 version to see what version of the ICS 46 environment you currently have stored on your VM. Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you'll need to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with these exercises.

2022-05-12 07:20:21
Exercise Set 6 template added

If you're unable to get outgoing network access to work on the ICS 46 VM — something that afflicts a handful of students each quarter — then the ics46 refresh command won't work, but an alternative approach is to download the latest environment from the link below, then to upload the file on to your ICS 46 VM using SCP. (See the Project #0 write-up for more details on using SCP.) Once the file is on your VM, you can run the command ics46 refresh_local NAME_OF_ENVIRONMENT_FILE, replacing NAME_OF_ENVIRONMENT_FILE with the name of the file you uploaded; note that you'd need to be in the same directory where the file is when you run the command.

ics46-2022spring-environment.tar.gz

Creating your project directory on your ICS 46 VM

A project template has been created specifically for this set of exercises, containing a similar structure to the basic template you saw in Project #0. Among other things, it contains a version of the gather script that's different from the ones in the projects, so you'll absolutely need to use the set6 template for these exercises, as opposed to the basic one.

Decide on a name for your project directory, then issue the command ics46 start YOUR_CHOSEN_PROJECT_NAME set6 to create your new project directory using the set6 template. (For example, if you wanted to call your project directory set6, you would issue the command ics46 start set6 set6.)

Problem 1 (2 points)

When we learn about Graph Traversals, one question that I'm sometimes asked by students is why we need them at all. Consider the two implementation strategies for graphs that we learned about previously: an adjacency matrix and adjacency lists. Both of them include a separate array-based structure in which information about every vertex is stored. So if our only goal is to visit every vertex, we can do that by just iterating through that array-based structure.

If visiting every vertex is as easy as iterating through them, then why do we need graph traversal algorithms such as depth-first and breadth-first? What purpose do they serve that just iterating through the vertices one at a time, without regard for the presence of edges, wouldn't?

What to submit

Add one PDF file to your core directory with this name: problem1.pdf, which contains your answer to this question.

Problem 2 (2 points)

One of the things that surprised me about graphs after I learned about them is how many problems that don't feel like graph problems can be thought of in terms of graphs. The idea that we have objects and relationships between those objects isn't exactly universal, but it's a lot more broadly applicable than you might first expect.

Recall, for example, the maze generator and maze solver algorithms that you implemented in Project #1. Neither of these was described as a graph algorithm, but it turns out that both of them could have been conceptualized in terms of graphs and still led to the same result.

Propose a way to re-conceptualize your maze generator algorithm from Project #1 as a graph problem, with answers to these questions.
- What would the vertices be?
- When would there be edges connected these vertices?
- Which of the graph algorithms we've learned about would be appropriate to generate a maze? What modifications would you need to make to your chosen algorithm to make it behave identically to your maze generator?
Now do the same for your maze solver from Project #1, answering the same questions.

Note that we're not asking you to write code here or write complete pseudocode for your algorithm; we're just asking you to answer the questions asked.

What to submit

Add one PDF file to your core directory with this name: problem2.pdf, which contains your answer to these two questions.

Problem 3 (2 points)

Suppose that you're working on an open-source social-networking project. Because social networks are predominantly built around people and the relationships between them, you reasonably suspect that graph algorithms can help in your endeavors.

Now suppose that you're adding the ability for a person P in the network to see anyone who is within three "links" of them (i.e., either your friend, your friend's friend, or your friend's friend's friend), with the results sorted by how closely linked each person is (i.e., your friends come before your friend's friend's, and so on) and, secondarily, by their last name.

Assuming that you already had a directed graph in which people were represented as vertices and relationships between them were represented by edges (i.e., if you're my friend, there will be an edge from my vertex to yours). Propose how would you modify the breadth-first traversal algorithm we discussed in lecture to solve this problem. Note that we're not asking you to write code here or write complete pseudocode for your algorithm; we're just asking for an explanation of what you think would need to change and why.

What to submit

Add one PDF file to your core directory with this name: problem3.pdf, which contains your answer to this question.

Problem 4 (2 points)

In our discussion of Graph Connectedness, we talked about how undirected graphs are either considered to be connected or they aren't; there's no gray area there. On the other hand, directed graphs have two different notions describing how "connected" they are: strong connectedness and weak connectedness.

In a sentence or two, explain why we need two different notions of connectedness in a directed graph.
Suppose that you're implementing a mobile application that is able to display a map of all of the world's streets. If we were to think of the entire world's map as a directed graph, which of the following kinds of connectedness would you expect to find? Briefly explain why.
- The entire graph would be strongly connected.
- The entire graph would be weakly connected.
- The entire graph would not be connected, but it would contain a small number of large strongly connected components.
- The entire graph would not be connected, but it would contain a small number of large weakly connected components.
- The entire graph would not be connected, and we wouldn't expect to find large connected components of any kind.

What to submit

Add one PDF file to your core directory with this name: problem4.pdf, which contains your answer to these two questions.

Problem 5 (2 points)

When we discussed Dijksta's Algorithm for finding Shortest Paths, we noted that Dijkstra's Algorithm solves a more particular problem than just "find shortest paths." It solves the positive-weighted single-source shortest-path problem.

One kind of graph for which Dijkstra's Algorithm won't be able to find shortest paths is the first one we saw in the notes.

Directed graph with negative weight cycle

Not only is this graph problematic for Dijkstra's Algorithm; it's problematic in general, because it contains a negative-weight cycle.

But what about a directed acylic graph that contains exactly one negative-weight edge somewhere? Suppose we wanted to find all shortest paths from some vertex in that graph. By definition, we're no longer solving the positive-weighted single-source shortest-path problem. But could Dijkstra's Algorithm always find the shortest paths in such a graph?

If so, then what additional characteristic would the graph need to have before Dijkstra's Algorithm would certainly fail to find the shortest paths?
If not, then show one example graph meeting this characteristic for which Dijkstra's Algorithm could not find the shortest paths. Demonstrate your answer by showing the table of k, d, and p values for each vertex at each step, as we saw in the Shortest Paths notes.

What to submit

Add one PDF file to your core directory with this name: problem5.pdf, which contains your answer to this question.

Deliverables

In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submited in the incorrect area.

Submit each file as-is, without putting it into a .tar.gz file or arranging it in any other way. (There is a gather script in the set6 template, but there's no need to use it.) If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for, we will not be offering you any credit on the submission. There are no exceptions to this rule.

Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally, and we won't be able to offer any credit on exercises that you forgot to submit.

Can I submit after the deadline?

Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 3% of your grade, so it's not a disaster if you miss one of them along the way.

Can I work on this outside of the VM?

Yes, but be aware that you must submit the files in the appropriate format, and that any C++ code you submit must compile and run on the ICS 46 VM.