Unit 1

Question 1

To determine the best algorithms to use, computer scientists analyze the complexity of the algorithm by comparing two algorithms at the blank level

Answer 1

idea

Question 2

To analyze algorithm complexity, computer scientists use pragmatic tools such as blank, blank and blank notations to formally measure how fast a program or algorithm runs.

Answer 2

big-O, Theta, and Omega

Question 3

An blank is a step-by-step method for solving a problem. A description of an algorithm specifies the input to the problem, the output to the problem, and the sequence of steps to be followed to obtain the output from the input.

Answer 3

algorithm

Question 4

Algorithms are often described in blank, which is a detailed yet readable description of what an algorithm must do, expressed in a formally-styled natural language rather than in a programming language.

Answer 4

pseudocode

Question 5

An important type of step in an algorithm is an blank, in which a variable is given a value.

Answer 5

assignment

Question 6

An assignment operator is denoted by:

blank

Answer 6

x := y

Question 7

The output of an algorithm is specified by a blank statement.

Answer 7

return

Question 8

A description of an algorithm starts with the blank.

Answer 8

name of the algorithm

Question 9

The name is followed by a blank of what the algorithm computes

Answer 9

description

Question 10

A description of an algorithm usually includes what five steps:

Answer 10

A name for the algorithm
A brief description of the task performed by the algorithm
A description of the input
A description of the output
A sequence of steps to follow

Question 11

An blank tests a condition, and executes one or more instructions if the condition evaluates to true.

Answer 11

if-statement

Question 12

In a blank, a condition and instruction appear on the same line.

Answer 12

single line if-statement

Question 13

What is the notation for an if-statement?

Answer 13

If (x = 5), y := 7

Question 14

An if-statement can also be followed by a blank of indented operations with a final end-if statement.

If ( condition )
Step 1
Step 2
. . .
Step n
End-if

Answer 14

sequence

Question 15

An blank tests a condition, executes one or more instructions if the condition evaluates to true, and executes a different set of instructions if the condition evaluates to false

Answer 15

if-else-statement

Question 16

Name the pattern for if-else statement

Answer 16

If ( condition )
One or more steps
Else
One or more steps
End-if

Question 17

An if-then statement tests a blank and executes one or more steps if the condition is true. An if-else statement tests the condition, and executes one or more instructions if the condition is true, and another instruction or set of instructions if it is false.

Answer 17

condition

Question 18

The structure of the if-then statement in pseudocode when there is only one step to execute when the condition is true is:
blank

Answer 18

If(condition), step

Question 19

When multiple steps should be performed upon a true condition, the steps are indented and the end of the list of steps is noted with an blank statement:

Answer 19

End-if

Question 20

The if-else statement in pseudocode is formatted in what format:

Answer 20

If (condition)
One or more steps
Else
One or more steps
End-if

Question 21

The multiple step if statement in pseudocode is formatted in what format:

Answer 21

If (condition)
Step 1
Step 2
…
Step n
End-if

Question 22

When needed, if-then and if-else statements can be blank

Answer 22

nested.

Question 23

There are blank regarding how many if-then or if-else statements can be placed under another if-then or if-else statement.

Answer 23

no limitations

Question 24

An blank is a process where a set of instructions or structures are repeated in a sequence a specified number of times or until a condition is met.

Answer 24

iteration

Question 25

To control the iterations, blank use an index or a counter and a variable that counts how many times a step or a block of steps executes.

Answer 25

for-loops

Question 26

Blank structures provide a means of specifying a sequence of steps that are to be repeated.

Answer 26

Looping

Question 27

There are two common types of loops: blank and blank.

Answer 27

for-loops and while-loops

Question 27

In a blank, a block of instructions is executed a fixed number of times as specified in the first line of the for-loop, which defines an index, a starting value for the index, and a final value for the index.

Answer 27

for-loop

Question 28

Each repetition of the block of instructions inside the for-loop is called an blank

Answer 28

iteration.

Question 29

The index is initially assigned a value equal to the blank, and is incremented just before the next iteration begins. The final iteration of the for-loop happens when the index reaches the final value.

Answer 29

starting value

Question 30

Give the syntax for a for loop

Answer 30

For i = s to t Step 1 Step 2 . . . Step n End-for

Question 31

For-loops are used when the number of iterations in the loop is blank.

Answer 31

known

Question 32

The for-loop iterates blank times.

Answer 32

final_value-start_value+1

Question 33

A blank iterates an unknown number of times, ending when a certain condition becomes false.

Answer 33

while-loop

Question 34

A while-loop is written as blank:

Answer 34

While ( condition ) Step 1 Step 2 . . . Step n End-while

Question 35

The blank is an expression that evaluates to true or false. If the expression evaluates to true, then steps 1 through n are performed and the algorithm goes back to the first statement where the condition is re-evaluated. The process continues until the condition evaluates to false, at which point the algorithm proceeds with the next step after the while-loop.

Answer 35

condition

Question 36

blank are used when the number of iterations in the loop is unknown and may execute zero or more iterations.

