CS 151: Introduction to Computer Science-1

Fall 2007

Mondays and Wednesdays, 9:00 - 10:20 am, Ryerson 276
Lab on Tuesdays 3:00 - 4:20pm, JRL A01C (Mac lab)


This document will be updated throughout the quarter. Please, check out the latest version at http://www.classes.cs.uchicago.edu/archive/2007/fall/15100-2/index.html
Announcements | Personnel | Textbooks | Software | Grading Policy | Lateness Policy | Collaboration Policy | Syllabus | | Homework | Exams

Announcements

Personnel

Name Role Office Office hours Email
Svetlozar Nestorov Instructor Ryerson 275-A by appt. evtimov at cs.uchicago.edu
Varsha Dani TA Ryerson 162A - varsha at cs.uchicago.edu
Casey Klein TA Ryerson 178 Tu 1:30-2:30pm clklein at cs.uchicago.edu
Jing Tie TA RI 340 Fr 3-4pm jtie at cs.uchicago.edu

Textbooks

The textbook for the course is How to design programs. The optional textbooks are The Little Schemer by Freidman and Felleisen and Structure and Interpretation of Computer Programs by Abelson and Sussman

Software

DrScheme
Installed in /opt/cs-plt/cs-plt-371 on cs machines; just type drscheme.

Grading Policy

The grades for the class will be based on your results on the weekly homework, labs, and midterm. The approximate weights are:

Lateness policy

Homework is due at the beginning of class. No late homework will be accepted. You have two 48-hour extensions for the project labs.

Collaboration policy

We encourage you to discuss the course material with you fellow students. However, submitted assignments should be your own work. If you discuss in details specific problems or assignments with other people, please, acknowledge them on the front of the work that you turn in. You should also read and understand the official University policy on Academic Honesty. If you have any questions, please, discuss them the instructor.

Syllabus

WeekTopicReadings
1Basic forms of dataCh 2 - 6
2define-struct, unions and listsCh 6 - 10
3Lists, trees, and data abstractionCh 12 - 16
4Iterative refinement, 2 complex pieces of data, localCh 16 - 18
5Mutually referential data definitions, abstractionCh 15, 19 - 21
6Abstraction, lambda, natural numbersCh 19 - 22, 24, 11
7Generative recursion, graphsCh 25 - 28
8Accumulators, more graphsCh 30 - 32, 14
9Evaluators
10Looking forward

Homework

Homework is due before the beginning of class. Print it out and bring it to class. Put your name and the homework number at the top of the page. All assignment numbers come from the online version of the text. They may be slightly different in the first and second printing (but they match the third printing).

Due DateLanguage (in DrScheme)Problems
9/28Beginning StudentImages: 1.1 - 1.5
10/1Beginning Student Images: 2.1 - 2.3, 3.1 - 3.2
10/3Beginning Student Write the function direct-to-0 : posn -> number that determines how far a posn is from the origin.

Write the function downtown-to-0 : posn -> number that determines how far a posn is from the origin, if the coordinates were block numbers. That is, you cannot cut through buildings and have to walk on streets (this is commonly called "Manhattan" distance).

Write the function direct-between : posn posn -> number that determines the distance between two points. (Hint: wishlists & reuse!)

HtDP: 7.2.2 (make sure all vehicles have wheels)

Develop the function toll : vehicle -> number. It determines the amount a vehicle must pay at a toll. The toll costs $0.50 per wheel.

Extend the animal data definition from class with one new kind of animal. Make sure the new animal has a weight.

Write the function diet : animal -> animal. It accepts an animal and returns the same animal, but with half of the weight.
10/8Beginning StudentWrite the following functions. Don't forget about re-use and helper functions (the functions we wrote in class are fair game for re-use as helper functions).

; a list-of-symbols is either
; - empty, or
; - (cons symbol list-of-symbols)

; contains-doll? : list-of-symbols -> boolean
; to determine if 'doll appears in alos
(define (contains-doll? alos) ...)

; a list-of-numbers is either
; - empty, or
; - (cons number list-of-numbers)

