Tutorial 6, CPSC 331, Winter 2012

home page -  news -  syllabus -  schedule -  assignments -  tutorials -  tests -  java -  references -  Mike Jacobson

Tutorial 1 -  Tutorial 2 -  Tutorial 3 -  Tutorial 4 -  Tutorial 5 -  Tutorial 6 -  Tutorial 7 -  Tutorial 8 -  Tutorial 9 -  Tutorial 10 -  Tutorial 11 -  Tutorial 12 -  Tutorial 13 -  Tutorial 14 -  Tutorial 15 -  Tutorial 16 -  Tutorial 17 -  Tutorial 18 -  Tutorial 19 -  Tutorial 20 -  Tutorial 21 -  Tutorial 22 -  Tutorial 23

 Arrays and Lists

About This Exercise

This exercise can be used by students to make sure that they are familiar with the properties and applications of arrays and lists that have been discussed in class.

Expected Background and Preparation

It is assumed that all students in this course are already somewhat familiar with static arrays and linked lists. Students may also have made use of dynamic arrays when programming — either by making use of a vector in C++ or an ArrayList in Java.

Students have already been asked to learn about Java by making use of other material provided through the course website.

It is assumed that students have attended the lectures on arrays and lists before considering the following properties, or reviewed the lecture notes that are available online.

Finally, additional material about the amortized analysis of operations on dynamic arrays is also available. Some students may find the analysis of operations included here to be of interest, but it is not essential for this to be understood. On the other hand, it is more important for students to understand the results themselves: you should have an idea of the worst-case costs of sequences of operations on dynamic arrays as well as the worst-case costs of individual operations.

Warmup Exercises — To Check That You Understand the Basics

It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, attended the lectures in which arrays and lists have been discussed, and read through the material about this that is listed above.

Teaching assistants will not be spending very much time in tutorials discussing these questions! Students should look at them anyway to make sure that they know how to answer them.

Students who do have difficulty with these questions, after completing the suggested reading, should contact the course instructor to get extra help.

  1. Compare and contrast each of the following pairs of data structures. When contrasting these data structures, mention a method that one supports that the other does not, or an operation that can be carried out significantly more efficiently using one data structure than is possible (in the worst case) using the other.

    1. a static array and a dynamic array
    2. a linked list and dynamic array

  2. Give the best asymptotic bound that you can for the number of steps needed to carry out each of the following operations, when each of the following data structures is used —

    • a static array
    • a dynamic array
    • a singly linked list

    — or state the the operation is not supported, if that is the case.

    1. reporting the value at a given index i
    2. setting the value at a given index i to be a given value v
    3. adding the value v at the end of the structure (extending its length or size by one, in the process)
    4. replacing the first occurrence of a given value, v, by another given value, w

  3. Now suppose that you are using a dynamic array in Java (that is, an ArrayList), and that you perform a sequence of n simple add operations — that is, operations that each insert an element onto the end — of an ArrayList that is initially empty.

    1. What is the best asymptotic bound that you can give for the worst-case running time of any one of these operations? Why?
    2. What is the best asymptotic bound that you can give for the worst-case running time for the entire sequence of these operations? Why?

  4. Each of the following variations on a “singly linked list” are described in the literature and are sometimes used. Say how each is different from a singly linked list, describing both an advantage and a disadvantage of the use of this other kind of linked list if you can.

    1. a singly linked list with dummy nodes (at either end)
    2. a doubly linked list
    3. a circular list

  5. What is a wrapper class for a primitive data type? How (and why) are wrapper classes useful when you wish to provide a dynamic array using Java’s ArrayList class, or when you wish to provide a linked list using LinkedList?

  6. What is a generic collection in Java? Give one or two examples of these that have been mentioned in lectures or in the assigned reading.

