Course topics 3 and 4

Self-study (videos and slides in english)

The topics for this week are as follows: (i) Divide and conquer, (ii) Quicksort, (iii) Mergesort

The following links will take you to the video-lectures and the accompanying slides:

Divide and conquer

Divide and conquer part 1.

Divide and conquer part 2.

Divide and conquer part 3.

slides for Divide and conquer

Mergesort

Mergesort part 1.

Mergesort part 2.

slides for Mergesort

Quicksort

Quicksort part 1.

Quicksort part 2.

Quicksort part 3.

slides for Quicksort

Week03 - Glossary

Lecture-questions

Question 1

In the divide and conquer design strategy

we divide the original problem into smaller subproblems and then solve one subproblem and then stop

we divide the original problem into smaller subproblems, which are smaller versions of the original problem

we always divide the original problem into exactly 2 subproblems

we divide the original problem into a set of subproblems whose solutions are all easy to compute and then we stop

Question 2

Which of the following best describes the relationship between the divide and conquer strategy and recursive algorithms?

Since the subproblems formed in a divide and conquer strategy are all different, using a recursive algorithm is almost impossible.

A recursive algorithm is always an implementation of a divide and conquer strategy.

Divide and conquer strategies are often implemented using recursive algorithms because the subproblems are smaller versions of the original problem.

A divide and conquer strategy can never be implemented using a recursive algorithm.

Question 3

Which of the following best describes a data structure for which divide and conquer strategies might be effective?

A data structure which cannot be broken up into parts.

A data structure which can broken up into parts and each part has the same features/properties as the original data structure.

A data structure which can broken up into parts and each part has some new feature or property that the original did not have.

Question 1

It is said that Quicksort uses the divide and conquer strategy when processing an array \(A\). What part of Quicksort corresponds to ’dividing’?

Elements of \(A\) are repeatedly divided by some constant until all the elements have an absolute value less than 1.

Partitioning is used to divide \(A\) into two subarrays and these two subarrays are then themselves used as inputs to Quicksort.

A binary search is used to divide elements of \(A\) into those whose absolute value is less than the pivot and those whose absolute value is greater than the pivot.

Question 2

The purpose of the Quicksort algorithm is

to find the largest element in an array

to produce an array where the elements are in order

to divide the elements of an array into large elements and small elements

Question 3

During Quicksort a partitioning procedure is used. Let the input to the partitioning procedure be array \(A\) and from \(A\) we must partition at least three elements. Which of the following is true? (More than one may be true.)

It is possible that no iterations of the for-loop in the partitioning need be done.

It is possible that the pivot element’s location does not change during partitioning.

It is possible that one of the two subarrays formed during partitioning is empty.

Assuming that \(A[1]\) is the first element, it is possible that the pivot position returned by partitioning is less than 1.

Question 4

In Quicksort, partitioning is used to

split the array into two subarrays, one having elements at least as large as the pivot and the other having elements at most as large as the pivot

split the array into two subarrays, one having elements equal to the pivot and the other having elements that are not equal to the pivot

split the array elements into two subarrays based on whether the pivot is an even number or an odd number

Question 5

Of the following statements, which is true regarding the Quicksort algorithm?

The partitioning procedure always partitions the array into two equally sized subarrays.

Quicksort stops recursively calling itself when the input subarray contains at most 1 element.

Quicksort never needs more than 3 recursion levels.

Each time the partitioning procedure is called, at the end of execution all elements to the left of the pivot are sorted from smallest to largest.

Question 1

It is said that Mergesort uses the divide and conquer strategy when processing an array \(A\). What part of Mergesort corresponds to ’dividing’?

During Mergesort, array \(A\) is divided into two subarrays whose sizes are as close as possible to each other.

When merging two subarrays, one option is to divide one of the subarrays into two parts. Of these two parts, only one is used in the merging operation.

During Mergesort, certain elements of array \(A\) are divided by 2 to make them smaller.

During Mergesort, we start from the left end of \(A\) and find the first index \(i\) for which \(A[i] > A[i+1]\). The array A is divided into subarrays at this index.

