This site is under construction. Please expect some changes.
Due dates for major assignments will not change. However, the particular topics we cover each day may change as we discover that we need more (or less) time on each topic.
We begin the class by exploring the definition of computer science and by trying to write some basic algorithms.
We consider Scheme, the programming language we will use throughout the course.
We consider a key technique in algorithmic thinking, how one “decomposes” a more complex problem or algorithm into simpler ones.
We consider ways to write your own procedures and why you might do so. We also explore how one interprets the algorithms others write. And we develop some mental models for what happens when we run Scheme/Racket programs.
We look at the fundamental building block of computation in functional programming languages, the expression, and build an appropriate model of how expressions “compute”.
NOTE: We forgot to post the second reading, “Mental models of computation,” on time. You do not need to include it in your reading response, but we recommend that you read through it carefully on your own as mental models is an essential topic for the course.
We explore many of the basic types of values in Scheme, the capabilities Scheme provides for working with those types, and how one builds more complex expressions. We also continue building our mental model.
We consider how one writes procedures that make decisions.
We consider the trifecta of software engineering: documentation, testing, and debugging. That is, we explore why and how you document your code, why and how you test your code, and how you might find errors in your code.
We expand our understanding of RGB transformations to image transformations.
We explore issues of redundacy in code and mechanisms for reducing such reducnancy.
The first core examination.
We return to Scheme’s list data structure and some ways to use lists to work with collections of data.
We explore ways to use lists to work with collections of drawings
using “the big three” list procedures: map, reduce, and filter.
We continue practicing list process with the “big three.” Additionally, we also take the time to consider good style in programming.
We begin our exploration of recursion, the most general form of repetition available in Scheme. You can use recursion to both build and iterate over different kinds of values.
We begin our exploration of recursion, the most general form of repetition available in Scheme. You can use recursion to both build and iterate over different kinds of values.
We continue to explore list recursion by examining how we use recursion to perform basic motions over lists.
We consider a slightly different kind of recursion, numeric recursion. In this technique, we once again have procedures call themselves. However, the parameter that we “simplify” at every step is a number, rather than a list.
We combine higher-order functions and recursive programming to implement the “big three” operations over lists. (Extra topic: Tail recursion – We look at an advanced version of recursion that is ubiquitous in functional programming, tail recursion.)
We combine higher-order functions and recursive programming to implement the “big three” operations over lists. (Extra topic: Tail recursion – We look at an advanced version of recursion that is ubiquitous in functional programming, tail recursion.)
We consider how we might use list recursion to build structures that allow us to store information for quick retrieval.
The second core examination.
We discuss (finally!) what a side-effect is, why they are useful, and how functional programming (correctly) encourages us to moderate their use.
We consider Scheme’s random procedure and how one might use
that procedure in generating language.
We dive deeper into how images are represented underneath the hood in anticipation for our final projects.
We kick-off the final project, finalizing topics, forming groups, and building a plan of action!
We consider how to write recursive programs that process trees and other tree-like structures.
Before Thanksgiving break, we pause to give everyone time to make substantial progress on their final projects.
We explore techniques for analyzing the number of calls made in evaluating procedures, particularly recursive procedures. We consider why such analysis is useful. We then delve into a common problem: That of finding values in a collection.
We review the material in this final leg of the course before the third exam.
The third core examination.
As a case study of looking at computational complexity, we examine different ways of performing two ubiquitous operations in programming, searching and sorting.
2-5 pm in our regular classroom