Summary Algorithms & Data Structures ()

Meijer, W. Summary Algorithms and Data Structures (2019-2020). Hanze University of Applied
Sciences.




Summary for the Algorithms and Data Structures Course of the HBO-ICT programme at Hanze
University of Applied Sciences.

Contains a combination of chapters 18 to 29 of the book “Introduction to Java Programming and
Data Structures (11th)” written by Y. Daniel Liang, and notes that were taken during lectures given by
Bas Heijne and Bart Barnard in the HBO-ICT Programme (2019-2020).

Summary written by Willem Meijer.




1

,Meijer, W. Summary Algorithms and Data Structures (2019-2020). Hanze University of Applied
Sciences.

Chapter 18: Recursion
Recursive Methods: methods tat invoke themselves. Divides one larger problem into multiple
subproblems. Knows how to deal with the simplest possible problem, base case or stopping condition.
int factorial (int n) {
if (n == 1) {
return n;
}
return n * factorial(n - 1);
}

In the example above a factorial is calculated by calculating a smaller factorial until its base case (n =
1) is reached.

Direct Recursion: the method invokes itself.
Indirect Recursion: a method invokes another method, which in turn calls this method.

Every recursive method has three characteristics:
• Has an if-else or switch statement that results in different cases.
• Has one or more base cases.
• Reduces the original problem into one or more smaller ones.
Recursive Helper Method: a method that is not used by the user, but called by the method that is.
Generally has additional parameters.
public boolean isPalindrome(String s) {
return isPalindrome(0, s.length - 1, s);
}

private Boolean isPalindrome(int low, int high, String s) {
if (high <= low) {
return true;
}
else if (s[low] != s[high]) {
return false;
}
else {
return isPalindrome(low++, high++, s);
}
}

The private method isPalindrome is the helper method of the public one.

Compared with iterating (using a loop), recursion has substantial overhead, as the system allocates
new resources every method call. However, there is not necessarily over either one as recursive
methods can very effectively solve problems.

Tail Recursion: calling the recursive method at the end of the method.
Auxiliary Parameters: parameters that contain the most up-to-date result.




2

, Meijer, W. Summary Algorithms and Data Structures (2019-2020). Hanze University of Applied
Sciences.

Chapter 19: Generics
Using Generics allows you to parameterize object types, allowing you to create functionalities (e.g.
lists) once, and use these for any type of object, reducing your workload and redundant code. In Java,
you can pass Type parameters using <>. This can both be done when instantiating a new object, or
when calling a specific function. When doing the former, this means all methods where generics are
used have to be of that specific type.
public class ObjectA<E> {
E element;
public ObjectA(E element) {
this.element = element;
}

public static <T implements Comparable> T getGreater(T e1, T e2) {
return e1.CompareTo(e2) == 1 ? e1: e2;
}
}

A class that uses a generic in two occasions When defining the object, a type can be parameterized
for the entire class (in code the type is substituted with E). A separate object can be parameterized
when calling getGreater() too (in code the type is substituted with T). generics can be required to
extend or implement specific classes (such as Comparable for T in the example). Such a generic is
called a bounded generic.

When no type is inserted to define the generic, we speak of a raw type. For getGreater() T would
default to Comparable, whereas in ObjectA E would default to Object. A wildcard is a version of
generics where no type needs to be defined when using that generic. In code, its type is substituted
with a question mark. Wildcards can be bounded as well.

Type Erasure: To make generics backwards compatible, the generic types are removed and all
implementations reverted to their most basic case during compilation (so for E Object, and T
Comparable). Therefore, type information is no longer available during runtime.




3