Tutorial 16, CPSC 331, Winter 2012

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23

 Merge Sort

About This Exercise

The objectives of this exercises are

Please read through and try to solve the problems on this exercise before attending the tutorial.

Expected Background

This exercise is based on material presented during the lecture on MergeSort. You can also find information about MergeSort on the Wikipedia page on this algorithm.

Warmup Problems — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, and attended the lecture in which MergeSort was discussed (reviewing the online notes, as needed).

These warmup problems will not be discussed in the tutorial; students who do have difficulty with them should contact the course instructor to get extra help.

  1. What is a “Divide and Conquer” algorithm? Explain why MergeSort is an example of this kind of algorithm.

  2. An algorithm to Merge two sorted arrays is used repeatedly as a subroutine by the MergeSort algorithm.

    1. Explain briefly what the Merge does. The inputs are mentioned above; what is the expected output?

    2. Briefly describe (or give pseudocode for) an algorithm that can be used to solve this problem, using a number of steps that is linear in the size of the input, in the worst case.

  3. Trace the execution of MergeSort by hand, when each of the following arrays is given as input.

    1.  

      Input Array for Sorting Problem

    2.  

      Another Input Array

To Be Discussed In the Tutorial

  1. When we consider the space used by MergeSort or, indeed, any recursive algorihm, we shoud include the space that is being used to keep track of all the recursive calls to this algorithm that are in progress at any given time.

    To keep things simple, consider a straightforward implementation of this algorithm that is appropriate if the computer being used has a single processor and suppose we are not using threads or any other mechanism for parallel processing.

    Recall that a run-time stack (possibly called an “activation stack”) is used to keep track of the information mentioned above, when a recursive algorithm like MergeSort is executed.

    1. What is the maximum size of this activation stack when MergeSort is executed? That is, how many activation records are on this stack at any given time? You should be able to state this as a function of the length of the input array.

    2. Notice that, if MergeSort was initially called with an array of length n as input, then every such activation record corresponds to a call to MergeSort with an array with some length, between one and n, as its input.

      What are the lengths of the input arrays that are found as the inputs on this stack, and how many arrays of a given length are found on the stack at once?

      To keep things simple you may assume that n is a power of two.

    3. Using the above, try to show that the total space used for an execution of MergeSort on an input array of length n is linear in n.

  2. How would your answer for the above change, if you were using threads when implementing this algorithm?

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial16.html