This is an abbreviated course syllabus.
Like everything else in this course, it is likely to change.
| Week 1: Starting Scheme
|
| Martin Luther King day
|
(01) Wednesday, 21 January 2004
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 course front door and the various administrative handouts.
Fill out the introductory survey (to be distributed via e-mail).
Read Starting Scheme.
|
(02) Thursday, 22 January 2004
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) Friday, 23 January 2004
Basic Types: Symbols, Lists, and Numbers
Overview of Types
Symbols
Lists
Numbers
Lab on Types
Assignments:
Read Procedures in Scheme (due Mon).
Do Homework 1: Lab Writeup: Types (due Wed).
|
| Week 2: Control Structures
|
(04) Monday, 26 January 2004
Procedures
Why define your own procedures?
How to define your own procedures.
Lab on user-defined
procedures.
Assignments:
Read Conditional evaluation in Scheme.
Read Boolean values in Scheme.
|
(05) Wednesday, 28 January 2004
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:
Homework 1: Lab Writeup: Types.
Assignments:
Read Repetition with recursion.
|
(06) Thursday, 29 January 2004
Recursion with Lists
Recursion basics.
Patterns of recursive functions over lists.
Lab: Repetition with Recursion.
Assignments:
Read Numeric Recursion.
Homework 2: Type-Checking.
|
(07) Friday, 30 January 2004
Numeric Recursion
Introduction to numeric recursion.
Lab.
Assignments:
Read Naming Values with Local Bindings.
|
| Week 3: Procedures, Revisited
|
(08) Monday, 2 February 2004
Local Bindings
Why name things.
Naming things with let.
Naming things with let*.
Naming non-recursive procedures.
Lab: Local Bindings with
let.
Assignments:
Read Preconditions and Postconditions.
|
(09) Wednesday, 4 February 2004
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 2.
Assignments:
Read Local Procedure Bindings with letrec.
|
(10) Thursday, 5 February 2004
Local Procedures
Lab.
|
(11) Friday, 6 February 2004
Variable-Arity Procedures
Lab.
Assignments:
Do Homework 3.
Read Characters in Scheme.
Read Strings in Scheme.
|
| Week 4: Compound Structures
|
(12) Monday, 9 February 2004
Strings
Short introduction to strings.
Lab: Characters and Strings.
Assignments:
Read Pairs and Pair Structures.
Begin Exam 1.
|
(13) Wednesday, 11 February 2004
Pause for Breath
Question: Summing Random Numbers.
On the relationship between modulo and remainder.
On the various real to integer conversion procedures.
Due:
Homework 3.
|
(14) Thursday, 12 February 2004
Pairs and Pair Structures
Behind the scences in Scheme: Memory.
Pairs and Cons cells.
Dotted pairs.
Lab.
Assignments:
Read Vectors.
|
(15) Friday, 13 February 2004
Vectors
Problems with lists.
A solution: Vectors.
Side note: The begin construct.
Lab.
Assignments:
Read Higher-Order Procedures (1). (Here's where Scheme gets really cool.)
|
| Week 5: Higher-Order Procedures and More
|
(16) Monday, 16 February 2004
Higher-Order Procedures (1)
Design patterns, revisited.
Key ideas of higher-order procedures.
Lab.
Assignments:
Read Higher-Order Procedures (2).
|
(17) Wednesday, 18 February 2004
Higher-Order Procedures (2)
Operator sections.
Rethinking procedure definitions.
Questions on readings.
Lab.
Due:
Exam 1.
Assignments:
Homework 4: Higher-Order Vector Procedures.
|
(18) Thursday, 19 February 2004
Higher-Order Procedures (3)
Lab (1), Continued.
Lab (2), Continued.
Reflection.
|
(19) Friday, 20 February 2004
Tail Recursion
Kinds of recursion.
Why do tail recursion.
How to do tail recursion.
Generating lists tail-recursively.
Lab.
Assignments:
Read Tail Recursion.
|
| Week 6: Algorithms
|
(20) Monday, 23 February 2004
Algorithm Analysis (1)
Comparing Algorithms.
Asymptotic Analysis.
Eliminating Constants.
Asymptotic Analysis in Practice.
The Role of Details.
|
(21) Wednesday, 25 February 2004
Algorithm Analysis (2)
Big O notation, revisited.
Doing Big-O Analysis.
Dominant terms.
Big-O Analysis of Recursive Procedures.
Experimental analysis.
Due:
Homework 4.
Assignments:
Read Searching.
|
(22) Thursday, 26 February 2004
Searching
Algorithms for common problems.
A key problem: Searching.
Sequential Search.
Binary Search.
Lab.
Assignments:
Read Sorting.
|
(23) Friday, 27 February 2004
Sorting
The problem of sorting.
Writing sorting algorithms.
Examples: Insertion sort, Selection sort.
Continue Searching lab.
Assignments:
Read Merge Sort.
Read Quicksort.
|
| Week 7: Introduction to Java
|
(24) Monday, 1 March 2004
Comparing Sorting Algorithms
O(n2) sorting algorithms.
Random detours.
|
(25) Wednesday, 3 March 2004
Detour: Miscellaneous Scheme Stuff
Equality predicates.
Continuations.
Assignments:
Exam 2: Algorithms and Higher-Order Procedures.
Read Randomness and simulation.
|
(26) Thursday, 4 March 2004
Discussion of Exam 1
|
(27) Friday, 5 March 2004
Fast Sorting Algorithms
Merge sort.
Quicksort.
Lab.
Assignments:
Read Experiments in Java, Chapter J1: An Introduction to Java.
|
| Week 8: More Java Basics
|
(28) Monday, 8 March 2004
Getting Started with Object-Oriented Programming
An introduction to object-oriented programming.
|
(29) Wednesday, 10 March 2004
Getting Started with Java
About Java.
Your first Java program.
Java in the MathLAN.
Lab.
Due:
Exam 2.
|
(30) Thursday, 11 March 2004
Discussion of Exam 2
Cloning.
Less-Than?.
Sectioning.
|
(31) Friday, 12 March 2004
Objects, Methods, and Classes
Building Classes.
The Problem: A RationalClass.
Overview of a Class Declaration.
Fields, Methods, and Constructors.
Different Class Uses.
Some Design Issues.
|
| Spring Break
|
| Week 9:
|
(32) Monday, 29 March 2004
Conditionals
Review.
Boolean expressions in Java.
Basic conditionals: the if statement.
Other conditionals: the switch statement.
Lab.
Assignments:
Read Lab J5: Loops.
|
(33) Wednesday, 31 March 2004
Loops
Iterative Repetition.
While Loops.
Do Loops.
For Loops.
Lab (J5.1 and J5.3).
Assignments:
Read X3: Input, output, files, and exceptions. Focus on the exceptions issues.
|
(34) Thursday, 1 April 2004
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:
Start homework 5.
|
(35) Friday, 2 April 2004
Building a Rational Class, Revisited
Review: Java.
Review: Rational.java.
Computing gcds.
Arithmetic operations.
Testing.
Constructors.
|
| Week 10: Lists
|
(36) Monday, 5 April 2004
Arrays
Introduction to Arrays.
Arrays in Java.
An Application: Fibonacci Numbers.
An Application: Box Packing.
Assignments:
Read O1: Object-Oriented Design.
|
(37) Wednesday, 7 April 2004
Designing Objects
Introduction to Object-Oriented Design.
Why do Object-Oriented Design.
Protection.
Some basic strategies.
Reuse.
A group exercise.
Assignments:
Read EIJ, Lab O2.
|
(38) Thursday, 8 April 2004
Inheritance
Reuse.
Inheritance.
Inheritance in Java.
Special issue: Constructors.
Special issue: Interfaces.
Special issue: Abstract Classes.
Lab.
Assignments:
Read EIJ, Chapter O3.
Begin Homework 5.
|
(39) Friday, 9 April 2004
Polymorphism
Quick review of inheritance.
Quick review of polymorphism.
Lab: Polymorphism.
|
| Week 11: Other Linear Structures
|
(40) Monday, 12 April 2004
Introduction to Abstract Data Types and Data Structures
Organizing Data.
Example: Arrays.
Collections.
Assignments:
Read the section on lists in the data structures book distributed to you. Summarize the methods associate with the list ADT.
|
(41) Wednesday, 14 April 2004
Scheme Lists
Scheme lists as ADT.
Implementing Scheme lists.
Due:Homework 6.
Assignments:
Exam 3.
|
(42) Thursday, 15 April 2004
List ADT Design
What else is a list?
A SimpleList ADT.
An OrderedList ADT.
An SortedList ADT.
The java.util perspective.
|
(43) Friday, 16 April 2004
Implementing Lists with Arrays
Implementation: Using Arrays.
Strategies for various methods.
Running time.
Determining if a position is valid.
Assignments:
Read Lists with "Current" Considered Harmful by Joseph Bergin.
|
| Week 12: Miscellaneous
|
(44) Monday, 19 April 2004
Yet Another Detour
|
(45) Wednesday, 21 April 2004
Determining Position Validity
Due:
Exam 3.
|
(46) Thursday, 22 April 2004
Implementing Lists with Nodes
Detour: Implementing isValid.
Implementing Lists with Nodes.
Basic Methods.
Implementing Ordered Lists.
Variants.
|
(47) Friday, 23 April 2004
Linear Structures
About linear structures.
Stacks.
Queues.
Priority Queues.
Implementation notes.
Assignments:
Homework 7: Task Lists.
|
| Week 13: Dictionaries
|
(48) Monday, 26 April 2004
Detour: Serialization
Why serialize objects.
How to serialize objects.
Other introspection issues.
|
(49) Wednesday, 28 April 2004
Cancelled
|
(50) Thursday, 29 April 2004
Priority Queues, Heaps, and Heap Sort
Priority Queues.
Simple Implementations.
Trees.
Heaps.
Due:
Homework 7.
Assignments:
Homework 8: Sorting.
|
(51) Friday, 30 April 2004
The Dictionary ADT
Introduction to the Dictionary ADT
Methods.
Applications.
Dictionaries vs. Databases.
Implementation: Association Lists (and variants).
Implementation: Binary Search Trees.
|
| Week 14:
|
(52) Monday, 3 May 2004
Implementing Dictionaries with Hash Tables
The Idea of Hashing.
Hash Functions.
Hashing in Java.
Handling Hashing Conflicts.
|
(53) Wednesday, 5 May 2004
Implementing Dictionaries with Binary Search Trees
An ADT for binary search.
Implementing that ADT with arrays.
Binary search trees.
BSTs and dictionaries.
|
(54) Thursday, 6 May 2004
Discussion of Exam 3
Problem 1: Erroneous Code.
Problem 2: Orders.
Problem 3: Dynamic Arrays.
Problem 4: Selection Sort.
|
(55) Friday, 7 May 2004
Evaluation
Evaluation.
The subject matter.
Final thoughts.
|
;
Check with Bobby