Fund. CS II (CS152 2006S)

CS152 2006S 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) 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
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
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
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
Form of loops. Lab.
Assignments: Read Espresso: When Things Go Wrong: Exceptions in Java.
(15) Wednesday, February 15, 2006
Techniques for Handling Errors. Exceptions: Java's Primary Error-Handling Technique. Lab.
Assignments: Do Homework 8: TBD.
(16) Friday, February 17, 2006
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 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
Background. Lab.
Assignments: Read Espresso: Reusing and Generalizing Code, Part 1: Polymorphism in Java.
(23) Wednesday, March 1, 2006
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
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
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.



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]


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 Mon Feb 18 11:45:38 2013.
The source to the document was last modified on Tue Aug 22 14:04:43 2006.
This document may be found at

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

Samuel A. Rebelsky,