The schedule below shows the tentative dates for all class topics, readings, and assignments. You should complete all assigned reading before class on the day it is listed. Labs will be available shortly before the assigned lab day. There may be some revisions to the schedule during the semester, but I will make sure to announce these changes in class.
If you view this page with JavaScript enabled you can jump to the current week on the schedule, and you should see the next day of class highlighted in the schedule below.
We begin the class by exploring the definition of computer science and by trying to write some basic algorithms.
We consider Racket, 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 explore many of the basic types of values in Racket, the capabilities Racket 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 pause to review some concepts from our first week of programming.
We explore the whys and hows of working with others. We also catch up on any confusing issues from the first week of class as we prepare for the first set of learning assessment.
We check in to make sure that we’re beginning to master the first set of concepts.
We return to Scheme’s list data structure and some ways to use lists to work with collections of data.
We continue our exploration of lists in Racket, including “the big three” list procedures: map, reduce, and filter.
We begin to explore regular expressions, tools used to identify patterns in strings.
We consider why and how to name values within procedures.
We consider documentation for your programs: Why to write documention, when to write documentation, how to write documentation. We also explore various styles of documentation that we use in this course.
We consider testing: When, why, and how you might test the procedures and programs that you write.
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 our introductory exploration of recursion in Racket.
We continue to continue our introductory exploration of recursion in Racket.
We check in to make sure that we’re beginning to master the second set of concepts. We revisit concepts missing from the first learning assessment inventory.
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 pause to consider some important issues in recursion.
We consider a host of other issues in the design of recursive procedures.
We explore patterns of recursion in the design of programs, particularly with regards to higher-order procedures.
We consider Scheme’s random procedure and how one might use
that procedure in generating language.
We explore pairs, the basic building blocks of lists, and consider
other, non-list structures one might build from pairs.
We also explore vectors, an alternative to lists for storing data.
We consider how data are stored in memory.
We consider structures that allow us to store information for quick retrieval.
We build upon the structures we have encountered so far to design our own types and reflect on mechanisms for separating the interface to a type from the implementation of the type.
We consider a common hierarchial mechanism for structuring data and its relationship to Scheme/Racket and XML/HTML.
We check in to make sure that we’re beginning to master the third set of concepts. We revisit any missing concepts from earlier assessments.
We consider how to write recursive programs that process trees and other tree-like structures.
Our technology fails us.
We consider ideas from SoLA 3
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 check in on the last set of topics and revisit any necessary topics from earlier in the term.
We conclude the course.
A chance to ask questions, for those who want it.
We have one more opportunity to check our learning.
We explore the problem of sorting. When you sort a list, vector, or other collection, you put the elements in order. The order of the elements usually corresponds to the type of the elements. We might sort strings alphabetically, grades numerically, colors by brightness, and so on and so forth. We also reflect on one common sorting algorithm.
We continue our exploration of sorting by considering the applicability of the divide-and-conquer approach to the problem of sorting. We look at one particular divide-and-conquer algorithm, merge sort. We explore the relationship between the number of steps the algorithm typically takes and the number of values in the list we are sorting.
We consider a different way to decompose sequences of operations.
We consider languages other than Scheme, particularly languages used to describe Web pages and similar resources.
We consider ways to search for patterns in text and to use the results of those searches. We also explore how to extract data from text files.