2 - Numbers and sequence

Question 1

What is an Abstract Data Type (ADT)?

Answer 1

An Abstract Data Type is a high-level specification that defines the collection of allowed values and the operations that can be performed on those values within a data structure, without concerning itself with implementation details.

Question 2

What are real numbers

Answer 2

Real numbers are numbers that can be represented in decimal form with either finite or infinite numbers after the decimal point.

Question 3

What are natural numbers?

Answer 3

Natural numbers are non-negative numbers starting from 0 and counting upwards infinitely: 0, 1, 2, 3, and so on.

Question 4

What is the typical format for assignments in M269 when writing algorithms in English?

Answer 4

Assignments in M269 English-style algorithms are typically written as:

“let variable be expression.”

Question 5

How can you display the value of an expression in an English-style algorithm?

Answer 5

To display the value of an expression in an English-style algorithm, you can use the instruction: “print expression.”

Question 6

What defines an algorithm with constant complexity?

Answer 6

Algorithms with constant complexity are those where the runtime does not grow with increasing input values.

Question 7

How is “complexity” defined in the context of algorithms?

Answer 7

Complexity, in the context of algorithms, measures the algorithm’s growth rate of runtime for ever-increasing inputs when executed in the same environment (e.g., operating system and hardware).

Question 8

What does complexity focus on in terms of algorithm performance?

Answer 8

Complexity is not about how fast an algorithm runs but is a measure of how it runs for different input sizes.

Question 9

Why are arithmetic instructions considered to have constant complexity in the context of modern processors?

Answer 9

Modern processors can perform arithmetic operations on 64-bit numbers in a single hardware instruction, which is why arithmetic instructions are considered to have constant complexity. This means that for any number, regardless of its size, the operation will always take the same amount of time.

Question 10

When dealing with algorithm analysis, what can be assumed about assignments and return statements in terms of complexity?

Answer 10

It is assumed that assignments and return statements have a constant complexity.

Question 11

How does an algorithm with a fixed number of operations, each with constant complexity, behave in terms of complexity?

Answer 11

An algorithm with a fixed number of operations, each with constant complexity, will itself have a constant complexity.

Question 12

How is Big-Theta notation used in algorithm analysis?

Answer 12

Big-Theta notation is used to concisely and precisely state the complexity of an algorithm.

Question 13

What does Θ(1) represent in Big-Theta notation when describing the complexity of an algorithm?

Answer 13

In Big-Theta notation, Θ(1) represents an algorithm with constant complexity, which means it has a runtime that doesn’t depend on the size of the input.

Question 14

How can we express an algorithm with constant complexity in terms of Big-Theta notation?

Answer 14

An algorithm with constant complexity is expressed using Big-Theta notation as:

It has complexity Θ(1).
It takes Θ(1) time.
Its run-time is Θ(1).

Question 15

What characterizes an algorithm with linear complexity?

Answer 15

An algorithm with linear complexity grows in proportion to the size of its inputs, meaning that its runtime increases as the input size increases.

Question 16

How is the size of an integer represented in the context of M269 algorithm analysis?

Answer 16

In M269 algorithm analysis, the size of an integer is represented as │n│, which is the number of its decimal digits. For example, │102│ = 3.

Question 17

How is the complexity of an algorithm with linear time expressed using Big-Theta notation in M269?

Answer 17

The complexity of an algorithm with linear time is expressed in Big-Theta notation as

Θ(inputs that affect the algorithm’s complexity).

It indicates that the algorithm’s complexity increases in proportion to the input values that affect it.

Question 18

How is the complexity of the exponentiation algorithm (x^y) described in terms of Big-Theta notation?

Answer 18

The complexity of the exponentiation algorithm (x^y) is expressed as Θ(y). This is because the time it takes to compute the exponentiation depends on the value of y, where y represents how many multiplication operations will be carried out.

Question 19

In algorithm analysis, how is the complexity of an algorithm determined by the inputs provided, and what notation is used to express this complexity?

Answer 19

The complexity of an algorithm in algorithm analysis can be either independent of the inputs, resulting in constant complexity Θ(1), or dependent on the inputs themselves. In cases where complexity is influenced by the inputs, it is crucial to represent the inputs affecting the complexity using Big-Theta notation.

Question 20

What is the difference between the size and value of an integer?

Answer 20

The size of an integer refers to the number of digits the integer is made up of and is expressed as |input| in M269. The value of an integer, on the other hand, refers to the actual numerical value of the integer.

Question 21

How can confusing the size and value of an integer lead to errors in algorithm analysis?

Answer 21

Confusing the size and value of an integer can lead to errors in algorithm analysis, as exemplified when assuming the complexity of 𝑥𝑦 is Θ(│y│). This incorrect assumption can lead to misunderstandings of how computation time scales, especially in cases like 𝑥22 versus 𝑥2. The complexity of exponentiation is correctly expressed as linear in the value (not the size) of the exponent, i.e., Θ(y) rather than Θ(│y│).

Question 22

Why is it important to use variables in expressions when measuring their execution time in algorithm analysis?

Answer 22

Using variables in expressions is crucial when measuring execution time because literals in an expression are unchanging, and the compiler can optimize the evaluation of the expression by storing the solution in memory.

When timing, this optimization masks the true run-time of the algorithm. However, when variables are used, the compiler cannot make this optimization, revealing the actual run-time of the algorithm.