Daily class schedule

Principles of Computer Science
Spring, 2005

2/7  Data structures, algorithms, and abstractions.

2/9   Review of object-oriented programming in Java.  Inheritance, abstract classes, and interfaces.

2/11   Interfaces.  Comparable.  List.  Iterator.

2/14   An array implementation of the List interface.

2/16   Array implementation of the List interface, continued.

2/18  Linked lists.  Begin linked list implementation.

2/21  Finish linked list implementation.  An Iterator for a linked list.

2/23  Recursive linked lists.

2/25  No class (SIGCSE).

2/28  Doubly-linked lists. Sorted lists.

3/2   More on recursion.

3/4   Introduction to Algorithm Analysis.   

3/7   Asymptotic analysis.  Big-oh notation.

3/9   More on asymptotic analysis.  Analysis of binary search, selection sort.

Review for exam 1

3/11  Exam 1.

3/14  Stacks and queues.  

3/16   Deques and priority queues.

3/18   Infix, postfix, and prefix notation for arithmetic expressions.

3/21   Algorithms for processing arithmetic expressions.

3/23   Solutions to the maximum segment sum problem.  Collections.

3/25   Implementing the addAll method for sorted lists.  The Map interface. (chapter 17).

3/26-4/3  Spring break

4/4   Map applications and implementations. (chapter 18).

4/6   Object-oriented design and analysis.

4/8   UML diagrams.  Design patterns.

4/11   Trees.  Basic terminology.  Binary trees.  Tree traversals.  Expression trees.  (chapter 24)

4/13  Implementing binary trees.  Implementing nonbinary trees.  Tree iterators.  (chapter 25)

4/15   Cloning a binary tree.  Binary search trees  (chapter 24.27-24.30, 26)

4/18   Binary search trees as Maps.  Balanced binary search trees.  AVL trees. (28.1-28.11).  Red-black trees.  (28.30-28.37)

4/20   Tries. (not covered in Carrano)

4/25   Exam 2.

4/27   GUI Design.  Layout managers.

5/2   Collision handling.  Open addressing.  Linear probing.  Double hashing.   (19.11-19.19).

5/4   Hash tables with chaining.  Hash table performance.  (19.20-19.39)

5/6   Sorting.  Simple sorting methods:  bubble sort, insertion sort, selection sort.  (chapter 11).  Merge sort. (12.1-12.8).

5/9   Heaps.  Heapsort.  Priority queues. (chapter 27)

5/11   Quicksort. (12.9-12.18).  Radix sort. (12.19-12.22)

5/13  Review for final exam.

5/18  Final exam   (7-9 pm)