Chapter 2: Algorithm Flashcards
What is a pseudocode?
It is a detailed yet readable description of what a computer program or algorithm must do.
What is an algorithm?
1) A rule-based solution that can be used to take inputs, process inputs, and produce expected outputs.
2) A method for solving a problem.
3) A set of pre-defined steps for solving a specific problem.
4) A list of instructions to follow in order to solve a problem.
In mathematic notation, which is equivalent to the following statement when writing a pseudocode?
x = 4y
x := 4y
___ complexity cares more about the space taken by an algorithm, A, on problems with input size n.
Space
Given the following pseudocode, the final value of x is __.
Start
int x = 5;
for i in 1 to 3 do
x = x + i
End
11
Given the following pseudocode, what will be the final output if m=24 and n=3?
r←m%n
while r !=0 do
m←n
n←r
r←m%n
return n
3
Given the following code segment, what is the total number of executions?
for (i=1; i<17; i++)
{
cout «_space;(5 / i) * 3;
}
16
The following is an example of __ time complexity.
int findRemainder(int x, int y)
{
int r = x % y;
return r;
}
Constant
If an algorithm runs in quadratic time, what is its time complexity using Big-O?
O(n^2)
Given the following code segment, the total number of executions is __.
int x = 3;
int y = 4;
for i = 1 to n do
x = x + i
y = y - i
print x
print y
4n + 4
What is the time complexity of accessing an element in an array by its index?
O(1)
Given the following codes, what is the number of total executions?
int count = 0;
for (int i = 0; i < 5; i++)
{
count++;
}
11
Given the following generic for loop, what is the time complexity?
for (int i = 0; i < n; i++)
{
// Code to be executed
}
O(n)
What is “time complexity” in algorithm analysis?
A measure of how long an algorithm takes to execute as a function of input size.
Given the following pseudo code, which Big O complexity should it be labeled?
function(x):
return x*x + 3
O(1)
A(n) __ is essentially a step-by-step procedure or set of rules designed to solve a specific problem.
algorithm
Which characteristic is NOT generally associated with a good algorithm?
Ambiguity
A __ provides ways of organizing and storing data.
Data structure
Which is NOT an example of common computer algorithms?
Unforeseen events
What is “space complexity” in algorithm analysis?
A measure of how much memory an algorithm uses as a function of input size.
