Functional Problem Solving (CSC 151 2014S) : Handouts
Primary: [Front Door] [Schedule]  [Academic Honesty] [Disabilities] [Email]  [FAQ] [Teaching & Learning] [Grading] [Rubric]  [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Setup]  [Functions AZ] [Functions By Topic]  [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2010S)] [Rebelsky (2013F)] [Weinman (2012F)] [Weinman (2014S)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)]
This is an approximate schedule. Expect dates and topics to change. (I will try to keep due dates the same.)
Some of the information here can also be found in the Google calendar for the course, which is available at <http://bit.ly/151gcal>.
Week 01: An Introduction to ...  

Date  Topic  Reading  Lab  Work Due  
01  Monday, 20 January 2014  An Introduction to Algorithms Introduction: What is CS? Exercise: An everyday algorithm. Debriefing on exercise.  
02  Tuesday, 21 January 2014  An Introduction to Linux Lessons from day one. Common parts of an algorithm. About the course. Getting started with Linux. Some administrative details (if there's time).  The Linux Environment and Parts of Algorithms  Getting Started with Linux No writeup required.  HW 1: Introductory Survey 
03  Wednesday, 22 January 2014  An Introduction to Scheme Why use programming languages? Scheme history. Scheme basics.  The Parts of an Algorithm & The DrRacket ProgramDevelopment Environment & Beginning Scheme & How Scheme Evaluates Expressions (Take 1)  Starting Scheme Writeup 03: Extra 2  
04  Friday, 24 January 2014  Computing with Symbols and Numbers Values and types. Kinds of numbers. The modulo operation.  Numeric Values & Symbolic Values  Numeric Computation Writeup 04: Extra 1  Quiz 1 
Week 02: Two Models of Images  
Date  Topic  Reading  Lab  Work Due  
05  Monday, 27 January 2014  Drawings as Values Representing images. Thinking about drawings through composition/decomposition. The underlying representation. Pure approaches vs impure approaches.  Drawings as Values  Drawings as Values Writeup 05: Exercise 4, parts a, c, d, f, and g  
06  Tuesday, 28 January 2014  Writing Your Own Procedures Why define your own procedures? How to define your own procedures.  Writing Your Own Procedures  Drawings as Values and Writing Your Own Procedures Writeup 06: Procedures, Exercises 3 and 6  HW 2: Starting Scheme 
07  Wednesday, 29 January 2014  Writing Your Own Procedures, Continued  Writing Your Own Procedures and How Scheme Evaluates Expressions (Take 2)  Writing Your Own Procedures Writeup 07: Exercises 3 and 6  
08  Friday, 31 January 2014  Documenting Programs and Procedures The need for documentation. The Six P's  a strategy for documenting procedures. A few additional P's. Practice.  Documenting Your Procedures  Writeup 08: Document the rectangle procedure 
Quiz 2 
Week 03: Design and Color  
Date  Topic  Reading  Lab  Work Due  
09  Monday, 3 February 2014  Testing Your Procedures Why test? Strategies for testing. The primary testing operations.  Testing Your Procedures  Testing Your Procedures Writeup 09: Exercise 2  
10  Tuesday, 4 February 2014 
Side Effects: Images, Output, and More
Output with display and newline .
Using output procedures to trace code.
More procedures for working with images.

Output in Scheme and Basic Image Operations  Side Effects Writeup 10: Exercise 4a  HW 3: Drawing Generally and Concisely 
11  Wednesday, 5 February 2014  A Design Perspective A bit about design. A bit about color theory. Exploring some images and design spaces.  Design and Color  
12  Friday, 7 February 2014  Raster Graphics and RGB Colors Representing images, revisited. Pixels and colors: The basics. RGB colors. Those weird numbers.  Raster Graphics: Images from Pixels and Colors and RGB Colors  Raster Graphics and RGB Colors Writeup 12: Exercise 10  Quiz 3 
Week 04: Transformations  
Date  Topic  Reading  Lab  Work Due  
13  Monday, 10 February 2014  Transforming Colors Review: Color basics. Integerencoded RGB colors. Computing new colors from old. An example.  Transforming RGB Colors  Transforming RGB Colors Writeup 13: Exercises 5 (parts a, c, and e) and 6 (parts b and e)  
14  Tuesday, 11 February 2014  Transforming Images Transforming images by transforming each pixel. Sequencing transformations with compose. Anonymous transformations.  Transforming Images  Transforming Images Writeup 14: Exercises 3 and 7a  Exam 1 (due 10:30 p.m. via email) 
15  Wednesday, 12 February 2014  Homogeneous Lists: Making and Manipulating Groups of Drawings Context: What and why lists? Building lists. Mapping lists. Other list operations.  Making and Manipulating Homogeneous Lists  Making and Manipulating Lists of Drawings Writeup 15: Exercise 5  Exam 1 (due in class in paper form) 
16  Friday, 14 February 2014  Programming the GIMP Tools A new model of images making. Coding algorithms for drawing. Other useful techniques.  The GNU Image Manipulation Program and Programming the GIMP Tools  Scripting the GIMP Tools No writeup  Quiz 4 
Week 05: Control  
Date  Topic  Reading  Lab  Work Due  
17  Monday, 17 February 2014  Exam 1 Discussion General issues. Exam strategies. Additional Q&A.  
18  Tuesday, 18 February 2014 
Boolean Values and Predicate Procedures
Boolean values.
Predicates  Procedures that return Boolean values.
Combining booleans with and and or .

Boolean Values and Predicate Procedures  Boolean Values and Predicate Procedures  HW 4: Transforming Colors, Drawings, and Images 
19  Wednesday, 19 February 2014 
Conditionals
The parts of an algorithm, revisited.
Choosing between two options with if .
Making multiple choices with cond .

Conditionals  Conditionals Writeup 19: Exercises 3c and 4d  
20  Friday, 21 February 2014 
Naming Local Values
Why name things.
Naming things with let .
Naming things with let* .
Naming procedures.

Local Bindings  Local Bindings Writeup 20: Exercises 6d and 7b  Quiz 5 
Week 06: Recursion  
Date  Topic  Reading  Lab  Work Due  
21  Monday, 24 February 2014  Anonymous Procedures What is a procedure? Describing procedures. Anonymous procedures. Anonymous procedures through lambda expressions. Other kinds of anonymous procedures.  Anonymous Procedures  Anonymous Procedures  
22  Tuesday, 25 February 2014  Images as Functions from Position to Colors Models of images. Iterating over positions: Images as functions from position to color. Blends and other positionallycomputed images. Drawing simple shapes. Some strange computations.  Building Images by Iterating Over Positions  Building Images by Iterating Over Positions Writeup 22: Exercise 4  HW 5: Conditional Transformations and Conditional Images 
23  Wednesday, 26 February 2014  Revisiting Lists Lists, revisited. New list operations. Drawings as values.  Building Data Structures with Heterogeneous Lists  Exploring Lists Writeup 23: Exercise 4  
24  Friday, 28 February 2014 
Recursion Basics
Some challenges.
The idea of recursion.
A sample recursive procedure: sum .

Recursion Basics  Recursion Basics  Quiz 6 
Week 07: Recursion, Continued  
Date  Topic  Reading  Lab  Work Due  
25  Monday, 3 March 2014  Recursion Basics, Continued Reflection. Questions. Recursion vs. other forms of repetition.  Recursion Basics  Recursion Basics Writeup 25: Exercise 4 and 5 from Recursion Basics  
26  Tuesday, 4 March 2014  Recursion with Helper Procedures Basics of helper recursion. A term: Tail recursion.  Recursion with Helper Procedures  Recursion with Helper Procedures Writeup 26: Exercise 6  HW 6: Conditionally Computed Images due; Exam 2 assigned 
27  Wednesday, 5 March 2014  Other Forms of List Recursion Questions and answers. Some notes on yesterday's lab. Some key ideas from the reading.  List Recursion, Revisited  List Recursion, Revisited Writeup 27: Exercise 5  
28  Friday, 7 March 2014  Numeric Recursion Recursion, generalized. Numeric recursion.  Numeric Recursion  Numeric Recursion Writeup 28: Exercise 4  Quiz 7 
Week 08: Other Image Models  
Date  Topic  Reading  Lab  Work Due  
29  Monday, 10 March 2014  Pause for Breath  
30  Tuesday, 11 March 2014 
Preconditions, Revisited
Verifying preconditions.
The error procedure.
Husk and Kernel programming.

Verifying Preconditions  Verifying Preconditions Writeup 30: Exercises 3h and 4  Exam 2 (due 10:30 p.m. via email) 
31  Wednesday, 12 March 2014 
Naming Local Procedures
Why have local procedures.
Creating local procedures with letrec .
Creating local procedures with named let.

Local Procedure Bindings  Local Procedure Bindings Writeup 31: Exercise 4  Exam 2 (due in class in paper form) 
32  Friday, 14 March 2014  Characters and Strings Representing text. Characters: The basic building blocks. Combining characters into strings.  Characters and Strings  Characters and Strings Writeup 32: Exercise 10  
Spring Break  
Week 09: Data Structures  
Date  Topic  Reading  Lab  Work Due  
33  Monday, 31 March 2014  Turtle Graphics Modeling images through process: Turtle graphics. Some historical notes. Turtle graphics in MediaScheme.  Turtle Graphics  Turtle Graphics Writeup 33: Extra 2  
34  Tuesday, 1 April 2014 
Iteration
Reflecting on procedures and sideeffects.
A useful tool for repetition: foreach .
Contrasting map , foreach , repeat , and recursion.

Iteration  Iteration Writeup 34: Exercises 4c and 4d  
35  Wednesday, 2 April 2014  Geometric Art Through Numeric Recursion Parallel lines, Concentric Circles, and Beyond.  Geometric Art  Geometric Art Writeup 35: Exercise 3d  HW 7: An introduction to GitHub 
36  Friday, 4 April 2014  Pairs and Pair Structures Representing lists: Pairs and cons cells. Why care about the underlying representation?  Pairs and Pair Structures  Pairs and Pair Structures  Quiz 8 
Week 10: Thinking About Image Making  
Date  Topic  Reading  Lab  Work Due  
37  Monday, 7 April 2014 
Trees
Thinking about trees in terms of cons .
Thinking about trees recursively.
Writing recursive tree procedures.

Trees  Trees Writeup 37: Exercises 4 and 6  
38  Tuesday, 8 April 2014  On TwoDimensional Design Background: About the project. General elements of design. Relationships between elements. Broader design principles. Some examples.  Elements and Principles of TwoDimensional Design & About the Project  HW 8: Turtles; Project assigned  
39  Wednesday, 9 April 2014  Project Kickoff Time to form groups. Playing and brainstorming.  Project Ideas  Playing with Project Ideas  
40  Friday, 11 April 2014  Vectors Problems with lists. A solution: Vectors. Behind the scenes: How Scheme implements vectors. Important vector procedures.  Vectors  Vectors Writeup 40: Exercise 6  Quiz 9 
Week 11: Thinking About Procedures  
Date  Topic  Reading  Lab  Work Due  
41  Monday, 14 April 2014  Analyzing Procedures Comparing algorithms. Two related metrics: Time and Number of steps. Counting procedure calls by printing. Tools for analysis.  Analyzing Procedures  Analyzing Procedures Writeup 41: Exercise 5d  
42  Tuesday, 15 April 2014  HigherOrder Procedures, Revisited Some program design principles. Thinking about repetition. Procedures as firstclass values.  Design Patterns and HigherOrder Procedures  Design Patterns and HigherOrder Procedures Writeup 42: Exercises 3 and 4  Project proposal due at 10:30 p.m. 
43  Wednesday, 16 April 2014 
Randomized (Unpredictable) Drawing
Random art.
Why use randomness.
The random procedure.
Simulation.

Randomized Drawing  Randomized Drawing Writeup 43: Exercises 3b and 6c  Project proposal images due 
44  Friday, 18 April 2014  Pause for Breath Questions. Project work time.  Quiz 10  
Week 12: Searching and Sorting  
Date  Topic  Reading  Lab  Work Due  
45  Monday, 21 April 2014  Association Lists Storing information in tables. Representing table entries as lists. Representing tables as lists. Association lists: Scheme's standard table representation. Implementing key association list procedures.  Association Lists  Association Lists Writeup 45: Exercises 4, 5d, and 6c  
46  Tuesday, 22 April 2014  Binary Search The problem of searching. Analyzing algorithmic efficiency. Making searching more efficient using divideandconquer. A demo: Destructive binary search. Considering the parameters to binary search.  Search Algorithms  Binary Search Writeup 46: Exercise 5  Project due 
47  Wednesday, 23 April 2014  Introduction to Sorting The problem of sorting. Writing sorting algorithms. Examples: Insertion, selection, etc. Formalizing the problem.  
48  Friday, 25 April 2014  Insertion Sort Insertion sort basics. Four questions about insertion sort. Analyzing insertion sort.  Sorting  Insertion Sort Writeup 48: Exercises 6e and 8f  Quiz 11 
Week 13: Miscellaneous  
Date  Topic  Reading  Lab  Work Due  
49  Monday, 28 April 2014  Merge Sort More efficient sorting techniques. Divide and conquer, revisited. Merge sort. Analyzing merge sort.  Merge Sort  Merge Sort Writeup 49: Exercises 6fgh  
50  Tuesday, 29 April 2014  Project Assessment: Images Reviewing images: The "big picture". Reviewing images: Policies for doing individual images. Image review. Debrief, if appropriate.  Exam 3 (due 10:30 p.m. via email)  
51  Wednesday, 30 April 2014  Project Assessment: Algorithms Additional images. Debriefing from image analysis. Students discuss programming techniques. Programming challenges.  Exam 3 (due in class in paper form)  
52  Friday, 2 May 2014  Objects in Scheme Motivating problems: Circles, turtles, and counters. Building and using compound values. Objects: A new approach to compound values. Creating objects in Scheme.  Building Objects in Scheme  Building Objects in Scheme  Quiz 12 
Week 14: Wrapup  
Date  Topic  Reading  Lab  Work Due  
53  Monday, 5 May 2014  Objects in Scheme, Continued Lab, continued. Reflection.  Building Objects in Scheme  Building Objects in Scheme  
54  Tuesday, 6 May 2014  File Basics File basics: Data persistence and beyond. Ports. Basic file operations.  Files  Files  HW 9: TBD; 
55  Wednesday, 7 May 2014  Wrapup The subject matter of the course. Course evaluation.  
56  Friday, 9 May 2014  Discussion of Exam 3 and Review for Final Some questions about the course. About the final. Short discussion of exam 3. Final thoughts. 
Primary: [Front Door] [Schedule]  [Academic Honesty] [Disabilities] [Email]  [FAQ] [Teaching & Learning] [Grading] [Rubric]  [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Setup]  [Functions AZ] [Functions By Topic]  [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2010S)] [Rebelsky (2013F)] [Weinman (2012F)] [Weinman (2014S)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)]
Samuel A. Rebelsky, rebelsky@grinnell.edu
Copyright (c) 20072014 Janet Davis, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials are copyright by John David Stone or Henry Walker and are used with permission.)
This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this
license, visit http://creativecommons.org/licenses/bync/3.0/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.