Fund. CS II (CS152 2005F)

CS152 2005F 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: 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
Review. Lab.
Assignments: Read Separating What from How: Interfaces in Java in Espresso.
(19) Tuesday, 27 September 2005
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
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
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

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 Dec 6 09:46:57 2005.
The source to the document was last modified on Thu Aug 25 16:34:46 2005.
This document may be found at

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

Samuel A. Rebelsky,