Pre

Question 1

What is bandwidth?

Answer 1

bandwidth describes the “Data transfer rate”. That is, the amount of bits transfered from one place to another in within a second.

Question 2

How algorithms are analyzed?

Answer 2

Occasionally, resources such as memory, communication bandwidth and computer hardware are of primary concern, but most often it is computational time that we want to measure.

Question 3

Which operations are considered to be O(1)?

Answer 3

• Arithmetic operations.*
• data movement operations - load, store, copy*
• control operations - conditional and unconditional brance, subroutine call and return*

Question 4

When analyzing we assume a limit on the size of each word of data, explain that

Answer 4

When working with inputs of size n, we assume that integers are represented by clogn bits, where c>=1. The upper bound makes sure n can be represented so we can index the input integers. C is a constant so that the word size don’t grow arbitrarily.

Question 5

What about “shift” operations are exponent operations, how much time do they take?

Answer 5

Here we enter a grey area because both shift and exponent take several operations. But if we assume the real numbers are relatively small, we consider it O(1).

Question 6

What does input size mean?

Answer 6

It can mean two different things, which depends on the problem being analyzed:

• The number of items in the input
  
  • Sometimes described by two numbers, like with graphs, vertices & edges
• The number of bits required to represent the input

Question 7

Describe running time

Answer 7

We look at it in the following way; a constant time is required to execute each line of our pseudocode.

Question 8

• Describe insertion sort.*
• Describe the best case and worst case in terms of run-time.*

Answer 8

Worst case:

• Array is sorted in reverse order. This way the inner loop work as much as possible
• O(n^2)

Best case:

• Array is already sorted. This way the inner loops doesn’t work at all.
• O(n)

Question 9

Describe divide and conquer method:

• Divide - ?
• Conquer - ?
• Combine - ?

How merge sort uses this method?

Answer 9

• Divide the problem to subproblems
• Conquer the subproblems by solving them recursively. When they are small enough, solve them in a straightforward manner.
• Combine the solutions to the subproblems to reach the solution for the problem.

Merge sort:

• Divide the n array problem into two n/2 subproblems.
• Sort the two arrays recursively using merge sort
• Merge the two sorted sequences to have the original sequence sorted.

Question 10

How does merge sort work?

Answer 10

• Input: two sorted arrays of sizes: q-p+1 and r-p
• Operation:
  
  • choose the smallest element of the two arrays to be the next element in the new created array
  • In each array, the last element is infinity. That’s how we maintain these procedure.
• Output:
  
  • New sorted array of the two combined, of size r-q+1.

Question 11

Explain the run time of merge sort

Answer 11

• Recursively:*
• T(n)=2T(n/2)+O(n)*
• 2T(n/2) - two new sub problems of size n/2
• O(n) - time it takes to merge
• division to sub problems is O(1)

Question 12

Describe the assymptotic relation between logarithmic, polynomial and exponential functions.

What is the relation between ln(1+x) and x?

Answer 12

For a>0

log^b(n) = o(n^a)

For any a>1

n^b = o(a^n)

ln and x

Attached

n! < n^n

n! > 2^n

log(n!) = nlogn

Question 13

Which methods do we have for finding assymptotic bounds on recursive formulas?

Answer 13

The substitution method - guess a bound and use mathematical induction to prove

The recursion-tree method - create a tree whose nodes represent the costs at each division. Then use techniques for bounding summations

The master method - provide bound for formulas of the form: T(n) = aT(n/b) + f(n)

Question 14

a^(log(b)) = ?

Answer 14

b^log(a)

Question 15

Memorize

Answer 15

Question 16

To be memorized

Answer 16