CSC 256 Fall 1997 Puzzle word file Output n o h t y p s ruby m i a r y c c cave XXXXXXXXXXc l l e k s a h XXXXXXXXXXa r u b y v m e XXXXXXXXXXr u b y v e h h e l l m XXXXXXXXXXe p c j n i c e r e e k...

Java programming



CSC 256 Fall 1997 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. 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 Problem 1 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). Word puzzle problem Let’s look at a simple example with chars: A 2-D 7x7 puzzle and a word list file are as follows: Problem 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. The pseudo-code of the algorithm is as follows: procedure GetMajorityElement(a[1...n]) Input: Array a of objects Output: Majority element of a if n = 1: return a[1] k = n/2 elemlsub = GetMajorityElement(a[1...k]) elemrsub = GetMajorityElement(a[k+1...n] if elemlsub = elemrsub: return elemlsub lcount = GetFrequency(a[1...n],elemlsub) rcount = GetFrequency(a[1...n],elemrsub) if lcount > k+1: return elemlsub else if rcount > k+1: return elemrsub else return NO-MAJORITY-ELEMENT c) Method 3 (O(N)) algorithm This algorithm is a two step process. 1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only. 2. Check if the element obtained from above step is majority element. The following is pseudo code of step 1. // Initialize index and count of majority element Maj_index = 0, count = 0 Loop for i = 1 to N – 1 { if a[Maj_index] = = a[i] count++ else count - - if count = = 0 Maj_index = i count = 1 } return a[Maj_index]