To Be Discussed in the Tutorial

  1. Consider Java’s Iterator and ListIterator interfaces. These were not discussed in any detail in class, you but found more information about them if you completed the assigned reading.

    1. What are these used for?

    2. Why is it helpful to have both of these, even though they are used for the same thing?

    3. Recall that an ArrayList and a LinkedList both provide methods to report the size of the list, as well as to add and remove elements at given positions.

      With the above information in mind, explain how you could write a program that does the same thing, without using an Iterator or a ListIterator, as a given program that uses these to access and change one of the above structures.

      Why is it a good idea to use an Iterator or a ListIterator anyway?

  2. While it is not very explicitly documented, a careful examination of the online material that discusses arrays in Java (notably including the types of values that can be used as indices into arrays) makes it clear that the length of an array in Java must be small enough to be represented as an int.

    Furthermore, the fact that an ArrayList is almost certainly implemented using an underlying static array suggests that the capacity of an ArrayList must be this small, as well.

    In other words (according to the textbook) neither the length of an array nor the capacity of an ArrayList can be greater than

    2,147,483,647

    so neither an array nor an ArrayList can be used to store more than couple of billion entries!

    1. Describe a way to show how, “in principle,” you could modify this restriction in order to support arrays that store as many as

      2,147,483,647 × 2,147,483,647

      in an array or ArrayList instead.

    2. In reality, the above length restriction on arrays and ArrayList’s is not very significant: Most realistic problems do not require structures that are larger than this.

      In order to see more evidence why it is not realistic, at the present time, to significantly increase this restriction, you should download and compile each of the following Java programs.

      1. declareLargeArray1.java: Initilizes an int array of length 100,000,000 and then prints “Hello, world!”
      2. declareLargeArray2.java: Initilizes an int array of length 200,000,000 and then prints “Hello, world!”
      3. declareLargeArray3.java: Initilizes an int array of length 300,000,000 and then prints “Hello, world!”
      4. declareLargeArray4.java: Initilizes an int array of length 400,000,000 and then prints “Hello, world!”
      5. declareLargeArray5.java: Initilizes an int array of length 500,000,000 and then prints “Hello, world!”
      6. declareLargeArray6.java: Initilizes an int array of length 600,000,000 and then prints “Hello, world!”
      7. declareLargeArray7.java: Initilizes an int array of length 700,000,000 and then prints “Hello, world!”
      8. declareLargeArray8.java: Initilizes an int array of length 800,000,000 and then prints “Hello, world!”
      9. declareLargeArray9.java: Initilizes an int array of length 900,000,000 and then prints “Hello, world!”
      10. declareLargeArray10.java: Initilizes an int array of length 1,000,000,000 and then prints “Hello, world!”

      Notice that even the largest of the arrays being considered, above, has length that is less than one-half of what is already supported (at least, in principle) by Java. Furthermore, since arrays whose entries are int’s are being considered, the storage needed to represent each entry of each array is not particularly high.

    3. Using the UNIX time command, try to get information about the time needed to run each of these programs. For example, you should be able to get some information about the time needed to run the first program by running the executing the following command (at least, at school):

      time java declareLargeArray1

      Before proceeeding to later parts of this question, use similar commands to see what happens when you try to execute the rest of these programs (as well as how much times it takes for them to complete).

    4. Note: As a courtesy to other students, try to follow the next instructions with care — in particular, try not to do the following at school when it seems like lots of other students are trying to use the system as well!

      Unless your Java environment is quite unusual, you discovered (when carrying out the above) that you were not able to execute some of the programs and have “Hello, World!” displayed, because an exception got thrown first! While it might not have been clear from the output you received, Java did not actually have access to enough memory to initialize the array that you asked for.

      It is possible to run Java with more memory available. For example, even though an attempt to run the program declareLargeArray6 might have failed, it is possible that an execution of the command

      java -Xmx3500m declareLargeArray6

      (which asks Java to try to use up to 3500 megabytes of storage) succeeds.

      Try to run the above programs, using the “-Xmx” option as suggested here.

      If you are able to run all these programs, then make note of the times used. Did anything unusual happen? Do you know why it might have?

      On the other hand, if you were not able to run these programs, then what happened instead?

    The Awful Truth: It is impossible for me to predict, reliably, exactly what will happen if you carry out the above! Using my Java setup at home I was able to increase the memory available to Java to be high enough to execute all of the above programs — but this was not possible at school.

    That said, you should have noticed that, after a while, the time used was growing more than linearly in the length of the array being declared (if, indeed, you were able to have programs executed at all) — it is possible that you noticed a significant increase in the times needed to initialize two arrays of “similar” sizes.

    While the teaching assistants will be able to tell you a little bit about why that is the case, a more complete explanation of this depends on information about the organization of memory, in modern computers, that you will learn about in other computer science courses.

    In any case, I hope that it is clear from the above that the current restrictions, in Java, on the length of any array or capacity of any ArrayList does not really restrict what we can do: Modern computers do not generally have the capacity to support computations on arrays or ArrayList’s that are larger than this.

  3. OK, OK! This exercise was different from previous ones, in the sense that it included a rather extensive reading assignment, and some of the “warmup problems” asked you about the material that you were supposed to read.

    If time is available, and there there is interest, then the TAs will be prepared to discuss the answers for Warmup Problems 5 and 6.

Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W12/tutorials/tutorial6.html