This is an abbreviated course syllabus.
Like everything else in this course, it is likely to change.
| Week 1: Starting Scheme
|
(01) Monday, 20 January 2003
Introduction to The Course
Definitions: Computer science, computer programming, computing,
ialgorithm, and more.
Course basics.
Administrative issues.
Getting started with the ECA.
Assignments:
Scan through the various administrative
handouts (due Tue).
Fill out the introductory
survey (due Tue).
Take the administrivia
quiz (due Tue).
Read: Beginning
Scheme (due Tue).
Skim: The DrScheme Lab
(due Tue).
|
(02) Tuesday, 21 January 2003
Starting Scheme
About Scheme
Lab: The DrScheme Programming
Environment.
Lab: Starting Scheme.
Assignments:
Read Symbolic Values in Scheme.
Read Lists in Scheme.
Read Numbers in Scheme.
|
(03) Wednesday, 22 January 2003
Basic Types: Symbols, Lists, and Numbers
Overview of Types
Symbols
Lists
Numbers
Lab on Types
Assignments:
Read Procedures in
Scheme (due Fri).
Do Laboratory Writeup 1
(due Mon).
|
(04) Friday, 24 January 2003
Procedures
Why define your own procedures?
How to define your own procedures.
Lab on user-defined
procedures.
Assignments:
Read Conditional
Evaluation in Scheme.
|
| Week 2: Control Structures
|
(05) Monday, 27 January 2003
Conditionals
A problem: Turning numbers into letters (in English and Scheme).
Making life easier: Conditionals.
What kinds of tests can you use in conditionals?
Due:
Laboratory writeup 1.
Assignments:
Read Boolean values.
|
(06) Tuesday, 28 January 2003
Conditionals Lab
Lab.
Assignments:
Read Repetition with
Recursion.
|
(07) Wednesday, 29 January 2003
Recursion with Lists
Reflections on Recursion.
Lab: Repetition with Recursion.
Assignments:
Do Homework 1: Deep Recursion.
Read Recursion
with Natural Numbers.
|
(08) Friday, 31 January 2003
Recursion with Numbers
Introduction to numeric recursion.
Lab.
Assignments:
Read Local bindings with
let.
|
| Week 3: Procedures, Revisited
|
(09) Monday, 3 February 2003
Local Bindings
Why name things.
Naming things with let.
Naming things with let*.
Naming procedures.
Lab: Local Bindings with
let.
Assignments:
Read Preconditions and
Postconditions.
|
(10) Tuesday, 4 February 2003
Preconditions and Postconditions
The need for documentation.
Verifying preconditions.
An example: Sum of squares.
Husk and Kernel programming.
Other uses of Husk and Kernel.
Lab.
Due:
Homework 1: Deep Recursion.
Assignments:
Laboratory Writeup 2: Preconditions
and Postconditions.
Read Local Procedure Bindings
with letrec.
|
(11) Wednesday, 5 February 2003
Local Procedures
Lab.
Assignments:
Read Variable-Arity
Procedures.
|
(12) Friday, 7 February 2003
Variable-Arity Procedures
Definition of arity.
Why have variable-arity procedures.
How to write variable-arity procedures.
Lab.
Assignments:
Read Characters in Scheme.
Read Strings in Scheme.
|
| Week 4: More Types
|
(13) Monday, 10 February 2003
Strings
Short introduction to strings.
Lab: Characters and Strings.
Assignments:
Scan Sam's Quick HTML
Reference.
Read CGI Scripting in
Scheme.
|
(14) Tuesday, 11 February 2003
CGI Scripting
What is CGI?
Giving input to CGI programs.
Reading input in CGI programs.
Lab: CGI.
Assignments:
Read Pairs and Pair Structures.
|
(15) Wednesday, 12 February 2003
Pairs and Pair Structures
Behind the scences in Scheme: Memory.
Pairs and Cons cells.
Dotted pairs.
Lab.
Assignments:
Start Exam 1.
Read Vectors.
|
(16) Friday, 14 February 2003
Vectors
Problems with lists.
A solution: Vectors.
Side note: The begin construct.
Assignments:
Read Design
Patterns and Higher-Order Procedures.
Read pp. 69-73 of Bailey. (Stop right before 4.1.2.)
|
| Week 5: Higher-Order Procedures and More
|
(17) Monday, 17 February 2003
Higher-Order Procedures
Design patterns, revisited.
Key ideas of higher-order procedures.
Two key higher-order procedures: map and apply.
Lab.
Assignments:
Read more
higher-order procedures.
Scan chapters 1 to 3 of Algorithms for Functional
Programming.
|
(18) Tuesday, 18 February 2003
More Higher-Order Procedures
Operator sections.
Currying.
Questions on readings.
Lab.
Assignments:
Review sections from Bailey.
|
(19) Wednesday, 19 February 2003
Algorithm Analysis
Comparing Algorithms.
Asymptotic Analysis.
Eliminating Constants.
Asymptotic Analysis in Practice.
The Role of Details.
|
(20) Friday, 21 February 2003
More Algorithm Analysis
Big O notation, revisited.
Doing Big-O Analysis.
Dominant terms.
Big-O Analysis of Recursive Procedures.
Experimental analysis.
Due:
Exam 1.
Assignments:
Homework 2: Some Web Services.
Read Tail Recursion.
|
| Week 6: Algorithms
|
(21) Monday, 24 February 2003
Tail Recursion
Kinds of recursion.
Why do tail recursion.
Generating lists tail-recursively.
|
(22) Tuesday, 25 February 2003
Searching
Algorithms for common problems.
A key problem: Searching.
Searching Examples.
Lab.
Assignments:
Read: Searching.
|
(23) Wednesday, 26 February 2003
Sorting
The problem of sorting.
Writing sorting algorithms.
Examples: Insertion sort, Selection sort.
Lab.
Assignments:
Read Sorting.
|
(24) Friday, 28 February 2003
Fast Sorting Algorithms
Formalizing the problem.
Merge sort.
Quicksort.
Lab.
Assignments:
Read Merge Sort.
Read Quicksort.
Read Randomness and
Simulation.
Laboratory Writeup 3.
|
| Week 7: Scheme, Concluded
|
(25) Monday, 3 March 2003
Sorting Laboratory
Due:
Homework 2.
Assignments:
Read Randomness and
Simulation.
|
(26) Tuesday, 4 March 2003
Randomness and Simulation
The Problem of Simulation.
Scheme's random procedure.
Simulating the roll of dice.
Lab.
Assignments:
Read Input.
|
(27) Wednesday, 5 March 2003
Program Input
Interacting with programs.
Scheme's output procedures.
Scheme's input procedures.
Lab.
Assignments:
Start Exam 2.
Read Files in Scheme.
|
(28) Friday, 7 March 2003
Files
Files and ports.
Reading values.
Reading characters and lines.
Lab.
Due:
Lab writeup 3.
Assignments:
Exam 2.
Read the introduction to Java in Bailey.
Read introduction
and discussion of
Experiments in Java, laboratory J1.
|
| Week 8: Introduction to Java
|
(29) Monday, 10 March 2003
Getting Started with Object-Oriented Programming
An introduction to object-oriented programming.
Assignments:
Read Introduction to J2: Objects in
Java and
Discussion for J2: Objects in Java.
|
(30) Tuesday, 11 March 2003
Getting Started with Java
About Java.
Your first Java program.
Java in the MathLAN.
Lab.
Assignments:
Read Introduction to J2: Objects in
Java and
Discussion for J2: Objects in Java.
|
(31) Wednesday, 12 March 2003
Java Lab
Preparation.
Lab.
|
(32) Friday, 14 March 2003
Objects, Methods, and Classes
Building Classes.
The Problem: A Fraction Class.
Overview of a Class Declaration.
Fields.
Methods.
Constructors.
Different Class Uses.
Some Design Issues.
Due:
Exam 2.
Assignments:
Read Lab J4: Boolean Expressions
and Conditionals.
|
| Spring Break
|
| Week 9: More Java Basics
|
(33) Monday, 31 March 2003
Conditionals
Review.
Boolean expressions in Java.
Basic conditionals: the if statement.
Other conditionals: the switch statement.
Lab.
Assignments:
Read J5: Loops.
|
(34) Tuesday, 1 April 2003
Loops
Review of Conditionals.
Iterative Repetition.
While Loops.
Do Loops.
For Loops.
Lab (J5.1 and J5.3).
Assignments:
Read Lab X3 (focus
on the section on exceptions).
Do Homework 3 (due
next Tuesday).
|
(35) Wednesday, 2 April 2003
When Things Go Wrong
Problems in Programs.
Techniques for Handling Errors.
Exceptions: Java's Primary Error-Handling Technique.
Dealing with Procedures that Throw Exceptions.
Optionally-Catchable Exceptions.
Throwing Exceptions.
Defining Exceptions.
Assignments:
Read J6: Arrays and Hash
Tables.
|
(36) Friday, 4 April 2003
Arrays
Introduction to Arrays.
Arrays in Java.
An Application: Fibonacci Numbers.
An Application: Box Packing.
|
| Week 10: Object-Oriented Design
|
(37) Monday, 7 April 2003
Exam 2
Quicksort.
From Strings to Values.
Assignments:
Think about what you know about inheritance for tomorrow.
|
(38) Tuesday, 8 April 2003
Designing Objects
Introduction to Object-Oriented Design.
Why do Object-Oriented Design.
Some basic strategies.
Reuse.
Assignments:
Read
Lab O1,
Lab O2, and
Lab O3.
|
(39) Wednesday, 9 April 2003
Inheritance
Reuse.
Inheritance.
Inheritance in Java.
Special issue; Constructors.
Special issue: Interfaces.
Special issue: Abstract Classes.
Example: Prerequisites.
|
(40) Friday, 11 April 2003
Polymorphism
Quick review of inheritance.
Questions from previous class.
Polymorphism.
Interfaces.
An Example.
Abstract Classes.
Assignments:
Exam 3: Java Basics.
Read Chapters 1 (The Object-Oriented Method) and 6 (Lists) of
Bailey.
|
| Week 11: Lists
|
(41) Monday, 14 April 2003
Polymorphism Example
Review: What is a Prereq?
Building the PrereqOr class.
Building the PrereqAnd class.
Building the PrereqCourse class.
|
(42) Tuesday, 15 April 2003
Introduction to Abstract Data Types and Data Structures
Organizing Data.
Example: Arrays.
An ADT Hierarchy.
Collections.
|
(43) Wednesday, 16 April 2003
Some List ADTs
What is a list?
A SimpleList ADT.
An OrderedList ADT.
An SortedList ADT.
The java.util perspective.
|
(44) Friday, 18 April 2003
List ADT Design, Continued
Due:
Exam 3.
|
| Week 12: Other Linear Structures
|
(45) Monday, 21 April 2003
Sorting Out Sorting
|
(46) Tuesday, 22 April 2003
Implementing Lists with Arrays
Implementation: Using Arrays.
Due:
Exam 3.
Assignments:
Homework 4:
A To-do List.
|
(47) Wednesday, 23 April 2003
Implementing Lists with Nodes
Deletion in Array-Based Lists.
Detour: Packages in Java.
Scheme Lists, Pairs, and Nodes.
Implementing Lists with Nodes.
Variants.
|
(48) Friday, 25 April 2003
LInear Structures
About linear structures.
Stacks.
Queues.
Implementation notes.
Assignments:
Read the chapter on linear structures in Bailey.
|
| Week 13: Dictionaries
|
(49) Monday, 28 April 2003
Priority Queues, Heaps, and Heap Sort
Priority Queues.
Simple Implementations.
Trees.
Heaps.
Assignments:
Read Bailey on Dictionaries and Hash Tables.
Begin Exam 4.
|
(50) Tuesday, 29 April 2003
The Dictionary ADT
Introduction to the Dictionary ADT
Applications.
More Details.
Dictionaries vs. Databases.
|
(51) Wednesday, 30 April 2003
Implementing Dictionaries with Lists
Review: The Design of Dictionaries.
Central Dictionary Methods.
Dictionaries vs. Databases.
Implementing Dictionaries with Lists.
|
(52) Friday, 2 May 2003
Implementing Dictionaries with Hash Tables
Dictionaries vs. Arrays.
The Idea of Hashing.
Hash Functions.
Hashing in Java.
Handling Hashing Conflicts.
Exceptions.
|
| Week 14: Wrapup
|
(53) Monday, 5 May 2003
Implementing Dictionaries with Binary Search Trees
Review.
An ADT for binary search.
Binarya search trees.
BSTs and dictionaries.
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
Algorithm Design, Revisited
ADT Design.
Algorithm Design.
A Problem: Filling Book Shelves.
A Solution: Dynamic Programming.
Due:
Exam 4.
|
(55) Wednesday, 7 May 2003
Evaluation
Final project presentations.
About evaluations.
Evaluations.
Final statements.
|
(56) Friday, 9 May 2003
Wrapup
Final comments.
|
;
Check with Bobby