The basis for education in the last millennium was “reading, writing, and arithmetic;” now it is reading, writing, and computing. Learning to program is an essential part of the education of every student, not just in the sciences and engineering, but in the arts, social sciences, and humanities, as well. Beyond direct applications, it is the first step in understanding the nature of computer science’s undeniable impact on the modern world.

This course covers the first half of our book Computer Science: An Interdisciplinary Approach (the second half is covered in our Coursera course Computer Science: Algorithms, Theory, and Machines).

Our intent is to teach programming to those who need or want to learn it, in a scientific context.

You can enroll here: Coursera Computer Science: Programming with a Purpose Week 7 Quiz Answers!

Performance

Question 1) Which statements that characterize the doubling hypothesis? Mark all that apply.

A way to better understand the performance of a program
A way to avoid empirical tests of program performance
A way to determine the order of growth of the running time of a program
A way to improve the performance of a program
A way to avoid mathematical analysis of program performance

Question 2) Which of the follovwing running times for a program consistent with the hypothesis that the order of growth of the program is quadratic (check all that apply)? Mark all that apply.

1 second for N = 1,000,000, 2 seconds for N = 2,000,000, 8 seconds for N = 8,000,000
1 second for N = 100,000, 4 seconds for N = 200,000, 16 seconds for N = 400,000
1 second for N = 100,000, 8 seconds for N = 200,000, 64 seconds for N = 400,000
1 second for N = 100,000, 4 seconds for N = 200,000, 32 seconds for N = 800,000
1 second for N = 100,000, 4 seconds for N = 200,000, 64 seconds for N = 800,000

Question 3) Which of the following is equivalent to saying a(n) - b(n) ? Mark all that apply.

The order of growth of a(n) is b(n)
The difference between a(n) and b(n) tends to 0 as n grows
The ratio of a(n) to b(n) tends to 0 as n grows
The difference between a(n) and b(n) is bounded by a constant
The ratio of a(n) to b(n) tends to 1 as n grows

Question 4) The Java function below returns a string of length n whose characters are all x.

What is the order of growth of its running time? (Recall that concatenating two strings in Java takes time proportional to the length of the resulting string.)

public static string method3(int n)
{
if (n == 0) return "";
if (n == 1) return "x";
return method3 (n/2) + method3 (n - n/2);
}

linear
linearithmic