Computer Science Fundamentals (CS153 2003S)

CS153 2003S At A Glance

This is an abbreviated course syllabus. Like everything else in this course, it is likely to change.

Weeks: 1, 2, 3, 4, 5, 6, 7, 8, break, 9, 10, 11, 12, 13, 14.

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
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
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
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
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
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
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
Algorithms for common problems. A key problem: Searching. Searching Examples. Lab.
Assignments: Read: Searching.
(23) Wednesday, 26 February 2003
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 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
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
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
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
Reuse. Inheritance. Inheritance in Java. Special issue; Constructors. Special issue: Interfaces. Special issue: Abstract Classes. Example: Prerequisites.
(40) Friday, 11 April 2003
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
Final project presentations. About evaluations. Evaluations. Final statements.
(56) Friday, 9 May 2003
Final comments.



This document is automatically generated from a number of other documents. Hence, I may not always remember to update the history.

Friday, 12 January 2001 [Samuel A. Rebelsky]

Tuesday, 7 Janaury 2003 [Samuel A. Rebelsky]

Tuesday, 14 January 2003 [Samuel A. Rebelsky]

Sunday, 16 February 2003 [Samuel A. Rebelsky]


Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Tue May 6 09:19:12 2003.
The source to the document was last modified on Sun Feb 16 20:54:53 2003.
This document may be found at

You may wish to validate this document's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky,