CS 232 Data Structures

Office Hours: e-mail for assistance at any time. 6:00-6:30 p.m. before class
Phone: Responses to numbers provided to the Instructor via WebCT e-mail.
E-mail: WebCTaccount and mmarquis@stagweb.fairfield.edu
Location: McAuliffe Room 204
When: Thursday, 6:30-9:30 p.m., September 7-December 21, 2006.
Prerequisite: CS132 or CS142 or equivalent.

Textbook: Data Structures using Java, D.S. Malik & P.S. Nair, Thomson Course Technolgy, 2003. ISBN 0-619-15950-2.

The textbook is the primary source of material for this course. The Lessons and Examples are also very important. All the homework assignments and examinations come directly from those three sources.

Additional References:

• Object-Oriented Data Structures using Java, Dale, Joyce, & Weems, Jones and Bartlett.
• Java 5 Illuminated, Anderson & Franceschi, Jones and Bartlett.
• Java How to Program, Sixth Edition, Deitel & Deitel, Prentice Hall.
• Java Programming: From Program Analysis to Program Design, D.S. Malik and P.S. Nair, Thomson Course Technology, 2003.
• Sun's Application Programming Interface, available on the Sun Java Website.

Computer Usage: Students MUST have access to a computer with a Java compiler and an ISP provider. The version of Java to be used is jdk1.5.0_06 or later, which can be downloaded free of charge from the http://java.sun.com web site. Eclipse 3.1.2 or later is the mandatory Integrated Development Environment (IDE) to be used for this course. It can be downloaded free of charge from the http://www.eclipse.org web site.

Microsoft Word and PowerPoint are also needed for the course.

A file compressor/de-compressor (e.g., WinZip) is required. It can also be downloaded from the web. The Windows XP Operating System (OS) has its own compressor/de-compressor, so WinZip is unnecessary if that is your OS.

All material: lectures, examples, and homework assignments, are on the WebCT site. The lectures can be viewed on the site or downloaded from it. The examples and homework assignments can be downloaded from the site. Students are responsible for obtaining homework assignments each week from WebCT.

The WebCT e-mail feature is the primary electronic communication medium for this course outside the classroom. Homework submittals, questions, or other online communication will be done using WebCT and its e-mail. Similarly, students are responsible for checking their WebCT e-mail account daily for possible messages from the instructor.

Course Notes: On WebCT

Course Description: This course presents problem solving with abstract data types such as lists, linked lists, stacks, queues, and trees. The course revisits recursion and discusses algorithm efficiency. Time permitting; the course includes sorting, reach ability, and minimal paths in graphs and their algorithms. Three credits.

Course Objectives: The major objective of this course is to make the student capable of writing algorithms for manipulating data in computer programs for the most efficient run time. That requires knowledge of the various ways to arrange the data and knowledge of the benefits of each arrangement. Each class period has a stated goal shown below.

Outcome: The student will be able to write time-efficient computer programs. He/she will be cognizant of the various data arrangements and will be able to measure their relative time-efficiencies. He/she will understand the derivation and implementation of lists such as arrays, the Java Vector and ArrayList classes, linked lists, stacks, queues, and trees. His/her understanding of recursion and object-oriented programming will be reinforced as a secondary outcome of the course. Each class period has a stated outcome shown below.

Student Activities: To achieve the course objectives, the student must have good class participation, and conduct the computer programming tasks assigned for homework.

This course offers four sources of material to assist the learning process: 1) the lessons, 2) a set of notes and examples for each class session, 3) the textbook, and 4) additional references. The amount of learning to be gained is directly related to the usage of this material. Most of the homework assignments and test material are taken from the textbook. They may be supplemented with material from the lessons (item #1 above) and the notes and examples (#2). The student should expect to take at least twice the lecture time for reading, studies, and assignments. Students are expected to study and perform homework each week.

Homework: There is a homework assignment for each of the chapters in the textbook. Each is numbered after its chapter. For example, HW09 is the homework for Chapter 9. The assignments are in two parts: 1) multiple choice questions (e.g., HW09Q), and 2) a program coding assignment (e.g., HW09C). The homework assignments are posted on WebCT. The answers to the questions and the coding solution are due as specified in the WebCT calendar.

The homework solutions are to be placed in a single folder, which will contain the Word document containing the answers to the questions, the source code file(s) (.java extension) for the programming assignment as well as any other file associated with the assignment, as specified in the assignment. Then zip the folder and submit it on WebCT before midnight on the due date. Timely homework submittals are strongly encouraged to permit immediate corrective actions for poorly performed or misunderstood assignments. Re-submittal of poor homework solutions to obtain a better grade is encouraged, but can only be accomplished if the original submittals are on time. Late homework submittals may cause a reduction of 10 points in its mark. Late homework solutions can only be submitted via e-mail.

E-mail: The WebCT e-mail feature is the primary mode of communication between the students and the Instructor outside of the classroom. Students should check their e-mail site daily. They are also encouraged to use e-mail to ask questions. Questions and their answers are provided to all students via e-mail.

Course Requirements: The schedule of activities and topics to be covered are outlined below. They should be done in the order shown. The student should familiarize himself with the Eclipse IDE and read the syllabus before proceeding with lessons.

Chapter 1 - Software Engineering Principles and Java Classes

Goals: Learn about software engineering principles, algorithms, and user-defined classes. Introduce the Big-O notation for measuring the relative time efficiency of algorithms.

Outcome: The student becomes aware of structured design, object-oriented programming methodologies, and the concept of time efficiency in algorithms.

Chapter 2 - Inheritance and Exception Handling

Goals: Learn about inheritance, composition, and abstract classes.

Outcome: The students are able to handle super classes and subclasses and their constructors and methods in writing computer programs.

Chapter 3 - Array-Based Lists

Goals: Learn about lists and the classes Vector and ArrayList and their operations.

Outcome: The student can conduct searches, insertions, and removals from lists.

Chapter 4 - Linked Lists

Goals: Learn about the basic properties of linked lists and their benefits.

Outcome: The student discovers how to build and manipulate a linked list.

Chapter 5 - Recursion

Goals: Reinforce the student's understanding of recursive methods.

Outcome: The student will use the base case and general case of a recursive definition to take advantage of recursion in algorithms.

Chapter 6 - Stacks

Goals: Learn about stacks and their operations.

Outcome: The student will be able implement a stack as an array and as a linked list.

Chapter 7 - Queues

Goals: Learn about queues and their operations.

Outcome: The student will be able implement a queue as an array and as a linked list.

Chapter 8 - Search Algorithms

Goals: Learn the various search algorithms.

Outcome: The student will become more efficient in programming searching methods.

Chapter 9 - Sorting Algorithms

Goals: Learn the various sorting algorithms.

Outcome: The student will become more efficient in programming sorting methods.

Chapter 10 - Binary Trees

Goals: Learn about binary trees.

Outcome: The student will be able to organize data in a binary search tree.

Chapter 11 - Graphs

Goals: Become familiar with the basic terminology of graph theory.

Outcome: The student will discover how to represent graphs in computer memory and how to implement various graph traversal algorithms.

Tests and Exams: There are two exams: a midterm exam and a final exam.

Grading Policy:

Homework : 1/3
Midterm Examination: 1/3
Final Examination : 1/3

A passing grade cannot be achieved without the submittal of the midterm and final examination projects, regardless of the points shown above. Non-submittal produces a penalty beyond the points shown above, and precludes a passing grade.