Schedule

This is an approximate schedule. Expect topics and dates of topics to change. (I will try to keep due dates of assignments the same.)

Week 01: Getting Started
	Date	Topic	Reading	Lab	Work Due
01	Friday, 29 August 2014	An Introduction to the Course About the course. A few notes on academic honesty. ADTs and data structures. An exercise: Designing a stack ADT.
02	Monday, 1 September 2014	An Introduction to ADT Design Thinking about problem solving ADT Design Exercise 1: Stacks Implementation Example: Stacks ADT Design Exercise 2: Dynamic Arrays	Designing Abstract Data Types and Designing Data Structures		HW 1: Course Details and RISC Survey and HW 2: Exploring an Expandable Array ADT (due 10:30 p.m. Sunday)
03	Tuesday, 2 September 2014	An Introduction to Java Development Tools for software development. Eclipse. Git.	An Introduction to Version Control with Git and The Eclipse IDE	Getting Started with Eclipse and Getting Started with Command-Line Git
04	Wednesday, 3 September 2014	An Overview of Java Some notes on Java. Lab: Simple Code Reading (more or less). Reflection.	Basics of Object-Oriented Problem Solving, An Introduction to Java, Simple Java for C Programmers	Reading Java
05	Friday, 5 September 2014	Unit Testing A few thoughts on testing. An example: Testing exponentiation. A few notes on test-driven development.	Unit Testing	Unit Testing
Week 02: Imperative Programming in Java
	Date	Topic	Reading	Lab	Work Due
06	Monday, 8 September 2014	Classes and Objects A brief introduction to objects. An exercise: Counters.	Writing Your Own Classes, Standard Object Methods	Writing Your Own Classes
07	Tuesday, 9 September 2014	Classes and Objects, Revisited Thinking in Objects. Naming Conventions. Additional Issues.	Writing Your Own Classes, Standard Object Methods	Writing Your Own Classes	HW 3: Getting started with Java, Testing, and Objects (due 10:30 p.m.)
08	Wednesday, 10 September 2014	Arrays in Java ADT Design. Minimalist vs. maximalist design. Arrays. Vectors.	Arrays	Arrays
09	Friday, 12 September 2014	Some Basic Types: Numbers and Strings in Java Numbers. Boxing and unboxing. Strings.	Numeric Values in Java, Strings in Java, and Input and Output in Java	Basic Types and Input and Output
Week 03: More Java Topics
	Date	Topic	Reading	Lab	Work Due
10	Monday, 15 September 2014	Pause for Breath Notes on recent ideas. Questions on the homework. Writing an equality test. Other issues.
11	Tuesday, 16 September 2014	Some Subtleties: References and Automatic Boxing/Unboxing Reference values vs. primitive values. Some typical misunderstandings. Primitive types and their corresponding classes. Automatic boxing and unboxing.	Reference Values in Java, Automatic Boxing and Unboxing in Java	Reference Values and Automatic Boxing and Unboxing	HW 4: Playful Parsing in Java (due 10:30 p.m.)
12	Wednesday, 17 September 2014	Debugging Why use debuggers? Debuggers vs. print statements. Text or graphical UI? Debugging in Eclipse.	Debugging in Eclipse	Debugging in Eclipse
13	Friday, 19 September 2014	Exceptional Programming Dealing with errors. Java's Exceptions. Writing your own Exceptions.	Exceptions	Exceptions
Week 04: Object Oriented Programming and Design in Java
	Date	Topic	Reading	Lab	Work Due
14	Monday, 22 September 2014	Interfaces and Polymorphism Interfaces. Polymorphism. An example: Text blocks.	Interfaces and Polymorphism	Polymorphism
15	Tuesday, 23 September 2014	Inheritance Inheritance basics. Inheritance and polymorphism.	Inheritance	Inheritance	HW 5: Numeric Computation (due 10:30 p.m.)
16	Wednesday, 24 September 2014	Inheritance, Continued Q and A. Reflection - What are benefits and issues of inheritance and polymorphism? Additional topic: Javadoc.	Inheritance and Documentation and Javadoc	Inheritance and Javadoc
17	Friday, 26 September 2014	Pause for Breath Inheritance and Polymorphism. Run-time vs. compile-time decisions.
Week 05: Miscellaneous Java Features
	Date	Topic	Reading	Lab	Work Due
