Description
1.6. Homework 1.1 (10 Points)
Objective: Compilation of a Java program, designing, implementing, and testing of a algorithm.
Grading:
Correctness: You can lose up to 40% if your solution is not correct
Quality: You can lose up to 80% if your solution is poorly designed
Testing: You can lose up to 50% if your solution is not well tested
Explanation: You can lose up to 100% if your solution if you can not explain your solution during the
grading session
Homework Description:
A prime number is defined as:
A number p is a prime number if p has the following properties:
• p must be a integer
• p >1and
• the factors of p are 1 and itself.
Look at the following program:
1 class Prime {
2
3 public static boolean isPrime(int n) {
4
5 for ( int index = 2; index < n; index ++ ) {
6 if(n%index == 0 )
-4-
7 return false;
8 }
9
10 return true;
11 }
12 public static void main( String args[] ) {
13 for ( int index = 2; index <= 10; index ++ )
14 if ( isPrime(index) )
15 System.out.println(index +””);
16 }
17 }
Source Code: Src/21/Prime.java
This program prints out all prime numbers in the range of [2 … 10].
The that every natural number n and n > 1, n is either a prime number, or can be represented as a product of
prime numbers. In other words n can be represented as:
n = p1 * … * pk; 1 ≤ i ≤ k
The sum of the prime factorials of n is defined as:
sum_of _ prim_ factorials : =
k
i=1
Σ pi
Explanation:
The prime factorials of 6 are 2 and 3. The sum of the prime factorials are 2 + 3 == 5.
Your Work:
Modify Prime.java in such a way that it prints out the sum of the prime factorials for 2 ≤ n ≤ 10.
Requirements:
• You have to name your program Prime.java
• You can only use basic types.
• You can not use any publicly available class or library which can determine if a number is a prime
number.
• Your program has to compute the sum of the prime factorials. In other words your program can not
be something like:
1 class PrimeWrong {
2
3 public static void main( String args[] ) {
4 System.out.println(“The sum of all primes for 2: 2 (2)”);
5 System.out.println(“The sum of all primes for 3: 3 (3)”);
6 System.out.println(“The sum of all primes for 4: 4 (2+2)”)7 System.out.println(“The sum of all primes for 5: 5 (5)”);
8 System.out.println(“The sum of all primes for 6: 5 (2+3)”)9 System.out.println(“The sum of all primes for 7: 7 (7)”);
10 System.out.println(“The sum of all primes for 8: 6 (2+2+11 System.out.println(“The sum of all primes for 9: 6 (3+3)”)12 System.out.println(“The sum of all primes for 10: 7 (2+5)”)13 }
14 }
Source Code: Src/21/PrimeWrong.java
-5-
Example:
An example of a solution execution:
% java Prime
The sum of all primes for 2: 2 (2)
The sum of all primes for 3: 3 (3)
The sum of all primes for 4: 4 (2+2)
The sum of all primes for 5: 5 (5)
The sum of all primes for 6: 5 (2+3)
The sum of all primes for 7: 7 (7)
The sum of all primes for 8: 6 (2+2+2)
The sum of all primes for 9: 6 (3+3)
The sum of all primes for 10: 7 (2+5)
Submission:
% ssh glados.cs.rit.edu # or use queeg.cs.rit.edu if glados is down
# password
# go to the directory where your solution is …
% try hpb-grd lab1-1 ’All files required’
# you can see if your submission was successful:
# try -q hpb-grd lab1-1
Solution:
(This solution serves as the basis for the discussion in class. Sometimes there will be errors introduced to
show common mistakes)
1 /*
2 * all is hardcoded
3 */
4 class Prime {
5
6 static String sumOfAllPrimesAsString = “”;
7 public static boolean isPrime(int n) {
8 for ( int index = 2; index < n; index ++ ) {
9 if(n%index == 0 )
10 return false;
11 }
12
13 return true;
14 }
15 private static int sumOfAllPrimes(int n) {
16 int sumOfAllPrimes = 0;
17 int mayBePrime = 1;
18 if (n<2)
19 return -1;
20 while (n>1){
21 mayBePrime++;
22 if ( isPrime(mayBePrime) ) {
23 while (n%mayBePrime == 0 ) {
24 sumOfAllPrimes +=mayBePrime;
25 n =n/mayBePrime;
-6-
26 if ( sumOfAllPrimesAsString == “”)
27 sumOfAllPrimesAsString = “”+mayBePrime;28 else
29 sumOfAllPrimesAsString = sumOfAllPrimesAs30 }
31 }
32 }
33 return sumOfAllPrimes;
34 }
35 public static void main( String args[] ) {
36 int minimum = 2;
37 int maximum = 15;
38 int sumOfAllPrimes = 0;
39
40
41 for ( int index = minimum; index <= maximum; index ++ ) {
42 sumOfAllPrimesAsString = “”;
43 System.out.println(“The sum of all primes for ” + index +
44 “: ” +
45 sumOfAllPrimes(index) +” “+
46 ” (” + sumOfAllPrimesAsString + “)” );
47 }
48
49
50 }
51 }
Source Code: Src/21_sol/Prime.java
1.7. Homework 1.2 (10 Points)
Objective: Designing, implementing, and testing of a algorithm.
Grading:
Correctness: You can lose up to 40% if your solution is not correct
Quality: You can lose up to 80% if your solution is poorly designed
Testing: You can lose up to 50% if your solution is not well tested
Explanation: You can lose up to 100% if your solution if you can not explain your solution during the
grading session
Homework Description:
Givenaset of sticks S, with | S | = n. The set of the lengths of the sticks are:
sl = {s1, … sn}
Given is a stick s_new, with length l; does a combination of elemenets of
{s1, … sn}
exist so such
l =
k
i=1
Σ si
; 1 ≤ k ≤ n
If such a set exist print out one set.
Explanation:
Assume give is the following set S = { 1, 2, 3, 4, 6 } and s_new, with length 5. The following combinations
would add up to the lenght of 5:
-7-
• 1 +4=5
• 2 +3=5
Your Work:
A1inch, 2 inch stick would add up to a stick of 3 length, a 1 inch, 2 inch, and 2 inch stick could add up to
a stick of length 5 and 4.
Your Work:
You hav e sticks with the following lengths: 1 inch, 5 inch, 8 inch, 12 inch, 12 inch, 35 inch, 35 inch, 35
inch, and 61 inch.
Write a program which can determine if a combination for f2s_new = 1, 6, 9, 24, 110, 111, 115, 62, 24,
202, 203, 204, 205 exist.
Write a program to solve the problem.
A snippet of the code might look like this:
public class Sticks {
static int[] stickLengths = { 1, 5, 8, 12, 12, 35, 35, 35, 61 };
static int[] unknowStickLengths = { 1, 6, 9, 24, 110, 111, 115, 62, 24, 202, 203, 204,…
public static void main( String[] arguments ) {
for ( int index = 0; index < unknowStickLengths.length; index ++ )
doTestLength(unknowStickLengths[index]);
}
}
Requirements:
• You have to name the file: Sticks.java
• You can use arrays to store the stick lengths and unknowSticks lengths, and you have to use an iterative algorithm.
• You can hardcode all values in your program.
• You can use basic types and arrays.
• You can not use any publicly available class or library which can determine if a particular set of
sticks matches the length.
Example:
An example of a solution execution:
% java Sticks
3 inch: yes; used sickLengths = 3 inch
5 inch: yes; used sickLengths = 5 inch
Submission:
% ssh glados.cs.rit.edu # or use queeg.cs.rit.edu if glados is down
# password
# go to the directory where your solution is …
% try hpb-grd lab1-2 ’All files required’
# you can see if your submission was successful:
# try -q hpb-grd lab1-2
Solution:
(This solution serves as the basis for the discussion in class. Sometimes there will be errors introduced to
show common mistakes)
-8-
1 public class Sticks {
2 static int[] stickLengths = { 1, 5, 8, 12, 12, 35, 35, 35, 61 };
3 static int soManySticks = stickLengths.length;
4 static int[] unknowStickLengths = { 1, 6, 9, 24, 110, 111, 115, 62, 24, 202, 25
6 private static String theFollowingSticksAreUsed (int value) {
7 String returnValue = “”;
8 for ( int index = soManySticks; index >= 0 ; index –) {
9 if ( ( ( 1 << index ) & value ) == ( 1 << index ) )
10 returnValue += stickLengths[index] + ” inch “;
11
12 }
13 if ( returnValue == “” )
14 returnValue = “empty set”;
15 return returnValue;
16 }
17
18 private static int calculteLengthForThisSet(int value) {
19 int sum = 0;
20 for ( int index = soManySticks; index >= 0 ; index –) {
21 if ( ( ( 1 << index ) & value ) == ( 1 << index ) ) {
22 sum += stickLengths[index];
23 }
24
25 }
26 return sum;
27 }
28 private static void doTestLength(int thisLength) {
29 int setSize = (int)Math.pow(2, stickLengths.length );
30 boolean foundAset = false;
31
32 int index = 0; // see comment in loop
33
34 while ((index < setSize ) && ! foundAset ) {
35 int sum = calculteLengthForThisSet(index);
36 if (!(foundAset = ( thisLength == sum ) ) )
37 index ++;
38 }
39 if ( foundAset ) {
40 System.out.println(thisLength +”inch: ” +
41 “\tyes; used stickLengths = ” +
42 theFollowingSticksAreUsed(index) );
43 } else
44 System.out.println(thisLength +”inch: \tno”);
45 }
46 public static void main( String[] arguments ) {
47 for ( int index = 0; index < unknowStickLengths.length; index ++ )
48 doTestLength(unknowStickLengths[index]);
49 }
50 }
Source Code: Src/21_sol/Sticks.java
