DATA STRUCTURES AND ALGORITHMS
Topic #0: THE TEMPLATE
Last modified: March 30, 1997
Matching students to lecture topics
This year, we will create a useful web site for
the course on Data Structures and Algorithms.
For the sake of uniformity, please format your
web pages exactly as in this template.
You will identify yourself at the end
of the document, so that we have a record of who did what.
It also enables other students to contact you with
possible comments or questions.
The students will be grouped in groups of 6 (depending
upon the final registration figures, this may change
slightly). Each group will be responsible for one
topic, which should roughly correspond to one lecture.
The topics are as follows:
-
#1
Abstract data types.
- #2
Models of computation. Complexity.
- #3
Analysis: O, THETA, OMEGA. Summations.
- #4
Recursion and recurrences.
- #5
Linear time selection.
- #6
Stacks, queues and lists.
- #7
Suffix trees.
- #8
Introduction to trees.
- #9
Binary search trees.
- #10
Random binary search trees and quicksort.
- #11
Game trees. Alpha-beta search.
- #12
Hashing by chaining.
- #13
Hashing by open addressing.
- #14
Hashing: overview and applications.
- #15
Priority queues: overview and applications.
- #16
Standard heaps.
- #17
Discrete event simulation.
- #18
Red-black trees.
- #19
Balanced search trees: overview.
- #20
Augmented data structures.
- #21
Coding and compression.
- #22
Huffman trees.
- #23
Lempel-Ziv compression.
- #24
Disjoint set structures.
- #25
Graphs: introduction.
- #26
Graphs: depth-first search.
- #27
Graphs: breadth-first search.
- #28
Minimal spanning trees.
- #29
Shortest path algorithms.
- #30
Directed acyclic graphs.
- #31
Lower bounds.
The due dates given with the student groups
in the student file
are almost without exception one week after the lecture.
Submit the web page via the "handin" command on binkley
as "Ass2" (click here for help).
The students should contact each other possibly by email
and organize the duties.
Of course, the tasks should be suitably split up
amomg the members of the group.
What is expected of you
The web page you create has three components:
- The lecture: please adhere as closely as possible
to what is said in class. So, follow the
structure of the lecture, reproduce all the
drawings, all the textboard material, and the
explanations and verbal comments.
During the lecture, your group should take
detailed notes.
- A creative component: you will find links
to related software, algorithms, java applets,
similar course notes elsewhere. These links
should be provided in a section entitled
"Links to related material". In addition, there
should be a section entitled "References".
This section should list books and papers
that may be consulted.
- One original java applet: this animated applet should
illustrate one algorithm, data structure or
application related to the lecture.
Place it in a section entitled "Java applet".
Place all material, including the figures,
in the body of the page so that the printed pages
have all the information. Things referred
to by pointers such as href
include links to other sources and to software,
but not essential figures or text.
As time is at a premium in this project,
you will have exactly one week to complete your web
page (by 2:30pm of the day of the lecture).
The page should be
submitted via the handin command on binkley.
For problems with submissions, send
email to Biao Hao.
it is a good idea to tell Biao Hao also that you
just handed in a web page.
You will receive feedback to enable you
to prepare a final version for submission
one week later. The students meet with the instructor
one evening (by appointment) to demonstrate
their final page.
The corrected page will be submitted and mounted
on the web site of our class.
Your mark is mainly based on the contents of the
first submission!
Ethics
Each member of the group will receive the same number of
bonus points. There are certain rules of conduct that one
must always follow:
- Always refer to sources. If you find an algorithm by
Wim Snotneus, then say so and provide sufficient
information to find that reference (a web page,
a book, an email address).
- Do not lift or copy existing java applets or
pieces of code. If a piece of code is based upon
a published program, with suitable modifications,
state so.
As our page is experimental, we would appreciate if
the URL is not divulged to the general public.
Check your work
Check your work. That is, check your web page. Test all
the pointers. Run the java applet. Repeat the procedures
for at least two different browsers.
Also, check your text for spelling errors.
Reporting algorithms
Report algorithms in the style of the Cormen,
Leiserson and Rivest book.
If there are specific examples where
the teacher uses pieces of C or PASCAL code
to make a technical point, then use those.
However, these situations are rather rare.
Mathematics
Mathematics is another matter.
You may get by by writing log(n^2) = O(log n)
or sqrt(n^8) = n^4 or sum(1 le i le n) i = n(n+1)/2,
but if you want to show prettier expressions,
you may wish to write your notes in TEX or LATEX
and then use latex2html. This
filter creates a valid html file,
in which mathematical expressions are replaced by
tiny gif files.
For various filters to and from html, check
the word processors entry in this
link.
You may also check this
link.
Java applet
Place you java applet here.
If you don't know Java, you may learn from books,
from examples on the net, from friends, and
by osmosis. As Java is a bit like an extension of C,
it should be relatively easy to absorb some things.
Remember, you do not need to learn the entire
language to write a Java applet!
You may also use JavaScript.
Furthermore, make the Java source code available
to readers by placing a link to the source file
in your page.
Do not write applets that are slide shows
or totally non-interactive animations.
The following is a list of Java related links and short
descriptions of their contents. The authorative book
on Java is "The Java Programming Language" by Ken Arnold
and James Gosling (the Java architect). There is one copy
of the book in the PSEAL library (48 hours loan).
Creating your own web page
To create your own web page, take any page from the web
and look at it carefully to detect its structure.
Then add, delete, modify and play.
At some point, you will want to know the precise rules
of the html language. Do this by consulting on-line help:
Links to related material
Many data structures and algorithms courses are ``on the web''.
Some useful pointers to get you started in your search
are given below.
| Algorithms Information and Course Materials on the Net |
Courses on algorithms.
|
| Princeton Data Structures |
Bob Sedgewick's course on data structures and algorithms at Princeton.
|
| Sedgewick's transparencies |
Bob Sedgewick's lecture notes (copies of transparencies)
on data structures and algorithms at Princeton.
For our course, of particular interest are sections 10 (tries),
11 (strings), 12 (more strings), and 13 (compression),
as this material is not covered in detail by Cormen,
Leiserson and Rivest.
|
| Sugihara's lecture notes on strings |
Sugihara's lecture notes on strings (storage, coding, compression, search)
are a nice supplement to Cormen as well. Sugihara teaches at
the University of Hawaii.
|
| Index of Sugihara's lecture notes. |
Index of Sugihara's lecture notes.
|
| Pointers to internet resources |
Sugihara's pointers to internet resources for his data structure
course.
|
| Class page for data structures at Stanford |
Leo Guibas' course on data structures and algorithms at Stanford.
|
| Computational Geometry Internet Resources |
Computational geometry links to software, course notes and resources.
|
| Java applets for five sorting algorithms |
Animation for sorting algorithms.
|
| Computational Geometry Internet Resources |
Computational geometry links to software, course notes and resources.
|
| Otfried Schwarzkopf's notes |
Otfried Schwarzkopf's data structures notes.
|
| List of courses |
A list of introductory Computer Science courses.
|
| Algorithms at UMass |
|
| CS16 at Brown |
Data structures at Brown.
|
| CS 240 at Pomona |
Data structures at Pomona.
|
| CS202 Tutorials |
|
| C++, Algorithms, and Data Structures (CS202) Notes |
|
| CS 138 at Caltech |
Data structures course at Caltech.
|
| Rivest's bibliography on algorithms |
Ron Rivest's bibliography on algorithms.
|
| Traveling Salesman Problem |
|
| MergeSort demo |
Mergesort demo from University of Toronto.
|
| Programming in C |
|
| Online University courses in Computer and Information Science |
|
| Sorting demo |
Sorting demo from UBC.
|
| DFG-Schwerpunkt "Diskrete Algorithmen" Home Page |
Discrete algorithms home page (in German).
|
| CS22 at UCSB: C and Unix |
UCSB intro course on C and UNIX.
|
References
Place your references to books, reports or papers in a separate
section. Consult the list of references in Cormen et al
for a sample format.
Web page creators
This section is intended to give readers the
opportunity to contact you, to point out errors
or omissions, to ask questions,
and to suggest improvements.
Include explanations on the role of each team member in
the creation of the web page. Something like:
``This web page was created by
John found all the web links and typed the document.
Bloody wrote the Java applet, and helped John with some
html commands.
The text is based on class notes taken by Bloody.
The figures were drawn with xfig
by John. The PostScript output was transformed into
gif files by ps2gif.''
Place a sentence or two here in the following spirit.
Last updated February 15, 1997 by
Bloody Mary.
Copyright © 1997, your names. All rights reserved.
Reproduction of all or part of this work is permitted for educational
or research use provided that this copyright notice is included in any
copy. Disclaimer: this collection of notes is experimental, and does
not serve as-is as a substitute for attendance in the actual class.