CS195 2003S Course Syllabus

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

• Week One: Preliminaries
• Week Two: C Fundamentals
• Week Three: Types
• Week Four: Types in C
• Week Five: Arrays and Pointers
• Week Six: Functions
• Week Seven: Input and Output
• Week Eight: Miscellaneous
• Break
• Week Nine: Review
• Week Ten: Linked Lists
• Week Eleven: Other Linked Structures
• Week Twelve: Program Development (1)
• Week Thirteen: Program Development (2)
• Week Fourteen: Miscellaneous

Week One: Preliminaries

Class 01 (Monday, 20 January 2003) Introduction

Assignments:

• Scan through the various administrative handouts (due Tue).
• Fill out the introductory survey (due Tue).
• Take the administrivia quiz (due Tue).
• Read Gries 0-1 (due Tue).
• Homework 0: Binary Search (due noon Tue).

Overview:

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

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:

• Homework 2: Evalauting Boolean Propositions (due Tue).

Due

• Homework 1: Binary Search, Revisited.

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

• Gries 2
• Homework 2

Assignments:

• Homework 3: Simple Boolean Proofs.

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:

• EBoard.
• Lab: An Introduction to C.

Overview:

• Lab: An Introduction to C.
• Reflection.

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

Due

• Homework 3: Simple Boolean Proofs.

Assignments:

• Representing Integers.

Overview:

• Lab: An Introduction to Arrays.
• Reflection.

Week Three: Types

Class 09 (Monday, 3 February 2003) Representing Integers

Assignments:

• Homework 4: Binary to Decimal and Back Again (due Fri).
• Read Gries, Chapter 4 (due Tue).
• Read IEEE Floating Point Representation.

Related Pages:

• EBoard.
• Representing Integers.

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:

• Read IEEE Floating Point Representation.

Related Pages:

• EBoard.

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:

• EBoard.

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

• Homework 4.

Assignments:

• Read K&R, Chapter 2
.

Related Pages:

• EBoard.
• Reading on IEEE Representation of Floating-Point Numbers.
• PrintFloatBits.java, a program for exploring the IEEE representation.

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:

• EBoard.
• Lab.

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:

• EBoard.
• Lab.

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:

• EBoard.
• Lab on Structs and Other User-Defined Types.

Overview:

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

Class 16 (Friday, 14 February 2003) Strings

Assignments:

• Read K&R, Chapter 5.
• Read Gries, Chapter 5.

Related Pages:

• EBoard.
• Lab on Strings.

Overview:

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

Week Five: Arrays and Pointers

Class 17 (Monday, 17 February 2003) Array Basics

Assignments:

• Read Gries, Chapter 5.

Related Pages:

• EBoard.
• Lab on Arrays.

Overview:

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

Class 18 (Tuesday, 18 February 2003) Array Assertions

Due

• Gries 5.

Related Pages:

• EBoard.

Overview:

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

Class 19 (Wednesday, 19 February 2003) Pointer Basics

Related Pages:

• EBoard.

Overview:

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

Class 20 (Friday, 21 February 2003) Pointer Lab

Assignments:

• Read K&R on Functions.

Related Pages:

• Eboard.
• Lab on pointers.

Overview:

• Quick review.
• Lab on Pointers.

Week Six: Functions

Class 21 (Monday, 24 February 2003) Function Basics

Assignments:

• Read Gries, Chapter 6.

Related Pages:

• EBoard.
• Lab.

Overview:

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

Class 22 (Tuesday, 25 February 2003) Program Documentation

Due

• Gries 6.

Related Pages:

• EBoard.

Overview:

• Using Assertions.
• Notation.
• Assertions about Assignments.
• Assertions about Sorting.

Class 23 (Wednesday, 26 February 2003) Asymptotic Analysis

Assignments:

• Homework 5.

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

Related Pages:

• EBoard.
• Lab.

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:

• Read K&R on files.

Related Pages:

• EBoard.

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:

• EBoard.
• Lab on files.

Overview:

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

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

Due

• Homework 5.

Related Pages:

• EBoard.
• Lab on files.

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:

• Read Gries, Chapter 9.

Related Pages:

• EBoard.

Overview:

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

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

Due

• Gries 9.

Related Pages:

• EBoard.

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

• Exam 1.

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:

• EBoard.
• Notes on exam 1.
• readLine.h.

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

Related Pages:

• EBoard.
• readLine.h.
• testrl.c.
• readLine.c.
• Notes on exam 1.

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:

• EBoard.

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:

• Reading Gries.

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.

Week Ten: Linked Lists

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:

• EBoard.

Overview:

• Review: What is a list?
• Key linked-list operations.
• Implementing nodes as records.
• Implementing key linked-list operations.

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

Due

• Gries 11.

Related Pages:

• EBoard.
• schemelist.h.
• schemelist.c.
• list.h.

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:

• Homework 6: A To-Do List.
• Read Gries 11.

Related Pages:

• EBoard.
• list.h.
• list.c.

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:

• Read Gries 12.

Related Pages:

• EBoard.
• list.h.
• list.c.

Overview:

• Implementing delete.
• Doubly-linked lists.
• Detour: ADTs vs. Data Structures.
• Circularly-Linked lists.

Class 42 (Tuesday, 15 April 2003) Cancelled

Class 43 (Wednesday, 16 April 2003) Queues

Related Pages:

• EBoard.
• Walker's Lab on Queues.
• queue.c.

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

Related Pages:

• EBoard.

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

• Homework 6.

Related Pages:

• EBoard.

Overview:

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

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

Related Pages:

• EBoard.

Overview:

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

Class 48 (Friday, 25 April 2003) Debugging

Assignments:

• Exam 3: Formal Methods

Related Pages:

• EBoard.

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:

• EBoard.

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:

• Exam 2

Due

• Gries 15.

Related Pages:

• EBoard.

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:

• EBoard.

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:

• EBoard.
• Lab.

Overview:

• Processes in Unix.
• Pipes.
• Lab.

Week Fourteen: Miscellaneous

Attendance is particularly important this week.

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

Assignments:

• Read About End-of-course Evaluations (due Wed).
• Fill out the development evaluation (distributed in paper form) (due Wed).

Related Pages:

• EBoard.
• peter.c, a sample solution to the exercise.

Overview:

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

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

Related Pages:

• EBoard.
• peter.c, the program from yesterday's class.
• piper.c, the program from today's class.

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