CS153 2003S Course Syllabus

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

• Week One: Starting Scheme
• Week Two: Control Structures
• Week Three: Procedures, Revisited
• Week Four: More Types
• Week Five: Higher-Order Procedures and More
• Week Six: Algorithms
• Week Seven: Scheme, Concluded
• Week Eight: Introduction to Java
• Break
• Week Nine: More Java Basics
• Week Ten: Object-Oriented Design
• Week Eleven: Lists
• Week Twelve: Other Linear Structures
• Week Thirteen: Dictionaries
• Week Fourteen: Wrapup

Week One: Starting Scheme

Class 01 (Monday, 20 January 2003) Introduction to The Course

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).

Overview:

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

Class 02 (Tuesday, 21 January 2003) Starting Scheme

Assignments:

• Read Symbolic Values in Scheme.
• Read Lists in Scheme.
• Read Numbers in Scheme.

Related Pages:

• Reading on Scheme Basics.
• DrScheme Lab.
• Lab on Scheme Basics.

Overview:

• About Scheme
• Lab: The DrScheme Programming Environment.
• Lab: Starting Scheme.

Class 03 (Wednesday, 22 January 2003) Basic Types: Symbols, Lists, and Numbers

Assignments:

• Read Procedures in Scheme (due Fri).
• Do Laboratory Writeup 1 (due Mon).

Handouts:

• Instructions for Laboratory Writeups.

Related Pages:

• Reading on Symbolic Values in Scheme.
• Reading on Lists in Scheme.
• Reading on Numbers in Scheme.
• Lab on Types in Scheme.

Overview:

• Overview of Types
• Symbols
• Lists
• Numbers
• Lab on Types

Class 04 (Friday, 24 January 2003) Procedures

Assignments:

• Read Conditional Evaluation in Scheme.

Related Pages:

• Reading on procedures.
• Lab on procedures.

Overview:

• Why define your own procedures?
• How to define your own procedures.
• Lab on user-defined procedures.

Week Two: Control Structures

Class 05 (Monday, 27 January 2003) Conditionals

Due

• Laboratory writeup 1.

Assignments:

• Read Boolean values.

Related Pages:

• EBoard.
• Reading on Boolean expressions.
• Reading on conditionals.

Overview:

• A problem: Turning numbers into letters (in English and Scheme).
• Making life easier: Conditionals.
• What kinds of tests can you use in conditionals?

Class 06 (Tuesday, 28 January 2003) Conditionals Lab

Assignments:

• Read Repetition with Recursion.

Related Pages:

• Reading on Boolean expressions.
• Reading on conditionals.
• Lab on conditionals.

Overview:

• Lab.

Class 07 (Wednesday, 29 January 2003) Recursion with Lists

Assignments:

• Do Homework 1: Deep Recursion.
• Read Recursion with Natural Numbers.

Related Pages:

• EBoard
• Initial reading on recursion.
• Lab on recursion.

Overview:

• Reflections on Recursion.
• Lab: Repetition with Recursion.

Class 08 (Friday, 31 January 2003) Recursion with Numbers

Assignments:

• Read Local bindings with let.

Related Pages:

• EBoard.
• Reading on numeric recursion.
• Lab on numeric recursion.

Overview:

• Introduction to numeric recursion.
• Lab.

Week Three: Procedures, Revisited

Class 09 (Monday, 3 February 2003) Local Bindings

Assignments:

• Read Preconditions and Postconditions.

Related Pages:

• EBoard.
• Reading on Local Bindings with Let.
• Lab on Local Bindings with Let.

Overview:

• Why name things.
• Naming things with let.
• Naming things with let*.
• Naming procedures.
• Lab: Local Bindings with let.

Class 10 (Tuesday, 4 February 2003) Preconditions and Postconditions

Due

• Homework 1: Deep Recursion.

Assignments:

• Laboratory Writeup 2: Preconditions and Postconditions.
• Read Local Procedure Bindings with letrec.

Related Pages:

• EBoard.
• Reading on Preconditions and Postconditions.
• Lab on Preconditions and Postconditions.

Overview:

• The need for documentation.
• Verifying preconditions.
• An example: Sum of squares.
• Husk and Kernel programming.
• Other uses of Husk and Kernel.
• Lab.

Class 11 (Wednesday, 5 February 2003) Local Procedures

Assignments:

• Read Variable-Arity Procedures.

Related Pages:

• Reading on Local Recursive Procedures.
• Lab on Local Recursive Procedures.

Overview:

• Lab.

Class 12 (Friday, 7 February 2003) Variable-Arity Procedures

Assignments:

• Read Characters in Scheme.
• Read Strings in Scheme.

Related Pages:

• EBoard.
• Reading on Variable-Arity Procedures.
• Lab on Variable-Arity Procedures.

