# CS 1025 Computer Science Fundamentals IAssignment 1

Department of Computer Science
University of Western Ontario
Given: September 13, 2011
Due: September 26, 2011

This assignment has a total of 60 points.

The instructions to hand in this assignment are located here.

Please see the course outline for information on late penalties and the rules of ethical conduct.

## Introduction

This assignment is to practice the mechanics of creating Java programs and submitting assignments.

For each of the questions below, hand in

• an implementation
• documentation of the class and each method
• the output

## Question 1. Creating a Class (30 points)

Write a class HelloWorld that has a main method that

• prints "Hello world!", then
• prints the result of calculating 6 times 7, then
• prints "Goodby world!"

## Question 2. Counting Primes I (30 points)

Compile and run the prime number seive given in class where the main program does its work by calling helper functions. This is the one organized as follows:

```public class Primes {
// Make a boolean array of the desired size with all elements true.
public static boolean[] makeSieve(int n) {
...
}
// Cancel the multiples k*n, for k = 2, 3, etc
public static void doCancel(boolean[] marks, int n) {
...
}
// Print out the required results.
public static void printPrimes(boolean[] marks) {
...
}
public static void main(String[] args) {
boolean[] sieve = makeSieve(1000);
for (....) doCancel(sieve, n);
printPrimes(sieve);
}
}
```

## Question 3 [BONUS]. Using Arrays (20 points)

Write a class NumberFactory that has a method to compute a sum of squares using the following artificially complicated scheme:

• There should be a method int sumOfSquares(int n) that computes the sum of the squares of the integers 0 to |n|. That is, it should calculate and return the value 0*0 + 1*1 + 2*2 + ... + n*n.
• This method should not print anything.
• The method should create an array of size |n| + 1 that contains entries of type int.
• The array, let's call it a, should be filled in a loop so that a[i] = i*i.
• The sum should be computed using a second loop, by adding up the entries of a.
• Test your sumOfSquares method by calling it several times from the main program and printing the results. Test with at least the values 1, 2, 100, 1024, -10, 0. You may find it useful to know that the sum of i*i for i from 1 to n is n*(n+1)*(2*n+1)/6.

## Question 4 [BONUS]. Counting Primes II (20 points)

Modify the prime number seive so that it does not print out the primes it fines -- it just counts them. Use your modified program to count the number of primes (a) less than 10, (b) less than 100, (c) less than 1000, (d) less than 10,000, (e) less than 100,000, (f) less than 1,000,000, (g) less than 10,000,000, (h) less than 100,000,000.

## Question 5 [BONUS]. Counting Primes III (20 points)

Modify the prime number seive to time how long it takes to count the primes. The function System.currentTImeMillis() can be used to get the current time (as a long value) so you can record the start and end times and take the difference. How long does it take to compute the number of primes less than each 10k, 1 ≤ i ≤ 8 ? Display this on a graph.