Version: 0.3.38

Sequences#

Module:

Sequences

Git Repository:

Lab 02—Sequences

Objectives:

  • Understand the sequence ADT

  • Understand dynamic arrays and memory allocation

  • Apply algorithm analysis techniques

Important

UPDATED! This is the first mandatory lab session. Organize yourself by groups of 2 to 3 students and write a short report, summarizing your answers. Here are some guidelines:

  • Justify every answer, especially calculations.

  • Do not exceed 8 pages

  • Do not attach a zip of your Java project

Submit your report, as a PDF file, on Blackboard by Friday September 22, 2023 at 23:30 at the latest.

Dynamic Arrays in Java#

This first section focuses on how to implement the Sequence ADT using dynamic arrays in Java (see lectures 2.2 and 2.3).

The class no.ntnu.idata2302.lab02.SequenceTest contains some unit tests that might help you.

Exercise (2 points)

Implement the insert function, which inserts the given item at the given position. If the underlying array is full, it shall resize the array appropriately, by doubling its capacity.

public void insert(int item, int index) {
  // TODO: Implement
  throw new RuntimeException("Not yet implemented.");
}

Exercise (2 points)

Implement the remove function, which delete the item stored at the given index. If the underlying array gets empty, it shall resize the array appropriately. It should halve the capacity as soon as the load is less or equal than 25 %.

public void remove(int index) {
    // TODO: Implement
    throw new RuntimeException("Not yet implemented.");
}

Exercise (2 points)

Implement the search function, which returns an index where the given item can be found, or 0 if the sequence does not include that item.

public int search(int item) {
  // TODO: Implement
  throw new RuntimeException("Not yet implemented.");
}

Finding Extrema#

We focus here on finding extrema, that is, both the minimum and the maximum of the sequence.

Exercise (3 points)

Propose an algorithm the finds both the minimum and the maximum of the sequence.

public int[] extrema() {
  // TODO: Implement
  throw new RuntimeException("Not yet implemented.");
}

Exercise (1 point)

What is the worst-case scenario for your algorithm? Give an example of sequence that triggers that worst case.

Exercise (2 points)

Given a sequence of length \(\ell\), how many comparisons are needed in the worst case. Express it as a function of \(\ell\).

Finding Duplicates#

Exercise (2 points)

Propose an algorithm that checks whether the given sequence has duplicates, that is, whether any item occurs more than once. Consider the following examples:

  • The sequence \(s_1 = (1, 2, 3, 4, 5)\) does not contain any duplicate.

  • The sequence \(s_2 = (2, 1, 3, 3, 5)\) contains one duplicate, 3, which occurs twice.

  • The sequence \(s_3 = (1, 2, 1, 3, 1, 4)\) also contains one duplicate, 1, which occurs three times.

Do not use any additional data structure, such as hash tables, hash sets, etc.

We can add it has a new operations on our Sequence class, as follows:

public boolean hasDuplicate() {
  // TODO: Implement
  throw new RuntimeException("Not yet implemented.");
}

Exercise (2 points)

What is the worst-case scenario for this algorithm? Given a sequence of length \(\ell\), how many comparisons does this worst-case requires? Express it a function of \(\ell\).

Exercise (3 points)

Consider the following growth orders:

  • \(g(x) = 10\)

  • \(g(x) = \log_2 x\)

  • \(g(x) = \sqrt x\)

  • \(g(x) = x\)

  • \(g(x) = x^2\)

  • \(g(x) = 2^x\)

  • \(g(x) = x!\)

  1. Which one(s) are valid upper bounds for the function you found the previous question?

  2. How would you express such an upper bound with the Big-Oh notation?

  3. Which one is the tightest bound?

Digital Counter#

Consider a counter whose value increases whenever the user presses the “increment” button. The user can read the value on a sequence of single-digit displays, where each display only shows a single symbol (from 0 to 9).

Each single-digit display accepts a next command that changes it to the next symbols, for instance, from 0 to 1, from 1 to 2, from 2 to 3, etc, and from 9 back to 0.

Exercise (2 points)

Implement the increment function, that increases the counter value by one.

public class Counter {

   private DigitDisplay digits[];

   public void increment() {
      // TODO: Implement, by calling digits[i].next() when appropriate
   }

}

class DigitDisplay {
   // ...
}

Note that, in some cases, we must propagate the carry to the left. For instance to increment 123, only the right-most digit change to make 124, but incrementing 199 yields 200 and three digits must changed.

Exercise (2 points)

When incrementing the value of the counter, how many times does your algorithm invoke the next operation for its digits. Use amortized analysis to find a bound.