CS321 - ADVANCED DATA STRUCTURES
Professor: Russell C. Bjork Fall semester, 1999 - quad B
Office: MacDonald 217 x4377 MWF 3:20-4:20 pm
Hours: MWF 1:30-2:30 pm;
And by appointment
HANDOUT #1: SYLLABUS - 10/18/99
PREREQUISITES: Computer Science 320, Mathematics 230
COURSE OBJECTIVES:
This course is intended to build upon the introduction to data structures you
received in CS122 and the introduction you received to object orientation and
C++ in CS320 in the following ways:
1. You will explore some of the structures we discussed in CS122 in greater
depth, and will consider more sophisticated variants of them.
2. You will develop your algorithm analysis skills.
3. You will learn how to use C++ templates to build re-usable, generic data
structures; in particular, you will learn how to use the C++ Standard
Template Library (STL).
4. You will learn how to deal with memory management issues.
TEXT: Weiss, Mark Allen. Data Structures and Algorithm Analysis in C++
(Reading, MA: Addison-Wesley, 1999).
ON RESERVE: Horowitz, Ellis and Sartaj Sahni: Fundamentals of Data Structures
in C++. (New York: W.H. Freeman Co., 1995).
COURSE TECHNIQUES AND PROCEDURES:
The over-riding aim of this course is to make your thoroughly familiar with the
spectrum of "standard" data structures so that you can make the best possible
choices of data representations for solving practical problems. To accomplish
this aim, we will make a methodical study of a number of different structures,
normally along the following lines:
1. A description of a typical problem for which the structure under
consideration might be appropriate.
2. A careful development of algorithms necessary for creating and maintaining
the structure.
3. A careful analysis of time and space efficiency questions pertaining to the
various algorithms.
4. One or more practical exercises (programming project or homework) designed to
give you practice implementing/and or using the structure.
You will notice that there is some overlap between portions of this course
and CS122. This is intentional; the second exposure in this course is
designed to cover the material in greater depth and with more rigor, while
also reviewing the basic concepts you learned in CS122.
COURSE REQUIREMENTS AND EVALUATION:
1. You will be expected to read most of the textbook, as assigned in the topic
schedule below.
a. Some of the sections in the book cover material that you should have
already learned in CS122 and/or CS320. In the course schedule, you will
be asked to "Review the material in" these sections. That means that
you should quickly scan through each section. If you understand the
material that's there, all is well; if not, it's your responsibility to
read through it carefully and come by for help if you are having
difficulty understanding it. That is, you are responsible to do whatever
it takes to have a solid basic understanding of this material.
b. Reading assignments dealing with new material should be completed BEFORE
the class hour in which the topic is discussed. Lecture presentations
will assume that you have read the text, and it is expected that your
participation in the class will reflect that fact. However, our classroom
discussion will not rigidly follow the order of material in the text, nor
will it be confined to material covered there. (Note: when a section
number is stated as an assignment, it includes all the subparts of that
section unless otherwise noted.)
2. Four problem sets will be distributed during the quad, and will be due as
shown in the course schedule, with value in the final grade computation as
shown below. Solutions to each problem set will be posted outside the
professor's office door after the set is turned in. (Note: in contrast to
CS320, these homework sets will be done individually.)
Set # Material covered Value
1 Algorithm Analysis; Sparse Polynomials, Matrices; STL 6%
2 Balanced Binary Trees; Hashtables 8%
3 Graphs and Networks 8%
4 Generalized Lists; BTrees; External Sorting; Sets 8%
---
30%
The following guidelines should be observed when doing these homework sets:
a. Homework sets will be due at the start of class on the date indicated.
Late homework sets will NOT be accepted.
b. Homework sets must be done on one side only of 8-1/2 x 11 paper, and pages
must be stapled in problem-number order. Problems must be numbered, and
final answers (where appropriate) should be highlighted. (Homework sets
not conforming to these standards will be returned ungraded.)
c. You may work together with another student on homework, provided each
of you works on each problem.
d. Where an exercise calls for writing a program, it is sufficient to write
it out by hand; you need not enter it into the computer.
3. Three programming projects will be due as assigned. Each will account for 12%
of the final course grade (36% total). The project emphases are as follows:
a. Project 1: Multilist Implementation of Sparse Matrices
b. Project 2: Threaded Binary Trees
c. Project 3: Graph Operations
These projects are intended to give you broad practice with the various
data structures we are covering. You are allowed (and encouraged) to
do these as teams of 2 students. (One team of 3 will be allowed if
necessary.) Also, the various teams will be allowed and (and encouraged) to
share design ideas and problems (but not code) with one another. Please
observe the following, though:
a. You must indicate via comments who was responsible for each portion of
the project. Ordinarily, each member of the team will receive the same
grade unless the work is obviously disproportionate.
b. Of course, for the purpose of the quiz you must be sure that you
thorougly understand all of the work that you turn in - borrowed or not.
As with other courses, some of the projects will have several options so
that you can attempt a less difficult version for a reduced number of points.
For additional details, see "Guidelines for Computer Science Projects"
attached. You are expected to read these carefully and comply with them
exactly.
4. There will be a final examination given as shown in the Course Schedule,
worth 34% of the final course grade. This exam will be open book, open notes.
5. Final grade computation: Homework 30%
Projects 36%
Final Exam 34%
-----
100%
The following are minimum guararanteed grades for the percentages indicated:
93% - 100%: A 90% - 92.9%: A-
87% - 89.9%: B+ 83% - 86.9%: B 80% - 82.9%: B-
77% - 79.9%: C+ 73% - 76.9%: C 70% - 72.9%: C-
67% - 69.9%: D+ 63% - 66.9%: D 60% - 62.9%: D-
POLICY STATEMENT ON EXTENSIONS AND INCOMPLETES:
1. Extensions of the due dates for homework or projects will be given in the
event of extenuating circumstances (such as illness, personal emergency)
IF you submit a brief written request to the professor as soon as
possible after the circumstances arise. This request will be initialled
(if approved) and will be returned to you. You must attach it to the
piece of work for which the extension was granted.
2. A grade of Incomplete will be given without penalty IF you are unable to
complete the course work by the last day of the term due to major illness or
other similar emergency. Again, a written request should be submitted. Such
a request will only be granted if you are substantially up-to-date with your
course work and were making good progress in the course up to the time that
the difficulty arose. Of course, you must complete all work for the course
by the midpoint of the next semester in accordance with College policy.
3. A grade of Incomplete with a penalty of one letter grade to be applied in the
final grade computation MAY be given if you are unable to complete all the
course work for reasons other than those noted above. You must make a
written request, and your progress in the course, class attendance etc. will
be taken into consideration in determining whether to grant it. Again, you
must complete all work for the course by the end of the next term.
ATTENDANCE POLICY:
Regular class attendance is expected of all students, and class attendance will
be recorded. Students who miss more than two classes during the quad
should expect to see their final grade reduced by 2% for every class missed over
two, and students who miss more than 6 classes will fail the course
automatically. Note that the allowance of missing two classes is meant to
cover unavoidable absences due to illness, field trips, athletic contests etc,
and these allowed absences should be saved for that purpose. There is no such
thing as an "excused absence" except in case of unusual hardship situations such
as being hospitalized for a period of time. Also, absence from class on the day
before or after a school holiday will be counted as a double absence, and each
late to class may be counted as half an absence.
You may ask the professor to waive this policy for you if you earned an A in the
prerequisite course. However, the policy will be reimposed if your subsequent
work deteriorates - in which case the allowed absences will be prorated.
TENTATIVE SCHEDULE OF TOPICS:
Date Topic(s) Reading Homework/
Projects Due
INTRODUCTION
M 10/18 Course Introduction; Review of (Review §1.1-1.5
Algorithm Analysis; Omega, Theta, as needed, 2.2-2.4)
and Little o Bounds. §2.1
W 10/20 An Example of How Choosing a Good Data (Review §3.1,
Structure can Make a Big Difference: 3.2.1-3.2.2,
Sparse Polynomials and Matrices; 3.2.4-3.2.6, 3.2.8)
Using the STL to Implement other Data §1.6-1.7,
Structures 3.2.3, 3.2.7
F 10/22 Sparse Polynomials and Matrices, STL (ctd) Start
Project 1
SEARCH STRUCTURES
M 10/25 Height-Balanced Binary Search Trees; (Review §4.1-4.3)
AVL Trees §4.4
W 10/27 AVL Trees (ctd); Splay Trees §4.5,12.1 Homework 1
F 10/29 Threading of Binary Trees (Review §4.6)
Horowitz (on
reserve) §5.5
M 11/1 2-3, 2-3-4 and Red-Black Trees §12.2
W 11/3 (TBA - professor at OOPSLA) Project 1
F 11/5 (TBA - professor at OOPSLA)
M 11/8 Weight-Balanced Binary Search Trees; §10.1 intro, 10.1.3,
Huffman Encoding 10.3 intro, 10.3.3
W 11/10 Hash Tables; Extendible Hashing (Review §5.1-5.3)
§5.4-5.6
GRAPH ALGORITHMS
F 11/12 Review of Graphs and Networks; (Review §9.1)
Graph/Network Operations §9.2-9.3
M 11/15 Graph/Network Operations (ctd) §9.4-9.5 Homework 2
W 11/17 Graph/Network Operations (ctd) §9.6
F 11/19 Graph/Network Operations (ctd) §9.7 Project 2
MISCELLANEOUS STRUCTURES (SUBJECT TO CHANGE)
M 11/22 Lists of Lists (General Lists); Horowitz (on
Heterogeneous Lists reserve)
§4.10,4.12
M 11/29 B-Trees §4.7
W 12/1 B-Trees (ctd) Homework 3
F 12/3 External Sorting (Review §7.1-7.10)
§7.11
M 12/6 Tree Representation of Sets ch. 8 Project 3
W 12/8 Review and catch up - or - trip to MIT to hear Donald Knuth
(date to be announced) Homework 4
THURSDAY 12/16 - 2:00-4:00 PM: FINAL EXAMINATION
Copyright ©1999 - Russell C. Bjork