This is an abbreviated course syllabus.
Like everything else in this course, it is likely to change.
| Week 1: Course Basics
|
|
|
|
(01) Friday, 26 August 2005
About the Course
About the course.
Some basic administrative issues.
An introduction to data structures and algorithms.
|
(02) Monday, 29 August 2005
An Introduction to Object-Oriented Programming
Grounding Ourselves
Object-Oriented Programming
Exercise: Rational Numbers
Assignments:
Read An Introduction to Unix in Espresso.
|
(03) Tuesday, 30 August 2005
An Introduction to Unix
Questions and answers
Lab
Assignments:
Read
An Introduction to Java,
Java Packages, and
Java in the MathLAN in
Espresso.
|
(04) Wednesday, 31 August 2005
An Introduction to Java (1)
Java basics.
Questions on the readings.
Lab.
Assignments:
Reread
An Introduction to Java,
Java Packages, and
Java in the MathLAN in
Espresso.
|
(05) Friday, 2 September 2005
An Introduction to Java (2)
Q and A.
Lab.
Assignments:
Read Textual Input and Output in Java in Espresso.
|
| Week 2: Designing Objects
|
(06) Monday, 5 September 2005
Input and Output in Java (1)
Questions.
Lab.
|
(07) Tuesday, 6 September 2005
Input and Output in Java (2)
Assignments:
Read Strings in Java in Espresso.
|
(08) Wednesday, 7 September 2005
Strings in Java (1)
Brief introduction to strings
Q & A
Lab
Assignments:
Read Numbers in Java.
Begin Homework 1: Simplified Mad Libs (due Wednesday, 14 September 2005).
|
(09) Friday, 9 September 2005
Strings in Java (2)
Questions
Lab
Reflection
|
| Week 3: Object Fundamentals
|
(10) Monday, 12 September 2005
Numeric Values in Java
Number basics.
Lab.
|
(11) Tuesday, 13 September 2005
Representing Numbers in Java
Key points from numbers lab.
Representing integers.
|
(12) Wednesday, 14 September 2005
Object Basics (1)
What is a class?
The three components of classes: fields, methods, and constructors.
Designing classes.
Building classes in Java.
|
(13) Friday, 16 September 2005
Object Basics (2)
Writing methods.
Kinds of classes.
Standard methods.
Class fields and methods.
Assignments:
Read Conditional Evaluation in Java in Espresso.
Begin homework 2: Basics of class design.
|
| Week 4: Control
|
(14) Monday, 19 September 2005
Conditionals (1)
Classes concluded.
Boolean expressions in Java.
Basic conditionals: the if statement.
Recursive methods.
|
(15) Tuesday, 20 September 2005
Conditionals (2)
Review
Standard comparison methods
Lab
Assignments:
Read When Things Go Wrong: Exceptions in Java in Espresso.
|
(16) Wednesday, 21 September 2005
Exceptions (1)
Exceptions: Java's Primary Error-Handling Technique.
Lab.
Assignments:
Reread When Things Go Wrong: Exceptions in Java in Espresso.
Due:
Homework 2.
|
(17) Friday, 23 September 2005
Exceptions (2)
Exceptions lab.
Assignments:
Read Loops in Java in Espresso.
Begin Exam 1: Java Basics. Bring questions on Monday.
|
| Week 5: Object-Oriented Design Issues, Revisited
|
(18) Monday, 26 September 2005
Loops
Review.
Lab.
Assignments:
Read Separating What from How: Interfaces in Java in Espresso.
|
(19) Tuesday, 27 September 2005
Interfaces
Review of reading.
Lab.
Assignments:
Read Reusing and Generalizing Code, Strategy One: Polymorphism in Java in Espresso.
Prepare any final questions you have on the exam.
|
(20) Wednesday, 28 September 2005
Polymorphism
Q&A.
Lab.
|
(21) Friday, 30 September 2005
Pause for Breath
Pause for review.
Review of polymorphism.
Polymorphic I/O.
Lab.
Assignments:
Homework 3: Composing Text.
Due:
Exam 1: Java Basics.
|
| Week 6: Review
|
(22) Monday, 3 October 2005
Discussion of Exam 1 / Review of Java Basics
General notes
Java basics
Class basics
|
(23) Tuesday, 4 October 2005
Review of Class Basics
|
(24) Wednesday, 5 October 2005
Review of Static Fields and Methods
Static fields.
Static methods.
Continuing example.
|
(25) Friday, 7 October 2005
Review of Control Structures
Motivating Example: Parsing Integers.
Conditionals.
Loops.
Exceptions.
|
| Week 7: Miscellaneous
|
(26) Monday, 10 October 2005
Review of Exceptions
Review: The problem at hand.
Throwing, catching, and passing exceptions.
Writing your own exceptions.
|
(27) Tuesday, 11 October 2005
A Motivationg Problem: Exponentiation
The problem.
A recursive solution.
An iterative solution.
A better recursive solution and its analysis.
Generalizing the solution.
|
(28) Wednesday, 12 October 2005
Review of Polymorphism
Generalizing the exponentiation problem.
Steps in using polymorphism.
Example, continued.
|
(29) Friday, 14 October 2005
Parameterized Classes
Exponentiation.
Generalizing.
Parameterized classes.
Another example: Comparison.
|
| Fall Break
|
| Week 8: Arrays and Vectors
|
(30) Monday, 24 October 2005
Arrays
Introduction to Arrays.
Arrays in Java.
An Application: Fibonacci Numbers.
An Application: Box Packing.
Assignments:
Daily assignment posted at the end of class (on the eboard).
|
(31) Tuesday, 25 October 2005
Vectors (1)
Vector philosophy.
Vector methods.
Using Vectors for Fibonacci.
Lab.
|
(32) Wednesday, 26 October 2005
Vectors (2)
Vectors, concluded.
|
(33) Friday, 28 October 2005
Algorithm Analysis (1)
Comparing algorithms.
Difficulties.
Informal analysis.
Experimental analysis.
|
| Week 9: Algorithm Analysis
|
(34) Monday, 31 October 2005
Algorithm Analysis (2)
Formalizing notions.
Eliminating constants.
Using the notation: Relating functions.
Analyzing recursive functions.
Assignments:
Do the lab on algorithm analysis in The TAO of Java.
|
(35) Tuesday, 1 November 2005
Algorithm Analysis (3)
Review.
Detour: Deletion, Revisited.
About the Lab.
|
(36) Wednesday, 2 November 2005
Algorithm Analysis (4)
Analyzing search methods.
Recurrence relations, revisited.
|
(37) Friday, 4 November 2005
Detour: Reuse through Inheritance
Polymorphism.
Reuse.
Inheritance.
Inheritance in Java.
Special issue: Constructors.
Example.
Inheritance and interfaces.
Assignments:
Exam 2 distributed.
|
| Week 10: Linear Structures
|
(38) Monday, 7 November 2005
Linear Structures
Collections.
Linear Structures.
Randomimzed Linear Structures.
|
(39) Tuesday, 8 November 2005
Pause for Breath
|
(40) Wednesday, 9 November 2005
Stacks and Their Implementation
The Stack ADT.
Implementing stacks.
|
(41) Friday, 11 November 2005
Queues and Their Implementation
Queues basics.
An array-based implementation.
Implementing queues with nodes.
Priority queues.
Due:
Exam 2: Objects, Structures, and Algorithms
|
| Week 11: Linear Structures, Concluded
|
(42) Monday, 14 November 2005
Priority Queues
Priority queue basics.
Applying priority queues.
Implementing priorty queues.
|
(43) Tuesday, 15 November 2005
Discussion of Exam 2
Problem 1: Dynamic Arrays
Problem 2: Making Change
Problem 3: An Interface
Problem 4: Searching
|
(44) Wednesday, 16 November 2005
Heaps and Heap Sort
Implementations of Priority Queues.
Trees.
Tree Terminology.
Heaps.
Implementing Heaps.
|
(45) Friday, 18 November 2005
Dictionaries (1): The Dictionary ADT
Introduction to dictionaries
Applications of dictionaries
A Dictionary ADT
Comparing dictionaries and databases
Implementing dictionaries with arrays
|
| Week 12: Dictionaries
|
(46) Monday, 21 November 2005
Dictionaries (2): Binary Search Trees
Binary search trees.
BSTs and dictionaries.
Lab.
Reflection.
|
(47) Tuesday, 22 November 2005
Dictionaries (3): Hash Tables
The Idea of Hashing.
Hash Functions.
Hashing in Java.
Handling Hashing Conflicts.
|
(48) Wednesday, 23 November 2005
Implementing Lists with Arrays
List Basics.
List ADTs.
Implementing Lists with Vectors.
Assignments:
Exam 3 distributed.
|
Thanksgiving Break
|
| Week 13: From Lists to Sorting
|
(49) Monday, 28 November 2005
Linked Lists
The design of lists, revisited.
A vector-based implementation.
A linked implementation.
Doubly-linked lists.
Circularly-linked lists.
|
(50) Tuesday, 29 November 2005
Lists Lab
Questions on list issues.
Lab on vector-based lists in The TAO of Java.
Lab on doubly-linked lists in The TAO of Java.
|
(51) Wednesday, 30 November 2005
An Introduction to Sorting
The problem of sorting.
Carefully specifying that problem.
Testing a sorting method.
|
(52) Friday, 2 December 2005
Quadratic Sorts
Bubble sort, and why not to use it.
Selection sort.
Insertion sort.
Comparing these algorithms.
Due:
Exam 3: Data Types and Data Structures
|
| Week 14: Wrapup
|
(53) Monday, 5 December 2005
Pause for Breath
|
(54) Tuesday, 6 December 2005
Faster Sorts
Review
Divide and conquer sorting
Merge sort
Iterative merge sort
Asymptotic analysis of merge sort
Quicksort
Asymptotic analysis of Quicksort
|
(55) Wednesday, 7 December 2005
Discussion of Exam 3
Problem 1: Removing elements from Linear-Probe Hash Table
Problem 2: Dynamic Arrays
Problem 3: Testing Sorting Routines
Problem 4: Stable Sorting
|
(56) Friday, 9 December 2005
Evaluation and Wrapup
Evaluations
The subject matter of the course
Final statements
|
;
Check with Bobby