Question

Problem 1. Word puzzle problem
Word puzzle problem is to find the words in a two-dimensional array of characters. The input to this problem is two input files: one is a two-dimensional array of characters and the other is a list of words we will find in two-dimensional array. These words may be horizontal, vertical, or diagonal in any direction (for a total of eight directions).
Let’s look at a simple example with chars:
A 2-D 7x7 puzzle and a word list file are as follows:

Puzzle        word file Output
n o h t y p s                ruby
m i a r y c c                 cave                       c
l l e k s a h                                            a
r u b y v m e                          r u b y v
e h h e l l m                                     e
p c j n i c e
r e e k b i p

Write a program to find for this problem and run your program with two given input data files (50 x 50 puzzle and a list of words.). And measure the actual running times of your program.

Problem 2. A majority element in an array, A, of size N is an element that appears more than N/2 times(thus, there is at most one). If there is no majority element, your program should indicate this.   Design three different algorithms and write them in Java.
And then run these algorithms with four given sample sets(Majex1, 2, 3, 4) of input files and measure execution time for each case.

a) Method 1 (O(N2) algorithm: Write a program to have two loops and keep track of maximum count for all different elements. If maximum count becomes greater than N/2 then break the loops and return the element having maximum count. If maximum count doesn’t become more than N/2 then majority element doesn’t exist
b) Method 2 (O(NlogN) algorithm using a divided-and-conquer method.   The algorithm begins by splitting the array in half repeatedly and calling itself on each half. When we get down to single elements, that single element is returned as the majority of its (1-element) array. At every other level, it will get return values from its two recursive calls.

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.

2.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;


public class MajorityElement {

public static void main(String[] args) throws FileNotFoundException
{
Scanner input = new Scanner(System.in);
int[] dataSet;
Scanner fileIn;
String fileName;
int dataCount = 0;

System.out.print("Please enter in the file name with the data: ");
fileName = input.next();
fileIn = new Scanner(new File(fileName));
long startTime;
while(fileIn.hasNextInt())
{
dataCount++;
fileIn.nextInt();
}
fileIn.close();
fileIn = new Scanner(new File(fileName));
dataSet = new int[dataCount];
for(int i = 0; i < dataCount; i++)
dataSet[i] = fileIn.nextInt();

startTime = System.nanoTime();
int majority = method1(dataSet);
if(majority != -1)...

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

Related Homework Solutions

Odd Numbers Problem in Java
Homework Solution
$10.00
Java
Programming
Computer Science
Mathematics
Integers
Odd Values
Even Values
Output
Input
Range
Loops
Conditions
Statements
Samples
Java Program For Longest Path in Graph
Homework Solution
$40.00
Java
Programming
Codes
Algorithms
Graph Theory
Classes
Nodes
Edges
Paths
Distances
Loops
Statements
Variables
Input Files
Output Files
HashMap
Array
Integers
Methods
Builder Dash Game in Java
Homework Solution
$163.00
Java
Programming
Computer Science
Codes
Algorithms
Classes
Timers
Statements
Variables
Moves
Instances
Graphics
Animations
Class Money in Java
Homework Solution
$20.00
Java
Programming
Coding
Money
UML Diagram
Computer Science
Dollars
Cents
Parameters
Statements
Methods
Strings
Integers
Finance
Arithmetic Operations
Java & UML Programming Problems
Homework Solution
$20.00
Java
UML
Programming
Coding
Computer Science
Fraction
Denominator
Numerator
Big Integers
Printing Outputs
Decimal Values
Arithmetic Operations
Get help from a qualified tutor
Live Chats