## 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