Algorithms and OOD (CSC 207 2014F) : Handouts


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