public void run() {
		for (int i=0; i < n; ++i) {
			for (int j=0; j < n; ++j) {
				ticker.tick();
				this.value = this.value + i;
			}
		}	
	}

	public void run() {
		ticker.tick();                      // i = 0
		for (int i=0; i < n; ++i) {
			ticker.tick();                  // i < n
			ticker.tick();                      // j = 0
			for (int j=0; j < n; ++j) {
				ticker.tick();                  // j < n
                                //
                                // original one below
                                //
				ticker.tick();                     // add two values
				this.value = this.value + i;
				ticker.tick();                  // ++j
			}
			ticker.tick();                  // ++i
		}	
	}

Question A3: From the runs you have tried so far, how does the placement of ticker.tick() calls affect the plots you see? In particular, do the changes affect the shapes of the curves, the values plotted, or both?

• Discuss with your TA:
  • Does it matter if you have extra ticker.tick() calls? In particular:

    Question A4: In terms of n, how would you characterize, in the most simple terms, the time and ticks curves that have been generated so far?

    Question A5: What would happen if you deleted all ticker.tick() calls in the innermost loop, while leaving other calls to ticker.tick() that you just placed in run()?

  Discuss in your team and with your TA:

  Throughout this course, you will be asked to place ticker.tick() calls in your code. Placing them everywhere seems like the right thing to do, so that every operation is counted, as shown in the box above.

  You could put them everywhere, and the results will be right, but isn't that tedious? Did your added ticker.tick() statements affect the shape of the resulting curves that show ticks or time?

  How do you decide where to put them most parsimoniously?

  We will soon speak of this as analyzing an algorithm's asymptotic complexity:

  • From a practical point of view, it's the part of your algorithm whose time dominates any curve you could generate that reflects the time or ticks taken by your algorithm.
  • We will say that constant differences in time really don't matter: they could attributed, for example, to the difference in speed between one computer and another.
  • We will care about the shape of the curves that correspond to ticks and time, and we will reason about those curves in terms of their asympototic behavior.

  For now, you have to look at the code and reason about where it spends most of its time, as a function of n.

  For the run() method we have been considering, most of the time must be spent in the innermost loop, where we have:

  			this.value = this.value + i;
  

  That is why placing just one ticker.tick() there creates operation counts that adequately model the time spent by the entire run() method.

B. Some statements take constant time, some don't

When we look at a line of Java code above, for example:

   this.value = this.value + i;

But is this true for all statements? Surely not. For example, the single line of code:

   Arrays.sort(array);

Let's investigate this for allocating an array of integers:

• In the studios source folder, find and open the AddsTwoNumbers class in the studio0.allocates package.
• Run AddsTwoNumbers, refresh the outputs folder, and open and plot the time and ticks shown in the and files.

Question B1: What do you see? How do the curves reflect the code inside AddsTwoNumbers?

Do you think the value of n matters here in terms of the time it takes to perform the operation? Why or why not?

Question B2: What do the data and plot tell you about the time it takes to allocate an array of n integers?

Is it reasonable to say that the line of code

     this.array = new int[this.n]

takes a constant amount of time, independent of the value of this.n?

Question B3: Do the ticks agree in shape with the time we measured in running the Allocates code?

   ticker.tick(n);

Question B4: Are the plots more similar to each other than before? What does this tell you about how much time it takes to allocate an array of n integers?

So we see (hopefully) that a line of code doesn't always take a constant amount of time. While it was fair to judge

   this.value = this.value + i;

as taking one tick, it is not fair to say that

     this.array = new int[this.n]

takes one tick. Instead we must insist it takes n ticks.

Why does the time depend on n? Java must allocate a chunk of memory for the n integers. While that might take constant time, Java must also initialize that chunk of storage to 0. That cannot take constant time: that cost must depend on n.

Throughout this course, you are asked to reason about the time of a computation. Eventually, you must reason about how much time a given operation or statement takes, in terms of the computation's input size n.

You will be producing timing curves, and we will be looking at your code to ensure you have accounted properly for how time is spent.

How you achieve a particular result—how you implement an algorithm—can have a profound impact on the time necessary to obtain that result.

• One person announces a positive integer n. There is no limit on how large n can be. For example, I might announce the integer five. However, you should pick a larger integer, say between 50 and 75.
• Divide the rest of the group into two teams: the decimal team and the tally mark team.
• The decimal team writes down the announced number in decimal form. For my announced five, they would write 5.
• The tally mark team writes down the announced number in tally mark form. The tally mark form for five is .

Question B5: Which group do you expect to finish first?

Can you formalize, in terms of n the amount of work (ticks) that each group must do to write n in the form required for that group?

Both groups achieve the same result, namely the recording of an integer n.

• Under what circumstances is the decimal notation more efficient than tally marks?
• Under what circumstances is the tally mark notation more efficient than decimal notation? If you are not sure, take a look this.

C. Growing a List

Let's apply what we have learned to growing an array-based list.

• In your repository, find the Rarrays class in the studio0.growinglist package in the studios source folder.

  You will see that this is an abstract class, because the method int getNewSize() is missing. This is intentional, because we want to experiment with various ways of replacing the full array, and we do that by specifying the array's new size.

  We provide two extensions of Rarrays for you:

  Doubling

  causes the new array to be twice the old array's size. This may seem wasteful: a full 1024 cell array would grow to contain 2048 cells just to accommodate, at present, one more cell.

  AddOne

  causes the new array to be one item greater than the previous array's size. This is the least we can do to make room for one new element in an already full array.

  Each of those classes completes the Rarrays abstract class by providing the missing method int getNewSize().

  Take a look.

