This is an abbreviated course syllabus.
Like everything else in this course, it is likely to change.
| Week 1: Course Basics
|
(01) Monday, January 23, 2006
About the Course
About the course.
Grounding ourselves.
Some basic administrative issues.
Assignments:
Homework 1: Rational Numbers.
|
(02) Tuesday, January 24, 2006
An Introduction to Object-Oriented Programming
Object-Oriented Problem Solving.
Exercise: Rational Numbers.
ADTs and Data Structures.
Due:
Homework 1: Rational Numbers.
Assignments:
Do Homework 2: Course Basics.
Read Espresso: An Introduction to Unix in MathLAN.
Read Espresso: Object-Oriented Problem Solving.
|
(03) Wednesday, January 25, 2006
An Introduction to Unix
Lab
Assignments:
Read Espresso: An Introduction to Java.
Read Espresso: Java Packages.
Read Espresso: Java Programming in Eclipse (not available until Thursday).
Due:
Homework 2: Course stuff.
|
(04) Friday, January 27, 2006
An Introduction to Java (1)
Questions on Unix.
Java basics.
Detours: Packages and Projects.
Your first Java program.
Running programs.
Assignments:
Reread Espresso: An Introduction to Java.
|
| Week 2: Java Basics
|
(05) Monday, January 30, 2006
An Introduction to Java (2)
Review readings.
Lab.
Assignments:
Read Basic Input and Output in Java.
|
(06) Tuesday, January 31, 2006
Input and Output in Java
Lab.
Assignments:
Read Espresso: Strings in Java.
Do Short homework 3: Mad Libs.
|
(07) Wednesday, February 1, 2006
Strings in Java
Brief introduction to strings
Q & A
Lab
Assignments:
Read Espresso: Numeric Values in Java.
Do Homework 4: Mad Libs, Revisited.
|
(08) Friday, February 3, 2006
Strings in Java, Continued
Questions
Lab
Reflection
Assignments:
Read Espresso: Numeric Values in Java.
Do Homework 4: Mad Libs, Revisited.
|
| Week 3: Values and Control
|
(09) Monday, February 6, 2006
Numeric Values in Java
String wrapup.
Lab.
Assignments:
Read Espresso: Binary Representation of Integers.
|
(10) Tuesday, February 7, 2006
Binary Representation of Integers
Remaining issues from numbers.
Basics of binary representation.
Lab.
Read Espresso: Conditionals in Java (available this afternoon).
Finish any labs you have not yet finished.
|
(11) Wednesday, February 8, 2006
Conditionals
Basic conditionals: the if statement.
Boolean expressions in Java.
Lab.
Assignments:
Read Espresso: Conditionals in Java (available Thursday).
Read Espresso: Static Methods (available Thursday).
Do Homework 5: A One-Line Calculator.
|
(12) Friday, February 10, 2006
Static Methods
Quick overview.
Lab.
Assignments:
Read Loops in Java.
Do Homework 6: Square Roots.
|
| Week 4: Control, Continued
|
(13) Monday, February 13, 2006
Pause for Breath
Sample square root code.
Miscellaneous issues.
Assignments:
If you have not yet read Espresso: Loops in Java, please do so.
Homework 7: Introduction to Approximate String Matching.
|
(14) Tuesday, February 14, 2006
Loops
Form of loops.
Lab.
Assignments:
Read Espresso: When Things Go Wrong: Exceptions in Java.
|
(15) Wednesday, February 15, 2006
Exceptions
Techniques for Handling Errors.
Exceptions: Java's Primary Error-Handling Technique.
Lab.
Assignments:
Do Homework 8: TBD.
|
(16) Friday, February 17, 2006
Documentation
Why document?
Where to document.
Preconditions and Postconditions.
Assignments:
Homework 9: Reading Integers.
Read Espresso: Static Fields and Constants.
Read Espresso: Documentating Programs with Javadoc.
|
| Week 5: Miscellaneous Java
|
(17) Monday, February 20, 2006
Javadoc
Javadoc basics.
Lab.
|
(18) Tuesday, February 21, 2006
Object Basics (1)
What is a class?
The three components of classes: fields, methods, and constructors.
An example: Fractions.
Assignments:
Read Espresso: Designing Your Own Classes (ready this afternoon).
|
(19) Wednesday, February 22, 2006
Object Basics (2)
Lab on Writing Your Own Classes.
Assignments:
Homework 10: Simplifying Fractions.
|
(20) Friday, February 24, 2006
Making Sandwiches
The problem: Instructions for making PB&J sandwiches.
Preliminary solutions.
Revising solutions.
Lessons.
Assignments:
Exam 1: Java Basics.
Read Espresso: Standard Object Methods.
|
| Week 6: Object-Oriented Design Issues, Revisited
|
(21) Monday, February 27, 2006
Standard Object Methods
Why have standard methods?
Lab.
Assignments:
Read Espresso: Separating What From How: Interfaces in Java.
|
(22) Tuesday, February 28, 2006
Interfaces
Background.
Lab.
Assignments:
Read Espresso: Reusing and Generalizing Code, Part 1: Polymorphism in Java.
|
(23) Wednesday, March 1, 2006
Polymorphism
About inheritance.
Lab.
Assignments:
Read Espresso: Reusing and Generalizing Code, Part Two: Building New Classes from Old with Inheritance (available Thursday).
|
(24) Friday, March 3, 2006
Reuse through Inheritance
Lab.
Assignments:
Read Espresso: Parameterized Interfaces and Classes (ready Sunday).
|
| Week 7: Linear Structures (I)
|
(25) Monday, March 6, 2006
Generics: Parameterized Types
A problem: Swapping.
A solution.
Improving the solution.
Generics: Improving the new solution.
Comparisons.
Due:
Exam 1.
Assignments:
Read Espresso: Arrays and Vectors in Java (ready this afternoon).
|
(26) Tuesday, March 7, 2006
Arrays and Vectors
Introduction to Arrays and Vectors.
Lab.
Assignments:
Do Homework 11: Exploring Vectors.
Read The TAO of Java: Linear Structures.
Read The TAO of Java: Stacks.
|
(27) Wednesday, March 8, 2006
Stacks and Their Implementation
ADTs.
The Stack ADT.
Implementing stacks.
Lab.
Assignments:
Read The TAO of Java: Queues.
Do Homework 12: Matching Parentheses.
|
(28) Friday, March 10, 2006
Queues and Their Implementation
Review of homework.
Queues, revisited.
Problems with the array-based implementation.
Implementing queues with nodes.
Priority queues.
|
| Week 8: Linear Structures (II)
|
(29) Monday, March 13, 2006
Class Cancelled
|
(30) Tuesday, March 14, 2006
Discussion of Exam 1
General notes.
String edits.
Creating fractions.
Comparing points.
Piggybanks.
Assignments:
Homework 13: Implementing Priority Queues.
|
(31) Wednesday, March 15, 2006
Priority Queues
Philosopy of Priority Queues.
Aplications of Priority Queues.
Methods for Priority Queues.
Implementing Priority Queues.
Assignments:
Read The TAO of Java: Heaps (ready Thursday).
|
(32) Friday, March 17, 2006
Heaps and Heap Sort
Review: Priority Queues.
Trees.
Tree Terminology.
Heaps.
Implementing Heaps.
|
| Spring Break
|
| Week 9: Algorithm Analysis
|
(33) Monday, April 3, 2006
Algorithm Analysis (1)
An Example: Exponentiation.
Comparing Algorithms.
Asymptotic Analysis.
Assignments:
The TAO of Java: Algorithm Analysis (ready this evening).
|
(34) Tuesday, April 4, 2006
Algorithm Analysis (2)
Asymptotic Analysis.
Asymptotic Analysis in Practice.
Supporting Asymptotic Analysis with Experiments.
Eliminating Constants.
Relating Functions.
|
(35) Wednesday, April 5, 2006
Algorithm Analysis (3)
Review.
Lab.
|
(36) Friday, April 7, 2006
Dynamic Programming (1)
Multiply-recursive algorithms.
The Fibonacci Numbers.
Improving computation with dynamic programming.
Another example: Efficient computation of prices.
Assignments:
Exam 2
|
| Week 10: Dictionaries
|
(37) Monday, April 10, 2006
Dictionaries (1): Implementing Dictionaries with Vectors
Introduction to dictionaries.
Lab.
|
(38) Tuesday, April 11, 2006
Dictionaries (2): Binary Search Trees
Binary search trees.
BSTs and dictionaries.
|
(39) Wednesday, April 12, 2006
Dictionaries (3): Binary Search Trees, Revisited
Balanced Trees.
Terminology.
BSTs and Dictionaries.
Removing Values.
Lab.
|
(40) Friday, April 14, 2006
Dictionaries (4): Hash Tables
The Idea of Hashing.
Hash Functions.
Hashing in Java.
Handling Hashing Conflicts.
Due:
Exam 2.
|
| Week 11: Lists
|
(41) Monday, April 17, 2006
List ADTs
What else is a list?
Two ways to iterate lists: Cursors and Positions
Three kinds of lists: Simple, Ordered, and Sorted
Assignments:
HW14: Text Analysis (due Wednesday).
|
(42) Tuesday, April 18, 2006
Implementing Lists with Arrays
Adding Preconditions and Postconditions.
Testing.
The Vector-Based Implementation.
Validating Positions.
|
(43) Wednesday, April 19, 2006
Linked Lists
Implementing lists with nodes.
Assignments:
Homework 15: Sorted Lists.
|
(44) Friday, April 21, 2006
Dynamic Programming, Revisited: Minimizing Coins
Reminder: Dynamic Programming.
Simple Example: Coin Minimization.
Detour: Returning Better Info.
Assignments:
Redo HW 15.
|
| Week 12: Sorting
|
(45) Monday, April 24, 2006
Approximate String Matching
Coin Minimization. Revisited.
String Matching and String Alignment.
Dynamic Programming with 2D Arrays.
Bottom-up vs. Top-down Dynamic Programming.
|
(46) Tuesday, April 25, 2006
An Introduction to Sorting
The Problem of Sorting.
Carefully Specifying Sorting Methods.
Testing Sorting Methods.
Assignments:
Homework 16: Approximate String Matching.
|
(47) Wednesday, April 26, 2006
Pause for Breath
Assignments:
Homework 17: Sorting.
|
(48) Friday, April 28, 2006
Quadratic Sorts
Review.
Bubble sort, and why not to use it.
Selection sort.
Insertion sort.
Assignments:
Exam 3 distributed (due a week from Monday).
|
| Week 13: Graphs
|
(49) Monday, May 1, 2006
Faster Sorts
Review.
Divide-and-Conquer Sorting.
Merge Sort.
Iterative Merge Sort.
Asymptotic Analysis of Merge Sort.
Quicksort.
|
(50) Tuesday, May 2, 2006
Discussion of Exam 2
Problem 1: Graphs.
Problem 2: Random Linear Structures.
Problem 3: Dynamic Arrays.
Problem 4: Heapsort.
|
(51) Wednesday, May 3, 2006
Graphs
Introduction: Modeling in CS.
One Modeling ADT: The Graph.
Some Graph Problems.
A Graph ADT.
Solving the Reachability Problem.
Coding the Solution.
|
(52) Friday, May 5, 2006
Shortest Path
Some Definitions (Path, The Problem).
A Simplified Version: Shortest Paths in Unweighted Graphs.
An Example.
The Solution.
Extracting the Path.
Weighted Graphs: Dijkstra's Algorithm.
Asymptotic Analysis.
|
| Week 14: Wrapup
|
(53) Monday, May 8, 2006
Pause for Breath
Shortest Path, Revisited: Some Optimizations.
Sorting, concluded: Evaluating Quicksort.
Expressing Graph Algorithms in Code: Reachability.
Expressing Graph Algorithms in Code: Shortest Path.
Due:
Exam 3.
|
(54) Tuesday, May 9, 2006
Scheme, Revisited
Some list procedures.
Some numeric procedures.
Other issues.
Solutions.
|
(55) Wednesday, May 10, 2006
Discussion of Exam 3
Grading.
Final.
Problem 1: Removing from Binary Search Trees.
Problem 2: Text Analysis.
Problem 3: Median.
Problem 4: Genetic Matching.
|
(56) Friday, May 12, 2006
Evaluation and Wrapup
The subject matter of the course.
Evaluations.
Final statements.
|
;
Check with Bobby