Schedule

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.

Week 0
W
Jan 22

Introduction to Algorithms

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

Reading
  • No reading
Lab
  • No lab
Assigned
Th
Jan 23

Work Due

Due
F
Jan 24

Getting Started with Linux and Scheme

We begin to consider the content and structure of the course. We also prepare ourselves to use our laboratory environment (that is, the Linux workstations and the DrRacket Programming Environment).

Week 1
M
Jan 27

Basic Types

We explore some of the basic types in Scheme and the operations available for those types.


W
Jan 29

Introducing Lists

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


F
Jan 31

Writing Your Own Procedures

We consider new ways to write your own procedures and why you might do so.

Week 2
M
Feb 3

Pair Programming

We explore the whys and hows of working with others. We also catch up on any confusing issues from the first few days of class.

Reading
Lab
  • No lab
Due
  • Quiz 1

W
Feb 5

Documenting Programs and Procedures

We consider documentation for your programs: Why to write documention, when to write documentation, how to write documentation. We also explore the 6P style of documentation that we use in this course.

Lab
  • No lab
Th
Feb 6

Work Due

Due
F
Feb 7

Testing Your Procedures

We consider testing When, why, and how you might test the procedures and programs that you write.

Week 3
M
Feb 10

Tables and Compound Data

We consider how to deal with compound data, such as the title, latitude, longitude, time, and date of an event.


W
Feb 12

Reading Lists and Tables from Files

We consider a variety of techniques for gathering lists and tables of data from files.

Th
Feb 13

Work Due

Due
F
Feb 14

Boolean Values, Predicate Procedures, and List Filters

We consider a new type and its use in selecting elements from lists.

Week 4
M
Feb 17

Local Bindings

We consider how and why to name values within procedures.


W
Feb 19

Conditionals

We consider one of the central components of algorithms.

Th
Feb 20

Work Due

Due
F
Feb 21

Displaying Data

We explore techniques for displaying simple kinds of data, such as coordinate pairs or counts of categorical data.

Reading
Assigned
  • Assignment 4
Week 5
M
Feb 24

Discussion of Exam 1

We consider your work on exam 1.

Reading
  • No reading
Lab
  • No lab
Due
  • Quiz 4

W
Feb 26

Preconditions, revisited

We revisit preconditions. We then consider programming techniques for ensuring that preconditions are met.

Th
Feb 27

Work Due

Due
  • Assignment 4 (by 10:30pm)
F
Feb 28

Recursion Basics

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.

Week 6
M
Mar 2

Recursion Basics, continued

We continue our exploration of recursion basics.

Due
  • Quiz 5

W
Mar 4

Recursion with Helper Procedures

We consider a different form of recursion, one based on the construction of recursive helper procedures that take additional parameters. Along the way, we consider the idea of tail recursion. We also explore how careless design of recursive procedures can inadvertently lead to slow execution.

Th
Mar 5

Work Due

Due
F
Mar 6

Other Forms of List Recursion

We conclude our initial forays into list recursion by looking for some common patterns in the design of recursive procedures.

Week 7
M
Mar 9

Numeric Recursion

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.

Due
  • Quiz 6

W
Mar 11

Naming Local Procedures

We explore how and why one writes local recursive procedures.

Th
Mar 12

Work Due

Due
F
Mar 13

Debugging

We explore techniques for understanding and correcting flaws in our programs.

Spring Break
Week 8
M
Mar 30

Randomness and Simulation

We consider Scheme’s random procedure and how one might use that procedure in writing simple simulations.


W
Apr 1

Pairs and Pair Structures

We consider pairs, the basic data type used to build lists and other structures in Scheme. We also consider why it is useful to understand about pairs.


F
Apr 3

Vectors

We consider vectors, an alternative to lists for storing collections of data.

Reading
Lab
  • Vectors
Assigned
  • Assignment 6
Week 9
M
Apr 6

Files in Scheme

We revisit files, considering the lower-level operations for working with files, a technique for structuring information that permits the information to persist across invocations of Scheme. Files also let our Scheme programs share information with other programs.

Reading
Lab
  • Files

W
Apr 8

Higher-Order Procedures, revisited

We revisit the topic of higher-order procedures, one of the most important techniques in languages like Scheme. Higher-order procedures are procedures – like map, left-section, or compose – that take other procedures as parameters, return other procedures as values, or both.

Lab
  • Higher-order procedures
Th
Apr 9

Work Due

Due
  • Assignment 6 (by 10:30pm)
F
Apr 10

Trees

We consider trees, structures built from pairs. Trees are somewhat like two-dimensional lists.

Reading
Lab
  • Binary trees
Assigned
  • Exam 3
Week 10
M
Apr 13

Analyzing Procedures

We explore techniques for analyzing the number of calls made in evaluating procedures, particularly recursive procedures. We consider why such analysis is useful.

Lab
  • Analyzing procedures

W
Apr 15

Association Lists

We consider association lists, a simple, but useful, technique for organizing tables of information.

Lab
  • Association lists and searching
Th
Apr 16

Work Due

Due
  • Exam 3 (by 10:30pm)
F
Apr 17

Project Introduction

We introduce the project.

Reading
  • Class Project
Lab
  • No lab
Assigned
  • Assignment 7
Week 11
M
Apr 20

Project Work Day 1

We provide time for groups to work on their projects.

Reading
  • No reading
Lab
  • No lab

W
Apr 22

Binary Search

We consider the general problem of searching. We explore binary search, one of the most efficient algorithms for searching.

Lab
  • Binary search
Th
Apr 23

Work Due

Due
  • Assignment 7 (by 10:30pm)
F
Apr 24

Introduction to 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.

Reading
  • No reading
Lab
  • No lab
Due
  • Project Proposal (by 10:30pm)
Week 12
M
Apr 27

Project Work Day 2

We provide additional time for groups to work on their projects.

Reading
  • No reading
Lab
  • No lab

W
Apr 29

Insertion Sort

We move from our general exploration of sorting to the implementation of a particular sorting algorithm, insertion sort. We also explore how the running time for that algorithm varies based on the number of values we are sorting.

Lab
  • Insertion sort

F
May 1

Project Work Day 3

We will have some additional time to work on projects before the project deadline.

Reading
  • No reading
Lab
  • No lab
Assigned
  • Exam 4
Week 13
M
May 4

Merge Sort

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 how the running time for that algorithm varies based on the number of values we are sorting.

Reading
Lab
  • Merge sort
Tu
May 5

Work Due

Due
  • Class Project (by 10:30pm)
W
May 6

Project Presentations

We explore your projects.

Reading
  • No reading
Lab
  • No lab
Th
May 7

Work Due

Due
  • Exam 4 (by 10:30pm)
F
May 8

Wrap Up

We conclude the course by considering the topics we’ve covered, and discuss the concepts you will see in future CS courses.

Reading
  • No reading
Lab
  • No lab