BrainScapeDeck_IT_1.1_20190609_215319 Flashcards
Definition
What is an algorithm?
Terminology
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 finite amount of time.
Definition
What is an assertion?
Terminology
An assertion is a logical statement on a program (execution) state.
Definition
What is Big-O notation?
Terminology
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).
Definition
What is computational complexity?
Terminology
The (best-case/worst-case) 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 (in the best/worst case).
Definition
What is the Decision Problem?
Terminology
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.
Definition
What is Invariant?
Terminology
An assertion INV is a loop invariant for a loop if the loop initialisa- tion 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).
Definition
What is Lexicographic order?
Terminology
Let x and y be two sequences containing mutually com- parable 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] or 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.
Definition
What are ‘NP, complexity class’?
Terminology
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 (the length of c must be polynomially bounded in the length of x), and for each D-input x there is a certificate c such that A(x, c) = True if and only if x is a yes-input of D.
Definition
What is NP-complete?
Terminology
A decision problem D is NP-complete if it is in NP and all problems in NP are polynomially reducible to D.
Definition
What is Permutation?
Terminology
A sequence a is a permutation of a sequence b if a and b contain the same elements at the same number of positions.
Definition
What are ‘P, complexity class’?
Terminology
The class P is the class of decision problems that can be solved by a polynomial time algorithm
Definition
What is Polynomial time?
Terminology
An algorithm is called polynomial time if its worst-case time complexity T (n) is in O(p(n)) for some polynomial p (i.e., p(n) = n, p(n) = n², p(n) = n³, etc.).
Definition
What is Polynomially reducible?
Terminology
A decision problem D1 is polynomially reducible to a decision problem D2 if there is a function t that transforms inputs of D1 to inputs of D2 such that t is computable by a polynomial time algorithm and maps yes-inputs of D1 to yes-inputs of D2 and no-inputs of D1 to no-inputs of D2.
Definition
What is an Adjacency Matrix?
Data structure
An adjacency matrix is an n × n table with 0/1 entries that represent a graph tt = (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).
Definition
What is an Adjacency List?
Data structure
An adjacency list is a list containing n lists that represents a graph of n vertices by storing in the i-th list the indices of the vertices adjacent to vertex i in order.
Definition
What is Binary Search Tree?
Data structure
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.
Definition
What is a Bit List?
Data structure
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 fol- lowing convention: the i-th option is present in the sub-selection if the i-th element of the bit list is 1 (and 0 otherwise).
Definition
What is a Heap?
Data structure
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.
Definition
What is a Pair-of-children List?
Data structure
A pair-of-children list represents a binary tree as a list of length equal to the number of vertices where index i contains a pair (l, r) referring to the indices of the left and the right child of i, respectively (or a special value if a child is missing; in Python we use None for this case).
Definition
What is a Parent List?
Data structure
A parent list represents a rooted tree as a list of length equal to the number of vertices where the parent of vertex i is stored at index i of the list.
Definition
What is a Queue?
Data structure
A queue is a linear data structure in which elements are added only to the back (enqueue) and removed only from the front (dequeue).
Definition
What is a Stack?
Data structure
A stack is a linear data structure in which elements are added (push) and removed (pop) only from the back.
Definition
What is a Table?
Data structure
A table is a data structure that organises a set of values along the two dimensions of rows and columns.
Definition
What is a Clique?
Graph definitons
A clique is a subset of vertices C of a graph such that for every two distinct vertices v, w from C there is an edge between v and w (cf. inde- pendent set).
Definition
What is a ‘Connected’ graph?
Graph definitons
A graph is called connected if it contains a path between any two of its vertices.
Definition
What is a Cycle?
Graph definitons
A cycle is a path P = [v1, . . . , vk] in a graph such that v1 = vk
Definition
What is an Independent Set?
Graph definitons
An independent set is a subset of vertices C of a graph such that for every two distinct vertices v, w from C there is no edge between v and w (cf. clique).
Definition
What is a Hamiltonian Cycle?
Graph definitons
A Hamiltonian Cycle of a graph is a cycle that contains all vertices of that graph.
Definition
What is a Path?
Graph definitons
A path is a non-self-intersecting sequence P = [v1, . . . , vk] of successively connected vertices in a graph tt = (V, E). That is, for all i from 1 to k we have that (vi, vi+1) is in E and additionally for all j from i + 1 to k − 1 we have that vi = vj (that means a vertex is only allowed to show up twice in the path if it is the start and end vertex, in which case we refer to the path as a cycle).
Definition
What is a Spanning Tree?
Graph definitons
A spanning tree of a graph tt = (V, E) is a subgraph T = (V, F ) of tt that contains all vertices of tt and that is a tree.
Definition
What is a Simple graph?
Graph definitons
A graph is called simple if it does not contain loops or parallel edges. In this unit we usually assume graphs to be simple unless we explicitly mention otherwise.
Definition
What is a Tree?
Rooted Trees
A tree is a graph that is connected and acyclic (does not contain any cycles).
Definition
What is a Vertex Cover?
Rooted Trees
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.
Definition
What is a Binary Tree?
Rooted Trees
A binary tree is a rooted tree where each vertex has at most two children, a left child and a right child.
Definition
What is a Child vertex?
Rooted Trees
In a tree with root r, a vertex v is called the child of another vertex p if
p is the predecessor of v on the unique path from v to the root r.
Definition
What is a Complete tree?
Rooted Trees
A rooted tree is called complete (or essentially complete) if only some right-most vertices on the last level are missing (when compared to a perfect tree).
Definition
What is the Height of a tree?
Rooted Trees
The height of a rooted tree is the maximum length of a path from the root to a leaf (or −1 if the tree is empty).
Definition
What is an Inner Vertex?
Rooted Trees
A vertex in a rooted tree is called an inner vertex if it has at least one child.
Definition
What is a Leaf?
Rooted Trees
A vertex in a rooted tree is called a leaf it it does not have any children.
Definition
What is the Level of a vertex?
Rooted Trees
The level of a vertex v in a tree with root r is the length of the unique path from v to r. This implies that the level of r is 0.
Definition
What is a Node?
Rooted Trees
The term node is a synonym for the term vertex which is often used in the context of rooted trees. To avoid confusion, we avoid using this synonym in this unit.
Definition
What is a Parent vertex?
Rooted Trees
The parent of a vertex v in a tree with root r is the predecessor of v on the unique path from v to the root r (the root itself does not have a parent).
Definition
What is a Perfect tree?
Rooted Trees
A binary tree is called perfect if all of its inner vertices have exactly two children and all leafs are on the same level.
Definition
What is a Path Length?
Graph definitons
In an unweighted graph the length P is simply the number of contained edges k1, which is the same as assuming that all edge weights are equal to 1.
The length of a path P = [v1, . . . , vk] in an edge-weighted graph tt = (V, E, w) is the sum of all edge weights along the path, i.e., w(v1, v2)+. . . + w(vk-1, vk).