• Let's look at the code from reset(Ticker):

  	public void reset(Ticker ticker) {
  		this.ticker = ticker;
  		this.array  = new int[2];
  		ticker.tick(2);
  	}
  

  • We save ticker in an instance variable this.ticker so we can use it throughout this class and any of its extensions.
  • We start our array with two elements.
  • We use the ticker.tick(2) to account for allocating the 2-cell array, recalling from above we model allocating n integers by spending n ticks.
• The run() method attempts to fill the current array, calling replaceArrayWithBiggerOne when the current array no longer has sufficient room.
• We can't make an existing array bigger, but the array instance variable that had two elements can be subsequently reassigned to reference another (perhaps bigger) array.

  For example, if for some reason two elements are insufficent for the array, the following would allow the instance variable to reference an 8-element array:

     this.array = new int[8];
  

  However, reassignment of the array loses the reference to the previous array. Any data in that previous array would be lost.

  To preserve information as you provision for a larger array, you must

  • hold on to both arrays,
  • copy the old information into the newer one, and
  • then reassign the instance variable.
• Find and look at the comments in the replaceArrayWithBiggerOne method.

  Your first task is to complete this method until it passes the TestRarrays unit tests.

  The TestRarrays contains 3 test cases:

  • testInit should work as given to you.
  • testGrowPreservesData ensures that you retain information from the old array as you make the newer, larger one.
  • testGrowSufficientTicks ensures that you account properly for the ticks taken for allocating and filling the newer, larger array.

• Work together to write the appropriate code below the comments.
• When your code successfully passes the testGrowPreservesData test, your code is copying data reliably from the old to new array.
• When your code successfully passes the testGrowSufficientTicks test, you are accounting properly for the allocations.

  Work on this until you get the green bar, indicating all tests are passing.

D. How much does it cost to grow the array?

OK we really don't grow the array, but we continually replace it with a larger one. Let's study how the growth rate of the arrays affects the overall cost of Rarrays.

• Run AddOne, which should run without error.
• As before, the output of the run is in your outputs folder, but you won't see anything until you refresh eclipse's view.
• Open the growbyone-ticks.csv and plot the ticks against n.

  Question D1: How would you describe the curve you see?

  As a team, think about possible polynomial functions that could generate such a curve.

• Repeat the above steps by running Doubling, refreshing your eclipse view, opening doubling-ticks.csv in Excel, and plotting the same data.

  • Question D2 Why does your program generate the data you see?
  • While the data has a certain disconnected quality to it, let's analyze the plotted data as follows:
    • Using any straight edge you can find nearby, see how tightly the straight edge can bound all the points from below.
    • Then see if that straight edge can also tightly bound all the points from above.
  • Question D3: Describe what you were able to do with the straight edge.
  • If you are successful, you see that the points generated by Doubling, while somewhat strange-looking,
    • make sense, because the jumps are due to the time spent doubling
    • are boundable below by one linear function
    • are boundable above by one linear function

You may not be able to complete this part in studio. Take a look at it on your own if necessary.

E. Mathematical analysis

Now let's look mathematically at how much time is spent growing the list by our two methods: add one, and doubling.

AddOne

Here, we reach a total of n cells in the array, growing by one cell each time, and copying the old array into the slightly larger new array.

How much time does this take? We copy 1, then 2, then 3, and so on, until we have copied n-1 items to make room for the n^th item. If we count the time for allocation, we can extend the sum to n. If T(n) represents the total time taken to achieve an array of n elements by growing one at at time, then

T(n) = 1 + 2 + … n $$=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}i$$

Question E1: What is the closed form solution for T(n)?

Search the web for summation formulas if you need help. You are expected to know such sums in this course.

Does it agree with what you have seen empirically?

Doubling

Here, we reach a total of n cells. Let's assume n=2^k for some k, so that we have performed work: T(n) = 1 + 2 + 4 + … 2^k $$=\underset{i=0}{\overset{k}{\sum <!--\; \sum \; -->}}{2}^i$$

Question E2: What is the closed-form solution for T(n)?

Recalling that n=2^k, can you express the result in terms of n?

Based on your analysis and what you have seen, what effect does the growing strategy have on the time necessary to accommodate the array-based list that grew to n items?

Further exploration

• For one strategy, you grow the array by 10% of its previous size, making sure that the growth adds at least one extra cell to the next array.
• For another strategy, you increase the array by 20 cells each time it fills.

Returning to your code, you will see an OurGrowth1 and OurGrowth2 class. Use those to experiment with these ideas and see what results you get.

Submitting your work (read carefully)

• If there is a file for you to complete in studiowriteups, please respond to the questions and supply any requested information.
• You must commit and push all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
• Follow the instructions in the green box below to receive credit for your work.

When you done with this studio, you must be cleared by the TA to receive credit.

• Commit all your work to your repository
• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for studio 0

	Last name	WUSTL Key	Propagate?
		(NOT your numeric ID)		Do not propagate
e.g.	Smith	j.smith
1				Copy from 1 to all others
2				Copy from 2 to all others
3				Copy from 3 to all others
4				Copy from 4 to all others

---

TA: Password: