FUCK Flashcards by Pep Sus | Brainscape

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

Q

Breadth first search

A

Explores all in the same level

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Binary Search Tree

A

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

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Insert function

A

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

How well did you know this?

1

Not at all

2

3

4

5

Perfectly

Q

Delete function

A

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

Q

Is member search function

A

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

Q

AVL Tree

A

When every vertex of a binary tree is height balanced

Q

Collision in AVL Tree

A

Two keys mapped to same position

Q

Hashing

A

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

Q

Load Factor

A

Alpha = num of keys / size of hash table

Q

Probing

A

Checking if hash table position is free

Q

Chaining

A

All keys mapped to same position sorted in a linked list

Q

Linear Probing Search

A

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

Q

Linear Probing Delete

A

Search for key and mark key as deleted

Q

Linear Probing Insert

A

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

Q

Linear Probing A/D

A

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

Q

Quadratic Probing

A

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

Q

Double Hashing

A

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

Q

Adjacency List

A

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

Q

Adjacency Matrix

A

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

For dense graph

Q

Incidence List

A

One list for every vertex listing all incidents

Q

Linked List

A

Keeps references to head and tail

Q

A queue

A

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

Q

A Stack

A

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

Q

Hierholzer

A

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

Q

Euler Circuit

A

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

Q

Euler Trail

A

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

Q

A forest

A

A graph that has no cycles but is not necessarily connected

Q

Spanning Subgraph

A

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

Q

Kruskal’s Algorithm

A

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

Q

Dynamic Partition

A

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

Q

Prim’s Algorithm

A

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

Q

Priority queue

A

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

Q

Iterative improvement

A

Starts with feasible solution and improves over iterations

Q

Dynamic Programming

A

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

Q

Coin row problem

A

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

Q

Robot coin problem

A

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

Q

Dijkstra’s Algorithm

A

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

Q

Bellman Ford

A

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

Q

Single pair

A

Shortest path between pair of vertices

Q

Single source

A

All shortest paths from source to other vertices

Q

Single destination

A

All shortest paths ending to some vertex from all other vertices

Q

All pairs

A

Shortest path between every pair of vertices

Q

Tree rebalance simple rotation

A

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

Q

Tree rebalance double rotation

A

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

Q

Amortised Analysis

A

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