CMSC 10500, Winter 2015, Lab 8

Preliminaries

Set Up

svn co https://phoenixforge.cs.uchicago.edu/svn/yourusername-cs105-win-15

replacing yourusername with your CNet ID. Press p to accept the certificate at the prompt, and then enter your password.

By now, you should know the basic steps to create and submit files to your repository. If not, go back and take a look at the previous lab's setup instructions.

You will need to create a lab8 directory in your repository and save in your lab8 directory the following file:

lab8.rkt, the Lab 8 Racket file.

Open lab8.rkt in DrRacket.

Problem Overview

You are familiar with binary trees, where each node has exactly two child nodes. We can generalize this data structure so that each node has an arbitrary number of children, represented as a list of nodes. We have defined such a struct for you in lab8.rkt -- a tnode that consists of a name (a string) and children, which is a list of tnodes. A tnode with no children has its children value equal to the empty list.

lab8.rkt also defines a variable named world-tree which stores the most populous cities of the world organized in a hierarchy of continents, countries, provinces, and cities. Take a look at the Racket code for the variable and understand how it corresponds to the tree below. (Only Africa is shown in detail in the interest of space.)

Part 1: Searching in a Tree

Let's consider how we might search for the place name in a tree. Either the place name is in the root of the tree, in one of the child nodes, or it does not exist in the tree. For example, to find out if Nairobi is in the world-tree, we would first check if (tnode-name world-tree) is Nairobi, and if not, recursively search for Nairobi in each of the continents the same way.

Write the following two mutually recursive functions to search for a place name in a tree:

search-tree : tnode string -> boolean
that takes in a tnode (like world-tree) and a place name, and returns true if the place is in the tree, and false if not. This function should make a call to search-forest which you will write as well.
search-forest : list-of-tnodes string -> boolean
takes in a list of tnodes (which we informally call a forest, since it is a collection of trees), and a place name, and returns true if the place is in at least one of the trees in the forest. This function should make a recursive call to itself, as well as to search-tree.

These check-expects should work:

(check-expect (search-tree world-tree "Nairobi") true) (check-expect (search-tree world-tree "United States") true) (check-expect (search-tree world-tree "South America") true) (check-expect (search-tree world-tree "Maharashtra") true) (check-expect (search-tree world-tree "Middle Earth") false)

Save and commit your work for Part 1.

Part 2: Tracing Paths

Instead of simply finding out whether a place exists is in a tree, we might want more information about its location in terms of its parent province, country, and/or continent. For example, we might want to know that the location of "Nairobi" in world-tree is

(list "World" "Africa" "Kenya" "Nairobi Region" "Nairobi")

Write two mutually recursive functions to return the path from the root of the tree to the place if it exists in the tree, and the empty list if not. These functions will be similar in spirit to the ones you wrote in Part 1, and may need to call search-tree.

get-path-from-tree : tnode string -> list-of-strings
takes in a tnode and a place name, and returns the path from the tnode to that place if it exists, or empty if not.
get-path-from-forest : list-of-tnodes string -> list-of-strings
takes in a list of tnodes and a place name as a string. If the place exists in the forest, this function should return the path from the appropriate tnode to that place. If the place does not exist under any of the tnodes, the function should return empty.

Check that

(check-expect (get-path-from-tree world-tree "Los Angeles") (list "World" "North America" "United States" "California" "Los Angeles")) (check-expect (get-path-from-tree world-tree "Colombia") (list "World" "South America" "Colombia")) (check-expect (get-path-from-tree world-tree "South America") (list "World" "South America")) (check-expect (get-path-from-tree world-tree "Bangalore") (list "World" "Asia" "India" "Karnataka" "Bangalore")) (check-expect (get-path-from-tree world-tree "Beijing") (list "World" "Asia" "China" "Beijing")) (check-expect (get-path-from-tree world-tree "Middle Earth") empty)

Optional Challenge Problem: Write these functions without calling search-tree, search-forest, or other functions that make a first pass through the tree to check if the place exists before finding the path. That is, find the path from the root to the place with a single pass through the tree.

You are finished with the lab. Make sure to save and commit your work. As usual, you will have the opportunity to finish your lab for this week's homework.

Part 3: Nearest Common Ancestor

We might want to know that the most that New York City and Los Angeles have in common is that they are both in the United States, or that Bogota and Lima are both in South America. We could also find the nearest common ancestor for places at different levels of the hierarchy, like a city and a province -- for example, the province of Sindh and the city of Seoul are both in Asia.

Write a function

closest-ancestor : string string tnode-> string or false

that takes in two place names (represented as two strings) and a tree and returns the place (as a string) that is their nearest common ancestor in the input tree. If either node is not in the input tree, your function should return false.

Check-expects:

(check-expect (closest-ancestor "Los Angeles" "New York City" world-tree) "United States") (check-expect (closest-ancestor "Bogota" "Lima" world-tree) "South America") (check-expect (closest-ancestor "Seoul" "Sindh" world-tree) "Asia") (check-expect (closest-ancestor "Singapore" "Mexico City" world-tree) "World") (check-expect (closest-ancestor "Lima" "Middle Earth" world-tree) false)

Helpful tips

One way to write this function is to use the get-path-from-tree function from Part 2.
Write an auxiliary function that takes in two parameters, which are the paths (from the beginning of the tree) for both places (i.e., calling get-path-from-tree with the world tree on your first string parameter and again on your second string parameter). This function makes the problem much easier because now you are dealing with recursion on lists.
Recurse on both lists until you reach an uncommon ancestor between the two.

Save and commit your work.

How to Check your SVN Submission

Visit https://phoenixforge.cs.uchicago.edu/ and log in with your CNET ID and password.
Under "Jump to a project..." select yourusername-cs105-win-15
From here, click on the "Repository" tab and you will be able to see the folders and files you have added and committed. You can even view the files from the website so that you can convince yourself that you have submitted the ones you want to be graded.