Introduction

Question 1

What does a problem p specify?

Answer 1

Given an input, what should be the output?

Question 2

What is each allowed input to the problem called?

Answer 2

An instance

Question 3

What is: an algorithm for problem P?

Answer 3

A step-by-step prodecure that, when given any instance I for problem P, gives the correct output in a finite amount of time

To describe an algorithm, we must provide a clear, unambiguous sequence of instructions. Anybody should be able to implement it without our help.

Question 4

For the attached problem P:

What is an example of an instance of problem P?

What would the correct output be of that instance?

Answer 4

Question 5

Design an algorithm for the attached example, adding two binary numbers.

Answer 5

Question 6

What are 3 types of questions we often ask about an algorithm?

Answer 6

Question 7

What is a model of computation?

Why is it important?

Answer 7

Question 8

In RAM word model, how is data stored in the machine

Answer 8

Data is stored in the machine as word

Each word consists of u binary digits (bits)

(for example u = 32 or u = 64)

Question 9

In the RAM word model what does each word represent?

Answer 9

Each word represents an integer. The possible values are called the universe u

Question 10

In the universe U, using standard encoding for signed integers, the range of each word U =?

Answer 10

U = {-2^u-1,…,2^u-1-1}

Question 11

In the RAM word model, what can we stored using O(1) words?

Answer 11

Any int, long, float, double can be stored using 0(1) words

Question 12

How much time does it take to read or write any word in the RAM word model?

Answer 12

Question 13

What is a primitive operation?

Answer 13

A primitive operation is an instruction that is assumed to take one “CPU step” (i.e., O(1) time, independent on word size u)

Question 14

What are the primitive operations in the RAM word model?

Answer 14

Question 15

What are examples of complicated arithmetic operations that are non-primitive

Answer 15

Question 16

What are the possible measures of an algorithms efficiency?

Answer 16

Question 17

In general, how do we express the cost of an algorithm in terms of the input size?

Answer 17

Question 18

If one line of code consists of a “small numer” of primitive opertions, let’s call that _______

Answer 18

Question 19

Count the steps of the two following operations

int x = 2;

int y = 5;

int z = x + y;
z += 10;

vs

int z = 10*(2+5);

Answer 19

Question 20

In general, how do you calculate the number of steps in a loop?

Answer 20

Question 21

What is the running time of the following? (using summation notation)

Answer 21

Question 22

What is the running time of the following (in summation)?

Answer 22

Question 23

What is the running time in terms of someFunction?

Answer 23

Question 24

How do we calcylate the number of steps if the code contains conditional statements?

Answer 24

Question 25

Answer 25

Question 26

What is the run time?

Answer 26

Question 27

Answer 27

Question 28

What is the run time?

Answer 28

Question 29

Answer 29

Question 30

What is the summary of Asymptotic notation?

Answer 30

Question 31

Describe how Big-Oh represents an upper bound, but not in an exact way

Answer 31

Question 32

What should you write, instead of f(n) = O(g(n))

Answer 32

f(n) € O(g(n))

Question 33

Answer 33