Functional Problem Solving (CSC 151 2014F) : Handouts
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [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.)
Week 01: An Introduction to ... | |||||
---|---|---|---|---|---|
Date | Topic | Reading | Lab | Work Due | |
01 | Friday, 29 August 2014 | An Introduction to Algorithms Introduction: What is CS? Exercise: An everyday algorithm. Debriefing on exercise. | |||
02 | Monday, 1 September 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 (due 10:30 p.m. Sunday night) |
03 | Tuesday, 2 September 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 | Wednesday, 3 September 2014 | Computing with Symbols and Numbers Values and types. Kinds of numbers. The modulo operation. | Numeric Values & Symbolic Values | Numeric Computation Writeup 04: Exercise 2, parts d, e, and f | |
05 | Friday, 5 September 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, and e | Quiz 1 |
Week 02: Two Models of Images | |||||
Date | Topic | Reading | Lab | Work Due | |
06 | Monday, 8 September 2014 | Writing Your Own Procedures Sequencing operations in Scheme. The drawings-as-values model, revisited. Why define your own procedures? How to define your own procedures. Evaluating expressions in Scheme. | Writing Your Own Procedures and How Scheme Evaluates Expressions (Take 2) | Drawings as Values and Writing Your Own Procedures No writeup for today | |
07 | Tuesday, 9 September 2014 | Writing Your Own Procedures, Continued Lab, continued. Questions. | Writing Your Own Procedures, How Scheme Evaluates Expressions (Take 2), and Wray: How Pair Programming Really Works | Writing Your Own Procedures Writeup 07: Exercises 5 and 6 | HW 2: Starting Scheme by Scoring Swimmers |
08 | Wednesday, 10 September 2014 | Documenting Programs and Procedures Debrief on procedures lab. 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 from the procedures lab |
|
09 | Friday, 12 September 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 09: Exercise 3a | Quiz 2 |
Week 03: Design and Color | |||||
Date | Topic | Reading | Lab | Work Due | |
10 | Monday, 15 September 2014 | Testing Your Procedures Why test? Strategies for testing. The primary testing operations. | Testing Your Procedures | Testing Your Procedures No writeup | |
11 | Tuesday, 16 September 2014 | A Design Perspective A bit about design. A bit about color theory. Exploring some images and design spaces. | Design and Color | No writeup | HW 3: Drawing Generally and Concisely |
12 | Wednesday, 17 September 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 | |
13 | Friday, 19 September 2014 | Testing Your Procedures, Revisited Using testing to assess candidate solutions. A problem in testing. Some strategies for improving your tests. | Testing Your Procedures | Testing Your Procedures | Quiz 3 |
Week 04: Transformations | |||||
Date | Topic | Reading | Lab | Work Due | |
14 | Monday, 22 September 2014 | Transforming Colors Review: Color basics. Integer-encoded RGB colors. Computing new colors from old. An example. | Transforming RGB Colors | Transforming RGB Colors Writeup 14: Exercises 5e and 7b | |
15 | Tuesday, 23 September 2014 | Transforming Images Transforming images by transforming each pixel. Sequencing transformations with compose. Anonymous transformations. | Transforming Images | Transforming Images Writeup 15: Exercises 4a, 5b, and 5e | Exam 1 (due 10:30 p.m. via email) |
16 | Wednesday, 24 September 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 16: Exercise 5 | Exam 1 (due in class in paper form) |
17 | Friday, 26 September 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 | Quiz 4 |
Week 05: Control | |||||
Date | Topic | Reading | Lab | Work Due | |
18 | Monday, 29 September 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 | |
19 | Tuesday, 30 September 2014 |
Conditionals
The parts of an algorithm, revisited.
Choosing between two options with if .
Optional evaluation with when .
Making multiple choices with cond .
Comparing approaches.
|
Conditionals | Conditionals Writeup 19: Exercises 3c and 4d | HW 4: Transforming Colors, Drawings, and Images |
20 | Wednesday, 1 October 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 No Writeup | |
21 | Friday, 3 October 2014 |
Naming Local Values
Why name things.
Naming things with let .
Naming things with let* .
Naming procedures.
|
Local Bindings | Local Bindings Writeup 21: Exercises 5d and 6b | Quiz 5 |
Week 06: Recursion | |||||
Date | Topic | Reading | Lab | Work Due | |
22 | Monday, 6 October 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 No writeup required. | |
23 | Tuesday, 7 October 2014 | Revisiting Lists Lists, revisited. New list operations. Drawings as values. | Building Data Structures with Heterogeneous Lists | Exploring Lists Writeup 23: Exercise 4 | HW 5: Conditionals and Colors; Exam 2 assigned |
24 | Wednesday, 8 October 2014 | Recursion Basics Some challenges. The idea of recursion. Some sample recursive procedures. Expressing recursion in Scheme. | Recursion Basics | Recursion Basics No Writeup | |
25 | Friday, 10 October 2014 | Recursion Basics, Continued Reflection. Questions. Recursion vs. other forms of repetition. | Recursion Basics | Recursion Basics Writeup 25: Exercises 4 and 5 | Quiz 6 |
Week 07: Recursion, Continued | |||||
Date | Topic | Reading | Lab | Work Due | |
26 | Monday, 13 October 2014 | Recursion with Helper Procedures Basics of helper recursion. A term: Tail recursion. | Recursion with Helper Procedures | Recursion with Helper Procedures Writeup 26: Exercise 4l and 5b | |
27 | Tuesday, 14 October 2014 | Recursion with Helper Procedures, Continued Further issues in helper recursion. Tail recursion. | Recursion with Helper Procedures | Recursion with Helper Procedures Writeup 27: Exercise 4l and 5b | Exam 2 (due 10:30 p.m. via email) |
28 | Wednesday, 15 October 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 28: Exercise 3 | Exam 2 (due in class in paper form) |
29 | Friday, 17 October 2014 | Numeric Recursion Recursion, generalized. Numeric recursion. | Numeric Recursion | Numeric Recursion No Writeup | Quiz 7 |
Fall Break | |||||
Week 08: Other Image Models | |||||
Date | Topic | Reading | Lab | Work Due | |
30 | Monday, 27 October 2014 |
Preconditions, Revisited
Verifying preconditions.
The error procedure.
Husk and Kernel programming.
|
Verifying Preconditions | Verifying Preconditions Writeup 30: Exercises 3h and 4 | |
31 | Tuesday, 28 October 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 | |
32 | Wednesday, 29 October 2014 | Characters and Strings Representing text. Characters: The basic building blocks. Combining characters into strings. | Characters and Strings | Characters and Strings Writeup 32: Exercises 5 and 6 | |
33 | Friday, 31 October 2014 | Turtle Graphics Modeling images through process: Turtle graphics. Some historical notes. Turtle graphics in MediaScheme. | Turtle Graphics | Turtle Graphics Writeup 33: Extra 1 | Quiz 8 |
Week 09: Data Structures | |||||
Date | Topic | Reading | Lab | Work Due | |
34 | Monday, 3 November 2014 |
Iteration
Reflecting on procedures and side-effects.
A useful tool for repetition: for-each .
Contrasting map , for-each , repeat , and recursion.
|
Iteration | Iteration No Writeup | |
35 | Tuesday, 4 November 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 No Writeup | HW 6: Exercises in Recursion; Exam 3 distributed |
36 | Wednesday, 5 November 2014 |
Trees
Thinking about trees in terms of cons .
Thinking about trees recursively.
Writing recursive tree procedures.
|
Trees | Trees Writeup 36: Exercises 2 and 4a | |
37 | Friday, 7 November 2014 | Geometric Art Through Numeric Recursion Using numeric recursion for making images. Parallel lines, concentric circles, and beyond. | Geometric Art | Geometric Art Writeup 37: Exercise 5 | Quiz 9 |
Week 10: Thinking About Image Making | |||||
Date | Topic | Reading | Lab | Work Due | |
38 | Monday, 10 November 2014 | On Two-Dimensional Design Background: About the project. Two sample projects. General elements of design. Relationships between elements. Broader design principles. Some examples. | Elements and Principles of Two-Dimensional Design & About the Project | ||
39 | Tuesday, 11 November 2014 | Project Kickoff Time to form groups. A few more notes on design. Playing and brainstorming. | Project Ideas | Playing with Project Ideas | Exam 3 (due 10:30 p.m. via email); Project assigned |
40 | Wednesday, 12 November 2014 | Vectors Problems with lists. A solution: Vectors. Behind the scenes: How Scheme implements vectors. Important vector procedures. | Vectors | Vectors Writeup 40: Exercise 5 | Exam 3 (due in class in paper form) |
41 | Friday, 14 November 2014 |
Randomized (Unpredictable) Drawing
Random art.
Why use randomness.
The random procedure.
Simulation.
|
Randomized Drawing | Randomized Drawing Writeup 41: Exercise 4c | Quiz 10 |
Week 11: Thinking About Procedures | |||||
Date | Topic | Reading | Lab | Work Due | |
42 | Monday, 17 November 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 | Tuesday, 18 November 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 No Writeup | Project proposal images due |
44 | Wednesday, 19 November 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 44: Exercises 1 and 4c | |
45 | Friday, 21 November 2014 | Pause for Breath Project work time. Key techniques. | Quiz 11 | ||
Week 12: Searching and Sorting | |||||
Date | Topic | Reading | Lab | Work Due | |
46 | Monday, 24 November 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 | ||
47 | Tuesday, 25 November 2014 | Binary Search Lab Exploring the search API. Remaining questions. | Search Algorithms | Binary Search Writeup 47: Exercise 4 | Project due |
48 | Wednesday, 26 November 2014 | An Introduction to Sorting The problem of sorting. Writing sorting algorithms. Examples: Insertion, selection, etc. Formalizing the problem. | Exam 4 distributed | ||
Thanksgiving Break | |||||
Week 13: Miscellaneous | |||||
Date | Topic | Reading | Lab | Work Due | |
49 | Monday, 1 December 2014 | Insertion Sort Insertion sort basics. Four questions about insertion sort. Analyzing insertion sort. | Sorting | Insertion Sort Writeup 49: Exercises 2e and 4f | |
50 | Tuesday, 2 December 2014 | Project Assessment: Images Reviewing images: The "big picture". Reviewing images: Policies for doing individual images. Image review. Debrief, if appropriate. | |||
51 | Wednesday, 3 December 2014 | Project Assessment: Algorithms Additional images. Debriefing from image analysis. Students discuss programming techniques. Programming challenges. | |||
52 | Friday, 5 December 2014 | Merge Sort More efficient sorting techniques. Divide and conquer, revisited. Merge sort. Analyzing merge sort. | Merge Sort | Merge Sort | |
Week 14: Wrapup | |||||
Date | Topic | Reading | Lab | Work Due | |
53 | Monday, 8 December 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 | Exam 4 (due 10:30 p.m. via email) |
54 | Tuesday, 9 December 2014 | Pause for Breath (aka 'The Network is Down') Debriefing on the course. Surveys galore! Quick discussion of the final. | Exam 4 (due in class in paper form) | ||
55 | Wednesday, 10 December 2014 | Objects in Scheme, Continued Objects, revisited. Building a four-way switch. Reflection. | Building Objects in Scheme | Building Objects in Scheme | |
56 | Friday, 12 December 2014 | Wrapup The subject matter(s) of the course. Course evaluation. Final comments. |