Bill Teter
Office:          149 Redcay
Telephone:    2782
Office Hours:  Tuesday, Thursday 9:00-12:00

email:  william.teter@plattsburgh.edu

Required Texts:
     Data Structures and Problem Solving using Java by Mark Allen Weiss, published by Addison Wesley, 3'rd edition, 2006.

Prerequisite:
    CSC223 - Data Structures and Algorithms (with a grade of at least C)
    CSC318 - Discrete Mathematics II
    MAT224 - Calculus I

Objectives:
    In this course students will:

1. Continue to develop programming skills in Java.

2.  Apply big Oh notation to analysis of algorithm.

3.  Extend understanding of principles of object oriented design.

4.  Use the data structures as implemented in the Java API.

5.  Implement tree and graph data structures along with their standard algorithms.

Course Content:

Java 5.0 -- Some new features

Recursion and efficient exponentiation

Randomized algorithms -- Pseudo primes

Graphs
    definitions
    Java representation
    unweighted shortest path
    positive weighted shortest path (Dijkstra's algorithm)
    topological sorts and Directed acyclic graphs

Trees
    terms
    binary trees
    traversals--pre-order, post-order, in-order, level-order
    binary search trees
        inserts
        deletes
        complexity
        AVL trees
        red-black trees
        aa-trees
        TreeSet and TreeMap implementations
    B-trees

Hashing
    hash functions, Horner's rule
    linear probing
        analysis
    quadratic probing

Priority queue with a binary heap
    complexity
    heap sort

Labs:
     There will be about 6 small programming assignments and one larger project.  The programs that you submit for the assignments must be entirely your own.  On the larger project you may consult and include code that was written by others so long as you credit the authors.

Exams:

There will be a final exam.

Quizzes: There will be a quiz each week covering current material. The lowest quiz score will be dropped when computing the final grade. If you must miss a quiz for an acceptable reason see me before the quiz. In this case the next quiz will be counted twice. Otherwise there will be no make-ups. The quizzes will be based on the assigned reading and lecture topics.

Policy: Students taking this course for the third, fourth, etc. time (excluding withdrawals) need special permission from the department chair. Under normal circumstances withdrawals will not be permitted after the end of advising.

Honesty:

Cheating on exams or plagiarizing others' work will not be tolerated. The first instance will result in a zero on the exam or assignment. If a second instance occurs you will be dropped from the class.

Grades: Your final grade should reflect your knowledge of the subject. It will be computed as follows:
    Programming assignments 30%
    project 20%
    Final exam 20%
    Quizzes 30%

I may override this formula if in my opinion the formula results in a grade that does not measure the students knowledge of the subject.

Attendance Policy: Students are responsible for all material and information presented in class.