# CS195 2003S Course Syllabus

This is a highly approximate syllabus. Expect topics, assignments, ordering, and almost everything else to change.

## Week One: Preliminaries

Class 01 (Monday, 20 January 2003) Introduction

Assignments:

Overview:

• Definitions: Computer science, computer programming, computing, algorithm, and more.
• Course basics.
• Getting started with the ECA.

Class 02 (Tuesday, 21 January 2003) Binary Search

Due

• Gries 0-1

Overview:

• Binary Search
• Assertions
• Logic and More

Class 03 (Wednesday, 22 January 2003) Program Verification

Assignments:

Due

Class 04 (Friday, 24 January 2003) The Structure of a Computer

Assignments:

• Read K&R 1 (due Mon).
• Read Gries 2 (due Tue).

Overview:

• What is a computer?
• Key operations
• Some simple programs

## Week Two: C Fundamentals

Class 05 (Monday, 27 January 2003) An Introduction to C

Assignments:

• Read Gries 2 (due Tue).

Overview:

• Three sample programs.
• A notation for instructions.
• Three sample programs, revisited.
• An introduction to C.
• C vs. Java.

Class 06 (Tuesday, 28 January 2003) Working with Boolean Expressions

Due

Assignments:

Overview:

• Review: The need for proof.
• Key aids to proof: Laws and Rules.
• Twelve Basic Laws.
• The Rule of Substitution.
• The Rule of Transitivity.

Class 07 (Wednesday, 29 January 2003) An Introduction to C, Continued

Related Pages:

Overview:

Class 08 (Friday, 31 January 2003) An Introduction to C, Concluded

Due

Assignments:

Overview:

## Week Three: Types

Class 09 (Monday, 3 February 2003) Representing Integers

Assignments:

Related Pages:

Overview:

• Binary representation.
• Unsigned binary integers.
• Computing with unsigned binary integers.
• Signed binary integers.
• Computing with signed binary integers.

Class 10 (Tuesday, 4 February 2003) Predicates

Due

• Gries 4

Assignments:

Related Pages:

Overview:

• Expanding our worldview: Numbers and Predicates.
• Evalutaing Predicates.
• Three-Valued Boolean Logic and Short-Circuit Conditionals.
• Quantification.
• Bound and Unbound Variables.
• Substittuion.

Class 11 (Wednesday, 5 February 2003) Predicates

Related Pages:

Overview:

• Expanding our worldview: Numbers and Predicates.
• Evalutaing Predicates.
• Three-Valued Boolean Logic and Short-Circuit Conditionals.
• Quantification.
• Bound and Unbound Variables.
• Substittuion.

Class 12 (Friday, 7 February 2003) Representing Real Numbers

Due

Assignments:

• .

Related Pages:

Overview:

• Real numbers.
• Method one: Rationals.
• Method two: Fixed precision.
• Method three: Floating point.
• Basics of the IEEE Standard.
• Some Special Cases.
• Learning from Java.

## Week Four: Types in C

Class 13 (Monday, 10 February 2003) Fundamental Types in C

Related Pages:

Overview:

• Integer types.
• Real types.
• Arithmetic operations.
• Enumerated types.
• Lab.

Class 14 (Tuesday, 11 February 2003) Bitwise Operations

Assignments:

• Read K&R 6.1, 6.7, 6.8, and 6.9.

Related Pages:

Overview:

• C's Bitwise Operations.
• Using C's Bitwise Operations.
• Lab.

Class 15 (Wednesday, 12 February 2003) Compound and User-Defined Types in C

Assignments:

• Read appendix B.3 of K& R.
• Scan the manual pages for those string procedures.

Related Pages:

Overview:

• Structures.
• Unions.
• Naming Types.
• Lab.

Class 16 (Friday, 14 February 2003) Strings

Assignments:

Related Pages:

Overview:

• Representing strings in C.
• Important string procedures.
• Lab.

## Week Five: Arrays and Pointers

Class 17 (Monday, 17 February 2003) Array Basics

Assignments:

Related Pages:

Overview:

