Brainscape's Knowledge GenomeTM

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


See full index

LPC 2019 Information Technology > BrainScapeDeck_IT_1.1_20190609_215319 > Flashcards

BrainScapeDeck_IT_1.1_20190609_215319 Flashcards

1
Q

Definition

What is an algorithm?

Terminology

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Definition

What is an assertion?

Terminology

A

An assertion is a logical statement on a program (execution) state.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Definition

What is Big-O notation?

Terminology

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Definition

What is computational complexity?

Terminology

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Definition

What is the Decision Problem?

Terminology

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Definition

What is Invariant?

Terminology

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Definition

What is Lexicographic order?

Terminology

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Definition

What are ‘NP, complexity class’?

Terminology

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Definition

What is NP-complete?

Terminology

A

A decision problem D is NP-complete if it is in NP and all problems in NP are polynomially reducible to D.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Definition

What is Permutation?

Terminology

A

A sequence a is a permutation of a sequence b if a and b contain the same elements at the same number of positions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Definition

What are ‘P, complexity class’?

Terminology

A

The class P is the class of decision problems that can be solved by a polynomial time algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Definition

What is Polynomial time?

Terminology

A

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.).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Definition

What is Polynomially reducible?

Terminology

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Definition

What is an Adjacency Matrix?

Data structure

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Definition

What is an Adjacency List?

Data structure

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Definition

What is Binary Search Tree?

Data structure

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Definition

What is a Bit List?

Data structure

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Definition

What is a Heap?

Data structure

A

A (min) heap is a binary tree where all vertices are labelled with mutually comparable keys that satisfies the following two properties:

  1. The tree is essentially complete, i.e., only some right-most vertices on the last level can be missing.
  2. 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.
19
Q

Definition

What is a Pair-of-children List?

Data structure

A

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).

20
Q

Definition

What is a Parent List?

Data structure

A

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.

21
Q

Definition

What is a Queue?

Data structure

A

A queue is a linear data structure in which elements are added only to the back (enqueue) and removed only from the front (dequeue).

22
Q

Definition

What is a Stack?

Data structure

A

A stack is a linear data structure in which elements are added (push) and removed (pop) only from the back.

23
Q

Definition

What is a Table?

Data structure

A

A table is a data structure that organises a set of values along the two dimensions of rows and columns.

24
Q

Definition

What is a Clique?

Graph definitons

A

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).

25
Q

Definition

What is a ‘Connected’ graph?

Graph definitons

A

A graph is called connected if it contains a path between any two of its vertices.

26
Q

Definition

What is a Cycle?

Graph definitons

A

A cycle is a path P = [v1, . . . , vk] in a graph such that v1 = vk

27
Q

Definition

What is an Independent Set?

Graph definitons

A

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).

28
Q

Definition

What is a Hamiltonian Cycle?

Graph definitons

A

A Hamiltonian Cycle of a graph is a cycle that contains all vertices of that graph.

29
Q

Definition

What is a Path?

Graph definitons

A

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).

30
Q

Definition

What is a Spanning Tree?

Graph definitons

A

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.

31
Q

Definition

What is a Simple graph?

Graph definitons

A

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.

32
Q

Definition

What is a Tree?

Rooted Trees

A

A tree is a graph that is connected and acyclic (does not contain any cycles).

33
Q

Definition

What is a Vertex Cover?

Rooted Trees

A

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.

34
Q

Definition

What is a Binary Tree?

Rooted Trees

A

A binary tree is a rooted tree where each vertex has at most two children, a left child and a right child.

35
Q

Definition

What is a Child vertex?

Rooted Trees

A

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.

36
Q

Definition

What is a Complete tree?

Rooted Trees

A

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).

37
Q

Definition

What is the Height of a tree?

Rooted Trees

A

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).

38
Q

Definition

What is an Inner Vertex?

Rooted Trees

A

A vertex in a rooted tree is called an inner vertex if it has at least one child.

39
Q

Definition

What is a Leaf?

Rooted Trees

A

A vertex in a rooted tree is called a leaf it it does not have any children.

40
Q

Definition

What is the Level of a vertex?

Rooted Trees

A

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.

41
Q

Definition

What is a Node?

Rooted Trees

A

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.

42
Q

Definition

What is a Parent vertex?

Rooted Trees

A

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).

43
Q

Definition

What is a Perfect tree?

Rooted Trees

A

A binary tree is called perfect if all of its inner vertices have exactly two children and all leafs are on the same level.

44
Q

Definition

What is a Path Length?

Graph definitons

A

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).

LPC 2019 Information Technology (1 decks)

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