Assignment 9 for CSCI 431

• Running Scheme

  MIT Scheme has been installed on all Sun workstations (i.e., flat-rock, hendersonville, marshall, and brevard), and on the linux box burnsville.

  You can invoke the Scheme interpreter by giving the command scheme at the UNIX prompt. To leave the Scheme interpreter give the command (exit).

  To load files of Scheme code use the procedure load:

  
     (load "assign9.scm")
  

  
  

• On-Line Resources

  The primary URL is http://www.swiss.ai.mit.edu/projects/scheme/. This site contains a manual as well as various implementations.

  There were also a number of on-line resourses listed in the class Scheme presentation.

  Here are a few scheme programming examples for you to look at.

  
  

• Description of Assignment

  In this assignment you will extract different sorts of information from a database of courses. For each course, the database describes which course (if any) logically follows it, who teaches the course, and which courses (if any) are prerequisites of the course.

  The database will be encoded in Scheme as a list of entries, with one entry for each course in an imaginary CS department. Each entry will be a list with the following form:

  
      ( <course #> <next course> <prof> <prereq1> ... <prereqN>)
  

  where the number of prerequisites for the course is N. If the course has no prerequisites, the list will have the form:

  
       (<course #> < next course > < prof >)
  

  If the course has alternative prerequisites, they are grouped in a list. For example:

  
       (cs301 cs302 Smith (cs102 ee220) cs201)
  

  means that cs301 requires cs102 OR ee220, and also requires cs201.

  When the course has no logical successor, <next course> will be designated by the atom NONE.

  The Scheme code for encoding a sample database is:
  

  
  (define COURSES
  '((cs101 cs102 Petty)
    (cs102 NONE Petty cs101 math101)
    (cs201 cs202 Vega (cs102 ee105) math101)
    (cs202 cs330 Gabriel cs201)
    (cs230 cs330 Vega cs201 math102)
    (cs330 NONE Vega (cs202 cs230) math102)
    (cs340 cs341 Gabriel cs202)
    (cs341 NONE Gabriel cs340)
    (cs380 NONE Gabriel cs102)
    (math102 NONE Lee math101))
  )
  

  NOTE:
  
  • You must implement the following functions exactly as defined in each step.
  • With the description of each function are some sample calls to the function to illustrate what is intended by the textual description. These are not intended to be a complete test suite.
  1. Cut and paste the above define into a .scm file that you will use as a sample database. Note that the Scheme statements define the value of COURSES to be the sample course database. This example is for your use during code development. Your submitted program will be run on a different database, but one which uses the same encoding as that described above. So there should be no COURSES database defined in the .scm file you submit.

     
     

  2. Write the following functions:
     1. SEQ: takes a single argument (a course name) and returns the next logical course following that one.
     2. PROF: takes a single argument (a course name) and returns the name of the professor who teaches that course
     3. PREREQS: takes a single argument (a course name) and returns a list of the course prerequisites. For example, given the sample database

        
             > (SEQ 'cs101) ==> cs102
             > (SEQ 'cs102) ==> NONE
             > (SEQ 'ee105) ==> NONE
             > (PROF 'cs202) ==> Gabriel
             > (PROF 'ee105) ==> NONE
             > (PREREQS 'cs101) ==> ()
             > (PREREQS 'cs102) ==> (cs101 math101)
             > (PREREQS 'cs201) ==> ((cs102 ee105) math101)
             > (PREREQS 'ee105) ==> ()
        

        HINT: each of these functions takes a single argument, but the functions need to step through the COURSES database using recursion. This means that you will need to have each of these functions call a recursive function that takes the course name and COURSES as arguments.

  3. Write the function TEACHES that takes a single argument (a prof name) and returns a list of courses that the prof teaches.

     
          > (TEACHES 'Lee) ==> (math102)
          > (TEACHES 'Vega) ==> (cs102 cs230 cs330)
          > (TEACHES 'Lester) ==> ()
     

  4. Write PREREQ-OF, a function that takes a course name and returns a list of courses that it is a prerequisite of. The list should include courses for which the course is an alternative prerequisite (note the call to (PREREQ-OF 'cs202) below).

     
          > (PREREQ-OF 'cs101) ==> (cs102)
          > (PREREQ-OF 'cs202) ==> (cs330 cs340)
          > (PREREQ-OF 'cs380) ==> ()
          > (PREREQ-OF 'ee201) ==> ()
     

  To Be Handed In

  You should turn in code implementing all of the functions detailed above, as well as any supporting routines that you write that are necessary for these functions to work correctly. All functions should be included in one file, which should be submitted electronically to your class ftp directory. The assignment is due Dec 6th.