Definitions List Flashcards
Algorithm
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a nite amount of time.
Big-O Notation
A function f(n) is in O(g(n)) (read “f is in big oh of g”) if there are positive numbers c and n₀ such that for all n ≥ n₀ it holds that t(n) ≤ cg(n).
Lexicographic order
In simple terms, Python sorts into Lexicographic order by default.
Let x and y be two sequences containing mutually comparable elements. Then we call x lexicographically smaller than y if either
a) up to some position i (exclusive) all elements of x and y are equal and x[i] < y[i]
b) if x is a proper prefix of y, i.e., x is shorter than y and the leading positions of y contain exactly the same element as x.
NP, complexity class
The class NP is the class of decision problems D that have a polynomial time verification algorithm A.
That is:
A accepts as inputs pairs of D-inputs x and short certificates c
For each D-input there is a certificate such that A(x, c) = True if and only if x is a yes-input of D.
Note: the length of c must be polynomially bounded in the length of x
Assertion
An assertion is a logical statement on a program (execution) state.
Computational complexity
The computational (time) complexity of an algorithm is the number of elementary steps T(n) needed for computing its output for an input of a size n.
Note: this typically is in the best or worst case
Decision Problem
A computational problem is called a decision problem if the required output for each input is Boolean (yes or no).
Inputs for which output is yes (True) are a called yes-input.
Inputs for which output is no (False) are a called no-input.
Invariant
An assertion INV is a loop invariant for a loop if the loop initialisation will yield a state in which INV holds and every execution of the loop body yields a state in which INV holds again (if run in any state in which INV holds and the loop exit condition does not hold).
What is a NP-complete?
A decision problem D is NP-complete if it is:
- In NP
and
- All problems in NP are polynomially reducible to D
Permutation
A sequence a is a permutation of a sequence b if a and b contain the same elements at the same number of positions.
P, complexity class
The class P is the class of decision problems that can be solved by a polynomial time algorithm
Polynomial time
An algorithm is called polynomial time if its worst-case time complexity is in O(p(n)) for some polynomial p
(e.g. O(n), O(n²), O(n³), etc.).
Polynomially reducible
A function exists to convert one decision problem to a different problem in polynomial time
A decision problem D₁ is polynomially reducible to a decision problem D₂ if there is a function t that transforms inputs of D₁ to inputs of D₂ such that t is computable by a polynomial time algorithm and maps yes-inputs of D₁ to yes-inputs of D₂ and no-inputs of D₁ to no-inputs of D2
Adjacency Matrix
Represntation of a graph as a 2D square matrix
An adjacency matrix is an n×n table with 0/1 entries that represent a graph G = (V, E) of n vertices by storing in row i and column j whether there is an edge between vertices i and j (0 means no edge, 1 means edge present).
[[0,1,1,0],
- *[1,0,1,1],**
- *[1,1,0,0],**
- *[0,1,0,0]]**
Adjacency List
List of lists, where each child list includes all the nodes that link to the existing node
An adjacency list is a list containing n lists that represents a graph of n vertices by storing in the i ͭ ͪ list the indices of the vertices adjacent to vertex i in order.
E.g.
[[1,2],
- *[0,2,3],**
- *[0,1],**
- *[1,3]]**
Binary Search Tree
Binary tree - all vertices to the left are smaller, all vertices to right are larger
A binary search tree is a binary tree where all vertices are labelled with mutually comparable keys and that satisfies the following order property:
for each vertex v with label k the labels of all vertices in the left subtree of v are less or equal to l
and the labels of all vertices in the right subtree of v or greater or equal to k.
Bit List
List of yes/no flags showing which options to include
A bit list is a list of 0/1 entries that represents a sub-selection of elements of some base list of options of the same length through the following convention: the i ͭ ͪ option is present in the sub-selection if the i ͭ ͪ element of the bit list is 1 (and 0 otherwise).
E.g.: bit list of length 3
[[0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0], [1,0,1], [1,1,0], [1,1,1]]
Min Heap
Type of tree where children are bigger than parent
A min heap is a binary tree where all vertices are labelled with mutually comparable keys that satisfies the following two properties:
- The tree is essentially complete, i.e., only some right-most vertices on the last level can be missing.
- The tree is partially ordered, i.e., for each vertex v with label k, the labels of each of its children are greater or equal to k.
1
/ \
2 3
/ \ / \
4 5 9 4
Vertex Cover
A set of nodes that includes at least one end of every link
A vertex cover is a subset of vertices C of a graph such that for every edge of the graph either of the two end points is in C.
○─●─┬○ or ●─●─┬○
└●┘ └○ └○┘ └○
not ○─●─┬○
└○┘ └○