18	Monday, 29 September 2014	OOD Design: An API for Ushahidi Modeling Ushahidi. Support for tests and experiments. Other design issues.	An API for Ushahidi	An API for Ushahidi
19	Tuesday, 30 September 2014	Java Generics Homogenous vs. heterogenous collections. Writing general code with type variables. Java's generics. Generic classes, interfaces, and methods. Handling multiple types.	Java Generics	Java Generics	HW 6: Explorations in Object-Oriented Design (due 10:30 p.m.)
20	Wednesday, 1 October 2014	Anonymous Functions Anonymous Functions Anonymous Functions in Java More About Functional Interfaces Useful Functional Interfaces	Java Tutorials: Lambda Expressions	Anonymous Functions
21	Friday, 3 October 2014	Anonymous Inner Classes Anonymous inner classes - the concept. Anonymous inner classes - the implementation. Anonymous inner classes vs. anonymous functions. Some subtleties.	Anonymous Inner Classes, Java Tutorial/Inner Classes, Java Tutorial/Local Clases, and Java Tutorial/Anonymous Classes	Anonymous Inner Classes
Week 06: Analyzing Algorithms
	Date	Topic	Reading	Lab	Work Due
22	Monday, 6 October 2014	Analyzing Algorithms Comparing algorithms. Potential problems in computing running time. Asymptotic analysis. Big-O, formalized. Implications of Big-O. Doing informal asymptotic analysis. Some recurrence relations. Experimental analysis.	Analyzing Algorithms
23	Tuesday, 7 October 2014	Linear and Binary Search Linear search. Binary search. Analyzing binary search. Testing binary search.	Linear and Binary Search in Java	Linear and Binary Search in Java	HW 7: Miscellaneous (due 10:30 p.m.)
24	Wednesday, 8 October 2014	Reasoning About Loops with Loop Invariants Writing correct iterative algorithms. The state of a program. Loop invariants. Loop termination. An exercise: Binary search.	Loop Invariants	Loop Invariants
25	Friday, 10 October 2014	Using Java from the Command Line A brief overview of basic commands. Ant and Maven. Lab.	Java on the Command Line (forthcoming)	Java on the Command Line
Week 07: Sorting
	Date	Topic	Reading	Lab	Work Due
26	Monday, 13 October 2014	An Introduction to Sorting The problem of sorting. An object-oriented approach. Testing our sorting algorithm.
27	Tuesday, 14 October 2014	Quadratic Sorts Our sorting package. Testing sorts. Insertion sort. Selection sort.	Sorting Basics	Quadratic Sorts
28	Wednesday, 15 October 2014	Merge Sort Lower bounds on sorting. Divide and conquer algorithms. An introduction to merge sort. Analyzing merge sort.	Merge sort	Merge sort
29	Friday, 17 October 2014	Quicksort A quick introduction to Quicksort. Key ideas from Quicksort.	Quicksort	Quicksort	Exam 1 (due 10:30 p.m. Thursday)
Fall Break
Week 08: Implementing Lists
	Date	Topic	Reading	Lab	Work Due
30	Monday, 27 October 2014	OOD in Practice: Designing a List Interface The design of ADTs, revisited. Exercise: Designing a list ADT. Quick notes on implementation.
31	Tuesday, 28 October 2014	Implementing Lists with Arrays Status of our List Interface. Implementing Lists with Arrays - The Basics. Implementing Lists with Arrays - Some Complications.	Designing A List ADT and Lists with Current Considered Harmful	Implementing Lists with Arrays
32	Wednesday, 29 October 2014	Pause for Breath
33	Friday, 31 October 2014	Linked Lists in Java Linked lists. Implementation details.		Linked Lists
Week 09: Linear Structures
	Date	Topic	Reading	Lab	Work Due
