CS362 Data Structure

Fall 2005

(this syllabus is subject to change)

Introductory information:

Course: Data Structure CS362 (3 cr.), Dept. of Computer and Information Science. P: CSCI340, CSCI240, Room No: BS3009, TR 4:00pm-5:15pm.
Required textbook: - Mark A. Weiss, Data Structure and Algorithm Analysis in C++ (2nd Ed.), Addison-Wesley, 1999.
M. Folk, B. Zoelick, and G. Riccardi, File Structures: An Object-oriented Approach with C++, Addison-Wesley, 1998
Instructor: Jiang (pronounced John) Yu ZHENG, 278-2365, jzheng@cs.iupui.edu
Teaching assistant: Mr. Ashwin Selka Padmanabhan, aselkapa@iupui.edu
Office hours: Teaching assistant - TR, 3:00pm-4:00pm at SL280 (CS department meeting room), Instructor - TR 5:15pm-6:00pm at instructor's office SL280G.

Course Description and/or Course Objectives

(3 cr.) P: CSCI 240 and CSCI 340 strictly enforced.

A study of the design and analysis of data structures and algorithms. Abstract data types: arrays, stacks, queues, lists, trees, graphs. Algorithms: sorting, searching, hashing. File structures, organization and access methods.

This is a fundamental subject for computer science and engineering. It will tell you how to store data in your computer (data structure) and how to efficiently manipulate these data (algorithm analysis). Students will learn basic concepts and principles of various abstract data types, file structures, and algorithm analysis techniques, and will gain practical experience and programming skills through the course projects.

Tentative Schedule of Assignments and Activities

Date

Class Schedule

Assignment Due

week 1: 8/25

Introduction, recursion (ch.1). C++ review (ch.1)

week 2: 8/30, 9/1

Algorithm analysis, (ch.2), running time calculations (ch.2). Lists (ch3),

week 3: 9/6, 9/8

Stacks and queues (ch.3), Trees and binary trees

Homework-1

week 4 : 9/13, 9/15

Binary search trees (ch.4), AVL trees (ch.4)

Homework-2

week 5 : 9/20, 9/22

Hashing (ch.5).

Homework-3

week 6 : 9/27, 9/29

Priority queues, binary heap (ch.6), D-heaps

Homework-4

week 7 :10/4, 10/6

Leftist heaps (ch.6), Sorting, insertion sort (Ch. 7)

Project-1

week 8 : 10/11, 10/13

Review. 10/13 Midterm exam

Midterm Exam,

week 9 : 10/18, 10/20

Heap sort (ch.7), Merge sort,

week 10 : 10/25, 10/27

Quick sort (ch.7), External sort.

Project-2

week 11 :11/1, 11/3

Graph, topological sort (ch.9), Shortest path

Homework-5

week 12 : 11/8, 11/10

FILE STRUCTURES preliminaries. (TA)

Homework-6

week 13 : 11/15, 11/17

FILE RECORDS, Multilevel Indexing, B-tree (TA)

week 14 : 11/22,

Network flow, Minimum spanning tree

Homework-7

week 15 : 11/29, 12/1

Depth-first search (ch.9).

Project-3

week 16 : 12/6, 12/8

Review.

week 17 : 12/16

Final Exam 3:30--5:30pm

Testing, Grading, and Evaluation Policies and Procedures

Grading scale:

<60

>=60

>=63

>=67

>=70

>=73

>=77

>=80

>=83

>=87

>=90

>=93

>=97

D-

D+

C-

C+

B-

B+

A-

A+

Exams and quizzes (for attendance check): 60%. Assignments and projects: 40%. The final scores will be curved to generate a good distribution of grades.

Notice: No late exam will be given under any condition. Early exam is acceptable during the week before the scheduled exam if students provide sound reasons.

Miscellaneous Information

This class will use Oncourse. You can login Oncourse using your IUPUI account.

TA Responsibilities

a. Work 10 hours per week, on average, assisting one professor in the conduct of one course.
b. Offer office hours twice per week to assist students with the course and homework material.
c. Assist in creating instructional material such as, slides, lecture assignments, tests and solutions as requested by the instructor.
d. Grade all lecture and homework assignments in a timely manner.
e. Cover lectures, if needed, in the instructor's absence.
f. Maintain the course website in a timely manner.
g. Maintain the Oncourse site with up-to-date student grades in a timely manner.
h. Monitor the class mailing list for any questions/ discussions and provide answers when appropriate.