Programming - Lecture 1 (Concepts)

Front 1

What is Running Time?

Back 1

A measure of 'Goodness' for software data structures and algorithms.

Front 2

True or False: In general, Running Time increases with more input.

Back 2

True

Front 3

Hardware that affects Running Time includes ___________, ___________, ___________, and ___________.

Back 3

- Processor speed

- Clock rate

- Memory size/speed

- Disk types/speed

Front 4

Factors of the software environment that affect Running Time include ___________, ___________, and ___________.

Back 4

- Operating system

- Programming language

- Compiler/Interpreter

Front 5

Which two approaches are used to measure Running Time?

Back 5

- Experimental Study

- Theory Analysis

Front 6

Describe steps taken in the Experimental Study method for studying Running Time.

Back 6

1) Implement the algorithm in question (code it).

2) Apply tests to algorithm using various sized inputs (record actual time spent at each input size using system calls or profiling in the O/S to determine Running Time).

3) Graph the results for visualization purposes.

Front 7

Describe 3 limitations of the Experimental Study method for studying Running Time.

Back 7

1) Experiments only done on a representative set of inputs (not all sets can be tested).

2) The same hardware/software must be used to make the comparisons valid.

3) Algorithm must already be fully implemented to test it properly (most expensive).

Front 8

Describe 3 benefits of the Theory Analysis method for studying Running Time.

Back 8

1) Algorithms are not implemented nor are experiments run (less expensive).

2) Allows us to take into account all possible inputs.

3) Allows evaluation of any 2 algorithms regardless of hardware and software.

Front 9

List the 5 Running time functions we've talked about in this course (in order of execution time).

Back 9

1) Constant

2) Logarithmic

3) Linear

4) Quadratic

5) Exponential

Front 10

The function that demonstrates Constant Running Time is expressed as ___________.

Back 10

f(n) = c

Front 11

In the 'f(n)' part of Running Time functions, what does 'n' represent?

Back 11

The input size

Front 12

True or False: A Constant Running Time will operate at the same time no matter the size of the input.

Back 12

True

Front 13

The function that demonstrates Linear Running Time is expressed as ___________.

Back 13

f(n) = n

Front 14

A Linear Running Time function operates how many times for each input?

Back 14

Once

Front 15

The function that demonstrates Quadratic Running Time is expressed as ___________.

Back 15

f(n) = n^2

Front 16

Quadratic Function Example:

If I select 2 students and write every combination of their names, I have n^2 = 2^2 = 4 combinations. How many combinations do I have if I choose 5 students?

Back 16

n^2 = 5^2 = 25 combinations

Front 17

The function that demonstrates Exponential Running Time is expressed as ___________.

Back 17

f(n) = b^n

Front 18

The function that demonstrates Logarithmic Running Time is expressed as ___________.

Back 18

f(n) = logbn

Front 19

True or False: With Logarithmic Running Time, after enough input, the more input, the less time it takes.

Back 19

True

Front 20

True or False: The Quadratic function is suitable for all input sizes.

Back 20

False. It increases quickly, so is only suitable for small input sets.

Front 21

True or False: The Exponential function grows rapidly and is mostly unusable.

Back 21

True

Front 22

The function that demonstrates Constant Running Time is expressed as ___________.

Back 22

f(n) = c

Front 23

True or False: Functions (if possible) should execute in constant or logarithmic time.

Back 23

True

Front 24

True or False: The Linear function is not acceptable and is rarely used.

Back 24

False. The Linear function is acceptable and must be used in many cases.

Front 25

True or False: Quadratic and Exponential functions should be avoided.

Back 25

True

Front 26

True or False: Algorithm Analysis involves counting primitive operations in a routine.

Back 26

True

Front 27

What is a primitive operation?

Back 27

A step the CPU must make to execute an instruction.

Front 28

True or False: High level languages often have several primitive operations per statement.

Back 28

True

Front 29

For Asymptotic notation, Best Case Execution is also referred to as ___________.

Back 29

Big Omega notation (aka Big-<insert omega symbol here> notation)

Pg. 34 in lecture 1

Front 30

True or False: For Asymptotic notation, Best Case Execution expresses the execution for an algorithm as fast as it can possible be.

Back 30

True

Front 31

For Asymptotic notation, Worse Case Execution is also referred to as ___________.

Back 31

Big-O

Front 32

True or False: For Asymptotic notation, Average Case Execution expresses the execution of an algorithm with an average amount of inputs.

Back 32

True

Front 33

True or False: Average Case Execution is commonly used to figure out how a program will run with normal inputs.

Back 33

False. Average Case Execution is typically not used to the complexities involved (requires extensive use of mathematics and probability theory).

Front 34

Between Best and Worst Case Execution, which is better to use in algorithm design?

Back 34

Worst Case Execution

- Operates well regardless of input size.

- Usually easy to identify the worst case.

Front 35

Changes in execution time as a result of input size are specified using ___________ notation.

Back 35

Big-O

- Specifies the worst case for an algorithm

Front 36

Describe two reasons we should care about expressing Running Time in Big-O notation?

Back 36

- Tells us how long an algorithm can take in general terms.

- Shows how well our solution scales as the amount of input increases.

Front 37

For Big-O notation, Constant execution times are expressed as ___________.

Back 37

O(1)

Front 38

For Big-O notation, Logarithmic execution times are expressed as ___________.

Back 38

O(Logn)

Front 39

For Big-O notation, Linear execution times are expressed as ___________.

Back 39

O(n)

Front 40

For Big-O notation, Exponential execution times are expressed as ___________.

Back 40

O(b^n)