• Representing arrays.
• Representing multi-dimensional arrays.
• Key array operations.
• Lab.

Class 18 (Tuesday, 18 February 2003) Array Assertions

Due

• Gries 5.

Related Pages:

Overview:

• What is an array? Additional perspectives.
• More notation.
• Multidimensional arrays.
• Array diagrams.
• Partitioning.

Class 19 (Wednesday, 19 February 2003) Pointer Basics

Related Pages:

Overview:

• Pointers.
• Pointers in C.
• Basic Operations.
• Memory allocation.

Class 20 (Friday, 21 February 2003) Pointer Lab

Assignments:

Related Pages:

Overview:

## Week Six: Functions

Class 21 (Monday, 24 February 2003) Function Basics

Assignments:

Related Pages:

Overview:

• Functions in C.
• C functions vs. Java funtions.
• Lab.

Class 22 (Tuesday, 25 February 2003) Program Documentation

Due

• Gries 6.

Related Pages:

Overview:

• Using Assertions.
• Notation.

Class 23 (Wednesday, 26 February 2003) Asymptotic Analysis

Assignments:

Class 24 (Friday, 28 February 2003) Pointers and Functions

Related Pages:

Overview:

• Detour: `#include` and `#define` preprocessor directives.
• Returning Pointers from Functions.
• Pointers to Functions.
• Lab.

## Week Seven: Input and Output

Class 25 (Monday, 3 March 2003) I/O Basics

Class 26 (Tuesday, 4 March 2003) Weakest Preconditions

Due

• Gries 7-8.

Assignments:

Related Pages:

Overview:

• Preconditions, defined.
• Weakness and strength.
• Using weakest preconditions.

Class 27 (Wednesday, 5 March 2003) Files

Assignments:

• Exam 1 (due Friday, 14 March 2003).

Related Pages:

Overview:

• The FILE type.
• Opening files.
• Writing to files.
• Lab.

Class 28 (Friday, 7 March 2003) Files, Contined

Due

Related Pages:

Overview:

• What's wrong with `readLine`?
• What's wrong with the display procedure?
• Lab.

## Week Eight: Miscellaneous

Class 29 (Monday, 10 March 2003) Designing a List Type

Assignments:

Related Pages:

Overview:

• What is a list?
• Scheme lists.
• Java lists.

Class 30 (Tuesday, 11 March 2003) Semantics of Assignment (1)

Due

• Gries 9.

Related Pages:

Overview:

• Review: Weakest Preconditions.
• Review: Substitution.
• Defining simple assignment.
• Some variations.
• Defining multiple assignment.

Class 31 (Wednesday, 12 March 2003) Semantics of Assignment (2)

Class 32 (Friday, 14 March 2003) Early Break

Due

## Break

Break runs from 5:00 p.m. on Friday, March 17, 1998 to 8:00 a.m. on Monday, April 3.

## Week Nine: Review

Class 33 (Monday, 31 March 2003) Reading Lines (1)

Related Pages:

Class 34 (Tuesday, 1 April 2003) Reading Lines (2)

Related Pages:

Overview:

• Testing `readLine`, continued.
• Implementing `readLine`.
• An efficient exponentiation algorithm.
• `strncpy`.

Class 35 (Wednesday, 2 April 2003) Semantics of Conditionals

Due

• Gries 10.

Related Pages:

Overview:

• A New Form of Conditional.
• Formal Definition.
• Example: Max.
• Example: Largest.
• An Interesting Theorem.

Class 36 (Friday, 4 April 2003) Reading Gries

Related Pages:

Overview:

• Background: Why discuss this issue?
• Background: How do you approach Gries?
• A basic technique for reading texts.
• Exercise: Spend ten minutes mapping the chapter.
• Discussion.
• Other techniques for reading texts.

Class 37 (Monday, 7 April 2003) Linked Lists (1)

Assignments:

• Think about what procedures you might include in the more imperative list that is simply a collection of values that you can step through one-by-one. I will ask you for your answer tomorrow.

Related Pages:

Overview:

