There will be two on-line exams where students must write program to
solve some problem related to data structure. The exam will be
held in the laboratory or the computer center of the faculty of
engineering. Students are advised to practice their programming
skill prior to sit in these exams. The environment will be similar to
Java programming that students took in the first year.
Reference Textbook
Mark Allen Weiss, Data Structures and Algorithm Analysis in Java
(Second Edition), Addison-Wesley, 2007, ISBN: 0-321-37013-9.
see author's home page: http://www.cs.fiu.edu/~weiss/
for errata and source code.
5 Sept 2008
Make amend to my rule set so that the infix-to-postfix
algorithm work
correctly. Hand-in not later than next Wednesday (10 Sept 2008).
12 Sept 2008
The program postfix_to_tree used iteration (while). Change it to
use recursion.
22 Oct 2008
Hash
Buid a hash table of the student names. Assuming your class list
contains at most 200 names and we are using only the first name as
key. Use open addressing with linear probing. Create your
own hash function.
1) Count how many collision occurs while inserting all names.
Vary table size (remember that the size must be a prime number to
evenly distribute the key throughout the table).
2) Now make the size small so that load factor is high. Then
perform rehashing by double the table size. Count the number of
collision both before and after rehashing.
Please hand in the following item
a) a report of the experiment, explain what happens and why.
b) a listing of the source code of your experiment, explain briefly
what the code is doing and how.
Please email your submission to data-2143203@hotmail.com
with the title "hash". Remember to include your id. and
name. Copying other people homework is considered a serious
offend and is against the rule of the class. Penalty including
failing the subject. Hand in by 29 Oct 2008.
12 Nov 2008
Sorting
Change the example heapSort to use
(min)heap. Using a temporary array instead of replacing the last
item.