Term
|
Definition
| artificial language that resembles the code of some familiar computer languages |
|
|
Term
|
Definition
| A procedure for solving a problem that consists of input, output and a finite sequence of step that converts the input to the output |
|
|
Term
|
Definition
| A function f: N-> R+ is big O of a function g:N-> R+ written f = O(g) or f(n) = O(g(n)) if there exist a postive constant C and positive integer k such that f(n) <= Cg(n) for every integer n >= k. |
|
|
Term
|
Definition
| A function f: N-> R+ is big O of a function g:N-> R+ written f = (-)(g) or f(n) = (-)(g(n)) if there exist a positive constants C1 and C2 and positive integer k such that C1g(n)<= f(n) <= C2g(n) for every integer n >= k. |
|
|
Term
|
Definition
| process for obtaining estimates of the time and space needed to execute the algorithm. |
|
|
Term
| complexity of an algorithm |
|
Definition
| the amount of time and space needed to execute the algorithm |
|
|
Term
|
Definition
| concerns a study of computer memory and the data structures employed |
|
|
Term
|
Definition
| concerns the study of the time required to solve the problem using the algorithm as a function of the size of the input. |
|
|
Term
| polynomial time complexity |
|
Definition
| If the time complexity of an algorithm can be expressed as (-)(f(n)) for some polynomial f(n) then it has polynomial time complexity |
|
|
Term
|
Definition
| If the time complexity can be expressed as (-)(n^p) with p=0 (so the time complexity is O(1)) then there are only a finite number of operations being counted in the algorithm and so the algorithm has constant time complexity. |
|
|
Term
|
Definition
| an algorithm with time complexity (-)(n) |
|
|
Term
| quadratic time complexity |
|
Definition
| an algorithm with time complexity (-)(n^2) |
|
|
Term
|
Definition
| Suppose two algorithms A and B have time complexities O(f(n)) and O(g(n)), respectively. If f(n) = O(g(n)) but g(n) != O(f(n)) then algorithm A is more efficient. |
|
|
Term
|
Definition
| if f(n) = (-)(g(n)) then f and g are said to have the same degree of efficiency. |
|
|
Term
| worst case time complexity |
|
Definition
| the maximum number of comparisons that can occur when a problem is solved using an algorithm |
|
|
Term
| average case time complexity |
|
Definition
| the average number of comparisons needed to determine where k appears in the sequence if k is any one of the n terms |
|
|
Term
|
Definition
| compare k to each number in the sequence until you find k |
|
|
Term
|
Definition
| compare k to the midpoint. If it is less than it repeat the process with the sequence from the beginning to the middle. If it is larger repeat the process from the midpoint to the end. |
|
|
Term
|
Definition
| compare each number to the next and swap so the smaller number is first |
|
|
Term
|
Definition
| sorts by inserting the number where it belongs in the sequence |
|
|
Term
|
Definition
| two sorted lists merged together |
|
|
Term
|
Definition
| n = (akak-1...a1a0)b: the expansion of a positive integer n in base b, where then b>=2 and n=akb^k+ak-1b^k-1+...a1b+a0 |
|
|
Term
|
Definition
| the expansion of an integer in base 2 |
|
|
Term
|
Definition
| 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 |
|
|
Term
| common divisor (of a and b) |
|
Definition
| an integer that divides both a and b |
|
|
Term
| common multiple (of a and b) |
|
Definition
| an integer that is a multiple of a and b |
|
|
Term
|
Definition
| an integer greater than 1 that is not prime |
|
|
Term
| congruence (a is congruent to b modulo n) |
|
Definition
|
|
Term
|
Definition
| the study of sending and receiving secret messages |
|
|
Term
|
Definition
| the study of systems for secure communications |
|
|
Term
|
Definition
| system for secure communications |
|
|
Term
|
Definition
| the expansion of an integer in base 10 |
|
|
Term
|
Definition
| a process of transforming a disguised message back to the original message |
|
|
Term
|
Definition
| the quotient when the integer m is divided by the positive integer n. |
|
|
Term
| divides (a divides b where a != 0) |
|
Definition
| a|b there is an integer c such that b = ac |
|
|
Term
| divisor (of an integer b) |
|
Definition
| an integer that divises b |
|
|
Term
|
Definition
| a process of transforming a message into a disguised message |
|
|
Term
|
Definition
| an integer that divises b |
|
|
Term
| greatest common divisor (of a and b) |
|
Definition
| gcd(a, b: the greatest positive integer that is a common divisor of a and b |
|
|
Term
|
Definition
| the expansion of an integer in base 16 |
|
|
Term
| least common multiple (of integers a and b) |
|
Definition
| lcm(a, b): the smallest positive integer that is a common multiple of a and b |
|
|
Term
| linear combination (of a and b) |
|
Definition
| an integer of the form ax+by where x and y are integers |
|
|
Term
|
Definition
| the remainder when the integer m is divided by the positive integer n |
|
|
Term
| multiple (of an integer a) |
|
Definition
| an integer that a divises |
|
|
Term
|
Definition
| the expansion of an integer in base 8 |
|
|
Term
|
Definition
| an integer greater than one whose only positive integer divisors are 1 and itself |
|
|
Term
|
Definition
| a substitute character for each character that could be contained in any message to be transmitted |
|
|
Term
|
Definition
| a cryptosystem in which two individuals who wish to communicate in secret have a private key |
|
|
Term
|
Definition
| a cryptosystem in which two keys are used, a public encryption key and private decryption key |
|
|
Term
| relatively prime (a and b relatively prime) |
|
Definition
|
|
Term
|
Definition
| a public key cryptosystem introduced by Richard Rivest, Adi Shamir and Leonard Adleman |
|
|
Term
| combination (r-combination) |
|
Definition
| an unordered selection of r elements of a set |
|
|
Term
|
Definition
| an arrangement (an ordered list) of the elements in a set |
|
|
Term
|
Definition
| an arrangement (an ordered list) of r elements of a set |
|
|
Term
| The multiplication principle |
|
Definition
| a procedure consists of a sequence of two tasks. To perform this procedure one performs the first taks followed by performing the second task. If there are n1 ways to perform the first task and n2 ways to perform the second task after the first task has been performed then there are n1n2 ways to perform the procedure. |
|
|
Term
|
Definition
| A procedure consists of two tasks that cannot be performed simultaneously. To perform this procedure either of the two tasks is performed. If the first can be performed in n1 ways and the second can be performed in n2 ways then the number of ways of performing this procedure is n1+n2. |
|
|
Term
| The principle of inclusion-exclusion |
|
Definition
| A procedure consists of two tasks. To perform the procedure, one performs either of the two tasks. If the first can be performed in n1 ways the second can be performed in n2 ways and the two tasks can be simultaneously performed in n12 was then the total number of ways of performing the procedure is n1+n2-n12 |
|
|
Term
|
Definition
| If a set S with n elements is divided into k pairwise disjoint subsets S1, S2...Sk then at least one of these subsets contains at least n/k elements. |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| binomial coefficient (n over r in that weird way) |
|
Definition
| the number of r-element subsets of an n element set |
|
|
Term
| extended binomial coefficient (alpha over r) |
|
Definition
| (alpha over 0) = 1 and (alpha over r) = alpha(alpha-1)...(alpha-r+1) / r! for r != 0 |
|
|
Term
| generating function (of a sequence a_k) |
|
Definition
| the series Summation k = 0 to infinity: a_kx^k |
|
|
Term
|
Definition
| a collection of elements in which repetition of elements is permitted |
|
|
Term
|
Definition
| a representation of the binomial coefficients such that the nth row of the triangle contains C(n, r) for 0 |
|
|