Overview:

• Definition of arity.
• Why have variable-arity procedures.
• How to write variable-arity procedures.
• Lab.

Week Four: More Types

Class 13 (Monday, 10 February 2003) Strings

Assignments:

• Scan Sam's Quick HTML Reference.
• Read CGI Scripting in Scheme.

Related Pages:

• EBoard.
• Reading on Characters.
• Reading on Strings.
• Lab on Strings.

Overview:

• Short introduction to strings.
• Lab: Characters and Strings.

Class 14 (Tuesday, 11 February 2003) CGI Scripting

Assignments:

• Read Pairs and Pair Structures.

Related Pages:

• EBoard.
• Reading on HTML.
• Reading on CGI.
• Lab on CGI.

Overview:

• What is CGI?
• Giving input to CGI programs.
• Reading input in CGI programs.
• Lab: CGI.

Class 15 (Wednesday, 12 February 2003) Pairs and Pair Structures

Assignments:

• Start Exam 1.
• Read Vectors.

Related Pages:

• EBoard.
• Reading on Pairs.
• Lab on Pairs.

Overview:

• Behind the scences in Scheme: Memory.
• Pairs and Cons cells.
• Dotted pairs.
• Lab.

Class 16 (Friday, 14 February 2003) Vectors

Assignments:

• Read Design Patterns and Higher-Order Procedures.
• Read pp. 69-73 of Bailey. (Stop right before 4.1.2.)

Related Pages:

• EBoard.
• Reading on Vectors.
• Lab on Vectors.

Overview:

• Problems with lists.
• A solution: Vectors.
• Side note: The begin construct.

Week Five: Higher-Order Procedures and More

Class 17 (Monday, 17 February 2003) Higher-Order Procedures

Assignments:

• Read more higher-order procedures.
• Scan chapters 1 to 3 of Algorithms for Functional Programming.

Related Pages:

• EBoard.
• Reading on higher-order procedures.
• Lab on higher-order procedures.

Overview:

• Design patterns, revisited.
• Key ideas of higher-order procedures.
• Two key higher-order procedures: map and apply.
• Lab.

Class 18 (Tuesday, 18 February 2003) More Higher-Order Procedures

Assignments:

• Review sections from Bailey.

Related Pages:

• EBoard.
• First reading on higher-order procedures.
• Second reading on higher-order procedures.
• First lab on higher-order procedures.
• Second lab on higher-order procedures.

Overview:

• Operator sections.
• Currying.
• Questions on readings.
• Lab.

Class 19 (Wednesday, 19 February 2003) Algorithm Analysis

Related Pages:

• EBoard.

Overview:

• Comparing Algorithms.
• Asymptotic Analysis.
• Eliminating Constants.
• Asymptotic Analysis in Practice.
• The Role of Details.

Class 20 (Friday, 21 February 2003) More Algorithm Analysis

Due

• Exam 1.

Assignments:

• Homework 2: Some Web Services.
• Read Tail Recursion.

Related Pages:

• EBoard.

Overview:

• Big O notation, revisited.
• Doing Big-O Analysis.
• Dominant terms.
• Big-O Analysis of Recursive Procedures.
• Experimental analysis.

Week Six: Algorithms

Class 21 (Monday, 24 February 2003) Tail Recursion

Related Pages:

• EBoard.
• Reading on tail recursion.

Overview:

• Kinds of recursion.
• Why do tail recursion.
• Generating lists tail-recursively.

Class 22 (Tuesday, 25 February 2003) Searching

Assignments:

• Read: Searching.

Related Pages:

• EBoard.
• Reading on Searching.
• Lab on Searching.

Overview:

• Algorithms for common problems.
• A key problem: Searching.
• Searching Examples.
• Lab.

Class 23 (Wednesday, 26 February 2003) Sorting

Assignments:

• Read Sorting.

Related Pages:

• EBoard.
• Reading on Sorting.
• Lab on Sorting.

Overview:

• The problem of sorting.
• Writing sorting algorithms.
• Examples: Insertion sort, Selection sort.
• Lab.

Class 24 (Friday, 28 February 2003) Fast Sorting Algorithms

Assignments:

• Read Merge Sort.
• Read Quicksort.
• Read Randomness and Simulation.
• Laboratory Writeup 3.

Related Pages:

• EBoard.
• Reading on Merge Sort.
• Reading on Quicksort.
• Lab on Fast Sorting Algorithms.

Overview:

• Formalizing the problem.
• Merge sort.
• Quicksort.
• Lab.

Week Seven: Scheme, Concluded

Class 25 (Monday, 3 March 2003) Sorting Laboratory

Due

• Homework 2.

Assignments:

• Read Randomness and Simulation.

Related Pages:

• EBoard.
• Lab.
• Reading on Merge Sort.
• Reading on Quicksort.