34	Monday, 3 November 2014	Linked Lists, Continued Review of singly-linked lists. Insertion and deletion in singly-linked lists. A trick for simplifying insertion and deletion.
35	Tuesday, 4 November 2014	Pause for Breath
36	Wednesday, 5 November 2014	Doubly-Linked Lists Doubly-linked lists. Circularly-linked lists.			HW 8: Sorting Out Sorting (due 10:30 p.m.)
37	Friday, 7 November 2014	An Introduction to Linear Structures Linear structures. Stacks. An application of stacks: Matching parens.	Linear Structures and Stacks	Stacks
Week 10: Dictionaries and Trees
	Date	Topic	Reading	Lab	Work Due
38	Monday, 10 November 2014	Implementing Queues with Arrays Wrappers, Adapters, Delegation, and such. Design patterns and terminology.	Queues	Array-Based Queues
39	Tuesday, 11 November 2014	Priority Queues and their Basic Implementation Wrappers, adapters, and delagates. Design patterns. A short introduction to priority queues. Array-based implementations. Running times. Sorting with priority queues.	Priority Queues	Priority Queues
40	Wednesday, 12 November 2014	Designing a Dictionary API Review: Designing ADTs and Data Structures. A Dictionary ADT. Simple implementations of dictionaries.			HW 9: Skip Lists (due 10:30 p.m.)
41	Friday, 14 November 2014	Implementing Dictionaries Review: Thinking about data structures. Association lists. Techniques for improving the implementation. Binary search trees.
Week 11: From Dictionaries to Hash Tables
	Date	Topic	Reading	Lab	Work Due
42	Monday, 17 November 2014	Implementing Dictionaries with Arrays or Lists Implementing dictionaries, mark I. Looking ahead: A better implementation.	Association Lists (not available)	Association Lists
43	Tuesday, 18 November 2014	Implementing Dictionaries with Binary Search Trees About binary search trees. Basic analysis.	Binary Search Trees (not available)	Binary Search Trees
44	Wednesday, 19 November 2014	Tree Traversal Orders for traversing the tree. Implementating traversal algorithms.	Tree Traversal	Tree Traversal	Project proposal (due 10:30 p.m.)
45	Friday, 21 November 2014	Implementing Dictionaries with Hash Tables An introduction to hash tables. Hash functions. An exercise. Handling collisions. Hashing in Java. Handling removal.
Week 12: Hash Tables, Concluded
	Date	Topic	Reading	Lab	Work Due
46	Monday, 24 November 2014	Hash Tables, Continued Questions. Lab.	Hash tables	Hash tables
47	Tuesday, 25 November 2014	Pause for Breath General project approaches. Time to work on projects and ask questions.			Project (due 10:30 p.m.)
48	Wednesday, 26 November 2014	Hash Tables, Continued Questions. Lab.	Hash tables	Hash tables
Thanksgiving Break
Week 13: Heaps and Projects
	Date	Topic	Reading	Lab	Work Due
49	Monday, 1 December 2014	Heaps Priority queues, revisited. Recent implementation techniques. Heaps. Adding elements to heaps. Removing elements from heaps. Asymptotic analysis. Storing heaps in arrays. Heap sort.
50	Tuesday, 2 December 2014	Heap Sort Heaps and heap sort, reconsidered.	Heaps and Heap Sort (not available)	Heaps and Heap Sort
51	Wednesday, 3 December 2014	Project Presentations Introduction. Presentations. Assessments.
52	Friday, 5 December 2014	Debrief on Projects and Makeup Exam Debriefing on the project. Debriefing on the makeup exam.
Week 14: Wrapup
	Date	Topic	Reading	Lab	Work Due
53	Monday, 8 December 2014	Dynamic Programming Fibonacci. Generalizing the idea. The stamps problem. Edit distance in strings.
54	Tuesday, 9 December 2014	Patterns of Object and Algorithm Design Algorithm design. ADT design. Data-structure design. Object design. Code design.			Exam 2 (due 10:30 p.m.)
55	Wednesday, 10 December 2014	Course Evaluation The subject matter(s) of the course. Evaluations.
56	Friday, 12 December 2014	Wrapup