Homework 11

Due Date: Friday April 09, 9pm

Purpose To practice mutually recursive data and graphs

Expectations

This is a pair assignment. Remember that working in pairs means that you both work on the problems together, ideally by one person developing the solution, while the other person observes and comments. After a while, you switch roles. Working in pairs does not mean to divvy up the work between the two of you.

As with all assignments, you must upload one .rkt file (for the entire pair/team), in the language specified at the top of the assignment to the Handin Server. Using the wrong language will invalidate your submission and result in a score of 0, so please be careful.

Unless otherwise stated, all data and functions you design must be designed according to the data and function design recipes, resp., following all four steps in each case.

Your code must conform to the guidelines outlined in the style guide on the course website. The style guide will be updated as the semester progresses so please remember to read it before submitting each assignment.

Revisit the filesystem data design from Lecture 28; you can find it here. Paste this file in at the top of your homework file.

Exercise 1 The System Administration has a policy that requires all executable (runnable) files in the directory tree to be written using lower-case letters. Help them, by designing a function large-caps-executables that returns the list of names of all files in a given dir that violate this policy.

For the remaining exercises, revisit the Page data design from Lecture 29; you find it here.

Exercise 2 One of the main questions to ask of a graph is whether there is a path from a node t1 to a node t2. This is the connected? function presented in class.

It turns out that was a rather inefficient implementation of the connectivity test. Several of you asked in the lecture whether we can, instead, keep track of the nodes already visited, to avoid running into an infinite cycle.

We can! Implement a new function connected?, same signature, etc., as before, but with a new implementation, as follows. Inside connected?, define a helper function connected-to-t2? that takes a single node t and asks whether it is connected to t2. This function carries, as an extra argument, the list of nodes already visited, i.e. the list of nodes for which we have already called connected-to-t2? recursively before. If so, we don’t want to call it again on the same node.

You still need the page-links-by-title function. It is included in the above file.

Exercise 3 Design a function cyclic? that returns true if the given wiki has a cycle, i.e. if there is a path from a page back to itself, following at least one link. For example, wiki-0 from Lecture 28 has cycles, whereas if we exclude the NEU page, all cycles are gone! (Turn these two into check-expects.)

Hint: a graph is cyclic exactly if there exists a node A such that some successor of A is connected to A. Please use this idea (an "algorithm") to implement your cyclic? function. Consider using the connected? function from above.

Exercise 4 Design a function broken-links that returns the list of broken links in a wiki. A broken link is a page name mentioned in a link that does not exist in the wiki. You may report a broken link multiple times.

Hint: break the problem down. First compute the list of broken links from a given page. Then combine these results for all pages.

Exercise 5 Design a function cleanup-links that takes a wiki and returns the wiki, but with all broken links removed. For example, given wiki-0, the function should return the same pages, except that "New Orleans" no longer links to "Mardi Gras".

Hint: Follow a hint similar to that in the previous exercise.

Exercise 6 Design a function max-indegree that returns the largest page indegree in a wiki, i.e., the largest number of incoming links, among all nodes in the wiki. You can return 0 if no links exist at all.