## Description

COSC 336

Assignment 5

Instructions.

1. Due October 14.

2. This is a team assignment. Work in teams of 3-4 students. Submit one assignment

per team, with the names of all students making the team.

3. Your programs must be written in Java.

4. Write your programs neatly – imagine yourself grading your program and see if it is

easy to read and understand. At the very beginning present your algorithm in plain

English or in pseudo-code (or both). Comment your programs reasonably: there is

no need to comment lines like ”i++” but do include brief comments describing the

main purpose of a specific block of lines.

5. You will submit on Blackboard 2 files. The first file should be a .pdf file with the

solution to Exercise 1and with descriptions in English or in pseudocode of the algorithms for the programming task you are required to do and the results that you are

required to report. Make sure you label the results as indicated below. Also insert

images/screenshots with the output you obtain for each testing data. The second file

will contain the Java sources of your two programs.

For editing the above document with Latex, see the template posted on the course

website.

assignment-template.tex and

assignment-template.pdf

To append in the latex file a pdf file, place it in the same folder and then include them

in the latex file with

\includepdf[pages=-,pagecommand={},width=\textwidth]{file.pdf}

To append in the latex file a .jpg file (for a photo), use

\includegraphics[width=\linewidth]{file.jpg}

1

Exercise 1 (has two questions:)

1. Exercise 6.1-6, textbook page 154.

2. Exercise 6.1-7, textbook, page 154.

Hint: You need to show that in the tree view of a heap the nodes indexed with

bn/2c + 1, bn/2c + 2, . . . , n do not have children (so they are leaves) and also that

the nodes indexed with 1, 2, . . . , bn/2c have at least one child (and consequently they

are not leaves). You can consider separately the case when n = 2k (n is even), and

n = 2k + 1 (n is odd). See also the formulas on page 152.

Programming Task 1.

The input consists of a sequence of numbers a[1], a[2, ] . . . , a[n]. Your task is to design

an O(n

2

) algorithm that finds an increasing subsequence with the maximum possible sum.

An increasing subsequence is given by a sequence of indices 1 ≤ i1 < i2 < . . . < ik ≤ n

such that a[i1] ≤ a[

i2] ≤ . . . ≤ a[

ik]. Note the the indices defining the subsequence are not

necessarily consecutive numbers. The program will output the max sum and the increasing

subsequence with that sum.

Your algorithm should work in time O(n

2

).

For example, for sequence 1, 14, 5, 6, 2, 3, the increasing subsequence 1, 14 has the largest

sum 1 + 14 = 15. (1, 5, 6 is another increasing subsequence but its sum, 1 + 5 + 6 = 12 is

smaller.)

Input specification: the first line contains n and the second line contains a1, . . . , an.

Numbers on the same line are separated by spaces. You may assume that n is not bigger

than 10, 000 and all the numbers fit in int.

Output specification: the output contains the maximum possible sum of an increasing

subsequence (note: you do not have to compute the subsequence itself, just the maximum

possible sum).

Sample inputs :

input-5.1.txt

input-5.2.txt

Sample outputs :

answer-5.1.txt

answer-5.2.txt

Test your program on the following inputs:

input-5.3.txt

input-5.4.txt

and report in a table the results you have obtained for these two inputs. Label the results

with appropriate text, for example ”output for file input-*.*.txt”, or something similar.

Hint: You should use a dynamic programming algorithm. For each i ≤ n, define

s[i] = max sum of an increasing subsequence with last element a[i], and

p[i] = index of the element preceding a[i] in an increasing subsequence with max sum

and last element a[i].

2

You start with s[1] = a[1] and p[1] = −1 (-1 is a just a conventional value that indicates that a[1] has no predecessor), and then in order you compute s[2], s[3], . . . s[n] and

p[2], . . . , p[n]. You need to think how to compute s[i], using the preceding s[j], j < i. At

the end, you get the the subsequence in reverse order from last element to the first element. More precisely, first you find the last element of an increasing subsequence with max

sum, and next, starting from the last element, you go from predecessor to predecessor and

construct the subsequence.

3