CLRS - Chapter 1 & 2

Question 1

What is an algorithm?

Answer 1

An algorithm in any well-defined computational procedure that takes some value, or set of values as input and produces some value, or set of values, as output

Question 2

How do we formally define the sorting problem?

Answer 2

Input: a sequence of n numbers

Output: a permutation (reordering) of the input sequence such that a1’ <= a2’ <= … <= an’

Question 3

When an algorithm is said to be correct?

Answer 3

An algorithm is said to be correct if, for every input instance, it halts with the correct output.

Question 4

What is a data structure?

Answer 4

A data structure is a way to store and organize data in order to facilitate access and modifications.

Question 5

In which cases insertion sort is said to be efficient?

Answer 5

When the sorting involves a small number of elements. , because the constant is usually way lower than in merge sort or quick sort. Since it sorts IN PLACE.

Question 6

Which line is missing from the insertion sort algorithm below?

INSERTION-SORT(A):
   for i=1 to A.length - 1:
      key = A[i]
      j = i - 1
      while j >= 0 and A[j] > key:
         A[j + 1] = A[j]
         j = j - 1

Answer 6

A[j + 1] = key

Question 7

Which line is missing from the insertion sort algorithm below?

INSERTION-SORT(A):
   for i=1 to A.length - 1:
      key = A[i]
      j = i - 1
      while j >= 0 and A[j] > key:

     j = j - 1
  A[j + 1] = key

Answer 7

A[j + 1] = A[j]

Question 8

What is the loop invariant of Insertion Sort?

Answer 8

At the start of each iteration of the for loop, the subarray A[0 .. i - 1] consists of the elements originally in A[0 .. i - 1], but in sorted order.

Question 9

What is the best-case running time of Insertion Sort (ignoring leading constants and lower order terms)?

Answer 9

O(n)

Question 10

What are the three properties that must be proved for a loop invariant?

Answer 10

Initialization, Maintenance and Termination

Question 11

What is the meaning of algorithm analysis?

Answer 11

Analyzing an algorithm has come to mean predicting the resources that the algorithm requires. Ocasionally, resources such as memory, communication bandwidth, or computer hardware are of primary concern, but most often it is computational time that we want to measure.

Question 12

Does the running time of insertion sort depend on the input?

Answer 12

True

Question 13

What is the “running time” of an algorithm?

Answer 13

Is the number of primitive operations, instructions or “steps” executed.

Question 14

What are the three reasons why we are mostly concerned about the worst-case running time of an algorithm?

Answer 14

+ It gives us and upper bound. A guarantee that the algorithm won’t take any longer
+ It occurs fairly often (searching a database)
+ Often as bad as the average-case (insertion sort)

Question 15

What are the three steps of the Divide-and-conquer approach of algorithm design:

Answer 15

Divide, Conquer and Combine

Question 16

Describe the three steps of the Divide-and-conquer approach in merge sort:

Answer 16

+ Divide the n-element sequence to be sorted in two subsequences of n/2 elements each
+ Conquer: Sort the two subsequences recursively using merge sort ( base case when n = 1)
+ Combine: Merge the two sorted subsequences using merge procedure, to produce the desired output.