# 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<br>

## 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.