Algorithms and Complexity

Question 1

A procedure for solving a problem that consists of input, output and a finite sequence of steps that converts the input to the output

Answer 1

Algorithm

Question 2

The average number of comparisons or arithmetic operations needed when a problem is solved using the algorithm

Answer 2

average case time complexity

of an algorithm

Question 3

f = O(g); there exists a positive constant C and a positive integer k such that f(n) <= Cg(n) for every integer n >= k

Answer 3

big-O

Question 4

f=Q(g): there exists a positive constant C and a positive integer k such that f(n) <= Cg(n) for every integer n>= k

Answer 4

big-theta

Question 5

an algorithm that determines whether a specified number is one of the numbers in a sequence of distinct numbers by successfully dividing the sequence in half

Answer 5

Binary Search

Question 6

an algorithm that sorts the terms in a sequence of numbers listed in a column, so that the largest numbers successively flow to the bottom, resulting in a nondecreasing sequence

Answer 6

Bubble Sort

Question 7

the amount of space and time needed to execute the algorithm

Answer 7

complexity of an algorithm

Question 8

time complexity of an algorithm is O(1)

Answer 8

constant time complexity

Question 9

an algorithm that sorts the terms in a sequence of numbers so that the terms are successfully inserted in a place in the sequence until a nondecreasing sequence results

Answer 9

Insert sort algorithm

Question 10

An algorithm that determines whether a specified number appears in a sequence by successively proceeding through the sequence term by term

Answer 10

Linear search algorithm

Question 11

the time complexity of the algorithm is O(n)

Answer 11

linear time complexity

Question 12

An algorithm that sorts the terms in a sequence of numbers by successively dividing the sequence and the resulting subsequences in half and them merging the sorted subsequences until a nondecreasing sequence results

Answer 12

Merge sort algorithm

Question 13

time complexity of the algorithm is Q(f(n)) for some polynomial f(n)

Answer 13

Polynomial time complexity

Question 14

time complexity of the algorithm is O(n^2)

Answer 14

quadratic tie complexity

Question 15

the amount of space required by a given algorithm to solve a problem

Answer 15

time complexity

Question 16

the maximum number of comparisons or arithmetic operations that can occur when a problem is solved using the algorithm

Answer 16

worst case time complexity

Question 17

the expansion of a positive integer n in base b, where b >= 2 and n = a_k * b^k + a_k-1 * b^k+1 + . . . + a_1 * b + a_0 * b^0

Answer 17

base b expansion

Question 18

the expansion of an integer in base 2

Answer 18

binary expansion

Question 19

a decryption technique in which each letter in the plaintext is replaced by a letter obtained by rotating the letter a fixed number of positions

Answer 19

Ceaser shift

Question 20

an integer that divides both a and b

Answer 20

common divisor

of a and b

Question 21

an integer that is multiple of a and b

Answer 21

common multiple

of a and b

Question 22

an integer greater than 1 that is not prime

Answer 22

composite

Question 23

a == b (mod n): n | (a-b)

Answer 23

congruence

a is congruent to b modulo n

Question 24

the study of sending and receiving secret messages

Answer 24

cryptography

Question 25

the study of systems for secure communications

Answer 25

cryptology

Question 26

systems for secure communications

Answer 26

cryptosystem

Question 27

a function that is one-to-one and onto

Answer 27

bijective function

Question 28

|A| = |B| | two sets A and B have the same cardinality

Answer 28

Cardinalities of two sets

Question 29

the smallest integer greater than or equal to x

Answer 29

ceiling function

Question 30

the set B where f is a function from A to B

Answer 30

codomain

Question 31

a+bi for some real numbers a and b where I = sqrt(-1)

Answer 31

complex number

Question 32

g of f: for functions f : A -> B and g: B-> C, the composition g of f: A-> C is the function defined by g(f(x)) for each x subset A

Answer 32

composition

Question 33

a consequence of another result

Answer 33

corollary

Question 34

a set A such that |A| = |N|

Answer 34

``` denumerable set (countably infinite set) ```

Question 35

the set A where fi s a function from A to B

Answer 35

domain

Question 36

the set of all elements in A that is related to a by R

Answer 36

``` equivalence class resulting from an equivalence relation R on A, |a| ```

Question 37

a reflexive, symmetric, and transitive relation on a set

Answer 37

equivalence relation

Question 38

the largest integer less than or equal to x

Answer 38

floor function

Question 39

an assignment of a unique element of B to each element of A

Answer 39

``` function (from A to B) f: A -> B ```

Question 40

the set of points (x,y) in the Cartesian plane for which x subset A, y subset B, and y = f(x)

Answer 40

graph

Question 41

b is an image of a under f: b = f(a)

Answer 41

image

Question 42

a function from A to B such that distinct elements of A have distinct images in B

Answer 42

injective function | one-to-one

Question 43

a bijective function

Answer 43

one-to-one correspondence

Question 44

a function from A to B such that distinct elements of A have distinct images in B

Answer 44

one-to-one function

Question 45

a function from A to B such that every element of B is the image of some element of A

Answer 45

onto function

Question 46

a bijective function from A to A

Answer 46

permutation | on a nonempty set A

Question 47

the set of all images of f

Answer 47

range

Question 48

a relation R on a set S is reflexive if (a, a) subset R for all a subset S

Answer 48

reflexive

Question 49

a R b: a is related to b by the relation R if (a, b) subset R. a !R b: a is not related to b by the relation R if (a, b) !subset R

Answer 49

related to

Question 50

a subset of A x B

Answer 50

relation (from set A to set B

Question 51

a relation from S to S or a subset of S x S

Answer 51

relation (on a set S)

Question 52

a function from A to B such that every element of B is the image of some element of A

Answer 52

surjective function | surjection

Question 53

a relation R on a set S is symmetric if (a, b) subset R, | then (b, a) subset R for all a, b, subset S

Answer 53

symmetric

Question 54

a relation R on set S is transitive if (a, b) subset R and (b, c) subset R, then (a, c) subset R for all a, b, c subset S

Answer 54

transitive

Question 55

a set that is not countable

Answer 55

uncountable set