HashTables

• behaves like a python dictionary
• look up by key instead of index
• static chaining - collisions become a linked list
• applications: associative array, word cloud, dictionary

4 methods: hash, insert, find, remove

• hash: will take in key an convert it into integer

  
  # this is a super simple version thats uniform distribution
  # for each character in key:
  hashsum += (char_index + key_length)^ char_code
  hashsum = hashsum % capacity
  return hashsum
  # hashsum must be between 0 and length of internal array
  

• insert:

  • increment size of ht
  • compute index of key with hash function
  • if bucket at index is empty, create new node and add it
  • if collision, iterate to end of linked list and add new node

• find: retrieve value under certain key

  • compute index for provided key using hash function
  • go to bucket for that index
  • iterate nodes in that linked list until key is found or until end of list
  • return value of found node, or None if not found

• remove:

  • compute hash for the key
  • iterate linked list, continue until end or key is found
  • if key isn't found return None
  • or, remove node from linked list and return node value

Dynamic Programming

• way of making algo more efficient by storing intermediate results

  3 ways

  1. Recursion
  2. Store (Memoize)
  3. Bottom-Up

Recursion

def fib(n):
	if n == 1 or n == 2:
		result = 1
	else:
		result = fib(n-1) + fib(n-2)
	return result

# O(2^n)

Memoization

• store return values in array once we compute so we can use that same value when you see it again

def fib(n, memo):
	if memo[n] != null:
		return memo[n]
	if n == 1 or n == 2:
		result = 1
	else:
		result = fib(n-1) + fib(n-2)
	memo[n] = result
	return result
		
# complexity: T(n) = # calls * t <= (2n + 1) * O(1)
# = O(n)
# t = time to execute call

Bottom-Up

def fib_bottomup(n):
	if n == 1 or n == 2:
		return 1
	bottom_up = new int[n+1]
	bottom_up[1] = 1
	bottom_up[2] = 1
	for i from 3 upto n:
		bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
	return bottom_up[i]
##O(n)

Graphs

• adjacency matrix is a 2D array, always |V|^2