Transcript Review
cs1321 December 6, 2001 Review Week 1 What is computer science? What's an algorithm? Processes and programs Overview of some programming language concepts Functional vs. imperative vs. object-oriented paradigms Compiled vs. interpreted languages Math revisited What's a function? What's a parameter? What's a literal? What's an operator? Going from mathematical functions to Scheme functions Review of function terminology Defining Scheme functions! Design Recipes Definitions More on Procedures Frequently, the term ‘algorithm’ is used in place of the term ‘computational procedure’. An algorithm is defined as: One Definition “Computer science revolves around computational processes, which are also called information processes or simply processes. A process is a dynamic succession of events---a happening.” -- H. Abelson, et al., “Structure and Interpretation of Computer Programs” • a finite procedure, • written in a fixed symbolic vocabulary, • governed by precise instructions, • moving in discrete steps, • whose execution requires no insight, cleverness, intuition, intelligence, or perspicuity, • that sooner or later comes to an end Definitions Definitions Functions, parameters, literals, operators Week 2 Fahrenheit to Celsius problem Use of abstraction Larger example with abstraction: Movie ticket prices, revenue, Abstraction – breaking the problem down Synthesis – building a larger solution from solved small abstracted parts Making decisions – cond statement Boolean types – true, false Boolean or logical operators and, or not Boolean valued functions – predicates Symbols Data analysis and definitions – variable pricing on DVDs based on quantity purchased Code driven by the data analysis Key Concepts Conditionals/Predicates (define (negative? num) (if (< x 0) true false)) What character do we usually use to end a predicate function name? (hint) Week 3 Grouping data with a structure Intro of posn data structure How to define your own structure define-struct Functions generated for you when you define a structure: field selectors predicate (and we see much later set functions as well) constructor (make-whatever) Embarrassing photo structure example Effect of structures on template Week 4 Shape data definition – can be circle, square, etc. Effect on template Self-referential data structures our own – matryoska doll structure scheme provided: list built with cons function first and rest functions cons cell underlying list list? empty? cons? effect on template Recursion a function calling itself used for repetition 1. function calls itself 2. has terminating condition(s) 3. moves closer to a trivial version of the problem (moves closer to the terminating condition) How does it work? Activation stack! substitution model of evaluation example: factorial Week 5 Given a list, build a new list increase TA salaries example Practice with handling TA structures Insertion sort on list insert a TA into a list of TAs based on salary Introduction of list function: (list 1 2 3) and ‘(1 2 3) Week 6 Binary Trees family tree example know the tree terminology!! Tree recursion Tree traversal preorder inorder postorder Binary Search Tree searching a BST inserting into a BST deleting from a BST – tough! Week 7 Processing lists of lists Tree style recursion Flatten function append function Mutually referential data structures Iterative refinement Processing two lists simultaneously The truth about append function Week 8 Merging lists Writing good test cases – cover the possibilities! Recognizing similarities in functions and abstracting! pass values as parameters pass functions as parameters Scope Introduction of local locally defined functions Week 9 Map function Examples of passing functions as parameters Effect on contract Merge sort – divide and conquer Lambda bodies Generative recursion Billiard balls Week 10 Quicksort Fractals Head recursion versus tail recursion pros cons converting between them Week 11 Graphs BFS what data structure does it use? DFS what data structure does it use? Week 12 Breaking away from pure functional programming: let set! Iteration – the do loop Vectors Big O – complexity of algorithms Week 13 More Big O examples Grouping statements with begin Persistence – intro to lexical closure adder example Coke machine example Week 14 Lexical closure continued Coke machine example Inheritance with vending machine and coke machines, coffee machine And a taste of Java…