Efficiency Portfolio

CS1010J Programming Methodology[pic 1]

Tutorial 3: Repetition Statements

To tutors:

• This week we focus on problem solving with single loops. Discuss algorithms with students and then let them code under your guidance. Walk around to help them as necessary.
• Ask students to attempt Problem Set 1 or Problem Set 2 if your class ends early. Allow those strong students to leave earlier if they wish.
• Please update the tutorial attendance mark on Google Drive right after your class.

To students:

Two weeks of tutorials have passed and hence we have removed the usual preamble, since you should already know what is expected of you by now.

Please be reminded that our Practical Exam 1 is on next Thursday (Sep. 15, 2016) 7pm – 8:30pm. Please check IVLE Files -> Practical Exam 1 folder for seating plan, etc.

I.        Manual Tracing

1.        Consider the following program.

import java.util.*;

class T3Q1 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter n: ");

        int n = sc.nextInt();

        int i = 1, count = 0;

        while (i < n) {

            if ( n%i == 0 )

                count++;

            i++;

        }

        System.out.println("count = " + count);

    }

}

1. Assuming that the user enters 20, what is the final value of count?

        Answer:

If the user enters 20, the value of count is 5. (Divisors of 20, excluding itself, are 1, 2, 4, 5 and 10.)

1. Assuming that the user always enters a positive number, describe the purpose of this program.

        Answer:

The program counts the number of divisors (or factors) of n, excluding itself.

1. If the final value of count is 1, what can be said about the input value n?

        Answer:

If the final value of count is 1, it means that n is a prime number.

1. Knowing what this program does, could you change the 'while' condition to make the program work a little more efficiently (i.e., take fewer iterations to compute the answer)?

        Answer:

It is unnecessary to check i up to n – 1. The upper limit can be reduced to half of n.

        while (i <= n/2) {

            if ( n%i == 0 )

                count++;

            i++;

        }

2.        Manually trace each of the following code fragments and write down its output.

int product = 0;

for (int i = 1; i < 10; i++)

    product *= i;