AP CS Assignments

Monday, February 19

Description

Finishing Binary Search Trees

Homework

Read the following sections in DSA

- Note that hash function selection and implementation is beyond the scope of this course. However, if you're interested to learn more about what goes into a hashing function, feel free to read Section 15.3 - Sample Hash Functions.
**This section is optional**.

Tuesday, February 20

Description

Introduction to Hashing

Homework

Read the following sections in DSA:

Thursday, February 22

Description

Hashing Details

Homework

Download and unzip the HashMap implementation lab.

**Read the comments carefully**to make sure you're meeting the requirements correctly, and make sure you've chosen one of the following 3 types of solution to the problem:- All HashMaps must have a
**load factor**that, once exceeded, causes the backing array to resize. - If you use
**chaining**, you must implement a**singly-linked list**from scratch**using the provided HashNode class**. The list's head should be the slot in the hash's array, and does not need a tail (it's unordered). - If you use
**buckets**, you should have a fixed bucket size and an overflow bucket at the end of the table. The table should resize appropriately if the overflow becomes full. - If you use
**probing**, you must use a non-linear collision resolution method such as quadratic, pseudo-random, or double-hashing.

**Final version is due Friday, March 2 at the start of class**.- All HashMaps must have a
- Read at least the first section of the Wikipedia entry on cryptographic hash functions.

Friday, February 23

Description

Cryptographic Hashing

Homework

- Work on HashMap lab, due next Friday at the start of class.
**However, we will work on other topics during class, so don't put this off! You should really aim to be done by Tuesday.**