Answer 36

While-loops

Question 37

While loops are controlled by a blank. If the blank is true, the loop initiates an iteration otherwise it stops.

Answer 37

conditional statement

Question 38

While-loops use the blank syntax in pseudocode:

Answer 38

While (condition) One or more steps End-while

Question 39

The while-loop iterates blank or blank times until the condition is met.

Answer 39

zero or more

Question 40

When a loop exists within another loop, it is called a blank loop

Answer 40

nested

Question 41

When loops are nested the blank loop takes control of the number of complete repetitions of the blank loop.

Answer 41

outer inner

Question 42

A blank is a loop that appears within another loop

Answer 42

nested loop

Question 43

The nested loop, known as the blank, is treated as a sequence of steps inside the outer loop.

Answer 43

inner loop

Question 44

blank can nest in blank, and vice-versa; loops of the same type can also nest.

Answer 44

While-loops for-loops

Question 45

The blank takes control of the number of complete repetitions of the blank. The first pass of the outer loop triggers the inner loop, which executes to completion. Then the second pass of the outer loop triggers the inner loop again. This repeats until the outer loop finishes.

Answer 45

outer loop inner loop

Question 46

To solve a problem an algorithm needs blank

Answer 46

resources

Question 47

The primary resources to optimize are blank, the time the algorithm requires to run, and blank, the amount of memory used.

Answer 47

time complexity space complexity

Question 48

The blank depends on the speed of the processing unit, the number of calculations that need to be performed, the number of conditions that need to be evaluated, or the number of iterations to be completed by the loops.

Answer 48

time

Question 49

The values of all variables, including the values of the input variables and all other values that will be computed, need to be stored somewhere in the blank of the system—in the RAM, hard drive, or external devices.

Answer 49

memory

Question 50

Naturally, a program will take more time and space on larger inputs. For example, a program that sorts a sequence of numbers will take a longer time to sort a long sequence than a short sequence. Therefore, time and space efficiency are measured in terms of the blank

Answer 50

input size

Question 51

The way the size of the input is measured varies based on the blank

Answer 51

type of problem

Question 52

When sorting numbers, for example, the blank is the number of numbers to be sorted.

Answer 52

input size

Question 53

An algorithm that processes a digital image would likely be measured as a function of the blank in the image.

Answer 53

number of pixels

Question 54

An algorithm that processes a recorded speech given at a commencement ceremony will likely use the blank as the size of the input.

Answer 54

length of the speech

Question 55

The input size for a problem is usually denoted by the variable blank , and the assessments of the algorithms' resources needs are denoted in functions of blank that give the best-, worst-, and average-case scenario behavior of the algorithms.

Answer 55

n

Question 56

Not all elements of the blank provide equally relevant information about how much more resources an algorithm would need as n grows.

Answer 56

complexity functions

Question 57

What is F[1] :=1 F[2]:=1 For i:=3 to n F[i] := F[i-1]+F[i- 2] End-for Return (F[n])

Answer 57

Algorithm Fibonacci-1

Question 58

The choice of blank can heavily influence the efficiency of a solution to a computing problem

Answer 58

algorithms

Question 59

Blank is a measure of the resources an algorithm uses.

Answer 59

Computational complexity

Question 60

blank measures the time an algorithm needs to complete.

Answer 60

Time complexity

Question 61

Blank measures the amount of memory an algorithm uses during its execution

Answer 61

Space complexity

Question 62

Programmers commonly seek optimal ways to sort numbers and optimize databases to store data with algorithms that will speed up blank

Answer 62

retrieval

Question 63

These operations (e.g., addition, multiplication, comparison) that one would find in a single line of pseudocode, are referred to as blank

Answer 63

atomic operations

Question 64

They are called "atomic," because they cannot be split any further; a computer would evaluate each in one step.

Question 65

blank takes longer to complete than addition, as multiple additions need to happen to find the product of two numbers.

Answer 65

Multiplication

Question 66

blank is the same as the addition of negated numbers and division is a series of subtractions.

Answer 66

Subtraction

Question 67

Blank is a repeated multiplication, so it takes longer to execute

Answer 67

Exponentiation

Question 68

At the same time, a blank takes longer to complete than assignments, as they consist of statements that are integrated multiple times.

Answer 68

loop

Question 69

As the size of the input grows, blank and blank partake less and less in the total time the algorithm takes to complete because the multiplication and loops dominate the time.

Answer 69

addition and assignment statements

Question 70

Each blank has its position in the sequence, and the total number of blank in the sequence is referred to as its size.

Answer 70

element

Question 71

Use these guidelines to count the number of atomic operations:

Answer 71

Count each assignment as one operation Multiply the operations in the body of the loop by the number of iterations of the loop Ignore constant factors; focus on the elements of the functions that grow the fastest

Question 72

Specific features of computing systems, such as blank, are not considered when comparing how the time to complete an algorithm grows as the size of the input grows.

Answer 72

processor speed

Question 73

