Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

remember for ita > FUCK > Flashcards

FUCK Flashcards

1
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
2
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
3
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
4
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
5
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
6
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
7
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
8
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
9
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
10
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
11
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
12
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
13
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
14
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
15
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
16
Q

Circuit

A

A closed trail

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
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
18
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
19
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
20
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
21
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
22
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
23
Q

Tree Definition

A

A cycle free connected graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
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
25
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
26
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
27
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
28
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

29
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

30
Q

AVL Tree

A

When every vertex of a binary tree is height balanced

31
Q

Collision in AVL Tree

A

Two keys mapped to same position

32
Q

Hashing

A

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

33
Q

Load Factor

A

Alpha = num of keys / size of hash table

34
Q

Probing

A

Checking if hash table position is free

35
Q

Chaining

A

All keys mapped to same position sorted in a linked list

36
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

37
Q

Linear Probing Delete

A

Search for key and mark key as deleted

38
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

39
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

40
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

41
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

42
Q

Adjacency List

A

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

43
Q

Adjacency Matrix

A

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

For dense graph

44
Q

Incidence List

A

One list for every vertex listing all incidents

45
Q

Linked List

A

Keeps references to head and tail

46
Q

A queue

A

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

47
Q

A Stack

A

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

48
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

49
Q

Euler Circuit

A

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

50
Q

Euler Trail

A

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

51
Q

A forest

A

A graph that has no cycles but is not necessarily connected

52
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

53
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

54
Q

Dynamic Partition

A

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

55
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

56
Q

Priority queue

A

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

57
Q

Iterative improvement

A

Starts with feasible solution and improves over iterations

58
Q

Dynamic Programming

A

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

59
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

60
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

61
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
62
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

63
Q

Single pair

A

Shortest path between pair of vertices

64
Q

Single source

A

All shortest paths from source to other vertices

65
Q

Single destination

A

All shortest paths ending to some vertex from all other vertices

66
Q

All pairs

A

Shortest path between every pair of vertices

67
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

68
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

69
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

remember for ita (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions