FUCK Flashcards by Pep Sus

Q

What is ln(e^n) and e^ln(n) =

A

n

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Log Rules

A

Product: loga(xy) = loga(x) + loga(y)
Quotient: loga(x/y) = loga(x) - loga(y)
Power: loga(x^y) = yloga(x)

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Quick Sort

A

Divides problem into two parts. Pick a pivot to split elements left and right if smaller or larger

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Merge Sort

A

Divides until length 1 merges and sorts list recombining them

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Big O Equation

A

G(n) less than or equal to c * f(n)

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Big Omega Equation

A

G(n) greater than or equal to c * f(n)

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Theta Equation

A

G is in Big O(f) and Big Omega(f)

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Small o Equation

A

Lim
G(n) / f(n) = 0
N -> Infinity

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Small Omega Equation

A

Lim
F(n) / g(n) = 0
N -> Infinity

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Interpretation

A

Big O - G does not grow sig faster than f
Big Omega - G does not grow sig slower than f
Theta - G grows as fast as f
Small o - g grows sig slower than f
Small omega - g grows sig faster than f

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Graph Definition

A

Undirected graph consists of vertex set and edge set where every edge connects two vertices referred to as nodes

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Edge Definition

A

An edge connects two vertices, each vertex being an endpoint

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Walk

A

Sequence of edges and vertices and every edge has both endpoints. If first vertex = last vertex the walk is closed

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Trail

A

A trail is a walk where all edges are distinct

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Path

A

A walk in which all vertices are distinct

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Circuit

A

A closed trail

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Cycle

A

A circuit where only the first and last vertex are equal

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

What is an inner node

A

Any node with children

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Height of a tree

A

Length of longest path to from root to any leaf

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Depth of a node

A

Length of path to its root

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Height of a node

A

Length of longest downward path to a leaf from that node

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Level of a tree

A

Level starts from 0 at root and increases for each level of children

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Tree Definition

A

A cycle free connected graph

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Depth first search

A

Searches “deeper” in the graph when possible exploring subtrees on the right first

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Breadth first search

Explores all in the same level

Binary Search Tree

Stores keys in the vertices, key stored must be greater than every key in left sub and smaller than every key in right sub

Insert function

Search for key, if not found keep going till vertex found with no children add left or right accordingly

Delete function

If a key is a leaf, remove, if a single child remove by connecting subtree with parent. If has sibling replace by smallest vertex in subtree and attach other subtree to parent

Is member search function

Start at root, if root = done If smaller go left or else go right Repeat till key is found or return null

AVL Tree

When every vertex of a binary tree is height balanced

Collision in AVL Tree

Two keys mapped to same position

Hashing

Use an unsorted array larger than number of keys. Use hash function to map key to the array

Load Factor

Alpha = num of keys / size of hash table

Probing

Checking if hash table position is free

Chaining

All keys mapped to same position sorted in a linked list

Linear Probing Search

Try to map k If position free, element not in table If contains k, search successful If contains different key check every next position

Linear Probing Delete

Search for key and mark key as deleted

Linear Probing Insert

Try to map k If position free insert k If contains k stop If contains different key try for every next position

Linear Probing A/D

A: No external data needed, cache friendly D: Access time bad for alpha > 0.7, new hash table must be created if full and insert all keys, keys should not or rarely be deleted

Quadratic Probing

Similar to linear probing but different hash function: h(k,i) = h(k) +x mod n X goes up in squares, +1 -1 +4 etc. Access time bad for alpha > 0.8 Between LP and chaining for cache

Double Hashing

Like linear but uses second hash function h(k,i) = ( h(k) + i*h'(k) )mod n Access time bad for alpha > 0.8 Between QP and chain for cache

Adjacency List

Every vertex has a list if vertices to which it is adjacent to [1][] [3][] [4][] For sparse graph

Adjacency Matrix

Makes matrix for all nodes with 1 for an edge, 0 otherwise For dense graph

Incidence List

One list for every vertex listing all incidents

Linked List

Keeps references to head and tail

A queue

Fifo structure Enqueue: Add to Tail Dequeue: Remove from head

A Stack

Lifo structure Push: Add to head Pop: Remove from head Peek: Access head element w/o removing

Hierholzer

Start at some vertex, go through graph till reaching root. Start second circuit for incident edge to starting vertex using only unused edges. Combine for euler circuit

Euler Circuit

Every edge visited exactly once in a circuit, vertices can be repeated. Makes graph Eulerian Every vertex needs even degree

Euler Trail

Like Circuit but does not have end return to root. Makes graph semi eulerian

A forest

A graph that has no cycles but is not necessarily connected

Spanning Subgraph

Contains all vertices of original graph but does not have to be connected, no edges can be added that do not already exist

Kruskal's Algorithm

Start with empty set Add next edge of minimal weight from graph to set without making cycles Stop once connected graph is reached Requires dynamic partition

Dynamic Partition

Makeset() creates one element set Find() returns subset containing element Union() constructs union of disjoint subsets

Prim's Algorithm

Pick arbitrary vertex as start Select edge of minimum weight from neighbour not already connected Repeat until every vertex in tree Requires Priority Queue

Priority queue

Extractmin - returns smallest element Insert - inserts element isEmpty - checks if data structure is empty

Iterative improvement

Starts with feasible solution and improves over iterations

Dynamic Programming

Subproblems are not independant solving every subproblem and storing answer in a table or array, no recomputing

Coin row problem

Row of n coins, find max money not picking up adjacent coins Divide row into two, f(n, n+2, etc.) and f(n+1, n+3 etc.) See which totals more

Robot coin problem

Coins placed in n*m board robot in upper left cell has to collect as much money as possible one step at a time Make matrix showing current value and take max from left or above to pick a value to take precedent

Dijkstra's Algorithm

``` Start from s Keep data structure with all vertices not added Add new vertex with minimal distance Update v with distance and predecessor Cant use negative weights ```

Bellman Ford

For negative edge weights but not as fast as dijkstra Has distances and predecessors If distance to starting vertex + edge weight is smaller than distance to destination vertex

Single pair

Shortest path between pair of vertices

Single source

All shortest paths from source to other vertices

Single destination

All shortest paths ending to some vertex from all other vertices

All pairs

Shortest path between every pair of vertices

Tree rebalance simple rotation

``` If parent unbalanced, Child becomes new root. Child's right sub becomes parent's left sub. Parent becomes child on right. Child's left sub remains the same ``` Simple if outer subtree taller

Tree rebalance double rotation

``` If parent unbalanced Child's child becomes root of parent C1 becomes left sub of c2 C2 right sub becomes parent left sub C2 becomes new root ``` Double if inner subtree taller

Amortised Analysis

Analyzing an algorithm's complexity or how much of a resource, or time/memory it takez to execute as sometimes worst case is too extreme