Syllabus[1]
Data Structures / IS 621
Fall 2001
Instructor:
Dr. Herbert Tesser x2696
Room: Science 326
Email: tesser@marshall.edu
Office hrs. Mondays 3:00 – 5:00
Wed. 3:00 – 4:00
Thurs 4:00 – 5:30
Other times by appointment
Course Objectives
IS 621 introduces the study of abstract data types (ADTs) and algorithms. The course builds on previous courses in programming. In this course we will:
- study a variety of abstract data types and their implementations
- develop algorithms for use with these data types
- analyze the data types and algorithms under various conditions
This course introduces students to the design and implementation of data structures. These include arrays, stacks, queues, linked lists, heaps, trees and some work on graphs. We will also discuss analysis of algorithms, sorting, hashing, and memory allocation.
Students who successfully complete the course will:
- understand and have had experience implementing several common abstract data types, including stacks, queues, lists, trees and graphs
- understand and have implemented basic algorithms used in searching and sorting
- have experience using algorithms and abstract data types in practical applications
- be able to analyze the design of algorithms and abstract data types
Text and materials
Text: Abstract Data Types
Authors: Dale, N. and Walker, H.
Publisher: Heath
ISBN: 0-669-40000-9
Supporting Texts (not required but it is highly recommended that you have at least one of the following texts)
Visual Basic Algorithms, by Stephens, R., Published by Wiley, ISBN 0-471-24268-3
Algorithms, Data Structures and Problem Solving with C++, by Weiss, M.A., Addison-Wesley, ISBN: 0-8053-1667-1
Or Data Structures and Algorithm Analysis in C, Weiss, M. A., Addison-Wesley, ISBN: 0-201-49840-5
Fundamentals of Computing II, by Tucker, A., et. al., McGraw Hill, ISBN: 0-07-065502-2
and the old standby – it might be out of print:
Fundamentals of Data Structures, by Horowitz. E. and Sahni, S., Computer Science Press,
ISBN: 0-914894020-X
Course Format
This course is designed to be a three-credit course with three lecture hours per week and some laboratory experience.
The course will meet on Thursday nights from 4:00 to 6:20.
Several short quizzes and a midterm will be given during class. Graded material will be returned during class hours.
Attendance
Do!
This is a course dense with information content. It is necessary to come to class. If you can learn it on your own save the money for tuition. I’m not a stickler about taking attendance, but (fill in words-to-the-wise here).
Submission of Homework and Assignments
The course is intended to be computer-language-independent. Homework and assignments may be submitted in any of the following languages: Visual Basic, C, C++, or JAVA (must be pure JAVA). While I’d like to keep things language independent, I won’t accept COBOL, Jupiter, Atlas, nor any machine language.
Make certain that programs and media submitted are virus free. You should submit source code with any special compiler options noted. In general, try to use ANSI standards when applicable.
All work must be handed in before the end of class on the day it is due. At my discretion, late assignments will be penalized 10% of the maximum for each day late.
In extraordinary circumstances, I may accept late work without penalty. I will want documentation for the reason for lateness. The decision whether to assess a penalty rests with the instructor.
Grading
The graded elements of the course are:
Homework and Assignments 25%
Term exam(s) 40%
Final exam 35%
The final grade may involve a “curve”. I expect a grade above 90% will earn an “A”, between 80 and 90, a “B”, between 70 and 80, a “C”. Below 70% will earn an “F”.
Makeup Policy
There won’t be any makeup for exams. If you miss an exam you must have a verifiable, well-documented excuse. If I accept the excuse one of two things will happen:
· you will get an incomplete and be given an extra project which will have to be completed within a month of the end of class, or
· Your grade will be computed without the exam and scaled based on all your other work.
The instructor will choose which option applies.
If the excuse is not accepted, you will get a zero grade for the missed exam.
Unauthorized Collaboration
You know what you shouldn’t do. Don’t do it! If you are in doubt check with
me beforehand
Sharing ideas is one of the benefits of the educational setting. You are encouraged to work with one or two classmates on homework and assignments. However, each participant must sign the document submitted. It is expected that all participants have contributed (approximately) equally to the collaboration.
All work on exams must be the product of individual effort.
Tentative
course schedule (Multimedia systems)
|
Week |
Chapter |
Topic |
Homework Assignments |
Due Date |
|
8/23 |
Ch. 1 |
Introduction, Concepts of Abstraction, Specification, Applications, and Realization |
Ch. 1 {1,2,8,9} |
8/30 |
|
8/30 |
Ch. 2 |
Analysis of Algorithms, Big O notation, typical growth rates, |
Ch. 2 {2,7,17} TBA |
9/6 |
|
9/6 |
|
Recursion, Common Examples (fibonacci series, Euclid’s algorithm) |
|
|
|
9/13 |
Ch. 3 |
Generality in Algorithms, Language Independence, Error Handling, Information Hiding, |
Ch. 3 {3, 4} |
9/13 |
|
9/20 |
Ch. 4 Ch. 5 pp. 152-154 |
Abstract Data Types (ADT), specification, representation and notation, Examples (lists, stacks) |
Ch. 4 TBA Project 1 |
TBA TBA |
|
9/227 and 10/4 |
Ch. 5 |
Queues Introduction to arrays |
Ch. 5 {1,2,4,21} |
9/24 |
|
10/11 |
Ch. 6 |
Arrays – one and multi-dimensional, sequences. Examples: string searching, sorting (quicksort, mergesort) |
Ch. 6 {2} TBA |
10/8 |
|
10/18 |
|
Exam |
|
|
|
10/25 |
Ch. 7 |
Introduction to trees, binary trees, heaps, Examples: expression trees |
Ch. 7 {1,2,7} Project 2 |
10/22 TBA |
|
11/1 |
Ch. 8 |
Binary trees, search trees, heaps, Examples: OS applications |
|
|
|
11/8 |
Ch. 8 |
Static and Dynamic trees, |
Ch. 8 {8, 15} |
11/29 |
|
11/15 |
|
Exam |
|
|
|
11/22 |
|
Fall Break |
|
|
|
11/29 |
Ch. 8 |
Examples: AVL trees and Huffman compression |
Ch. 8 {18,19,29} |
12/6 |
|
12/6 |
|
Review |
|
|
|
12/13 |
|
Final Exam |
|
|