That Stuff

Question 1

Binary trees
BST
AVL

Answer 1

- 2 children
- Left < x < Right
- Height Limit

Question 2

Depth

Answer 2

Top down

Question 3

Height

Answer 3

Bottom up

Question 4

Single Rotation

Answer 4

Move subtree

Question 5

Double rotation

Answer 5

• X and grandchild
• X and child

Question 6

B Trees

Answer 6

- Path is like streets to data
- Data is in leaves
- O(N log N)

Question 7

Load Factor

Answer 7

- # of Items / Table Size
- O(N/M)
- Rehash if λ >= 3/4

Question 8

Binary Heap / Priority Queue

Answer 8

- A full binary tree
- [2i] - [i/2] - [2i+1]
-perlocateDown

Question 9

d Heaps

Answer 9

-Heap with d children
- Insert O(log_d N)
- Delete d-1 comparions

Question 10

Merge Heaps Types

Answer 10

Leftist < Skew < Binomial

Question 11

Insertion Sort

Answer 11

- O(N) to O(N^2)
- Read i, insert, read i,…
- N < 20

Question 12

Shell Sort

Answer 12

- Long one
- Distance = Lenght/2
- O(N^3/2) to O(N^2)

Question 13

Merge Sort

Answer 13

- Split, Combine
- O(N log N)

Question 14

Quick Sort

Answer 14

- Pivot = 3 median
- Smaller < x < Larger
- O(N logN) to O(N^2)

Question 15

Partitioning

Answer 15

Compare two outer pivots and move inwards

Question 16

Connected Graph

Answer 16

All nodes have an edge

Question 17

Adjacent Matrix

Answer 17

A[i][j]
i is adj to j
Dense graphs
Ω(V^2)

Question 18

Complete Graph

Answer 18

Every node is linked

Question 19

Vertex count

Answer 19

Directed 0 < E < V(V-1)
Undirected 0 < E < (V(V-1)) / 2
Sparse E = V
Dense E = V^2

Question 20

Adjecent List

Answer 20

Like Heap
Store undirected nodes twice
Sparse graphs
Ω(V + E)

Question 21

Topological Sort

Answer 21

- Find vertex with indegree = 0
- Print v
- Delete v + edges
- Queue children if indegree = 0

Question 22

Hamiltonian Cycle

Answer 22

Visits every vertex once

Question 23

Path Runtime

Answer 23

+ O(E logV)
- O(EV)

Question 24

P Complexity

Answer 24

Easy to solve and confirm

Question 25

NP Complexity

Answer 25

Difficult to solve, easy to confirm

Question 26

EXP Complexity

Answer 26

Difficult to solve and confirm

Question 27

B Trees
d Heaps

Answer 27

- O(N logN)
- O(log_d N)

Question 28

Insert Sort
Merge Sort
Shell Sort
Quick Sort

Answer 28

- O(N) to O(N^2)
- O(N logN)
- O(N^3/2) to O(N^2)
- O(N logN) to O(N^2)

Question 29

Adj Matrix
Adj List

Answer 29

- Ω(V^2)
- Ω(V + E)

Question 30

Path Runtime

Answer 30

+ O(E logV)
- O(EV)