; len : list-of-numbers -> number
; to determine the number of elements in alon
(define (len alon) ...)

; avg : list-of-numbers -> number
; to determine the average of the elements in alon
(define (avg alon) ...)

; sq-nums : list-of-numbers -> list-of-numbers
; to square each element in alon
(define (sq-nums alon) ...)

; rev : list-of-numbers -> list-of-numbers
; to reverse the elements in alon
(define (rev alon) ...)

Images: 4.1 - 4.3
Hint: break down complex tasks into smaller ones. Wishlists!
10/10Beginning Student w/List AbbreviationsDevelop the function bm. The function consumes two numbers (n and m) and a symbol (s). It produces a list of n lists. Each of these lists is a list of m symbols, namely, s.

Hint: You need an auxiliary function.

Consider the following modification. Instead of using the same symbol over and over again, create a string that says "cell23" where 2 and 3 are (running) indices. You can us the functions string-append which concatenates two strings and number->string which creates a string representation from a number. This variant is, for example, useful in Web programming.
10/15Beginning Student w/List AbbreviationsWrite the following functions.
; a ftn is either
; - 'unknown, or
; - (make-child symbol number symbol ftn ftn)
(define-struct child (name date eyes mom dad))

; 40-year-old-ancestor? : ftn -> boolean
; to determine if a 40-year-old ancestor is in a-ftn
(define (40-year-old-ancestor? a-ftn) ...)

; count : ftn -> number
; to count the number of people in a-ftn
(define (count a-ftn) ...)

; avg-age : ftn -> number
; to determine the average age in an-ftn
(define (avg-age a-ftn) ...)
Hint: use helper functions


;; above : image image -> image
;; to put one image above another
;; HINT: use put-pinhole to move the pinhole of
;;       the first to the middle of the bottom edge
;;       and the second to the middle of the top edge
(define (above i1 i2) ...)

;; a lego is
;; - (make-lego symbol number)
(define-struct lego (color width))

;; lego->image : lego -> image
;; to render a lego brick. All legos are rectangular
;; and are 10 pixels tall
(define (lego->image l) ...)

;; a lego-building is either:
;; - lego
;; - (make-bigger lego lego-building lego-building)
(define-struct bigger (lego left right))

;; how-high : lego-building -> number
;; to determine how high a lego building is, in pixels
;; (reminder: each lego is ten pixels tall)
(define (how-high an-lb) ...)

;; find-colored-brick : lego-building color -> lego or false
;; to find any colored brick with the color `color' in an-lb
;; or return false if there are no such legos.
(define (find-colored-brick an-lb color) ...)

;; lb->image : lego-building -> image
;; to render a lego building into an image
(define (lb->image an-lb) ...)

;; Examples as tests
;; (make more tests yourself -- these should be your last tests!)

(lb->image
 (make-bigger (make-lego 'blue 100)
              (make-bigger (make-lego 'green 60)
                           (make-lego 'orange 40)
                           (make-lego 'purple 40))
              (make-bigger (make-lego 'pink 60)
                           (make-lego 'orange 40)
                           (make-lego 'purple 40))))


(lb->image
 (make-bigger (make-lego 'lightblue 80)
              (make-bigger (make-lego 'blue 40)
                           (make-bigger (make-lego 'green 20)
                                        (make-lego 'orange 10)
                                        (make-lego 'purple 10))
                           (make-bigger (make-lego 'pink 20)
                                        (make-lego 'orange 10)
                                        (make-lego 'purple 10)))
              (make-bigger (make-lego 'salmon 40)
                           (make-bigger (make-lego 'green 20)
                                        (make-lego 'orange 10)
                                        (make-lego 'purple 10))
                           (make-bigger (make-lego 'pink 20)
                                        (make-lego 'orange 10)
                                        (make-lego 'purple 10)))))
10/22Intermediate StudentHtDP: 17.1.2, 17.6.5, 18.1.5 (1,2,5)

Exams

  • The midterm (open-book) will be held during lab hours on Tuesday, October 23, 2007.