Homework Assignments

Week 1

Monday

Implement a HashTable. Resolve collisions with linear chaining using linked list. No need to implement linked list (assume it's already there). Assume keys and values to be Integers. The class should have the following:

• count

• isEmpty()

• hash(x) // returns hash value of x

• set(key, value)

• get(key) // returns value for key. Throw exception or return NULL if it doesn't exist

Wednesday

Implement a Trie (aka Prefix Tree)

Class Trie {}

• trie.insert(word) // inserts word into trie

• trie.delete(word) // deletes word from trie

• trie.contains(word) // returns true if word is in the trie, false if it doesn't exist

• trie.isPrefix(word) // returns true if word is a prefix, false if it isn't

• trie.allWordsWithPrefix(word) // returns list of words that have the given prefix

Week 2

Monday

Implement a singly linked list. Class should contain:

• removeFirst() // removes first element in the linked list

• removeLast() // removes last element in the linked list

• removeAt(Location) // removes node at location

• insert(Node, Location) // inserts node at specific location

• reverse() // reverses a linked list. Do it in O(1) space

Wednesday

Graphs, graphs, and graphs!

• Implement Depth First Search and Breath First Search using Adjacency matrix.

• Write a function to count connected components in a graph

• Write a function that takes in a directed graph as input. It should output true if any cycle exists and false if no cycles exist.