Question 2

When two sorted arrays are merged,

we obtain one array where the largest element is located in the middle

we obtain one array which is sorted

we obtain one array whose size cannot be known beforehand

we obtain two arrays one of which is sorted in non-decreasing order and the other is sorted in non-increasing order

Question 3

When two subarrays are merged in Mergesort,

all the elements of one subarray must be larger than the largest element of the other subarray

the final array never contains two consecutive elements from the same subarray

in the final merged array it may be that all elements from one subarray occur consecutively

both subarrays must have exactly the same number of elements

Question 4

Let the size of an array (or subarray) be the number of elements it contains. The Mergesort algorithm

increases the size of the input array by 1

does not recursively call itself when the size of the input array is less than 8

will not work when the size of the input array is odd

divides the input array into two subarrays whose sizes are as close as possible to each another

Question 5

Regarding Mergesort, which of the following are true. (More than one may be true.)

When two subarrays are being merged, both are sorted.

Mergesort never calls itself with an input array (or subarray) containing exactly one element.

A midpoint (or midway index) is only computed when the input array (or subarray) contains at least two elements.

Mergesort will not correctly sort an input array where two or more elements have the same value.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

divide and conquer

quicksort

partitioning

mergesort

merging

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

• An Introduction to Recursion, Part 1
• Efficient recursion
• Wikipedia’s pages on quicksort
• Wikipedia’s pages on mergesort

Week03 - Glossary

Viikko03 - Sanasto

Submit weekly exercises

Questions to be submitted this week .. _courseweek04:

Course topic 4

Self-study

The topics for this week are all related to Asymptotic analysis and algorithm efficiency: (i) Big-O, Big-Omega, Big-Theta (ii) Best case, worst case, average case

The following links will take you to the video-lectures and the accompanying slides:

Big-O, -Omega, -Theta

Big-O, Big-Omega, Big-Theta part 1.

Big-O, Big-Omega, Big-Theta part 2.

Big-O, Big-Omega, Big-Theta part 3.

Big-O, Big-Omega, Big-Theta part 4

slides for Big-O, Big-Omega, Big-Theta

Best case, worst case, average case

Best case, worst case, average case

slides for Best case, worst case, average case

Algorithm efficiency of Mergesort and Quicksort

Algorithm efficiency of Mergesort and Quicksort part 1.

Algorithm efficiency of Mergesort and Quicksort part 2.

slides for Algorithm efficiency of Mergesort and Quicksort

Week04 - Glossary

Question 1

What can we use the big-O notation ( \(O\) ) to describe?

an upper bound on the runtime efficiency of an algorithm when the size of the input data is sufficiently large

a lower bound on the runtime efficiency of an algorithm when the size of the input data is sufficiently large

an accurate count of the number of pseudocode lines needed to implement an algorithm

both an upper and a lower bound on the runtime efficiency of an algorithm when the size of the input data is sufficiently large

Question 2

Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(1)\). Which of the following statements is true?

The algorithm’s execution time will always be at most 1 second, regardless of the size of the input data or the computer the algorithm is run on or the language used to code the algorithm.

For large enough \(n\), \(f(n)\) is never larger than some constant.

The function \(f(n)\) does not depend on \(n\).

The algorithm does not have any for-loops or while-loops.

Question 3

What can we use the big-Omega notation ( \(\Omega\) ) to describe?

an upper bound on the runtime efficiency of an algorithm when the size of the input data is sufficiently large

a lower bound on the runtime efficiency of an algorithm when the size of the input data is sufficiently large

an accurate count of the number of pseudocode lines needed to implement an algorithm

both an upper and a lower bound on the runtime efficiency of an algorithm when the size of the input data is sufficiently large

Question 4

Suppose that algorithms A and B can be used to compute the same thing. Which of the following statements is true? (More than 1 may be true.)

If A runs in linear time and B runs in logarithmic time, A is faster when the input data size is large enough.

If A runs in linearithmic time and B runs in logarithmic time, A is faster when the input data size is large enough.

If A runs in quadratic time and B runs in linearithmic time, B is faster when the input data size is large enough.

