3 | Elementary operations / Asymptotics I

Question 1

Definition:
Problem vs. instance

Answer 1

Problem: a specification of desired input-output relationship.

Instance: (of a problem) all inputs needed to compute solution to problem.

• A problem specifies its domain of definition
  i.e., the set of instances to be considered.
• Many interesting problems have infinitely many instances.
• Some problems have a single instance (e.g. sink/source)

Question 2

How to show that an algorithm is incorrect?

Answer 2

• find one instance for which algorithm does not find correct solution.

Question 3

What is a bit?

Answer 3

A bit (short for binary digit) is the smallest unit of data in a computer

A bit has a single binary value either 0 or 1

Question 4

What is a byte?

Answer 4

8 bits = 1 byte
used for storing data and executing instructions

Question 5

Steps to convert decimal number to binary?

Answer 5

Divide the number by 2.
- The modulus (remainder) is the next digit of the new binary number (in reverse order).
- The floor is carried over for the next iteration

Repeat until the floor is zero

Question 6

size of bits needed for n = size(n)

Formula?

Answer 6

size(𝑛) = ⌊log₂(𝑛) + 1⌋ (= ⌊log₂(𝑛)⌋ + 1 )

Question 7

Proof of formula:

size(𝑛) = ⌊log₂(𝑛) + 1⌋

Answer 7

see notes

Question 8

Size of an instance: formal definition?

Answer 8

Formal definition
Size of an instance corresponds to the number of bits needed to represent the instance on a computer using a precisely defined coding scheme.

Question 9

Size of an instance: less formal definition?

Answer 9

Less formal
Size stands for any integer than measures the number of components of an instance.

Question 10

Size of an instance:

examples?

Answer 10

Examples
In sorting, the size corresponds to the number of items.
(ignoring the fact that more than one bit may be needed to represent each integer)

In graphs, the size is the number of nodes, number of edges, or both

Question 11

Advantages of the theoretical approach to determine efficiency

Answer 11

It does not depend on
- the computer being used
- the programming language employed
- the skills of the programmer

It allows to study the efficiency of an algorithm on instances on any size

Empirical approach – small vs. large instances

Expressing efficiency
storage – bit
time – seconds, minutes, etc. (no convention)

Question 12

Algorithm efficiencey - Principle of invariance?

Answer 12

Two different implementations of the same algorithm will not differ in efficiency by more than some multiplicative constant.

The running time of either implementation is bounded by the running time of the other

Question 12

Algorithm efficiencey - Principle of invariance?
formulas?

Answer 12

If 𝑡₁(𝑛) and 𝑡₂(𝑛) (seconds) are the running times of two implementations of an algorithm, then there exist two positive constants 𝑐 and 𝑑 for which

𝑡₂(𝑛) /𝑑 ≤ 𝑡₁(𝑛) ≤ 𝑐𝑡₂(𝑛)

whenever 𝑛 is sufficiently large.

1/𝑑 = 𝑑′ ≤ 𝑡₁(𝑛)/𝑡₂(𝑛) ≤ 𝑐 (assuming 𝑡(𝑛) ≠ 0

Question 13

1.
Principle of invariance remains true…

2
… what allows constant speed up?

3.
Only change in ____ allow us a marked speed up which reflects the change in the size of the instance

Answer 13

The principle remains true irrespective of
change of computer
change of programming language / compiler

Change in implementation detail may allow us a constant speed up

Only change in algorithm allow us a marked speed up which reflects the change in the size of the instance

Question 14

An algorithm takes time in the order of …..

Answer 14

An algorithm takes a time in the order of 𝒕(𝒏) , if there
exists a positive constant 𝒄 and an implementation of the
algorithm capable of solving every instance of size 𝒏 in
not more than 𝒄𝒕(𝒏) seconds.

No unit for expressing theoretical efficiency!

Question 15

Name 4 types of algorithms based on efficiency

Answer 15

Linear algorithms
𝑐𝑛
Quadratic algorithms
𝑐𝑛²
Polynomial algorithms
𝑐𝑛^𝑘
Exponential algorithms
𝑐^𝑛

Question 16

Issue with the multiplicative (hidden) constants in algorithm efficiency?

Answer 16

e.g. 𝑛² days vs. 𝑛³ seconds for the same algorithm

when is 𝑛² 𝑑𝑎𝑦𝑠 < 𝑛³ 𝑠𝑒𝑐𝑜𝑛𝑑𝑠?

asymptotically the first is better than the second, practically not

Question 17

Average case analysis - definition? Issues?

Answer 17

Average-case analysis: average over all possible instances

but are all instances equally likely?

requirement for an adequate distribution of instances

–> more difficult than worst-case analysis

Question 18

Insertion sort - principle?

Answer 18

For each element, from the second to the last, we find the appropriate place among its predecessors

Question 19

Insertion sort - pseudocode?

Answer 19

procedure insert(𝑇[1. . 𝑛])

for 𝑖 ← 2 to 𝑛 do
    𝑥 ← 𝑇[𝑖]
    𝑗 ← 𝑖 − 1
    while 𝑗 > 0 and 𝑥 < 𝑇[𝑗] do
        𝑇 [𝑗 + 1] ← 𝑇 𝑗
        𝑗 ← 𝑗 − 1
    𝑇[𝑗 + 1] ← 𝑥

Question 20

Selection sort – principle?

Answer 20

Find the smallest element in the array and bring it to the front;
continue applying the principle to the array from the second position.

Question 21

Selection sort - pseudocode?

Answer 21

procedure select(𝑇[1. . 𝑛])

for 𝑖 ←1 to 𝑛 − 1 do
    𝑚𝑖𝑛𝑗 ← 𝑖
    𝑚𝑖𝑛𝑥 ← 𝑇[𝑖]
    for 𝑗 ← 𝑖 + 1 to 𝑛 do
        if 𝑇[𝑗] < 𝑚𝑖𝑛𝑥 then
            𝑚𝑖𝑛𝑗 ← 𝑗
            𝑚𝑖𝑛𝑥 ← 𝑇[𝑗]
    𝑇[𝑚𝑖𝑛𝑗] ← 𝑇[𝑖]
    𝑇[𝑖] ← 𝑚𝑖𝑛𝑥

Question 22

Worst case complexity:

Insertion sort?

Selection sort?

Answer 22

O(n²)

Question 23

Linear algorithms

Answer 23

cn

Question 24

Polynomial algorithms

Answer 24

𝑐𝑛^𝑘

Question 25

Exponential algorithms

Answer 25

𝑐ⁿ

Question 26

Quadratic algorithms

Answer 26

𝑐𝑛²

Question 27

Insertion sort complexities?

Answer 27

O(n²) Θ(n²) Ω(n)

Question 28

Selection sort complexities?

Answer 28

all n² O(n²) Θ(n²) Ω(n²)

Question 29

best case symbol

Answer 29

Ω

Question 30

average case symbol

Answer 30

Θ