Monash University > CSSE > CSE1303 > Part A > Tutorials > Tutorial A6

CSE1303 Computer Science
Summer Semester, 2003
Part A
Tutorial A6 : Hash Tables, Recursive Sorts and Revision

This tute covers material from lectures A14 to A17.

There may not be time in the tutorial to cover all of these questions. Attempt at least the ones marked with an asterisk before the tutorial; these are the ones that will be focussed on during the class. If you have specific questions about unmarked questions, you can ask the tutor about them during the tutorial. If you want further revision questions, suggestions of questions from the textbooks are provided at the end of the tutorial sheet.

---

Note: The purpose of tutorials is not simply to give you the answers to these questions! (Solutions will be released in about a week online, so if all you want is the answers, there are easier ways.)

---

* Exercise 1

Using the following function:

int hash(char* s)
{
   return (s[0]-'A') % 11;
}

and linear probing, calculate the hash value of the following names and insert them into a Hash Table of size 11.

Eva, Amy, Tim, Ron, Jan, Kim, Dot, Ann, Jim, Jon

* Exercise 2

Repeat Exercise 2 using Chaining instead of linear probing.

* Exercise 3

For Exercise 1, illustrate what happens, after you have inserted all the names, when you search for the names Jim, Jon and Joe.

Exercise 4

Show the steps taken to sort the following array:

3

9

1

12

8

4

10

2

1. Using mergesort
2. Using quicksort

* EXAM REVISION

Attempt all the questions on the sample exam.

ADDITIONAL QUESTIONS

Kruse et al. 2^nd Edition
    Exercises 7.6 E1, E2, E3
    Exercises 8.6 E6 a, b, c, d, E8, E11

Additional Reading for Revision:

R. Sedgwick - Algorithms in C
    Chapters 3, 4, 5, 9, 12, 14, 16

Deitel & Deitel - C: How to Program, 2^nd edition
    Chapters 1, 2, 5, 6, 7, 8, 9, 10, 11, 12

Kruse et al. - Data Structures & Program Design in C, 2^nd edition
    Chapters 1, 2, 3, 4, 5, 6 (6.1 - 6.4), 7, (7.1, 7.2, 7.6 - 7.8), 8 (8.6, 8.7), 9 (9.1 - 9.3), 12 (12.2 - 12.4), Appendix C

[ Top | Home ]

Last modified: Tuesday 02 December 2003 22:29:33