Algorithms

Question 1

Is there a difference between a Problem and an Algorithm?

Answer 1

Yes

Question 2

Problem

Answer 2

description which associates inputs to output states

Question 3

Problems include 2 things

Answer 3

precondition + postcondition

Question 4

Does a problem statement itself indicate how to solve the problem?

Answer 4

No; just pre and post

Question 5

Algorithm

Answer 5

describes a possible sequence of steps which when carried out solves a problem by meeting post conditions upon completion.

Question 6

Do algorithms have to meet a problems’ post conditions upon completion?

Answer 6

yes

Question 7

Function details can be hidden T or F?

Answer 7

True

Question 8

Pseudocode

Answer 8

english-like representation of algorithm logic

and is independent of implementation language

Question 9

in pseudocode, do we explicitly declare primitive data items? (eg. int number)

Answer 9

no.

Question 10

Conventions for variable names:

Answer 10

1. meaningful names
2. no single-char names except for loops
3. Do not use generic names : count sum row
4. use descriptive names
5. use abbreviations

Question 11

Is this a valid Psuedocode variable name?

count

Answer 11

NO

Question 12

Is this a valid Psuedocode variable name?

add

Answer 12

NO

Question 13

Is this a valid Psuedocode variable name?

thisPointer

Answer 13

Yes

Question 14

Is this a valid Psuedocode variable name?

a :: character

Answer 14

NO

Question 15

Is this a valid Psuedocode variable name?

pow

Answer 15

NO

Question 16

Psuedocode algorithm headers include:

Answer 16

Name
Description
Preconditions
Postconditions
return

Question 17

Psuedocode has 3 kinds of statements:

Answer 17

sequence of statements [blocks]
loop statement
conditional statement [if/else]

Question 18

Psuedocode: sequences

Answer 18

dont alter execution path within the algorithm

1. assignment
2. input
3. output
4. Arithmetic expressions
5. higher-level english descriptions

Question 19

another name for guarded loop?

Answer 19

while loop

Question 20

How do we measure running time?

Answer 20

in steps

Question 21

Implementation-independent Method

Answer 21

running time as a relationship between size of the input n, and the number of time units t needed to execute the algorithm

Question 22

primitive operations

Answer 22

all take the same amount of time;
assigning a value to variable
calling another algorithm
performing an arithmetic operation
indexing into an array
comparing two values
following an object reference
returning from a method

Question 23

asymptotic complexity or time complexity

Answer 23

only consider the term that grows the fastest to characterize algorithms

Question 24

what is the lowest big Oh?

Answer 24

log log n

Question 25

what is the biggest big Oh?

Answer 25

n!

Question 26

which is a bigger oh? n^k or a^n ?

Answer 26

a^n cannot expect to solve tho

Question 27

algorithms with polynomial or better time complexity are considered:

Answer 27

tractable

Question 28

algorithms with exponential (or worse) complexity are considered:

Answer 28

intractable

Question 29

T or F : problems with simple descriptions cannot be intractable.

Answer 29

False

Question 30

what is the worst case tractable Big OH?

Answer 30

n^k polynomial

Question 31

what is the best case intractable BIG OH?

Answer 31

k^n exponential

Question 32

The travelling salesman problem is:

Answer 32

a bunch of cities and find the cheapest route between them all; grows exponentially if you try them all.

Question 33

Knapsack problem is:

Answer 33

what is the most valuable subset of items whose weight does not exceed some threshold ? grows exponentially

Question 34

what type of problem is worse than intractable/

Answer 34

undecidability

Question 35

an example of an undecided problem?

Answer 35

post's correspondence problem

Question 36

undecided problem:

Answer 36

can't find a solution