If A runs in logarithmic time and B runs in constant time, A is faster when the input data size is large enough.

If A runs in linear time and B runs in linearithmic time, A is faster when the input data size is large enough.

Question 5

Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(n)\). Which of the following statements is true? (More than one may be true.)

\(f(n)\) belongs to \(O(1)\)

\(f(n)\) belongs to \(O(n \log n)\)

\(f(n)\) belongs to \(O(\log n)\)

\(f(n)\) belongs to \(O(n^2)\)

Question 6

Suppose an algorithm’s running time function is \(f(n)\) and we know that \(f(n)\) belongs to \(O(g(n))\) and also to \(\Omega(h(n))\). Which of the following statements is always true?

there exists constants \(c_1\) and \(c_2\) such that asymptotically \(f(n)\) grows at least as fast as a \(c_1 g(n)\) and at most as fast as \(c_2 h(n)\)

\(g(n) = h(n)\)

there exists constants \(c_1\) and \(c_2\) such that asymptotically \(f(n)\) grows at most as fast as a \(c_1 g(n)\) and at least as fast as \(c_2 h(n)\)

there exists a constant \(c_1\) or a constant \(c_2\) such that asymptotically either \(f(n) = c_1 g(n)\) or \(f(n) = c_2 h(n)\)

Question 1

Which statement is true for insertion sort?

it runs in log time for best case input data

it runs in linear time for worst case input data

it runs in quadratic time for worst case input data

Question 2

Suppose array \(A\) is input into insertion sort and suppose insertion sort outputs array \(A\) whose elements are sorted from smallest to largest. What is the worst case input \(A\)?

all input arrays \(A\) are the worst case

array \(A\) whose elements are sorted from largest to smallest

array \(A\) whose first element is the smallest and all other elements can be in any order

Question 3

Suppose we have an array \(A\) with numbers. For this collection of numbers let \(A_{best}\) and \(A_{worst}\) correspond to the best and worst input cases for insertion sort. Which of the following is true?

The runtime efficiencies for both \(A_{best}\) and \(A_{worst}\) belong to the same \(\Theta\) set.

The runtime efficiency of \(A_{best}\) does not belong to any \(\Theta\) set. The same can be said for the runtime efficiency for \(A_{worst}\).

There exists a size for \(A\) for which the runtime efficiency for \(A_{worst}\) can be one milloin times greater than the runtime efficiency for \(A_{best}\).

Question 1

MERGESORT is called with an input array \(A\) having \(n\) elements. Of the following, which is the best upper bound on the number of recursion levels that MERGESORT will use?

\(n\)

\(n/2\)

\(\lceil \log_2 n \rceil\)

\(n \lceil \log_2 n \rceil\)

Question 2

Suppose the asymptotic runtime efficiency of QUICKSORT is analyzed when the starting array \(A\) has \(n\) elements. Which of the following are true?

The best case runtime efficiency occurs when, at all recursion levels, the pivot position is as close as possible to the middle of the input array.

The runtime efficiencies for the best and worst cases are the same.

In the best case no partitioning needs to be done and so the best case runtime efficiency belongs to \(\Omega( n )\).

The best case runtime efficiency belongs to \(\Omega( n \log_2 n )\).

Question 3

Suppose MERGESORT, QUICKSORT and INSERTIONSORT are being compared. Which of the following are true? (There may be more than one true statement.)

The best case runtime efficiencies for both MERGESORT and QUICKSORT are better than \(O( n^2 )\).

Both QUICKSORT and INSERTSORT require temporary storage space whereas MERGESORT does not.

The best case runtime efficiencies for both MERGESORT and QUICKSORT are worse than the best case runtime efficiency of INSERTSORT.

Both QUICKSORT and MERGESORT can be presented as recursive procedures, whereas INSERTSORT cannot.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

asymptotic analysis in general

big-O, big-Omega, big-Theta notation

best case and worst case input data

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

• Khan Academy material on asymptotic notation

Week04 - Glossary

Viikko04 - Sanasto

Submit weekly exercises

Questions to be submitted this week

Posting submission...