School

University of WaterlooDepartment

Computer ScienceCourse Code

CS116Professor

Jiye LiStudy Guide

FinalThis

**preview**shows pages 1-3. to view the full**14 pages of the document.**CS 116

Introduction to Computer Science

Module 1: Review

•Design Recipe- A development process that leaves behind a written explanation:

1. Contract – Describes what type of arguments the function consumes and what value it

produces

2. Purpose – Describes what the program is to compute (i.e. consumes & produces)

3. Examples – Illustrating use of the program

4. Definition – Scheme definition of the function

5. Tests – A representative set of inputs and expected outputs

ex. ;; sum-of-squares: num num -> num

;; Purpose: produces sum of squares of arg1 and arg2

;; Examples: (sum-of squares 0 2.5) => 6.25

;; (sum-of-squares 3 4) => 25

(define (sum-of-squares arg1 arg2) (+ (* arg1 arg1) (* arg2 arg2)))

;; Test sum-of-squares

(check-expect (sum-of-squares 2 3) 13)

(check-expect (sum-of-squares -1 1) 2)

* check-expect is used for exact numbers only; use check-within for a range of values

•Structure- Combines a fixed number of values into a single piece of data; represents

compounds of information

1) Structure Definition:

(define-struct nameofstructure (var1 var2 … vark))

2) Data Definition:

;; comment on the constraints of each var

3) Regular design recipe

(i) Contract

instead of num, symbol, string, etc. use the name of the structure

for the use of one type of variable, use (union type1 type2 … etc)

ex. mminfo-artist: (union mp3info movieinfo) string

(mminfo-artist (make-mp3info "Beck" "Time Bomb" 183 'Rock)

=> "Beck"

(mminfo-artist (make-movieinfo "Orson Welles" "Citizen

Kane" 119 'Classic)) => "Orson Welles"

(ii) Purpose

(iii) Examples

(iv) Testing

Create structure:

(define structure1 (make-nameofstructure n1 n2 … nk))

Extract a single item from structure using selector functions:

(nameofstructure-var1 structure1) => n1

(nameofstructure-var2 structure1) => n2

...

(nameofstructure-vark structure1) => nk

1

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Ex. (define-struct date (year month day hour))

;; A date is a structure (make-date y m d h) where y is a positive

integer (>= 2009) representing the year. m, a month in a year, is an

integer in the range of 1 to 12 inclusive. d, a day in a month, is

an integer in the range of 1 to 31 inclusive. h is an integer in the

range of 0 to 23 inclusive to represent an hour in a day.

(define date1 (make-date 2001 6 2 23))

(date-year date1) => 2001

(date-month date1) => 6

(date-day date1) => 2

(date-hour date1) => 23

•local contains a series of local definitions (variables, helper functions, constants, etc.) plus

an expression (evaluation) using them of the form:

(local

[(...def1...)

(...def2...)

...]

exp)

Module 2: More Functional Abstraction

•filter consumes a predicate and a list and filters out all items in that list that produce true

to the predicate

;; filter: (X boolean) (listof X) (listof X)

(define (filter pred alist)

(cond

[(empty? alist) empty]

[(pred (first alist))

(cons (first alist) (filter pred (rest alist)))]

[else (filter pred (rest alist))]))

Ex. (filter even? '(1 2 3 4 5 7)) => '(2 4)

•map transforms a list element-by-element into another list of the same length

;; map: (X Y) (listof X) (listof Y)

(define (map f alist)

(cond

[(empty? alist) empty]

[else (cons (f (first alist)) (map f (rest alist)))]))

Ex. (map sqr '(2 3 4)) => '(4 9 16)

•foldr consumes a list of X and produces a Y by processing the list to the right

;; foldr: (X X X) X (listof X) X

(define (foldr combine base alist)

(cond

[(empty? alist) base]

[else (combine (first alist)

(foldr combine base (rest alist)))]))

Ex. (foldr + 0 '(1 2 3)) => 6

(foldr max 0 '(2 4 6 8)) => 8

2

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

•member consumes X and a list of X and produces True if the list of X contains the given X

;; member: X (listof X) boolean

(define (member x lox)

(cond

[(empty? lox) false]

[(equal? x (first lox)) true]

[else (member x (rest lox))]))

Ex. (member 'a '(a b c)) => true

•Polymorphic Function- has a contract that has variables for the types; arguments are

flexible

•build-list consumes a natural number greater than zero and a function and produces a

list of every natural number from 0 to the inputted number with the function applied to it

;; build-list: nat (nat X) (listof X)

(define (build-list n func)

(local

[(define (count-up x i)

(cond

[(= n i) empty]

[else (cons i (count-up (add1 i)))]))]

(map func (count-up n 0)))

Ex. (build-list 6 sqr) => '(0 1 4 9 16 25)

•lambda lets us build a function from scratch: (lambda (p1 p2 … pn) expr)

where (p1 p2 … pn) are the parameters and expr is the expression that evaluates the

parameter(s); can be used to build an anonymous function

Ex. Instead of: Use:

(define (power-of-2 n) (define (power-of-2 n)

(local => (build-list n (lambda (x)

[(define (fn x) (expt 2 x))))

(expt 2 x))]

(build-list n fn))

•arithmetic is a list of functions '( + - * /)

Module 3: Generative Recursion

•Natural/Structural Recursion- Follows templates derived from a self-referential data

definition; has a template that tests a base case, etc.

•Generative Recursion- More complex recursion that may make the program run faster

where structural recursion may not be the best way to solve a problem; the argument of the

recursive (function) application is “generated” by new volumes of data, not just recursion on

the rest of the list

Ex. Selection Sort

Using Structural Recursion:

(define (sort-list lon)

(cond

[(empty? lon) empty]

[else (insert (first lon) (sort-list (rest lon)))]))

(define (insert item sortedlist)

(cond

3

###### You're Reading a Preview

Unlock to view full version