Exam 1: Scheme Fundamentals

Distributed: Friday, September 22, 2000
Due: 11 a.m., Friday, September 29, 2000
No extensions!

This page may be found online at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Exams/exam.01.html.

• Preliminaries
• Problems
  • A. Some Definitions
    • 1. Functional Programming
    • 2. Recursion
  • B. A CD Database
    • 3. The Database Format
    • 4. Searching the Database
    • 5. Searching with Two Keys
    • 6. Searching for Songs
  • C. A Course Record
    • 7. Some Sample Records
    • 8. Computing GPA
    • 9. Distribution Credits
    • 10. Summaries

Preliminaries

There are 10 problems on the exam. Each problem is worth 10 points.

For convenience, the questions are divided into sections. The point value associated with a problem does not necessarily correspond to the complexity of the problem or the time required to solve the problem. If you write down the amount of time you spend on each question, I'll give you three points of extra credit.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use all reasonable resources available to you except for other people. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. Do not use exam or homework solutions you find on the Web.

This is a take-home examination. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast your work. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted.

You must include the following statement on the cover sheet of the examination. Plesae sign and date the statement. Note that the statement must be true; if you are unable to sign the statement, please talk to me at your earliest convenience.

I have neither given nor received help (except from my instructor) on this examination. I am not aware of any other students who have given or received help (except from their instructor) on this examination.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is among the hardest exams I have ever taken. If you don't start it early, you'll have no chance of finishing the exam.'' You may also summarize these policies.

Answer all of your questions electronically and turn them in in hardcopy. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam (a plain text file, please). Put your answers in the same order that the problems appear in. If you write ``have a happy day'' at the end of your exam, I'll give you two points of extra credit.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by emphasizing your answer and including a clear set of work that you used to derive the answer.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem yo u have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.

Problems

A. Some Definitions

1. Functional Programming

Find and record three reasonable definitions of functional programming. You might look on the Web, in textbooks (programming languages textbooks are best), or in dictionaries.

For each definition, indicate how the Scheme you've learned to date has and has not matched the definition.

You should make sure to cite the sources you use in appropriate format.

2. Recursion

In your own words, explain the concept of recursion.

B. A CD Database

Sarah and Steven Schemer have decided to use Scheme to record their enormous collection of popular CDs. For each CD, they'd like to record (1) the artist, (2) the title, (3) the genre, and (4) a list of songs on the CD.

3. The Database Format

a. How might you represent this database in Scheme? Be as clear as you can in your description.

b. Using this representation, show how to represent your five favorite CDs.

4. Searching the Database

The Schemer's would like to be able to search their database so that they can easily look up lists of albums.

Write and test a procedure, (search-cd category key database) that lets them search by artist, title, or genre and returns all matching records. For example, (search-cd 'artist "Van Morrison" samscds) should return all the CDs I have by Van Morrision.

5. Searching with Two Keys

Show how to use search-cd to find a CD matching a given artist and title.

6. Searching for Songs

Write and test a procedure, (search-songs song database) that lets someone search the database by song title.

C. A Course Record

After too many years of a difficult registration system, the Registrar has decided to turn to CSC151 for help in writing a new system. We've decided to store the information as a list of student records. For each student, we record name, id, graduation year, major, and a list of courses. For each course, we record semester, department, abbreviation, grade, and credits.

For example

(define students
  '(("Sarah Schemer" "000011235" "2002" "CS"
     (("Fall 1999" "Math/CS" "CSC151" "A-" 4)
      ("Fall 1999" "General" "TUT101" "B" 4)
      ("Fall 1999" "Math/CS" "MAT133" "C+" 4)
      ("Spring 2000" "Math/CS" "CSC152" "F" 4)))
    ("Steven Schemer" "000011236" "2003" "Math"
     (("Fall 1999" "Math/CS" "CSC151" "A-" 4)
      ("Fall 1999" "General" "TUT101" "B" 4)
      ("Fall 1999" "Math/CS" "MAT133" "C+" 4)
      ("Spring 2000" "Math/CS" "CSC152" "F" 4)))))

7. Some Sample Records

Using this form, create a list of four students in the class of 2001 (who will have finished three years of classes).

8. Computing GPA

Write a procedure, (gpa studentname) that computes a student's GPA. You may wish to create an auxiliary list that gives a point value for each letter grade.

9. Distribution Credits

Write a procedure, (credits division studentname), that computes the number of credits the student has in a division (or non-divisional credits, such as tutorial). For example,

> (credits 'Science "Sam Rebelsky")
54

10. Summaries

Write a procedure, (summarize studentname) that summarizes information about a student. For example,

> (summarize "Sam Rebelsky")
(GPA 3.2 Science 54 Humanities 20 SocSci 30 General 10)