Data Structures

600.226 Data Structures
Fall 2000

Department of Computer Science

This page will be updated regularly. Please visit (and reload) often.

When:: MTW 11-11:50
Where:: Shaffer 3
Instructor:: Subodh Kumar. Email: subodh@cs.jhu.edu. Tel: 516-0060.
Office:: 218A New Engineering Building
Office Hours:: Monday 12-1, Wednesday 1-2. Or by appointment.
TAs: Jason Corso. (Send mail); Office Hours: Tue: 10-11 (by email only), Fri: 1-2 (Grad Trailer next to Whitehead).; Manju Kolencherry. (Send mail); Office Hours: Mon: 10-11 (by email only).; Nelson Yang. (Send mail); Office Hours: Mon 3-5, 7-8(pm), Tue 7-9(pm) [Java turorial session], Wed: 3-5, Thu: 12-2, Fri: 12-1.; Bin Feng. (Send mail); Office Hours: Fri: 1-2 & 4-5.

All TA Office hours will be held in the undergraduate lab except where specified otherwise.

Latest news:
	Final grades are available. You can see your graded Finals in NEB218A. The overall average was 691 and stdev 141.

Course Description

Course covers the design and implementation of data structures including sequences, trees, and graphs. Other topics include sorting, searching and hashing, using JAVA. An overview of JAVA will be provided. Prereq: 600.107 or 600.109. Recommended: 600.118 or 600.121

Textbook

Goodrich, M. and Tamassia, R.Data Structures and Algorithms in Java 2ed, John Wiley and Sons, Inc., 2000.

Other books on JAVA

Lewis & Loftus.Java Software Solutions, 2ed., Addison-Wesley, 2000.

Arnow & Weiss. Introduction to Programming using java, Addison-Wesley, 2000

Current Coverage

Week of	Material covered
Oct 30:	Midterm exam dissection, Dictionary interface, Binary Search on an array
Nov 6:	(Ch 9) Binary Search tree (search/update), Non-unique keys, AVL trees
Nov 13:	AVL trees, multi-way trees, B-trees, 2-4 trees, intro to red-black trees
Nov 20:	More red-black trees, Intro to Skip Lists, Hashing
Nov 27:	More Hashing, Sorting (Selection sort, Insertion sort, Bubble sort, Merge sort, Quick sort, Bucket sort, Radix sort)
Dec 04:	Strings, Tries (standard, Patricia and Compressed), Pattern matching (brute force and KMP), intro to graphs (terminology, ADT)
Dec 11:	More graphs (Representation, DFS, connected components) Class Survey, Question-Answer session intro to graphs

Overall Syllabus

Design principles

Data Structures and Algorithms
Object-Oriented Design Principles

Analysis techniques

Running Time
Pseudo-Code
Quick Mathematical Review
Analysis of Algorithms
Asymptotic Notation: The ``Big-Oh''
Asymptotic Analysis

Stacks, Queues, Lists

Stacks
Queues
Linked Lists
Double-Ended Queues

Sequences

Ranked Sequences
Positional Sequences
General Sequences
Trees

The Tree Abstract Data Type
Basic Algorithms on Trees
Binary Trees
Data Structures for Representing Trees

Priority Queues

The Priority Queue Abstract Data Type
Priority Queue as a Sequence
Heaps

Dictionaries

The Dictionary Abstract Data Type
Binary Search Trees
AVL Trees
Hash Tables

Sets, Sorting, Selection

Sets
Sorting: Merge Sort, Quick Sort, Radix Sort
Complexity of Sorting
Selection

Graphs

The Graph Abstract Data Type
Data Structures for Graphs
Graph Traversal
Directed Graphs

Strings

The String Abstract Data Type
Brute-Force String Pattern Matching
Regular Expression Pattern Matching
Tries

Go to the top

Grading

Work	Date Due	Points
Class participation	NA	50
Assignment 1	Wed, Sep 20, 10:59am	50
Project 1	Wed, Oct 4, 10:59am	100
Assignment 2	Wed, Oct 11, 10:59am	50
Project 2	Fri, Oct 20, 5:00pm	100
Assignment 3	Mon, Nov 6, 11:00am	50
Project 3	Nov 20	100
Assignment 4	Nov 28	50
Project 4	Dec 12	100
Mid-term Exam	Oct 25, 11-12	150
Final Exam	Dec 18, 9-12	200

The programming assignments will be graded 80% on correctness and 20% on readability and documentation. All assignments must be turned in electronically by 11am on the date due. There is a 10% penalty for each day that the assignment is late. No points will be awarded if it is more than 5 days late.

Plagiarism