CS 307Assignment 1B, Designing and Implementing Algorithms
Programming Assignment 1B: Individual Assignment. You must complete this assignment on your own. You may not discuss their work with anyone except the instructor and other members of the instructional staff (TA, section leader, or lab proctor). You may not acquire from any source (e.g., another student or an internet site) a partial or complete solution to a problem or project that has been assigned. You may not show another student your solution to an assignment. You may not have another person (current student, former student, tutor, friend, anyone) “walk you through” how to solve an assignment. Review the class policy on collaboration from the syllabus.
Description: The purposes of this assignment are:
Provided File: A1.java contains 3 method shells you will complete and a main method used for testing. A1.html is the documentation for the program.
Assignment design in CS307: If you took CS305J, one thing that will be different is you will not always write complete programs. You will often, but not always, be given a partial program and have to complete it. You will do a lot of coding to "spec", that is coding to specification; the program will have already been designed and you must implement it given the design. You will have to develop algorithms on your own, but the specification of methods will already be complete. Many of the methods you write won't ask the user for input or do any output. The "input" to the methods will be via parameters and the "output " will be the return value. Of course you can add user input and output in a method that calls the specified method to provide a way of interactively testing the methods you write, but this is not required.
Download A1.java and complete the methods
matches, findMmajority, and
mostVowels. You may add helper methods if you wish,
but do not change the headers for any of the original methods.
The matches method:
Complete the matches method in A1.java.
Very important: The only methods from the Java library you may use
in completing method matches are the charAt and
length methods from the String class and the
constructor and add method from the ArrayList class.
Also, very important. The method does not do any input or output on its own. You don't "ask the program user" for the input string or print out the result. The input comes as a parameter to the method and the output is the return value from the method.
This method finds all complete matches of a target String in a source String. String matching is used in many different applications. Every time you use the find command or replace command in a word processing document or on a web page you are making use of string matching. String matching is also used in areas such as computer virus detection and mapping of DNA.
You may implement a naive, brute force string matching algorithm as described below and you will not lose points for efficiency. The intention is for you to design and implement your own algorithm. Don't look up an algorithm on the web and implement that. You should take pencil and paper and work out your own algorithm and then implement that in Java code. This is an exercise in creating a non trivial algorithm. Something you will have to do later in the class on assignments and exams.
Example of naive string matching algorithm: Assume target string is "aaa" and source string is "aaaabaaaa". The answer for this example is [0, 1, 5, 6]. Here is a detailed explanation of how to arrive at the answer for this example. The numbers indicate the position of each character in the source and target strings.
Initial lineup per naive algorithm. The numbers are the indices of each character in the Strings.
012345678
aaaabaaaa source String
aaa target String (looking for
complete matches of target in source)
012
The above line up results in a match starting at index 0 in source.
Next slide the target
down 1 spot.
012345678
aaaabaaaa
aaa
012
The above lineup results in a match starting at index 1 in source.
Slide the target down another spot.
012345678
aaaabaaaa
aaa
012
The above lineup is not a match.
Slide the target down another spot.
012345678
aaaabaaaa
aaa
012
The above lineup is not a match.
Slide the target down another spot.
012345678
aaaabaaaa
aaa
012
The above lineup is not a match.
Slide the target down another spot.
012345678
aaaabaaaa
aaa
012
The above lineup results in a match starting at index 5 in source.
Slide the target down another spot.
012345678
aaaabaaaa
aaa
012
The above lineup results in a match starting at index 6 on source.
Tip: The real complexity in this problem is that you have to keep track of two different indices. The index in the target string and the index in the source string. These two values are not equal to each other, except for the first line up.
In method matches you will be returning an ArrayList of
Integer objects. The
method includes the code to create the ArrayList. To add an
int to the end
of the ArrayList use the add method as show below.
ArrayList<Integer> result = new
ArrayList<Integer>();
int index = 0;
result.add(index);
// even though it is an ArrayList of Integer objects, ints may
// be added directly (example of autoboxing)
The fastest known string matching algorithm is the Boyer-Moore String algorithm. If interested after you have completed youw own method read sections 1- 4 from the original paper. You are NOT expected to implement the Boyer-Moore algorithm.
The findMajority method
Complete method findMajority in A1.java. You may add helper methods if you wish.
Very important. You may not use any other Java classes when completing this method.
This method determines if an array of ints contains a majority element.
/**
* Determine if there is a majority element in an array of ints.
* The parameter list is not altered as a result of this
* method.
* @param list != null
* @return the first index of the first occurrence of the majority element if it exists.
* If a majority element does not exist return -1.
*/
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 such element. For example the array
index 0 1
2 3 4 5 6 7
element 3, 4, 4, 4, 2, 4, 2, 4
has a majority element equal to 4.
Note your method returns the index of the first occurrence of the majority element if one exists. If there is no majority element your method returns -1.
The following array does not have a majority element:
index 0 1
2 3 4 5 6 7
element 3, 3, 4, 4, 2, 4, 2, 4
To be a majority element it
must appear more than N/2 times where N is equal to the list. With a list of
length 8 there must be at least 5 elements equal to one another for there to be
a majority element. Your method shall return -1 if an array does not contain a
majority element.
The mostVowels method:
Complete the mostVowels method in
A1.java.
On method mostVowels you can use any and all
parts of the Java standard library you choose. It can be completed
relatively easily just using arrays and some methods from the String class.
The mostVowels methods takes in an array of Strings as a parameter and determines which String has the most vowels.
For this method vowels are the characters 'A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', and 'u'. The method is not trying to determine which String has the largest number of distinct vowels. Thus "aaaaaa" has more vowels that "aeiou". "aaaaaa" has 6 vowels while the String "aeiou" only has 5 vowels. You can use whatever String methods you want when completing this method.
/**
* Determine the index of the String thaht
* has the largest number of vowels.
* Vowels are defined as 'A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', and 'u'.
* The parameter list is not altered as a result of
* this method.
* pre: list != null, list.length > 0, there is an least 1 non null element in
list
* post: return the index of the String in list that has the largest number of
characters that are vowels.
* If there is a tie return the index closest to zero.
* @param list the array to check
* @return the index of the String in list that has the greatest number of
vowels.
*/
public static int mostVowels(String[] list)
The file A1.java contains a main method with some tests for
the matches, findMajority, and mostVowels
methods. Some of these tests may be
incorrect. You are required to find and fix any incorrect tests. Use the
class listserv
to share information about other students about which tests are wrong and
how to correct them.
Add at least 5 more tests for each method (15 tests total) to the main method. You may post your tests to the listserv and you may use tests that other people post to the listserv.
A simple way
to test the matches and findMajority methods is to create ArrayLists that hold the expected
results and then use the equals method to
check the returned ArrayList with the expected ArrayList. Here is an
example:
ArrayList<Integer> result;
ArrayList<Integer> expected = new ArrayList<Integer>();
//test 1
result = matches("aaaa", "aaa");
expected.add(0);
expected.add(1);
if( result.equals( expected ) ) {
System.out.println( "passed test 1." );
}
else {
System.out.println( "failed test 1." );
}
//empty expected to get it ready for next test
expected.clear();
Fill in the header for A1.java. Replace <NAME> with your name. Note, you are stating, on your honor, that you did the assignment on your own, as required. If you copy your code from another source (internet, another student in the course, another student who previously took the course) you will be guilty of academic dishonesty and will receive am F in the course.
When finished turn in your A1.java program using the
turnin program.
Checklist: Did You: