Schedule

An introduction to algorithms

We begin the class by exploring the definition of computer science and by trying to write some basic algorithms.

Getting started with Racket

We consider Racket, the programming language we will use throughout the course.

Algorithmic and image decomposition

We consider a key technique in algorithmic thinking, how one “decomposes” a more complex problem or algorithm into simpler ones.

Reading and writing procedures

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.

Expressions and types

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.

Booleans, predicates, and conditionals

We consider how one writes procedures that make decisions.

Pair programming

We explore the whys and hows of working with others.

Lists

We return to Scheme’s list data structure and some ways to use lists to work with collections of data.

Lists, revisited

We continue our exploration of lists in Racket, including “the big three” list procedures: map, reduce, and filter.

Files and regular expressions

We begin to explore regular expressions, tools used to identify patterns in strings. We also consider files, structures that store data, often for use by other programs.

Files and regular expressions, continued

We continue our exploration of regular expressions and files.

Introduction to list recursion

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.

Introduction to list recursion, continued

We continue our introductory exploration of recursion in Racket.

Unofficial Working Differently Day

A day (or at least a class period) for you to not worry about CS.

Recursion practice

We continue to continue our introductory exploration of recursion in Racket.

Local bindings

We consider why and how to name values within procedures.

Documenting and testing your code

We consider documentation for your programs: Why to write documention, when to write documentation, how to write documentation.
We also consider testing: When, why, and how you might test the procedures and programs that you write.

Recursion over numbers

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.

Randomness

We consider Scheme’s random procedure and how one might use that procedure in generating language.

Pause for Breath

We pause to discuss a variety of issues.

Pairs

We explore pairs, the basic building blocks of lists, and consider other, non-list structures one might build from pairs.

Vectors

We explore vectors, an alternative to lists for storing data. We consider how data are stored in memory.

Vectors, continued

We continue to explore vectors.

Dictionaries and hash tables

We consider structures that allow us to store information for quick retrieval.

Data abstraction

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.

Structured data

We consider Racket’s techniques for creating structured data types.

Topics: Structured data. Using structs. Mutable and immutable structs.

Getting started with HTML and CSS

We begin to consider the content and structure of the course, exploring both our laboratory environment (Linux workstations) and mechansisms for representing and styling text.

Topics: Getting started with Linux. Generalized markup with XML. Web markup with HTML. Page styling with CSS.

Processing XML

We consider how one writes programs that process HTML and XML.

Topics: XML, revisited. Representing XML in Racket. Expressing patterns in XML. Seaching XML. Constructing new documents from old.

Transforming XML

We consider additional ways to extract data from XML documents or to transform XML documents into new XML documents.

Topics: Replacing elements. Inserting elements. Deleting elements.

Higher-order recursive design

We explore patterns of recursion in the design of programs, particularly with regards to higher-order procedures.

Recursion, reviewed

We get our brains back working on recursion

Project prep

We prepare to undertake an individually designed project.

Trees

We consider a common hierarchial mechanism for structuring data and its relationship to Scheme/Racket and XML/HTML.

Tree recursion

We consider how to write recursive programs that process trees and other tree-like structures.

Complexity analysis and binary search

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.

Project Work Day

We pause to give you an opportunity to work on your projects.

Sorting

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.

Case study: Mergesort

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.

Project presentations

Students present their projects

Wrapup

We conclude the course.