blank is performed to measure the resources (time or space) that an algorithm requires in the worst case.

Answer 73

Worst-case analysis

Question 74

The term "worst case" refers to an input that triggers the blank of calculations, thus taking the longest to complete of all other inputs of the same size

Answer 74

maximum number

Question 75

The worst-case analysis provides an blank on the resources required by the algorithm.

Answer 75

upper bound

Question 76

blank are compared by their average running and best running times.

Answer 76

Algorithms

Question 77

blank is used to estimate how much time might be needed in the worst case to guarantee that the algorithm will always finish on time.

Answer 77

Worst-case complexity

Question 78

blank and blank are the most used in algorithm analysis.

Answer 78

Average performance and worst-case performance

Question 79

the behavior of the complexity function as n grows.

Answer 79

asymptotic complexity

Question 80

Any program that doesn't have loops will have an asymptotic complexity of blank, since the number of instructions it needs is just a constant.

Answer 80

1

Question 81

Any program with a single loop which goes from 1 to n will have asymptotic complexity blank since it will do a constant number of instructions before the loop, a constant number of instructions after the loop, and a constant number of instructions within the loop which all run n times.

Answer 81

n,

Question 82

This method of searching for a value within an array is called blank. The asymptotic complexity for this algorithm is n due to the single for-loop. Note that this algorithm might not need to go through all n elements of the array to find one; however, in the worst-case scenario when it does (when no elements equals V or the last element of the array equals V), the loop will run n times.

Answer 82

linear search.

Question 83

Simple programs can be analyzed by counting the blank of the program. A single loop over n items yields asymptotic complexity n.

Answer 83

nested loops

Question 84

If you have a program that calls a function within a loop and you know the number of atomic operations the called function performs, it is easy to determine the blank of the whole program.

Answer 84

number of atomic operations

Question 85

Since you know that f(n) is a function that performs exactly n instructions, you then know that the number of instructions of the whole program is asymptotically blank, as the function is called exactly n times.

Answer 85

n2

Question 86

Given a series of for-loops that are sequential, the blank of them determines the asymptotic behavior of the program.

Answer 86

slowest

Question 87

blank is a basic mathematical tool for working with functions that we only know up to a constant factor. There are three types of asymptotic notation that are commonly used in algorithmic analysis, O(n) ("big-O"), Ω(n) ("Omega"), and Θ(n) ("Theta").

Answer 87

Asymptotic notation

Question 87

Two nested loops followed by a single loop is asymptotically blank as the nested loops alone, because the nested loops dominate the simple loop.

Answer 87

the same

Question 88

Blank—serves as a rough upper bound for functions (disregarding constants and small input values).

Answer 88

The big-O notation—O(n)

Question 89

The blank is similar to big-O, except that it provides a lower bound on the growth of a function.

Answer 89

Ω notation—Ω(n)—

Question 90

The blank—indicates how the algorithm performs for any case. This is referred to as an average time or random case function and, when possible, gives us a sense of how the algorithm performs in any case. Note that it is often possible to estimate upper and lower bounds, but not average cases especially if there are complex branching in the code.

Answer 90

Θ notation—Θ(n)

Question 91

Blank describes the behavior of the complexity function as n grows. Only the terms that grow fastest in a complexity function significantly influences its blank, so they are retained without constant multipliers.

Answer 91

Asymptotic complexity

Question 92

To find the asymptotic behavior for the given function, drop the constant factors and keep the terms that blank. For example, in this function: 6n + 4, drop the 4 because it remains constant and the constant multiplier 6.

Answer 92

grow the fastest

Question 93

An algorithm without loops has a constant asymptotic complexity of blank, since the number of instructions it needs is just a constant.

Answer 93

1

Question 94

Any program with a single loop which goes from 1 to n will have asymptotic complexity blank, since it will do a constant number of instructions before the loop, a constant number of instructions after the loop, and a constant number of instructions within the loop which all run n times.

Answer 94

n

Question 95

If you cannot readily decide which one of the terms grows faster, plug in several large values for blank and compare.

Answer 95

n

Question 96

A single loop that iterates up to n times has a blank asymptotic complexity.

Answer 96

linear

Question 97

The asymptotic complexity of a loop nested in a loop is blank.

Answer 97

quadratic

Question 98

The blank is the most common in the context running times/time complexity.

Answer 98

big-O notation

Question 99

The functions f(n) and g(n) are called upper and lower bounds of the asymptotic complexity of the algorithm and the following is true by definition:

Answer 99

Ω(f(n)) ≤ Θ(f(n)) ≤ O(f(n)).

Question 100

blank, blank and blank are formal notational methods for stating the growth of resource needs (time and storage) of an algorithm.

Answer 100

Big-O, Omega, and Theta

Question 101

The function that counts the atomic operations of an algorithm falls under the blank.

Answer 101

big-O function

Question 102

The function that counts the atomic operations of an algorithm is above blank.

Answer 102

the Omega function

Question 103

The blank falls between the big-O and Omega functions.

Answer 103

Theta function