My first two weeks at Recurse Center have been pretty intense and hyper-focused. While first few days were dedicated to adjusting to the space, managing my time, and trying to scope what exactly I will be covering while I am here, I jumped into my work without much of a hitch.

In previous post I listed a handful of topics I wanted to cover. My top priority is algorithms and data structures and will be for the remainder of the batch.

To give a loose guide as far as what I should cover, I started Part 1 of Coursera/Princeton’s Algorithms course taught by Kevin Wayne and Robert Sedgewick, and using their text book in tandem with the lessons. So far I have covered:

  • stacks and queues
  • space and time complexity for linked lists vs arrays operations

While there are many resources available for learning algorithms and data structures, Sedwick and Wayne’s lessons were the more attractive option because having video lectures to watch text book explanations helpful is the most beneficial for me.

Many of the video lectures contain helpful animations that Sedgewalk walks through step by step as he explains an algorithm and associated data structure(s).

Additionally, each week a project is assigned that uses the information learned during previous week’s lessons.

One thing I would like to touch on is generics in Java. Why mention them in the context of algorithms? Java is the language used in the above mentioned course. Because Java is strongly-typed, a mechanism for type-safe, easy to read algorithm implementation is needed. Otherwise a new version of the same algorithm would have to be implemented for each particular type a client would use (i.e. StringStack, IntegerStack, etc.).

Java Generics

Generics enable types to be parameters when defining classes, interfaces, and methods. Their benefit is allowing code reuse. See the following examples of non-generic versus generic version of the class Box:

// non-generic version
public class Box {
    private Object obj;
    public void set(Object obj) { this.obj = obj; }
    public Object get() { return obj; }
}
// generic version
public class Box<T> {
    // `T` is simply an identifier to recogize the *type*
    private T t;
    public void set(T t) { this.t = t; }
    public T get() { return t; }
}

The non-generic Box in the first example gives no way to verify at compile time how the class is used. For instance, if the non-generic Box is used by a client to add and receive Integer objects to and from a Box instance, and later in the code the client attempts to add a String, it will cause a runtime error. The second example uses type parameters (delineated with angle brackets) to determine which type the Box instance will use when instantiated.

This is accomplished using a generic type invocation:

Box<Integer> box;

The above code does not create a new Box. All it does is declare the instance box will hold a reference to a Box of type Integer, known as a parameterized type. To instantiate box, we assign it to a new box instance with the expected data type (Box) and type parameter (Integer):

box = new Box<Integer>();

Another benefit of generics use is errors will be caught at compile time instead of runtime, leading to less buggy code. Fixing compile time errors are easier to fix than runtime errors, which can be difficult to find.

Generics are also helpful because they eliminate the need for casts, for the most part (see below):

// non-generic ArrayList
List list = new ArrayList();
list.add("foo");
String s = (String) list.get(0); // casting here...
// generic ArrayList
List<String> list - new ArrayList<String>();
list.add("bar");
String s = list.get(0);  // look! no cast necessary!

The one caveat is Java does not allow generic array creation. Let’s say you want to create an array inside a class for the passed-in type-parameter:

    T[] tArr = new Item[1];  // compilation error!

Instead a cast must be used:

    T[] tArr = (T[]) new Object[1]; // OK!