Exercises A#

Note

You must complete these exercises by Wednesday of W2.

Exercise 1.1.1#

Define what an abstract data type (ADT) is. In Java, is it better to describe an ADT by a class or an interface? Why?

Exercise 1.1.2#

How would you implement a stack using a singly linked list where the push and pop operations are done at the end of the list? Is this solution efficient? Justify your answer.

Exercise 1.1.3#

What are the possible implementations for a stack? By consulting the Java API documentation, describe the implementation of a stack by the class java.util.Stack. Go to the source code of the implementation java.util.Stack (Ctrl+B from IntelliJ).

Why do you think Java developers chose this implementation (hint: argue about memory and garbage collection)?

Exercise 1.1.4 (INGInious: Implement a stack with two queues)#

How do you implement the abstract data type stack using two queues? In particular, describe how the push and pop methods work in this case.

As an example, specify the state of each of the two queues after pushing the integers 1 2 3 onto an initially empty stack. Describe what happens next when the pop operation is performed.

What is the time complexity of these methods if we assume that each enqueue and dequeue operation is executed in constant time?

Is this implementation of a stack efficient (for \(n\) operations) compared to the other implementations presented in the reference book?

Once you have imagined your solution on paper, you can solve the corresponding INGInious task StackWithTwoQueues.

Exercise 1.1.5#

What do you think about these three different ways of iterating over the elements of a java.util.LinkedList? Are they equivalent? Use a time-complexity argument.

LinkedList<Integer> list = new LinkedList<>();

// assume I insert n elements in the list here

for (Integer val: list) {
    System.out.println(val);
}

Iterator<Integer> itr = list.iterator();
while (itr.hasNext()) {
    Integer val = itr.next();
    System.out.println(val);
}

for (int i = 0; i < list.size(); i++) {
    Integer val = list.get(i);
    System.out.println(val);
}

Exercise 1.1.6#

The \(\sim\) (tilde) notation is used in the reference book for the analysis of the running times of algorithms. How does this notation differ from or resemble the more commonly used notations \(\mathcal{O}\) (big Oh), \(\mathcal{\Omega}\) (big Omega), and \(\mathcal{\Theta}\) (big Theta)?

Explain precisely the links and similarities between them. What do you see as the advantage of using the \(\sim\) (tilde) notation rather than \(\mathcal{O}\) when possible?

Exercise 1.1.7#

Explain how we can extract the \(\sim\) (tilde) characterization from the implementation of an algorithm using the doubling ratio test.

  • How does this test work?

  • What are the limitations and advantages of this test?

Suppose we measure the following \(T(n)\) execution times (in seconds) of a program as a function of the input size \(n\):

\(n\)

1000

2000

4000

8000

16000

32000

64000

\(T(n)\)

0

0

0.1

0.3

1.3

5.1

20.5

  • How can you best characterize the growth order of this function?

  • What would be the running time for 128000?

Exercise 1.1.8#

  • What do heap and stack represent when talking about the execution of a program?

  • What do the -Xmx and -Xms parameters mean when running Java bytecode on the JVM?

  • Can these parameters influence the execution speed of a Java program? Why?

  • What is the JVM garbage collector?

Exercise 1.1.9#

  • What is a good set of unit tests to verify the correctness of a data structure?

  • Do you think about edge cases?

  • What could possibly go wrong with this method implementation?

// return the floor of the average between a and b
public static int average(int a, int b) {
   return (a + b) / 2;
}

  • How can random data generation be useful for testing data structures?

  • Why is it important to work with a fixed seed for testing?

  • How can a code coverage analysis tool (such as JaCoCo) help you design tests?

  • How can you verify experimentally that the implementation of a data structure or an algorithm has the expected theoretical time complexity?

  • How can you test the time complexity of your program?

Exercise 1.1.10 (INGInious: SegmentedList and iterators)#

You are asked to implement an ADT called a SegmentedList and the iterator method of this ADT: SegmentedList.