Due Date: Wednesday June 17, 10pm EDT.
Purpose: To do exercises with Graphs
Extra Credit This assignment is optional and will count as extra credit
You must submit a single .rkt file containing your responses to all exercises via the Handin Server. We do not accept email submissions.
You must use the programming language specified at the top of this page.
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 revisit it before submitting each assignment.
Unless otherwise stated, for all programming problems you must provide (i) a signature, (ii) a purpose statement, (iii) sufficiently many check-expects (not for big-bang programs), and (iv) the code, in the language specified at the top of this page.
Be sure to look at the feedback for previous assignments before submitting, as we will be grading you more strictly on things we have pointed out before.
Use list abstractions whenever possible in your solution.
If you design any functions with accumulators (coming in Tuesday’s lecture), don’t forget to add accumulator statements.
Exercise 1 Consider again the data designs of Page and Wiki from Lecture last Thursday. Copy these designs into your homework file.
(define-struct page [title links]) ; A Page is a (make-page String [List-of String]) ; repr. a web page's title and links to other pages. (define PAGE-0 (make-page "Khoury" (list "NEU"))) (define PAGE-1 (make-page "NEU" (list "Khoury" "Boston"))) (define PAGE-2 (make-page "Boston" (list "NEU" "Shillman Hall"))) (define PAGE-3 (make-page "Shillman Hall" (list "NEU"))) (define PAGE-4 (make-page "New Orleans" (list "Mardi Gras"))) ; A Wiki is a [List-of WebPage] ; Interpretation: A list of webpages (like the Internet) (define WIKI-0 (list PAGE-0 PAGE-1 PAGE-2 PAGE-3 PAGE-4))
Design the function find-path that takes two strings t1 and t2 representing page names in a wiki, and a wiki. If there is a path (following links) from t1 to t2 in the wiki, your function should return such a path as a list of strings, representing the pages visited along the path. Note that the first string in the output must be t1, and the last string must be t2.
If there is no such path, your function should return the empty list.
The length of the list your function returns should equal the number of links followed along the path PLUS 1. For example, if t1 and t2 are equal, then (list t1) is one valid answer (the number of links followed is 0; the list has length 1).
Hint: You will need a helper function that finds a path from one of t1’s links to t2. This function and find-path will call each other mutually recursively. Also, you may need the eliminate function (shown below) although you are not required to use it.
; eliminate : String Wiki -> Wiki ; the wiki without page with the given name (check-expect (eliminate "NEU" (list PAGE-0 PAGE-1)) (list (make-page "Khoury" '()))) (define (eliminate t w) (cond [(empty? w) '()] [(cons? w) (if (string=? (page-title (first w)) t) (eliminate t (rest w)) (cons (eliminate-links-to t (first w)) (eliminate t (rest w))))])) ; eliminate-links-to : String Page -> Page ; the page without any links to the page with the given name (check-expect (eliminate-links-to "NEU" PAGE-3) (make-page "Shillman Hall" '())) (define (eliminate-links-to t p) (make-page (page-title p) (filter (lambda (l) (not (string=? l t))) (page-links p))))