CS 1025 Computer Science Fundamentals I
Assignment 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

Question 1. Creating a Class (30 points)

Write a class HelloWorld that has a main method that

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:

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.