CSC 225 ASSIGNMENT 2-PROGRAMMING and WRITTEN solved

Description

1 Programming Assignment
In a sequence 𝑆 = 𝑠1, 𝑠2, … , 𝑠𝑛 of 𝑛 integers, an inversion is a pair of elements 𝑠𝑖 and 𝑠𝑗 where
𝑖 < 𝑗 (that is, 𝑠𝑖 appears before 𝑠𝑗 in the sequence) and 𝑠𝑖 > 𝑠𝑗
. For example, in the sequence
𝑆 = 2, 1, 5, 3, 4
the pairs (2,1), (5,3) and (5,4) are inversions.
The programming assignment is to implement an algorithm which counts the number of
inversions in an input sequence:
Input: An array 𝐴 of 𝑛 integers in the range 1 − 𝑛.
Output: An integer, corresponding to the number of inversions in 𝐴.
An array with 𝑛 elements may have as many as
(
𝑛
2
) =
𝑛(𝑛 − 1)
2
inversions. When the number of inversions 𝑘 may be any value between 0 and 𝑛(𝑛−1)
2
, the best
algorithm for counting inversions has running time 𝑂(𝑛 log(𝑛)). There also exists a 𝑂(𝑛 + 𝑘)
algorithm for counting inversions, which is 𝑂(𝑛
2
) when 𝑘 ∈ 𝑂(𝑛
2
).
In this assignment, we will assume that the number of inversions is at most 𝑛 (that is, 𝑘 ≤ 𝑛).
When the 𝑂(𝑛 + 𝑘) algorithm is used with such values of 𝑘, its running time is 𝑂(𝑛 + 𝑛) =
𝑂(𝑛). For full marks, your implementation must run in 𝑂(𝑛) time when 𝑘 ≤ 𝑛.
Your task is to write a java program, stored in a file named CountInversions.java that
contains a function CountInversions, which takes an integer array A as its only argument,
and returns an integer value. The main function in your code should help you test your
implementation by getting test data or reading it from a file. It should also handle errors but don’t
worry about running times.
2 Examples
The table below gives the inversion count and a list of the inversions present in several small
input arrays.
Input Array # of Inversions Inversions
1, 2, 3 0 none
1, 2, 3, 5, 4 1 (5, 4)
10, 30, 40, 20, 50 3 (30, 20), (40, 20)
4, 3, 2, 1, 5, 6 6 (4, 3), (4, 2), (4, 1), (3, 2), (3, 1), (2, 1)
5, 1, 2, 3, 4 4 (5, 1), (5, 2), (5, 3), (5, 4)
3 Test Datasets
A set of input files have been uploaded to ConneX, containing arrays of various sizes and
inversion counts. You should test your implementation on the uploaded files before submitting.
Note that an algorithm with a running time which is 𝑂(𝑛 log 𝑛) or better should be able to
process any of the files within a few seconds. The uploaded files may not cover all possible
cases, so you should test your implementation on other inputs as well.
4 Evaluation Criteria
The programming assignment will be marked out of 25, based on a combination of automated
testing (using large test arrays similar to the ones posted on ConneX) and human inspection. All
of the tested input arrays will have an inversion count 𝑘 which is at most 𝑛.
Score (/25) Description
0 – 5 Submission does not compile or does not
conform to the provided template.
5 – 15 The implemented algorithm is 𝑂(𝑛
2
) or is
substantially inaccurate on the tested inputs.
15 – 20 The implemented algorithm is 𝑂(𝑛 log 𝑛) or
contains minor errors.
20 – 25 The implemented algorithm is 𝑂(𝑛 + 𝑘) on an
array with 𝑛 elements and 𝑘 inversions, resulting
in a 𝑂(𝑛) algorithm when 𝑘 ∈ 𝑂(𝑛).
To be properly tested, every submission must compile correctly as submitted. If your submission
does not compile for any reason (even trivial mistakes like typos), it will receive at most 5 out of
25. The best way to make sure your submission is correct is to download it from ConneX after
submitting and test it. You are not permitted to revise your submission after the due date, and
late submissions will not be accepted, so you should ensure that you have submitted the correct
version of your code before the due date. ConneX will allow you to change your submission
before the due date if you notice a mistake. After submitting your assignment, ConneX will
automatically send you a confirmation email. If you do not receive such an email, your
submission was not received. If you have problems with the submission process, send an email
to the instructor before the due date.

CSC 225
ALGORITHMS AND DATA STRUCTURES I
ASSIGNMENT 2
1. Describe how to implement the stack ADT using two queues. What is the running time of the push()
and pop() methods in this case?
2. Show the various steps of Selection Sort, Bubble Sort and Insertion Sort on the example array,
𝐴 = {5, 7, 0, 3, 4, 2, 6, 1}.
3. An Array 𝐴 contains 𝑛 − 1 unique integers in the range [0, 𝑛 − 1]. That is, there is one number in
this range that is not in 𝐴. Describe in pseudo-code an 𝑂(𝑛)-time algorithm for finding that number.
You are only allowed to use 𝑂(𝑙𝑜𝑔 𝑛) bits of additional space besides the array 𝐴 itself.
4. Consider an implementation of a stack using an extendible array. That is, instead of giving up with a
“StackFullException” when the stack becomes full, we replace the current array 𝑆 of size 𝑁 with a
larger one of size 𝑓(𝑁) and continue processing the push operations. Suppose that we are given two
possible choices to increase the size of the array: (1) 𝑓(𝑁) = 𝑁 + 𝑐 (for convenience, we start
with an initial array of size 0) (2) 𝑓(𝑁) = 2𝑁 (we start with an initial array of size 1). Compare the
two strategies and decide which one is better.
To analyze the two choices, assume the following cost model: A “regular” push operation costs one
unit of time. A “special” push operation, when the current stack is full, costs 𝑓(𝑁) + 𝑁 + 1 units
of time. That is, we assume a cost of 𝑓(𝑁) units to create the new array, 𝑁 units of time to copy the
𝑁 elements and one unit of time to copy the new element.
5. Characterize each of the following recurrence equations using the master method (assuming that
𝑇(𝑛) = 𝑐 for 𝑛 < 𝑑, for constants 𝑐 > 0 and 𝑑 ≥ 1).
a. 𝑇(𝑛) = 2𝑇(𝑛/2) + log 𝑛
b. 𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑛
2
c. 𝑇(𝑛) = 16𝑇(𝑛/2) + (𝑛 log 𝑛)
4
d. 𝑇(𝑛) = 7𝑇(𝑛/3) + 𝑛
e. 𝑇(𝑛) = 9𝑇(𝑛/3) + 𝑛
3
log 𝑛