• Review: What is a list?
• Implementing nodes as records.

Class 38 (Tuesday, 8 April 2003) A List Wrapper (1)

Due

• Gries 11.

Related Pages:

Overview:

• From Scheme List to Iterated Collection.
• A Key Idea: Cursors.
• Important List Procedures.

Class 39 (Wednesday, 9 April 2003) A List Wrapper (2)

Assignments:

Related Pages:

Class 40 (Friday, 11 April 2003) Semantics of Iteration

## Week Eleven: Other Linked Structures

Class 41 (Monday, 14 April 2003) Extending Linked Lists: Doubly- and Circularly-Linked Lists

Assignments:

Related Pages:

Overview:

• Implementing `delete`.
• Detour: ADTs vs. Data Structures.

Class 42 (Tuesday, 15 April 2003) Cancelled

Class 43 (Wednesday, 16 April 2003) Queues

Related Pages:

Class 44 (Friday, 18 April 2003) Semantics of Procedure Calls

Related Pages:

Overview:

• What is a procedure definition?
• Gries-style procedure definitions.
• Informal semantics of procedure calls.
• Formal semantics of procedure calls.

## Week Twelve: Program Development (1)

Class 45 (Monday, 21 April 2003) Sorting Out Sorting

Class 46 (Tuesday, 22 April 2003) Program Mangagement

Due

Related Pages:

Overview:

• Overview.
• Using Multiple Source Files.
• Make and Makefiles.
• CVS.

Class 47 (Wednesday, 23 April 2003) The C Preprocessor

Related Pages:

Overview:

• Overview of the C Preprocessor.
• Using #define.
• Some silly tricks.

Class 48 (Friday, 25 April 2003) Debugging

Assignments:

• Exam 3: Formal Methods

Related Pages:

Overview:

• Introduction to debugging.
• Offline deubgging.
• Using print statments.
• Using assertions.
• Debuggers

## Week Thirteen: Program Development (2)

Class 49 (Monday, 28 April 2003) Program Development, the Gries Perspective

Due

• Gries 13-14.

Related Pages:

Overview:

• Plan of the Week.
• How and Why Gries Wants You to Work.
• An Example: Cap.
• Some Rubrics.
• An Example: Binary Something.

Class 50 (Tuesday, 29 April 2003) From Invariants to Loops

Assignments:

Due

• Gries 15.

Related Pages:

Overview:

• Form of a loop.
• Overview of Goals.
• Checklist for understanding loops.
• Example: Minimum.
• Some Principles.

Class 51 (Wednesday, 30 April 2003) Developing Invariants

Due

• Gries 16.

Related Pages:

Overview:

• Smallest example, continued.
• Some general principles.
• Detour: The infinite loop on failure principle.
• Invariants as simplified postconditions.

Class 52 (Friday, 2 May 2003) Processes (1)

Due

• Exam 3: Formal Methods

Related Pages:

Overview:

• Processes in Unix.
• Pipes.
• Lab.

## Week Fourteen: Miscellaneous

Attendance is particularly important this week.

Class 53 (Monday, 5 May 2003) Processes (2)

Assignments:

Related Pages:

Overview:

• Q&A on Previous Class.
• Exercise: Forking Multiple Children.

Class 54 (Tuesday, 6 May 2003) Processes (3)

Related Pages:

Overview:

• Standard Input and Output.
• Detour: Command Line.
• Executing Other Prorams.
• Exercise.

Class 55 (Wednesday, 7 May 2003) Evaluation

Class 56 (Friday, 9 May 2003) Wrapup

## History

The history will not include small changes to the summaries of individual classes or perhaps even on the arrangement of courses. You can find more information on such changes in the individual outlines.

Friday, 12 January 2001 [Samuel A. rebelsky]

• First generic version, based on syllabi of years past.

Tuesday, 7 January 2003 [Samuel A> Rebelsky]

• Slight changes to generic format.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Fri May 9 12:56:18 2003.
The source to the document was last modified on Tue Jan 7 13:49:58 2003.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS195/2003S/Handouts/syllabus.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu