Course week 3

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

Course week 3¶

Self-study (videos and slides in english)¶

Divide and conquer¶

Mergesort¶

Quicksort¶

Lecture-questions¶

Submit weekly exercises¶