This is a highly approximate syllabus. Expect
topics, assignments, ordering, and almost everything else to change.
Class 01
(Monday, January 24, 2000)
Introduction to the Course
- Course overview
- Definition of computer science
- Introduction to data structures and algorithms
- Introduction to programming paradigms
- Handouts:
Class 02
(Tuesday, January 25, 2000)
Introduction to Java
- Introduction to data structures
- Introduction to object-oriented programming
- An introduction to Java
- Java vs. Scheme
- Due:
- Handouts:
Class 03
(Wednesday, January 26, 2000)
Lab: Getting Started with Java
- The structure of Java programs, revisited
- Using Java in the MathLAN, revisited
- Laboratory J1:
An Introduction to Java
- Due:
Class 04
(Friday, January 28, 2000)
Lab: Objects and Methods
- The structure of a class, revisited
- Fields
- Methods
- Constructors
- Scheme vs. Java
- Lab J2: Objects and Methods
- Due:
- Preparatory reading of Lab J2
Class 05
(Monday, January 31, 2000)
Lab: Objects and Methods, Continued
- The usss of classes, revisited
- Lab J2, continued
- Initial reflections on Lab J2
Class 06
(Tuesday, February 1, 2000)
Lab: Objects and Classes
- Encapsulating object state with fields
- Constructors
- Overloading
- Lab J3: Building Your Own Classes
- Due:
- Preparatory reading of Lab J3
- Homework 1: Completed Lab J2
Class 07
(Wednesday, February 2, 2000)
Lab: Objects and Classes, Revisited
- Project selection, continued
- Lab J3, Continued
- Distributed:
- Homework 2:
The Design of a Student Information Class
(Due Monday, February 7, 2000)
Class 08
(Friday, February 4, 2000)
Object-Oriented Design
- Project discussion
- (Re)Introduction to object-oriented design
- Motivation
- Key attributes
- Sample object-oriented designs
- The six P's
- Due:
- Reading of Lab O1: Object-Oriented Design (we will not
do this lab)
Class 09
(Monday, February 7, 2000)
Reuse Through Inheritance and Polymorphism
- Goals of reuse
- Inheritance
- Overloading
- Polymorphism
- Due:
Class 10
(Tuesday, February 8, 2000)
Lab: Conditionals
- Boolean values and expressions
- The
if statement
- The
switch statement
- Lab J4:
Boolean Expressions and Conditionals
- Handouts:
- Due:
- Homework 2:
The Design of a Student Info Class
- Preparatory reading of Lab J4: Boolean Expressions and Conditionals
Class 11
(Wednesday, February 9, 2000)
Lab: Loops
- Project selection
- The need for repetition
- Primary looping control structures:
- Lab J5:
Control Structures for Repetition
- Distributed:
- Java Plus Data Structures, Chapters 4, 5, 6, and 11
- Due:
- Preparatory reading of Lab J5
Class 12
(Friday, February 11, 2000)
When Things Go Wrong
- Program design: How to handle and check errors
- Test before execution
- Test results
- Catch exceptions
- Avoiding errors: Preconditions and postconditions
- Handouts:
- Exam 1 (due Friday, February 18, 2000)
- Due:
- Preparatory reading of Lab X3
Class 13
(Monday, February 14, 2000)
Project Design
- Discussion:
- Project components and architecture
- Working in a team
- Selecting components
Class 14
(Tuesday, February 15, 2000)
Lab: Java's Abstract Windowing Toolkit
- GUI basics
- Java's Abstract Windowing Toolkit (AWT)
- Primary components: Frames, TextFields, etc.
- Event handling
- Lab G2:
Java's Abstract Windowing Toolkit
- Due:
- Preparatory reading of Lab G2
Class 15
(Wednesday, February 16, 2000)
Discussion of Homework 2
- Protection levels, revisited
- Static methods, revisited
- Notes from assignment 2
- Handouts:
Class 16
(Friday, February 18, 2000)
Java's AWT, Revisited
- Javadoc
- Organizing the frame
- Event Handling, Revisited
- Lab G3:
Java's Abstract Windowing Toolkit, Continued
- Handouts:
- Due:
- Exam 1
- Preparatory reading of Lab G3
Class 17
(Monday, February 21, 2000)
Growing a Language
- Some notes on the origin(s) of Java.
- Handouts:
Class 18
(Tuesday, February 22, 2000)
Growing a Language
- Two simple ``find the smallest value'' algorithms
- Basics of algorithm analysis
- Other searching algorithms
- Due:
- Java Plus Data Structures, Section 5.5
Class 19
(Wednesday, February 23, 2000)
Algorithm Analysis
- Recursion
- The three question method:
- Recursive case
- Base case
- Shrinking input
- Recursion vs. iteration
- Lab A1: Recursion
- Due:
- Preparatory reading of Lab A1
- Java Plus Data Structures, Chapter 6: Recursion
- Homework 4: A Graphical Student Database
Class 20
(Friday, February 25, 2000)
Lab: Recursion
- Examples
- Three versions of exponentation
- Two versions of Fibonacci
- Recursive functions and recurrence relations
- Due:
- Project, Phase 1: Initial specifications for all your classes
(written as interfaces)
Class 21
(Monday, February 28, 2000)
Algorithm Analysis, Revisited
- Some recursive algorithms
- Binary search
- Efficient exponentiation
- Coputing Fibonacci numbers
- Some techniques for analyzing those algorithms
Class 22
(Tuesday, February 29, 2000)
Analyzing Recursive Algorithms
- Exponentiation, revisited
- Techniques for analyzing recursive functions
- Fibonacci numbers.
Class 23
(Wednesday, March 1, 2000)
Arrays
- Arrays as a data structure
- General model
- Java's model
- An application: improving Fibonacci
- Another application: bin packing
- Due:
- Preparatory reading of Lab J6
- Project, Phase 2: Specifications
- Handouts:
Class 24
(Friday, March 3, 2000)
Project Discussion: Specifications
- Box packing, continued
- Project narrative
Class 25
(Monday, March 6, 2000)
Introduction to Sorting
- Project discussion, continued
- The problem of sorting
- In-place vs. out-of-place sorting
- Stable sorts
- Due:
- Java Plus Data Structures, Chapter 11: Sorting
Class 26
(Tuesday, March 7, 2000)
Some Sorting Algorithms
- Comparators
- Two basic sorting methods:
- Selection sort
- Bubble sort
- Choosing a sorting method
Class 27
(Wednesday, March 8, 2000)
More Efficient Sorting Algorithms
- Divide and conquer sorts
- Other sorting techniques
- Sorting, concluded
- Handouts:
- Exam 2 (due Friday, March 17, 2000)
Class 28
(Friday, March 10, 2000)
Discussion of Assignment 3
- I'll be at the SIGCSE conference, speaking and learning about
CS education. Mr. Stone will teach today's class.
- Why document?
- Audiences for documentation
- Javadoc: Java's documentation toolkit
- Short Javadoc lab
Class 29
(Monday, March 13, 2000)
Introduction to Data Structures
- Introduction to data structures
- Four key issues: functionality, implementation, efficiency,
applications
- Compound data types
- Collections
- Iterated Collections
- Keyed Tables
Class 30
(Tuesday, March 14, 2000)
Introduction to Lists
- Introduction to lists
- Iteration
- The design of lists
- A data-oriented perspective
- A functionality-oriented perspectivve
- Other design issues
- Due:
- Project, Phase 3:
Compilable interfaces and stubs for all your project classes.
- Java Plus Data Structures, Chapter 4: Implementing Lists
with Arrays
- Due:
- Java Plus Data Structures, Chapter 7: Linked Lists
Class 31
(Wednesday, March 15, 2000)
Implementing Lists with Arrays
- Scheme lists, revisited
- Primary implementation techniques for other lists
Class 32
(Friday, March 17, 2000)
Lab: Animation
- It's the day before break, so we'll just have fun working with
animations in Java
- Key topics:
- Drawing in Java
- Threads in Java
- Handout:
- Due:
Break runs from 5:00 p.m. on Friday, March 17, 1998 to
8:00 a.m. on Monday, April 3.
Class 33
(Monday, April 3, 2000)
Discussion of Exam 2
- Summary of exam results
- Discussion of
- Handouts:
- Answer key to exam 2
- Java Plus Data Structures, Chapter 9: Dictionaries
Class 34
(Tuesday, April 4, 2000)
Linked Lists
Class 35
(Wednesday, April 5, 2000)
Adding Elements to Linked Lists
- Linked list implementation, revisited
- Special cases for adding elements
- Different positions for adding elements
Class 36
(Friday, April 7, 2000)
Linked Lists, Concluded
- Linked list structure revisted
- Length
- Deletion
Class 37
(Monday, April 10, 2000)
Introduction to Linear Structures
- Linear Structures
- Three types of linear structures
- Stacks
- Queues
- Priority queues
Class 38
(Tuesday, April 11, 2000)
Implementing Stacks and Queues
- Implementing stacks and queues
- Lab: Working with implementations
Class 39
(Wednesday, April 12, 2000)
Priority Queues, Heaps, and Heap Sort
- A ``divide and conquer'' implementation of priority queues
- Heaps: balanced implementations of priority queues
- Heapsort: Sorting using heaps
Class 40
(Friday, April 14, 2000)
Automated Problem Solving with Linear Structures
- Modeling puzzles
- Modeling the solution space as a tree
- An algorithm for solving puzzles
- Using stacks
- Using queues
Class 41
(Monday, April 17, 2000)
Dictionaries
Class 42
(Tuesday, April 18, 2000)
Binary Search Trees
- Dictionary ADT, revisited
- A simple implementation: Association lists
- An advanced implementation: Binary search trees
Class 43
(Wednesday, April 19, 2000)
Hash Tables
- The elusive goal: O(1) lookup and retrieval
- Using objects as numeric indices
- Hash tables
- Java's
java.util.Hashtable class
Class 44
(Friday, April 21, 2000)
Project Discussion
- Designing hash functions
- Handling conflicts in hashing
- Supporting deletion in hash tables
Class 45
(Monday, April 24, 2000)
Introduction to Trees
- Heaps and search trees, revisited
- Representing arithmetic expressions
- Generalizing: a binary tree ADT
- Generalizing further: a tree ADT
Class 46
(Tuesday, April 25, 2000)
Implementing Trees
- Tree ADT, continued
- Implementation techniques
- Arrays
- Nodes
- Parent/child lists.
Class 47
(Wednesday, April 26, 2000)
Lab: Traversing and Iterating Trees
- Generalizing the puzzle solution: How d you iterate, visit, or list
the elements of a tree?
- Preorder vs. postorder
- Depth-first vs. breadth-first
- Special Lab: Travering trees
Class 48
(Friday, April 28, 2000)
Integration Discussion
- Implementation details
- Handouts:
- Exam 3 (due Friday, May 5, 2000)
- Due:
- Project, Phase 7: Final implementations
Class 49
(Monday, May 1, 2000)
Project Discussion: Preparation for Presentation
- We will give a public presentation of the project at lunch time.
Class time will be devoted to preparation for that presentation.
I'll pay for pizza and pop.
- Due:
- Project, Phase 6: Descriptive handouts
Class 50
(Tuesday, May 2, 2000)
Reflection on Project
- Modeling and pictures
- Sample modeling problems
- Introduction to graphs
- A structure for modeling some common problems
- Terminology
- Methods
- Common implementations
Class 51
(Wednesday, May 3, 2000)
Introduction Graphs
- Common graph problems
- The traveling salescritter problem
- Reachabliity: Can you get there from here?
Class 52
(Friday, May 5, 2000)
The Shortest Path Problem
- Shortest path: How fast can you get there from here?
- A brute-force shortest-path algorithm
- Dijkstra's algorithm
- Design issues in graph problems
- Minimum spanning tree
- Handouts:
- Due:
Attendance is particularly important this week.
Class 53
(Monday, May 8, 2000)
Graphs, Concluded
- Summary of results of exam 3
- Special problems
- Comments on projects
Class 54
(Tuesday, May 9, 2000)
What is Computer Science? Revisited
- Course topics, Revisited
- Object-Oriented Programming and Program Design
- Algorithms: Analysis, Common, Design
- Data Structures: Design issues, Common
- Java Programming
- Time for official course evaluation
Class 55
(Wednesday, May 10, 2000)
Course Summary and Evaluation
- An overview of CS
- Three threads: Mathematics, Science, Engineering
- Many subtreads
- Topics/courses available at Grinnell
- Due:
- Homework 8: Project Questions
Class 56
(Friday, May 12, 2000)
An Abbreviated History of Computer Science
- Some definitions: Computing, Electronic Computing, Binary vs. Analog,
Networking, Computer Science
- A timeline
- The impact of computing
- Other implications
- Due:
- Course development questionaire
You may turn in the take-home final any time during finals week.
The history will not include small changes to the summaries of
individual classes. You can find more information on such changes
in the individual outlines.
Monday, January 4, 2000
Tuesday, January 18, 2000
- Filled in the details for the first half of the semester.
Wednesday, January 19, 2000
- Updated some notes in the first half.
- Added the second half of the semester.