This is an abbreviated course syllabus.
Like everything else in this course, it is likely to change.
| Week 1: Preliminaries
|
(01) Monday, 20 January 2003
Introduction
Topics:
Definitions: Computer science, computer programming, computing,
algorithm, and more.
Course basics.
Getting started with the ECA.
Administrative issues.
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).
|
(02) Tuesday, 21 January 2003
Binary Search
Topics:
Binary Search
Assertions
Logic and More
Due:
Gries 0-1
|
(03) Wednesday, 22 January 2003
Program Verification
Assignments:
Homework 2: Evalauting
Boolean Propositions (due Tue).
Due:
Homework 1: Binary Search,
Revisited.
|
(04) Friday, 24 January 2003
The Structure of a Computer
Topics:
What is a computer?
Key operations
Some simple programs
Assignments:
Read K&R 1 (due Mon).
Read Gries 2 (due Tue).
|
| Week 2: C Fundamentals
|
(05) Monday, 27 January 2003
An Introduction to C
Topics:
Three sample programs.
A notation for instructions.
Three sample programs, revisited.
An introduction to C.
C vs. Java.
Assignments:
Read Gries 2 (due Tue).
|
(06) Tuesday, 28 January 2003
Working with Boolean Expressions
Topics:
Review: The need for proof.
Key aids to proof: Laws and Rules.
Twelve Basic Laws.
The Rule of Substitution.
The Rule of Transitivity.
Due:
Gries 2
Homework 2
Assignments:
Homework 3: Simple Boolean Proofs.
|
(07) Wednesday, 29 January 2003
An Introduction to C, Continued
Topics:
Lab: An Introduction to C.
Reflection.
|
(08) Friday, 31 January 2003
An Introduction to C, Concluded
Topics:
Lab: An Introduction to Arrays.
Reflection.
Due:
Homework 3: Simple Boolean Proofs.
Assignments:
Representing Integers.
|
| Week 3: Types
|
(09) Monday, 3 February 2003
Representing Integers
Topics:
Binary representation.
Unsigned binary integers.
Computing with unsigned binary integers.
Signed binary integers.
Computing with signed binary integers.
Assignments:
Homework 4: Binary to Decimal
and Back Again (due Fri).
Read Gries, Chapter 4 (due Tue).
Read IEEE Floating
Point Representation.
|
(10) Tuesday, 4 February 2003
Predicates
Topics:
Expanding our worldview: Numbers and Predicates.
Evalutaing Predicates.
Three-Valued Boolean Logic and Short-Circuit Conditionals.
Quantification.
Bound and Unbound Variables.
Substittuion.
Due:
Gries 4
Assignments:
Read IEEE Floating
Point Representation.
|
(11) Wednesday, 5 February 2003
Predicates
Topics:
Expanding our worldview: Numbers and Predicates.
Evalutaing Predicates.
Three-Valued Boolean Logic and Short-Circuit Conditionals.
Quantification.
Bound and Unbound Variables.
Substittuion.
|
(12) Friday, 7 February 2003
Representing Real Numbers
Topics:
Real numbers.
Method one: Rationals.
Method two: Fixed precision.
Method three: Floating point.
Basics of the IEEE Standard.
Some Special Cases.
Learning from Java.
Due:
Homework 4.
Assignments:
Read K&R, Chapter 2.
|
| Week 4: Types in C
|
(13) Monday, 10 February 2003
Fundamental Types in C
Topics:
Integer types.
Real types.
Arithmetic operations.
Enumerated types.
Lab.
|
(14) Tuesday, 11 February 2003
Bitwise Operations
Topics:
C's Bitwise Operations.
Using C's Bitwise Operations.
Lab.
Assignments:
Read K&R 6.1, 6.7, 6.8, and 6.9.
|
(15) Wednesday, 12 February 2003
Compound and User-Defined Types in C
Topics:
Structures.
Unions.
Naming Types.
Lab.
Assignments:
Read appendix B.3 of K& R.
Scan the manual pages for those string procedures.
|
(16) Friday, 14 February 2003
Strings
Topics:
Representing strings in C.
Important string procedures.
Lab.
Assignments:
Read K&R, Chapter 5.
Read Gries, Chapter 5.
|
| Week 5: Arrays and Pointers
|
(17) Monday, 17 February 2003
Array Basics
Topics:
Representing arrays.
Representing multi-dimensional arrays.
Key array operations.
Lab.
Assignments:
Read Gries, Chapter 5.
|
(18) Tuesday, 18 February 2003
Array Assertions
Topics:
What is an array? Additional perspectives.
More notation.
Multidimensional arrays.
Array diagrams.
Partitioning.
Due:
Gries 5.
|
(19) Wednesday, 19 February 2003
Pointer Basics
Topics:
Pointers.
Pointers in C.
Basic Operations.
Memory allocation.
|
(20) Friday, 21 February 2003
Pointer Lab
Topics:
Quick review.
Lab on Pointers.
Assignments:
Read K&R on Functions.
|
| Week 6: Functions
|
(21) Monday, 24 February 2003
Function Basics
Topics:
Functions in C.
C functions vs. Java funtions.
Lab.
Assignments:
Read Gries, Chapter 6.
|
(22) Tuesday, 25 February 2003
Program Documentation
Topics:
Using Assertions.
Notation.
Assertions about Assignments.
Assertions about Sorting.
Due:
Gries 6.
|
(23) Wednesday, 26 February 2003
Asymptotic Analysis
Assignments:
Homework 5.
|
(24) Friday, 28 February 2003
Pointers and Functions
Topics:
Detour: #include and #define
preprocessor directives.
Returning Pointers from Functions.
Pointers to Functions.
Lab.
|
| Week 7: Input and Output
|
(25) Monday, 3 March 2003
I/O Basics
|
(26) Tuesday, 4 March 2003
Weakest Preconditions
Topics:
Preconditions, defined.
Weakness and strength.
Using weakest preconditions.
Due:
Gries 7-8.
Assignments:
Read K&R on files.
|
(27) Wednesday, 5 March 2003
Files
Topics:
The FILE type.
Opening files.
Reading from files.
Writing to files.
Lab.
Assignments:
Exam 1 (due Friday, 14 March 2003).
|
(28) Friday, 7 March 2003
Files, Contined
Topics:
What's wrong with readLine?
What's wrong with the display procedure?
Lab.
Due:
Homework 5.
|
| Week 8: Miscellaneous
|
(29) Monday, 10 March 2003
Designing a List Type
Topics:
What is a list?
Scheme lists.
Java lists.
Assignments:
Read Gries, Chapter 9.
|
(30) Tuesday, 11 March 2003
Semantics of Assignment (1)
Topics:
Review: Weakest Preconditions.
Review: Substitution.
Defining simple assignment.
Some variations.
Defining multiple assignment.
Due:
Gries 9.
|
(31) Wednesday, 12 March 2003
Semantics of Assignment (2)
|
(32) Friday, 14 March 2003
Early Break
Due:
Exam 1.
|
| Spring Break
|
| Week 9: Review
|
(33) Monday, 31 March 2003
Reading Lines (1)
|
(34) Tuesday, 1 April 2003
Reading Lines (2)
Topics:
Testing readLine, continued.
Implementing readLine.
An efficient exponentiation algorithm.
strncpy.
|
(35) Wednesday, 2 April 2003
Semantics of Conditionals
Topics:
A New Form of Conditional.
Formal Definition.
Example: Max.
Example: Largest.
An Interesting Theorem.
Due:
Gries 10.
|
(36) Friday, 4 April 2003
Reading Gries
Topics:
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 10: Linked Lists
|
(37) Monday, 7 April 2003
Linked Lists (1)
Topics:
Review: What is a list?
Key linked-list operations.
Implementing nodes as records.
Implementing key linked-list operations.
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.
|
(38) Tuesday, 8 April 2003
A List Wrapper (1)
Topics:
From Scheme List to Iterated Collection.
A Key Idea: Cursors.
Important List Procedures.
Due:
Gries 11.
|
(39) Wednesday, 9 April 2003
A List Wrapper (2)
Assignments:
Homework 6: A To-Do List.
Read Gries 11.
|
(40) Friday, 11 April 2003
Semantics of Iteration
|
| Week 11: Other Linked Structures
|
(41) Monday, 14 April 2003
Extending Linked Lists: Doubly- and Circularly-Linked Lists
Topics:
Implementing delete.
Doubly-linked lists.
Detour: ADTs vs. Data Structures.
Circularly-Linked lists.
Assignments:
Read Gries 12.
|
(42) Tuesday, 15 April 2003
Cancelled
|
(43) Wednesday, 16 April 2003
Queues
|
(44) Friday, 18 April 2003
Semantics of Procedure Calls
Topics:
What is a procedure definition?
Gries-style procedure definitions.
Informal semantics of procedure calls.
Formal semantics of procedure calls.
|
| Week 12: Program Development (1)
|
(45) Monday, 21 April 2003
Sorting Out Sorting
|
(46) Tuesday, 22 April 2003
Program Mangagement
Topics:
Overview.
Using Multiple Source Files.
Make and Makefiles.
CVS.
Due:
Homework 6.
|
(47) Wednesday, 23 April 2003
The C Preprocessor
Topics:
Overview of the C Preprocessor.
About included files.
Using #define.
Some silly tricks.
|
(48) Friday, 25 April 2003
Debugging
Topics:
Introduction to debugging.
Offline deubgging.
Using print statments.
Using assertions.
Debuggers
Assignments:
Exam 3: Formal Methods
|
| Week 13: Program Development (2)
|
(49) Monday, 28 April 2003
Program Development, the Gries Perspective
Topics:
Plan of the Week.
How and Why Gries Wants You to Work.
An Example: Cap.
Some Rubrics.
An Example: Binary Something.
Due:
Gries 13-14.
|
(50) Tuesday, 29 April 2003
From Invariants to Loops
Topics:
Form of a loop.
Overview of Goals.
Checklist for understanding loops.
Example: Minimum.
Some Principles.
Assignments:
Exam 2
Due:
Gries 15.
|
(51) Wednesday, 30 April 2003
Developing Invariants
Topics:
Smallest example, continued.
Some general principles.
Detour: The infinite loop on failure principle.
Invariants as simplified postconditions.
Due:
Gries 16.
|
(52) Friday, 2 May 2003
Processes (1)
Topics:
Processes in Unix.
Pipes.
Lab.
Due:
Exam 3: Formal Methods
|
| Week 14: Miscellaneous
|
(53) Monday, 5 May 2003
Processes (2)
Topics:
Q&A on Previous Class.
Exercise: Forking Multiple Children.
Assignments:
Read
About End-of-course Evaluations (due Wed).
Fill out the development
evaluation (distributed in paper form) (due Wed).
|
(54) Tuesday, 6 May 2003
Processes (3)
Topics:
Standard Input and Output.
Detour: Command Line.
Executing Other Prorams.
Exercise.
|
(55) Wednesday, 7 May 2003
Evaluation
|
(56) Friday, 9 May 2003
Wrapup
|
;
Check with Bobby