Scribd
Upload
358 views1 page

Assignment 3 PDF

The document describes an assignment involving sorting integers using quicksort. It involves computing the number of comparisons needed to sort an input file containing integers 1-10,000 using three different pivoting rules: (1) always using the first element as pivot, (2) always using the last element, and (3) using the median-of-three rule. It also involves designing divide and conquer algorithms to determine if an array contains an element equal to its index, compute x^n, and find the smallest index of 1 in a sorted boolean array.

Uploaded by

Faizaan Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
358 views1 page

Assignment 3 PDF

The document describes an assignment involving sorting integers using quicksort. It involves computing the number of comparisons needed to sort an input file containing integers 1-10,000 using three different pivoting rules: (1) always using the first element as pivot, (2) always using the last element, and (3) using the median-of-three rule. It also involves designing divide and conquer algorithms to determine if an array contains an element equal to its index, compute x^n, and find the smallest index of 1 in a sorted boolean array.

Uploaded by

Faizaan Ali
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Analysis of Algorithms Spring 2016

Assignment - 3
Task - I: Sorting Integers using Quick-Sort
The input file IntegersToSort.txt contains all of the integers between 1 and 10,000 (inclusive, with no
repeats) in unsorted order. The integer in the ith row of the file gives you the ith entry of an input array.
Your task is to compute the total number of comparisons used to sort the given input file by using QuickSort algorithm. As you know, the number of comparisons depends on which elements are chosen as pivots,
so we'll ask you to explore three different pivoting rules. You should not count comparisons one-by-one.
Rather, when there is a recursive call on a subarray of length n, you should simply add n1 to your running
total of comparisons. (This is because the pivot element is compared to each of the other n1 elements
in the subarray in this recursive call.)

Part-a: Compute the number of comparisons, always using the first element of the given array as the
pivot element

Part-b: Compute the number of comparisons, always using the final element of the given array as the
pivot element.

Part-c: Compute the number of comparisons, using the "median-of-three" pivot rule. [The primary
motivation behind this rule is to do a little bit of extra work to get much better performance on input
arrays that are nearly sorted or reverse sorted.] In more detail, you should choose the pivot as follows.
Consider the first, middle, and final elements of the given array. (If the array has odd length it should be
clear what the "middle" element is; for an array with even length 2k, use the kth element as the "middle"
element. So for the array 4 5 6 7, the "middle" element is the second one --- 5 and not 6!) Identify which
of these three elements is the median (i.e., the one whose value is in between the other two), and use
this as your pivot.
EXAMPLE: For the input array 8 2 4 5 7 1 you would consider the first (8), middle (4), and last (1) elements;
since 4 is the median of the set {1, 4, 8}, you would use 4 as your pivot element.

Task - II: Designing Divide and Conquer Algorithms


Part-a: Given a sorted array A of n distinct integers, design an O(logn) divide and conquer algorithm that
can decide whether or not there is an index i such that A[i] = i. [HINT: Take inspiration from binary search]

Part-b: Design a divide and conquer algorithm which can compute xn in O(logn) time.
Part-c: Given a sorted boolean array A, design an algorithm to find out the smallest index i in the array
A such that A[i] = 1 in O(logn) time. [HINT: Take inspiration from binary search]

Deadline: September 10, 2016. This is an individual assignment.

Part of this assignment has originally been designed by Tim Roughgarden for the course he taught at Coursera.

You might also like