Study Guides (238,408)
CS 116 (15)
Midterm

# CS 116 Winter 2012 Midterm Package.pdf

4 Pages
417 Views

School
University of Waterloo
Department
Computer Science
Course
CS 116
Professor
Victoria Sakhnini
Semester
Fall

Description
CS 116 Winter 2012 SOS Midterm Review Package Design Recipe Includes: - Contract - Purpose o Using parameter names - (Effects) o (when doing questions with mutation only) o Explains what is happening when the function is called - Examples - Body of the Function - Testing o Includes base case o Includes all possible cases Why use Local Functions? - readability - efficiency - encapsulation Abstract List Functions - map: (X -> Y) (listof X) -> (listof Y) - filter: (X -> boolean) (listof X) -> (listof Y) - foldr: (X X -> Y) (listof X) -> Y - build-list: nat (nat -> X) -> (listof X) andmap: do all the elements in the list satisfy the Boolean function? ormap: do any of the elements in the list satisfy the Boolean function? Lambda - for single-use functions - not good to use in recursive problems Ex: ((lambda (x y) (* x y)) 2 3) ⇨ (* 2 3) ⇨ 6 Running Time - Constant – O(1) o Independent of the size of the input - Linear – O(n) o Proportional to the size of the input 2 - Quadratic -- O(n ) o Proportional to the square of the size of the input - Exponential – O(2 )n o As the size of input increases by 1, running time doubles - When comparing Running Time, we compare: o Running time on a single output o Running time on all output o Running time on a typical output o Average running time over all inputs o Best-case running time over all inputs o Worst-case ru
More Less

Related notes for CS 116

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.