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 to implement a stack by a simply linked list where the operations and pop operations are done at end of list? Is this solution efficient? Argue.

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 (crtl+B from IntelliJ).

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

Exercise 1.1.4 (Inginious)

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 stacking the integers 1 2 3 from 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 queue and dequeue operation operations are 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-complecity 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 calculation times of algorithms. How this notation differs or resembles the more classically 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 \(\sim\) (tilde) notation rather than \(\mathcal{O}\) when possible?

Exercise 1.1.7

Explain how we can extract the characterization \(\sim\) (tilde) from the implementation of an algorithm to 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 mean when talking about the execution of a program in a programming language?

  • What do the -Xmx, -Xms parameters mean that we can pass to the JVM for the execution of a bytecode?

  • 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 borderline cases?

  • What could possibly go wrong with the implementation of 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 a code coverage analysis tool can be useful (such as Jacoco)

    to help you design tests.

  • How to 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?