Class 26 (Tuesday, 4 March 2003) Randomness and Simulation

Assignments:

• Read Input.

Related Pages:

• EBoard.
• Reading on Simulation.
• Lab.

Overview:

• The Problem of Simulation.
• Scheme's random procedure.
• Simulating the roll of dice.
• Lab.

Class 27 (Wednesday, 5 March 2003) Program Input

Assignments:

• Start Exam 2.
• Read Files in Scheme.

Related Pages:

• EBoard.
• Reading on Input in Scheme.
• Lab on Input and Output in Scheme.

Overview:

• Interacting with programs.
• Scheme's output procedures.
• Scheme's input procedures.
• Lab.

Class 28 (Friday, 7 March 2003) Files

Due

• Lab writeup 3.

Assignments:

• Exam 2.
• Read the introduction to Java in Bailey.
• Read introduction and discussion of Experiments in Java, laboratory J1.

Related Pages:

• EBoard.
• Reading on Files.
• Lab on Files.

Overview:

• Files and ports.
• Reading values.
• Reading characters and lines.
• Lab.

Week Eight: Introduction to Java

Class 29 (Monday, 10 March 2003) Getting Started with Object-Oriented Programming

Assignments:

• Read Introduction to J2: Objects in Java and Discussion for J2: Objects in Java.

Overview:

• An introduction to object-oriented programming.

Class 30 (Tuesday, 11 March 2003) Getting Started with Java

Assignments:

• Read Introduction to J2: Objects in Java and Discussion for J2: Objects in Java.

Related Pages:

• EBoard.
• Lab J1.

Overview:

• About Java.
• Your first Java program.
• Java in the MathLAN.
• Lab.

Class 31 (Wednesday, 12 March 2003) Java Lab

Related Pages:

• EBoard.
• Lab.

Overview:

• Preparation.
• Lab.

Class 32 (Friday, 14 March 2003) Objects, Methods, and Classes

Due

• Exam 2.

Assignments:

• Read Lab J4: Boolean Expressions and Conditionals.

Related Pages:

• EBoard.
• Lab J2.
• Lab J3.

Overview:

• Building Classes.
• The Problem: A Fraction Class.
• Overview of a Class Declaration.
• Fields.
• Methods.
• Constructors.
• Different Class Uses.
• Some Design Issues.

Break

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

Week Nine: More Java Basics

Class 33 (Monday, 31 March 2003) Conditionals

Assignments:

• Read J5: Loops.

Related Pages:

• EBoard.
• Lab J4.

Overview:

• Review.
• Boolean expressions in Java.
• Basic conditionals: the if statement.
• Other conditionals: the switch statement.
• Lab.

Class 34 (Tuesday, 1 April 2003) Loops

Assignments:

• Read Lab X3 (focus on the section on exceptions).
• Do Homework 3 (due next Tuesday).

Related Pages:

• EBoard.
• Lab J5.

Overview:

• Review of Conditionals.
• Iterative Repetition.
• While Loops.
• Do Loops.
• For Loops.
• Lab (J5.1 and J5.3).

Class 35 (Wednesday, 2 April 2003) When Things Go Wrong

Assignments:

• Read J6: Arrays and Hash Tables.

Related Pages:

• EBoard.

Overview:

• 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.

Class 36 (Friday, 4 April 2003) Arrays

Related Pages:

• EBoard

Overview:

• Introduction to Arrays.
• Arrays in Java.
• An Application: Fibonacci Numbers.
• An Application: Box Packing.

Week Ten: Object-Oriented Design

Class 37 (Monday, 7 April 2003) Exam 2

Assignments:

• Think about what you know about inheritance for tomorrow.

Related Pages:

• EBoard.

Overview:

• Quicksort.
• From Strings to Values.

Class 38 (Tuesday, 8 April 2003) Designing Objects

Assignments:

• Read Lab O1, Lab O2, and Lab O3.

Related Pages:

• EBoard.

Overview:

• Introduction to Object-Oriented Design.
• Why do Object-Oriented Design.
• Some basic strategies.
• Reuse.

Class 39 (Wednesday, 9 April 2003) Inheritance

Overview:

• Reuse.
• Inheritance.
• Inheritance in Java.
• Special issue; Constructors.
• Special issue: Interfaces.
• Special issue: Abstract Classes.
• Example: Prerequisites.

Class 40 (Friday, 11 April 2003) Polymorphism

Assignments:

• Exam 3: Java Basics.
• Read Chapters 1 (The Object-Oriented Method) and 6 (Lists) of Bailey.

Related Pages:

• EBoard.
• Code files for Four-Year Planner.

Overview:

• Quick review of inheritance.
• Questions from previous class.
• Polymorphism.
• Interfaces.
• An Example.
• Abstract Classes.

