6.6

Assignment 17

home work!

Programming Language ISL

Due Date Monday 11/19 at 9pm

Purpose To process graphs.

Expectations
  • You should submit a single .rkt file containing your responses to all exercises via the Handin Server. We accept NO email submissions.

  • You are only allowed to use one of the language specified at the top of this page: failure to do so will result in a 0.

  • You are expected to use pre-defined abstractions when stated and/or when appropriate.

Below is a data definition for a network consisting of people who have names, beliefs, and a list of friends. You do not need to provide a template for this data definition.

; A Network is a [List-of Person]
 
; A Person is a (make-person String Belief [List-of String])
(define-struct person [name belief friends])
; and represents their name, their belief, and the name of their friends
 
; A Belief is one of:
; - "blue"
; - "red"
 
(define NETWORK
  (list
   (make-person "Alice" "red" (list "Carol" "Heidi"))
   (make-person "Bob" "blue" (list "Carol" "Dan"))
   (make-person "Carol" "red" (list))
   (make-person "Dan" "blue" (list "Carol" "Eric" "Frank" "Grace"))
   (make-person "Eric" "red" (list "Alice" "Bob" "Carol" "Dan" "Frank" "Grace"))
   (make-person "Frank" "blue" (list "Alice" "Bob" "Carol" "Dan" "Grace"))
   (make-person "Grace" "red" (list "Bob" "Frank"))
   (make-person "Heidi" "blue" (list "Alice" "Bob" "Carol" "Dan" "Eric" "Grace"))))

Exercise 1 Design the function update-network, which takes a Network and updates every individual’s belief to become the belief the majority of their friends have. If there is no majority amongst their friends (a tie), then their belief is unchanged. Note that this update is atomic which means everyone’s beliefs updates at once based only on the previous network’s state. In other words, where someone appears in the network should have no effect on the update process.

Exercise 2 Design the function can-reach?, which takes the names of two people and a network asks if the first person can reach the second. Anyone can reach themselves, and anyone can reach another person through their friends if that friend has the same belief as them.

Assume the network given to this function is acyclic and specify as such in your purpose statement. Be sure to only test on acyclic networks; the provided network is not acyclic.