06191170: Data Structure
(Autumn 2006)
Department of Mathematics
Zhejiang University
Announcements General
Course Goals
Topics Texts
Grading
Syllabus
Assignments
Requirements on Assignments
Professional Conduct
Miscellaneous
Announcements
- Nov. 13: Course is over.
- Oct. 30: Final examination will be
held on Nov. 13.
- Sep. 30:
Source codes of class.
- Sep. 29: Announce
Homework#2, deadline is Monday,
Oct. 30
- Sep. 25: Announce
Project#1, deadline is Monday,
Oct. 23
- Sep. 25: Deadline of Homework #1
is postponed to Sep. 30.
- Sep. 18: Announce
Homework#1, deadline is Monday,
Sep. 25
- Sep. 18:
Source codes of class.
- Sep. 15:
Source codes of class.
- Sep. 12: FTP for homework uploading (ZJU internal):
ftp://10.13.61.167:21
username/password: DS06
- Sep. 12: The website is open. Look
for your ID number.
General
Course Goals
The goals of this course are to extend
and deepen the student's knowledge and understanding of algorithms and data
structures and the associated design and analysis techniques. It examines
previously studied algorithms and data structures more rigorously and introduces
the student to "new" algorithms and data structures. It focuses the student's
attention on the design of program structures that are correct, efficient in
both time and space utilization, and defined in terms of appropriate
abstractions.
Topics
This course provides a
comprehensive introduction to data structures and algorithms, including their
design, analysis, and implementation. Topics include:
·Analysis
tools: running time, pseudo-code, algorithm analysis, asymptotic notations
·Stacks,
queues, linked lists, deques
·Vectors,
lists, sequences
·Trees:
basic algorithms on trees, binary trees, representing trees
·Priority
queues, heaps
·Dictionaries:
log files, hash tables, ordered dictionary ADT, look-up tables, skip lists
·Search
trees: binary search trees, AVL trees, multi-way search trees, (2,4) trees,
red-black trees
·Sorting,
sets, and selection
·Graphs:
traversal, directed graphs, weighted graphs, minimum spanning trees
Texts
Required textbook:
C/C++与数据结构，王立柱编著，清华大学出版社, 第2版.
Optional textbook:
Data
Structures, Algorithms, and Applications in C++, Sartaj Sahni, McGraw-Hill.
（数据结构算法与应用——C++语言描述，机械工业出版社.）
Data Abstraction and
Problem Solving with C++: Walls and Mirrors by Frank Carrano, fourth edition,
Addison Wesley.
Any good
introductory book on C++ programming.
Readings:
Various
journal, conference, or WWW materials as appropriate.
Grading
Credit toward the semester grade will
be allocated to each of the components as indicated in the following table.
| Assignments |
30% |
| Projects |
40% |
| Final Exam |
30% |
Note: Final examination will be
in-class, closed-book. More information will be provided prior to it.
Syllabus
Note: Here you can view or
download the notes that we use in class. DO NOT depend solely on these notes as
many details are missing. You should read the textbook and take notes in class.
Applets
Assignments
Homework
Projects (Project
requirement)
Note: Please zip your submission stuffs
of the assignment into one single file either using WinZip or WinRAR. Name the
file name as "ID_Homework1_Name.zip" or "ID_Project1_Name" where ID is
your unique ID number in the class. For
Example, my submission file name might be "007_Homework1_刘利刚.zip".
Requirements on Assignments
Requirements
- All students are expected to study
the relevant portions of the textbook and handouts in conjunction with our
class discussions (i.e., before coming to class). Explicit reading
assignments will not always be given.
- All programming for this course
will be done in C++ according to
the coding styles. We will compile and test programs on MS Visual C++
Version 6.0 under Windows XP. It is the responsibility of the student to
submit a program that will successfully compile and execute on the specified
platform.
Assignment Submission
- All students are expected to
complete their homework assignments by their due dates.
All assignments are due prior to
11:59:59 PM Wednesday night every week.
-
Submission stuffs
Your ID number, your name, the
assignment number or name, source codes, related document
- Grading of programming assignments
will be based on the following criteria:
1. Correctness of program.
2. Output from program that adequately demonstrates correctness.
3. Documentation, internal and external, included as appropriate according
to the
Computer Program
Documentation Standards.
4. Efficient use of algorithms and appropriate data structures.
5. Stress - program must function correctly under all and/or extreme and
unusual combinations of input.
6. Creativity - credit for innovation in interface, implementation, style,
etc.
- Submission approach
Please submit your assignment stuffs via my FTP not via email.
- Late Work
No late work will be accepted. If you know you will miss a test due to an
excused absence, you must contact me ahead of time to schedule a make-up
session.
- Late programming assignments
follow the following rules:
25% deduction for 1-day late
50% deduction for 2-day late
Not accepted after being 2-day late
Regarding your marks, contact the grading TA within two weeks after the
assignment is handed back. After this two-week period, your assignment stays
as it is graded.
What constitutes Creativity ?
Creativity is any substantial improvement beyond the basic solution - it can be
applied to any part of the project. For example, the following are relevant in
most cases :
- User Interaction
̶
It would be nice to present the user
with options to either test the program using internal tests or an
interactive interface
̶
Work around limitations in the
program. For example, if the program asks for lines of input and quits when
it sees "X", invent a special syntax (called an escape sequence) to allow
the user to type in "X" without the program exiting. Hypothetically, if the
user enters $X the program interprets it as X, if the user enters $$ the
program interprets it as $ and if the user enters X the program exits.
- Visualization
̶
A representation of how data is
actually being stored in the data structure, by specific position and value
(this would even help greatly with debugging) - this could be accomplished
with specialized data access routines for output formatting
- Testing
̶
Simulating real-world conditions for
input by making some assumptions about the distribution of operations
performed and the rate of operations, then simulating using random number
generators
̶
Intensively testing creation, usage
and destruction of the data structure to prove there are no memory leaks
̶
Exhaustive automatic testing - go
through many (or every) possible scenarios for the data structure (up to
some time limit). For example, assign "add" and "remove" to a binary
variable - then generate all possible strings of operations - test the
structure for each case, and test the results automatically in your main
program to make sure they are what was expected.
̶
Develop a syntax for file-based
testing and use this as an option - eg. "enter X" and "retrieve"
- Efficiency
̶
Minimize the number of allocations of
memory blocks by reusing deleted blocks
Ask yourself these questions ...
̶
How can I make the interface more
natural ?
̶
How can I make the program run faster
?
̶
How can I use less memory/disk space ?
̶
Have I thoroughly tested my program ?
Will my program survive real-world tests ? Will my program survive
worst-case scenario tests ?
Professional Conduct
As a
student in our class, you are expected to conduct yourself in a professional
manner.
Limited Collaboration Policy.
Unless otherwise indicated, any homework assignment or programming exercise
given in this class will be an individual assignment. The work you submit is to
reflect the knowledge, understanding, and skill that you have attained as an
individual. However, the instructor does want to encourage the development of a
community of scholars who are actively engaged in discussion of the ideas
related to this course. With this in mind, you are allowed to discuss solutions
of the homework and programming problems with other students if done so
according to the following guidelines:
- You
may discuss ideas for homework and programming assignments with your
classmates. However, you cannot collaborate on writing the solution or the
program code. That is, you can talk about the problems and ideas for solving
them, but you cannot write things down with anyone else. You are, of course,
prohibited from copying or seeing another student's written solution, and
you are not allowed to show your work to anyone else.
- You
should accept help with care. If you work too closely with another student,
you might mislead yourself into believing that you understand the concepts
and techniques better than you actually do. Don't forget that the instructor
has office hours and can probably give you hints or suggestions to get you
started.
- You
should give help with care. Do not help anyone too much. When you have
solved a problem, it is tempting to just tell other students how you solved
it. Instead, try to allow them to come to the solution on their own. Maybe
give them a hint to help them get "over a hump." Remember that helping
someone too much will hurt them in the long term if they can't work through
problems on the exams by themselves. So avoid the temptation to do so. If
you can't help other students without giving away the whole solution, direct
them to see the instructor (who may or may not have a way to "edge" them
toward the solution).
- You
are not obligated to help anyone. If you feel uncomfortable helping another
student for any reason, please direct them to see the instructor.
Miscellaneous
Professionals
Online C++ resources
Useful coding related sites on the
internet
Send any comments or
suggestions to Dr. Ligang Liu,
ligangliu@zju.edu.cn
Copyright © 2006, Ligang Liu
Last modified: Mon. Sep. 11, 2006