Functional Problem Solving (CSC 151 2014S) : Handouts

# Schedule

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 Program-Development 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. Integer-encoded 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 positionally-computed 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 side-effects. A useful tool for repetition: `for-each`. Contrasting `map`, `for-each`, `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 Two-Dimensional Design Background: About the project. General elements of design. Relationships between elements. Broader design principles. Some examples. Elements and Principles of Two-Dimensional 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
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 Higher-Order Procedures, Revisited Some program design principles. Thinking about repetition. Procedures as first-class values. Design Patterns and Higher-Order Procedures Design Patterns and Higher-Order 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 divide-and-conquer. 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.

Samuel A. Rebelsky, rebelsky@grinnell.edu

Copyright (c) 2007-2014 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/by-nc/3.0/` or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.