Question

Problem 1.
Find the longest increasing sequence of numbers in a 15 x 15 array. For example, if the array, 4x4, contains

97 47 56 36
35 57 41 13
89 36 98 75
25 45 26 17

then the longest increasing sequence of numbers is the sequence of length eight consisting of 17, 26, 36, 41, 47, 56, 57, 97. Note that there are no duplicates in the increasing sequence.

Design and write a program in Java to solve the same problem using a stack and run your program with given test data:

48, 64,254,275, 43, 2, 13,196,286,175, 65,181,244, 12,138
49,267,281,107, 69, 16, 60,123, 3,277,252,198,196, 64,248
32, 51,263,253, 56,118,100,102,160, 57,211,133, 29, 78, 40
267, 40,300,106, 17,187, 5,254,160,142,216,185,143, 74, 94
289, 35, 54, 99,175,136, 14,104, 45, 16,218, 88,187,104,121
11,247,186,287,151, 12, 2,170,201, 66,166,105, 55,230, 96
223, 74,275,292,126,174,236, 36,205, 19, 25,288,239,174, 40
96,294, 61, 8,105,256,181,191,157,155,294,226,144,273,118
244,147,237,165,173, 13,124,170,157, 41, 20, 49, 21, 75,181
6, 98, 10,163,250,251,270,171,178,187,151, 12,113,270, 48
212,168, 14,249,253, 26,220, 33,294,248,208, 59,220,149, 53
89,148,295, 33, 89,108, 8,234,283, 88,151, 56,238,132,125
100,160,116,232, 98, 16,142, 91,182,253,116,231,171,248,282
85,172,231, 99,155,166,245, 60,105,185,126,150,205,122, 83
154,171,157, 99,105,281, 25, 31,282, 93, 74,255,250,274,193

Run your programs for a given input data.
NOTE: A 15 x 15 matrix has been generated by a random function.

Output: Print the complete longest increasing sequence of numbers with their positions.
(It is an sample output for the 4x4 example above.)

17 (3,3)
26 (3,2)
36 (2,1)
41 (1,2)
47 (0,1)
56 (0,2)
57 (1,1)
97 (0,0)

The length of the sequence is 8.

Problem 2

This problem is an exercise in the implementation of queue. We will look at the implementation of a circular array. Then we will use the implementation to solve a problem called the Josephus problem.
Josephus Flavius was a famous historian of the first century at the time of the Second Temple destruction. During the war he got trapped in a cave with a group of 39 soldiers surrounded by Romans. The legend has it that preferring suicide to capture, the people decided to form a circle and, proceeding clockwise around it, to kill every seventh(It will be given as an input) person until only one was left, who must then commit suicide. Josephus, an accomplished mathematician, quickly found the safe spot in the circle (24th) to be the last to go. But when the time came, instead of killing himself he joined the Roman side. The problem rightfully raises the question of how someone might be able to quickly compute the correct place to stand.

Note: For this program, a queue data structure should be used.

In this assignment you are to simulate the Josephus problem.

Input data (interactively input by keyboard):

How many soldiers? 10
The Order of Eliminated Soldiers:
Andy
Shawna
Jianjia
Adam
Jacob
Wesley
Zahari
Thomas
Chris
Ben

The program should simulate the Josephus problem by repeatedly removing the nth name from the list and displaying it. At the end, display the name of the survivor. For the example above, your output should be:
Enter the position 3
Eliminating order:
1. Jianjia (3)
2. Wesley(6)
3. Chris(9)
4. Shawna(2)
5. Zahari(7)
6. Andy(1)
7. Thomas(8)
8. Jacob(5)
9. Ben(10)
(Note: The number of the parenthesis is an original spot number.)

The survivor is Adam(4).

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;


public class SequenceFinder {
public static class Data
{
int x, y, data;
public Data(int x, int y, int data)
{
this.data = data;
this.x = x;
this.y = y;
}
}

public static void main(String[] args) throws FileNotFoundException
{
Scanner input = new Scanner(System.in);
Scanner fileIn;
int size = 0, dimension, max = 0, index = 0;
int[][] array;
String fileName;
System.out.print("Please enter the filename to test: ");
fileName = input.next();
fileIn = new Scanner(new File(fileName));
while(fileIn.hasNextLine())
{
String[] ints = fileIn.nextLine().trim().replaceAll(",", " ").replaceAll("\\s+", " ").split(" ");
size += ints.length;
}
System.out.println(size);
fileIn.close();
fileIn = new Scanner(new File(fileName));
dimension = (int)Math.sqrt(size);
array = new int[dimension][dimension];
ArrayList<Stack<Data>> data = new ArrayList<Stack<Data>>();
for(int i = 0; i < dimension; i++)
{...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Java Program With Lists & Integers
Homework Solution
$40.00
Java
Programming
Codes
Algorithms
Linked Lists
File Management
Data Structures
Libraries
Scanner
Zero Sum Subset
Input
Output
Statements
Variables
Positive Integers
Negative Integers
Binary Mask
Pseudo-Codes
Binary Tree in Java
Homework Solution
$40.00
Java
Programming
Coding
Computer Science
Binary Tree
Data
Generic Types
Functions
Variables
Recursive Methods
Nodes
Input
Output
Java Program: Strings, Integers, Statements
Homework Solution
$20.00
Java
Programming
Coding
Computer Science
Integers
Statements
Strings
Special Characters
Error Messages
Lines
Input
Output
Variables
Operators
Java Programming: User Defined Company
Homework Solution
$40.00
Java
Programming
Computer Science
Company
Stock Symbol
Stock Value
Constructor
Methods
Strings
Variables
Business
Finance
Economy
Hardware
Software
Arrays
Lists
Array Problems in Java: Summation, Average, Min/Max, Searching, Sorting
Homework Solution
$13.00
Java
Programming
Coding
Computer Science
Arrays
Summation
Average
Minimum Number
Maximum Number
Bubble Sort
Selection Sort
Sequential Search
Binary Search
Algorithms
Input
Output
Methods
Integers
Functions
Cylinder Containers in Java
Homework Solution
$38.00
Java
Programming
Codes
Algorithms
Computer Science
Statements
Variables
Loops
Input
Output
Integers
Strings
Geometry
Mathematics
Cylinder
Radius
Finance
Costs
Containers
Companies
Functions
Get help from a qualified tutor
Live Chats