Syllabus

This is an approximate syllabus, and is likely to change.

Week One: Introduction and Java Basics

• Class 01: Friday, August 29
  • Introduction to the course
  • About data structures
  • Introduction to object design
  • Reading: Bailey, Sections 1.1-1.3 (read it when it arrives)
  • Scan: Bailey, Chapter 1

• Class 02: Monday, September 1
  • Introduction to Java
    • History
    • Local compilers
    • "Hello world"

• Class 03: Tuesday, September 2
  • Java: Classes and objects
  • Java: Methods

• Class 04: Wednesday, September 3
  • More on Methods

• Class 05: Friday, September 5
  • Java: Constructors and Finalizers

Week Two: More Java

• Class 06: Monday, September 8
  • Java: Documentation
  • Reading: Bailey, Chapter 2
  • Reference: How to write doc comments for javadoc
  • Reference: javadoc - the Java API documentation generator

• Class 07: Tuesday, September 9
  • Java, review

• Class 08: Wednesday, September 10
  • An exercise in object-oriented design

• Class 09: Friday, September 13
  • The exercise, continued

Week Three: Even More Java and Some Data Structures

• Read Bailey, Chapter 1 for the beginning of this week

• Class 10: Monday, September 15
  • Java: Control structures
    • Conditionals

• Class 11: Tuesday, September 16
  • Java: Loops

• Class 12: Wednesday, September 17
  • Newton's Method

• Class 13: Friday, September 19
  • Java: Exceptions
  • We may have prospective students visiting

Week Four: Introduction to Structures

• Class 14: Monday, September 22
  • Review

• Class 15: Tuesday, September 23
  • Program input in Java

• Class 16: Wednesday, September 24
  • The vector, a basic data structure
  • Reading: Bailey, Chapter 3

• Class 17: Friday, September 26

Week Five: Algorithm Analysis

• Class 18: Monday, September 29
  • Introduction to algorithm analysis
  • Reading: Bailey, Chapter 4

• Tuesday, September 30
  • No class: Physics lecture

• Class 19: Wednesday, October 1
  • Recursion

• Class 20: Friday, October 3
  • Recursion, continued

Week Six: Sorting and Lists

• Class 21: Monday, October 6
  • Introduction to sorting
  • Basic sorting methods: selection and insertion sort
  • Reading: Bailey, Sections 5.1-5.3

• Class 22: Tuesday, October 7
  • Merge sort
  • Reading: Bailey, Section 5.4
  • Quick sort
  • Reading: Bailey, Section 5.5

• Class 23: Wednesday, October 8
  • Alternative sorting techniques
  • Sorting, wrapup
  • Reading: Bailey, Sections 5.6-5.8
  • Introduction to lists and sequences
  • Reading: Bailey, Sections 6.1-6.2

• Class 24: Friday, October 10
  • Introduction to singly-linked lists.
  • Reading: Bailey, Section 6.3

Week Seven: Representation

• Class 25: Monday, October 13
  • We may have prospective students visiting
  • Doubly linked lists
  • Reading: Bailey, Sections 6.4
  • Circularly linked lists
  • Reading: Bailey, Section 6.5

• Class 26: Tuesday, October 14
  • Implementing lists with vectors

• Class 27: Wednesday, October 15
  • Lists, concluded

• Class 28: Friday, October 17
  • Midterm exam

• Break from October 18 through October 26

Week Eight: Representation

• Class 29: Monday, October 27
  • Data representation: bits, bytes, words, registers, addresses
  • Representing integers

• Class 30: Tuesday, October 28
  • Representing characters
  • Representing reals
  • Problems with reals
  • Reading: Handout
  • Reading: Article by Plauger

• Class 31: Wednesday, October 29
  • Stacks
  • Reading: Bailey, Section 8.1
  • Queues
  • Reading: Bailey, Section 8.2

• Class 32: Friday, October 31
  • Some review of exceptions (requested in class)
  • Bailey's Iterative Quicksort

Week Nine: Iterators

• Class 33: Monday, November 3
  • Solving puzzles
  • Iterators
  • Reading: Bailey, Chapter 9
  • We may have prospective students visiting

• Class 34: Tuesday, November 4
  • Implementing Iterators

• Class 35: Wednesday, November 5
  • Filters

• Class 36: Friday, November 7
  • Comparable Structures
  • Reading: Bailey, Section 10.1

Week Ten: Trees

• Class 37: Monday, November 10
  • Ordered Structures
  • Reading: Bailey, Sections 10.2-10.3

• Tuesday, November 11
  • No class

• Class 38: Wednesday, November 12
  • Introduction to Trees
  • Reading: Bailey, Sections 11.1-11.3

• Class 39: Friday, November 14
  • Expression trees

Week Eleven: Trees, Continued

• Class 40: Monday, November 17
  • Implementing Trees
  • Reading: Bailey, Section 11.4

• Class 41: Tuesday, November 18
  • Tree-based Iterators

• Class 42: Wednesday, November 19
  • Traversing Trees
  • Reading: Bailey, Section 11.5
  • Implementation, continued

• Class 43: Friday, November 21
  • Implementation, concluded.
  • Trees, concluded.
  • Reading: Bailey, Sections 11.6-11.8
  • Priority Queues
  • Reading: Bailey, Sections 12.1-12.3

Week Twelve: Structures for Information Retrieval

• Class 44: Monday, November 24
  • Heaps and Heap Sort
  • Reading: Bailey, Section 12.4

• Class 45: Tuesday, November 25
  • Dictionaries and Tables
  • Reading: Bailey, Chapter 14
  • Search Trees
  • Reading: Bailey, Chapter 13

• Class 46: Wednesday, November 26
  • Hash Tables

• Thanksgiving Holiday from November 27 through November 30

Week Thirteen: Graphs

• Class 47: Monday, December 1
  • Hash tables, continued.

• Class 48: Tuesday, December 2
  • Introduction to Graphs
  • Reading: Bailey, Sections 15

• Class 49: Wednesday, December 3
  • Topological Sort

• Class 50: Friday, December 5
  • Shortest Path Algorithms

Week Fourteen: Wrapup

• Class 51: Monday, December 8
  • Minimum Spanning Trees
  • Implementation of graphs

• Class 52: Tuesday, December 9
  • A short survey of Computer Science
  • Topics in Systems
  • Topics in Theory

• Wednesday, December 10
  • Class cancelled due to illness.

• Class 53: Friday, December 12
  • Reflection on structures learned
  • Wrapup

• Final held at 9:00 a.m. on Wednesday, December 17