Brainscape's Knowledge GenomeTM

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


See full index

Discrete Mathematics > Algorithms and Complexity > Flashcards

Algorithms and Complexity Flashcards

1
Q

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

A

Algorithm

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

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

A

average case time complexity

of an algorithm

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

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

A

big-O

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

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

A

big-theta

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

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

A

Binary Search

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

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

A

Bubble Sort

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

the amount of space and time needed to execute the algorithm

A

complexity of an algorithm

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

time complexity of an algorithm is O(1)

A

constant time complexity

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

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

A

Insert sort algorithm

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

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

A

Linear search algorithm

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

the time complexity of the algorithm is O(n)

A

linear time complexity

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

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

A

Merge sort algorithm

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

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

A

Polynomial time complexity

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

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

A

quadratic tie complexity

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

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

A

time complexity

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

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

A

worst case time complexity

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

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

A

base b expansion

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

the expansion of an integer in base 2

A

binary expansion

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

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

A

Ceaser shift

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

an integer that divides both a and b

A

common divisor

of a and b

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

an integer that is multiple of a and b

A

common multiple

of a and b

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

an integer greater than 1 that is not prime

A

composite

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

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

A

congruence

a is congruent to b modulo n

24
Q

the study of sending and receiving secret messages

A

cryptography

25
Q

the study of systems for secure communications

A

cryptology

26
Q

systems for secure communications

A

cryptosystem

27
Q

a function that is one-to-one and onto

A

bijective function

28
Q

|A| = |B|

two sets A and B have the same cardinality

A

Cardinalities of two sets

29
Q

the smallest integer greater than or equal to x

A

ceiling function

30
Q

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

A

codomain

31
Q

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

A

complex number

32
Q

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

A

composition

33
Q

a consequence of another result

A

corollary

34
Q

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

A 
denumerable set
(countably infinite set)
35
Q

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

A

domain

36
Q

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

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

a reflexive, symmetric, and transitive relation on a set

A

equivalence relation

38
Q

the largest integer less than or equal to x

A

floor function

39
Q

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

A 
function (from A to B)
f: A -> B
40
Q

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

A

graph

41
Q

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

A

image

42
Q

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

A

injective function

one-to-one

43
Q

a bijective function

A

one-to-one correspondence

44
Q

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

A

one-to-one function

45
Q

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

A

onto function

46
Q

a bijective function from A to A

A

permutation

on a nonempty set A

47
Q

the set of all images of f

A

range

48
Q

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

A

reflexive

49
Q

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

A

related to

50
Q

a subset of A x B

A

relation (from set A to set B

51
Q

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

A

relation (on a set S)

52
Q

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

A

surjective function

surjection

53
Q

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

A

symmetric

54
Q

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

A

transitive

55
Q

a set that is not countable

A

uncountable set

Discrete Mathematics (1 decks)

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