Week Eleven: Lists

Class 41 (Monday, 14 April 2003) Polymorphism Example

Related Pages:

• EBoard.

Overview:

• Review: What is a Prereq?
• Building the PrereqOr class.
• Building the PrereqAnd class.
• Building the PrereqCourse class.

Class 42 (Tuesday, 15 April 2003) Introduction to Abstract Data Types and Data Structures

Related Pages:

• EBoard.

Overview:

• Organizing Data.
• Example: Arrays.
• An ADT Hierarchy.
• Collections.

Class 43 (Wednesday, 16 April 2003) Some List ADTs

Related Pages:

• EBoard.
• Documentation for java.util.List.

Overview:

• What is a list?
• A SimpleList ADT.
• An OrderedList ADT.
• An SortedList ADT.
• The java.util perspective.

Class 44 (Friday, 18 April 2003) List ADT Design, Continued

Due

• Exam 3.

Related Pages:

• EBoard.
• List.java.
• Cursor.java.
• TestDelIt.java.
• Documentation for java.util.List.
• Documentation for java.util.ListIterator.
• Documentation for java.util.ArrayList.

Week Twelve: Other Linear Structures

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

Class 46 (Tuesday, 22 April 2003) Implementing Lists with Arrays

Due

• Exam 3.

Assignments:

• Homework 4: A To-do List.

Related Pages:

• EBoard.
• List.java.
• Cursor.java.
• ArrayList.java.
• ArrayListCursor.java.

Overview:

• Implementation: Using Arrays.

Class 47 (Wednesday, 23 April 2003) Implementing Lists with Nodes

Related Pages:

• EBoard.
• linkedlist package Code.

Overview:

• Deletion in Array-Based Lists.
• Detour: Packages in Java.
• Scheme Lists, Pairs, and Nodes.
• Implementing Lists with Nodes.
• Variants.

Class 48 (Friday, 25 April 2003) LInear Structures

Assignments:

• Read the chapter on linear structures in Bailey.

Related Pages:

• EBoard.
• Linear.java.
• FullStructureException.java.
• EmptyStructureException.java.
• Queue.java.

Overview:

• About linear structures.
• Stacks.
• Queues.
• Implementation notes.

Week Thirteen: Dictionaries

Class 49 (Monday, 28 April 2003) Priority Queues, Heaps, and Heap Sort

Assignments:

• Read Bailey on Dictionaries and Hash Tables.
• Begin Exam 4.

Related Pages:

• Priority Queues.

Overview:

• Priority Queues.
• Simple Implementations.
• Trees.
• Heaps.

Class 50 (Tuesday, 29 April 2003) The Dictionary ADT

Related Pages:

• EBoard.
• Dictionary.java
• Documentation for java.util.Dictionary.
• Documentation for java.util.Map, the successor to java.util.Dictionary.

Overview:

• Introduction to the Dictionary ADT
• Applications.
• More Details.
• Dictionaries vs. Databases.

Class 51 (Wednesday, 30 April 2003) Implementing Dictionaries with Lists

Related Pages:

• EBoard.
• Dictionary.java
• Documentation for java.util.Dictionary.
• Documentation for java.util.Map, the successor to java.util.Dictionary.

Overview:

• Review: The Design of Dictionaries.
• Central Dictionary Methods.
• Dictionaries vs. Databases.
• Implementing Dictionaries with Lists.

Class 52 (Friday, 2 May 2003) Implementing Dictionaries with Hash Tables

Related Pages:

• EBoard.
• Documentation for java.util.Hashtable.

Overview:

• Dictionaries vs. Arrays.
• The Idea of Hashing.
• Hash Functions.
• Hashing in Java.
• Handling Hashing Conflicts.
• Exceptions.

Week Fourteen: Wrapup

Attendance is particularly important this week.

Class 53 (Monday, 5 May 2003) Implementing Dictionaries with Binary Search Trees

Assignments:

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

Related Pages:

• EBoard.

Overview:

• Review.
• An ADT for binary search.
• Binarya search trees.
• BSTs and dictionaries.

Class 54 (Tuesday, 6 May 2003) Algorithm Design, Revisited

Due

• Exam 4.

Related Pages:

• EBoard.
• ShelfPacking.java .

Overview:

• ADT Design.
• Algorithm Design.
• A Problem: Filling Book Shelves.
• A Solution: Dynamic Programming.

Class 55 (Wednesday, 7 May 2003) Evaluation

Related Pages:

• EBoard.
• About End-Of-Course Evaluations.
• End-Of-Course Evaluation.

Overview:

• Evaluations.

Class 56 (Friday, 9 May 2003) Wrapup

Related Pages:

• EBoard.
• What I hope you learned in CSC153.
• Final Statements.

Overview:

• The subject matter of the course.
• Final comments.