Course Number: CSCI 311

Course Name: Algorithms and Data Structures in Java

Prerequisite: CSCI 112

Prerequisite by Topic: Familiarity with the principles of program design and implementation in a high-level language

Units: 3

Class Dates and Times: LECTURE: TTH 3:30-4:45

Instructor: Anne Keuneke

Office: 223 O'Connell

Office Hours: see http://www.ecst.csuchico.edu/~amk/foo/hours.html for current information

Office Phone: (530) 898-5998
Department Phone: (530) 898-6442
email: amk@ecst.csuchico.edu
WebPage: http://www.ecst.csuchico.edu/~amk

Textbooks:

Data Structures, Algorithms, and Applications in Java, 2^nd edition, Sartaj Sahni, Silicon Press, 2005, ISBN 0-929306-33-3.

Access to Java WebPage: http://java.sun.com and course web page

Course Description: The purpose of this course is to introduce students to object-oriented software design methodologies and implementation alternatives for various fundamental data structures and problems in computer science. In addition, due to the focus on object-oriented techniques and the capabilities Java provides, we will address newer problems such as multithreading in concurrent and distributed programming. We will study various data structure/algorithm combinations and analyze their relative advantages and disadvantages using both mathematical and empirical measurements. The Abstract Data Type (ADT) constructs of data abstraction and information hiding are emphasized throughout the course and are explicitly implemented for each data structure via Java objects.

Language Choice: Rather than simply using any language as a vehicle for programming the data structures, the class will use Java since its language constructs force the student to program in a manner consistent with the principles of good object-oriented programming (unlike hybrid OO languages). In addition, this language was chosen since it is, by its nature, simple, object-oriented, distributed, interpreted, robust, secure, architecturally neutral, portable, multithreaded, and dynamic. Java's access to large, easy to access libraries, make it a great choice for experimenting in data structures and creating maintainable and reusable code.

Goals: To give a thorough coverage of the object-oriented design, analysis, implementation and application of advanced data structures and the algorithms required to process them.

Laboratory Projects: Four substantial program design and implementation assignments.

Lab submission: See http://www.ecst.csuchico.edu/~amk/foo/design.html for how labs should be submitted

Grade Evaluation Procedures:

	Labs		1/2
	Mid-term	1/4
	Final Exam	1/4

Topics:

1. Review of Program Design and Simple Data Structures (2 hours)
2. Abstract Data Types (ADTs) (3 hours)
   • Description and Examples
   • More on Specifications and Proofs
     • Predicates; preconditions and postconditions
3. Object-Oriented Programming and Data Structures (3 hours)
   • The Paradigm
   • Objects and Abstraction
     • Classes, Inheritance, Information hiding, Encapsulation
   • Methods
   • Instances and Instantiation
   • Additional Terms (in course description)
4. Java (4 hours)
   • The Environment
     • Appleviewer, Applications
   • Fundamentals
     • Basic Java Constructs and Syntax
   • Advanced Constructs
     • Threads, Interfaces, Vectors, "Producer/Consumer"
5. Complexity Analysis (3 hours)
   • Theoretical
   • Empirical
6. Linear Structures (1 hour)
   • Lists, Arrays, Queues, Stacks
7. Trees (6 hours)
   • Ordered binary trees; balancing
   • Heaps
   • 2-3 Trees, B-trees
8. Graphs (5 hours)
   • Representation of undirected, weighted and digraphs
   • Graph traversals and processing
   • Applications of graphs:
     Shortest Paths, Minimum Cost Spanning Trees
9. Sorting and Searching(5 hours)
   • Review of simple techniques
   • Hash Tables
   • Huffman Coders
   • Patricia Structures
10. Advanced Programming in Java (3 hours)
    • Distributed Programming, Multithreading, I/O and security
    • User-Interfaces
    • Distributed Objects (as time allows)
11. Lab Discussion

    ---