epgy:ai13:day_4

# EPGY - Day 4

## Morning

Question of the day: I am given 1000 random integers between 0 and 100. What is the least number of steps it will take you to sort the list of numbers?

House Keeping

Review

• Comparing 2 languages: (Processing and Java)
• Hash Tables: terminology
• int hashed by mod
• name hashed by sum of letters
• complex class hashed by big complex equation

Big O

• Merge Sort - recursion!

Lisp

More recursion

```(defun merge-sort (list)
(if (small list) list
(merge-lists
(merge-sort (left-half list))
(merge-sort (right-half list)))))

(defun right-half (list)
(last list (ceiling (/ (length list) 2))))
(defun left-half (list)
(ldiff list (right-half list)))

(defun small (list)
(or (null list) (null (cdr list))))

(defun merge-lists (list1 list2)
(merge 'list list1 list2 #'<))

(print (merge-sort '(2 4 1 2 4 2 3 1)))```

Deeper into Datastructs:

• Binary Trees
• BST
• Red Black Trees
• Non-Binary Trees
• 2-3 (B) Trees
• kD Tree
• Heap
• Heap Sort
• Binomial Heap
• Fibonacci Heap
• Graph Theory

NP-Complete Problems

Big O

• O(polynomial degree k) = O(n^k)
• O(1) - constant time
• query i-th element in array
• query hashmap
• O(log n)
• binary search
• O(n) - linear time
• remove element from array
• find element in linked list
• O(nlogn) -
• quicksort
• find closest pair of points
• O(2^n) - exponential time
• consider all subsets
• Sorting algos, find their Big O (Best, Worst, Average)
• insertion - B O(n), W O(n^2), A O(n^2)
• qsort - B O(nlogn), W - O(n^2), A O(nlogn)
• bogo - B O(n), W = O(inf), A O(n! * n)
• Big O for recursive algos
• fib O(2^n)
• memorization → O(n)

## Afternoon 