After chatting with some alums who were visiting, I decided it would be a good idea to spend some time studying Data Structures and Algorithms while I’m at Hacker School. The great thing about being involved in a program with other people instead of learning on your own is that you become aware of some of your unknown unknowns. I can certainly teach myself things I know that I need to learn, but it’s more challenging to know if there’s something I need to learn that I’ve never even heard of.

As I was getting ready to post a question about any books or online courses for Data Structures that folks recommended, a couple of friends walked over and started coincidentally talking about the exact same thing. We picked out The Algorithm Design Manual as the book we’d work through, and put together a study group to read through it and work on the exercises together.

We ended up working late into the evening reading through the Data Structures section and implementing our own versions of some data structures in Apple’s new Swift programming language. This worked wonderfully, as Swift works with XCode’s new Playgrounds, which auto-compile code to show you right away if your code is working the way you expect it to.

We implemented a Swift version of a Linked List, and had some great conversations about the advantages and drawbacks of structuring some of the necessary methods in different ways, ending up with a neat implementation that took advantage of recursion to keep the code simple.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class LinkedList {
    var head : LinkedListNode?

    func search(item: String) -> LinkedListNode? {
        if head {
            return head!.search(item)
        } else {
            return nil
        }
    }
    func add(item: String) {
        if head {
            head!.add(item)
        } else {
            head = LinkedListNode(item)
        }
    }
    func size() -> Int {
        if head {
            return head!.size()
        } else {
            return 0
        }
    }
}

class LinkedListNode {
    var item: String
    var next: LinkedListNode?

    init(_ contents: String) {
        self.item = contents
    }
    func add(itemToAdd: String) {
        if let nextNode = self.next {
            nextNode.add(itemToAdd)
        } else {
            self.next = LinkedListNode(itemToAdd)
        }
    }
    func cons(itemToAdd: String) -> LinkedListNode {
        var oldHead = LinkedListNode(self.item)
        self.item = itemToAdd
        self.next = oldHead
        return self
    }
    func search(itemToFind: String) -> LinkedListNode? {
        if self.item == itemToFind {
            return self
        } else if let nextNode = self.next {
            return nextNode.search(itemToFind)
        } else {
            return nil
        }
    }
    func size() -> Int {
        if let nextNode = self.next {
            return 1 + nextNode.size()
        } else {
            return 1
        }
    }
}

I learned a lot that I didn’t know before about what an Array represents on a machine level (same-type items stored in consecutive memory locations), and how it differs from a Linked List or a Dictionary (same-type items stored in different memory locations with pointers to the next item), which explained some things about Objective-C that I hadn’t known the reasoning behind before we started, like why empty Arrays are initialized with a capacity.

We also learned a much more generalized definition of a Dictionary which was interesting. It was also helpful to go through worst-case algorithm processing times, called Big O notation or Asymptotic notation. We figured out the Big O notation for various functions on an unsorted and a sorted array, and then learned that deletes on an unsorted array can be done more cleverly than we had originally thought.

I learned about Binary Searches on sorted arrays, where instead of having to iterate through every item to find a specific value, you keep splitting the array down the middle and figuring out which half the value would be in, reducing the number of steps to find an item dramatically.

Later that evening, we learned about Binary Trees and the special Binary Search Trees. The Binary Search Trees work just like Binary Searches on sorted arrays, and the search is cleverly designed in the structure of the data itself. Each larger value is put into a branch node to the right, and each smaller value goes to the right. That way, to find a specific value, you have built in short-cuts as compared to an array.

Binary Trees might be unbalanced- if you added the values in numerical order, you would end up with just a line from the lowest value at the top to the highest value at the bottom right. The tree would be very tall, and thus it would take just as long to traverse as a regular array. The “balancing” of the tree, which is the distribution of values so that the right and left branches of the tree and its nodes are approximately equal, makes it possible to find values much more quickly, because each node is linked to not one but two different values, and you still know which of the links to follow simply by knowing if you are looking for a larger or smaller value. A cool trick is that if the values you are putting in can be expected to have a large degree of randomness, the tree has a high probability of being well-balanced (since subsequently-added values are equally likely to go to the left or the right of existing values, and not just all in one direction), and therefore not too tall, which will make it quickly searchable.

We implemented a Binary Tree structure in Swift, which was exciting because of its simplicity in code once we understood how the structure worked.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class BinaryTree {

    var data: Int?

    var left: BinaryTree?
    var right: BinaryTree?

    init() {
    }

    func insert(d: Int) {

        if !self.data {

        } else {

            if d < self.data {
                if let l = self.left {
                    l.insert(d)
                } else {
                    var tree = BinaryTree()
                    tree.data = d
                    self.left = tree
                }
            } else {
                if let r = self.right {
                    r.insert(d)
                } else {
                    var tree = BinaryTree()
                    tree.data = d
                    self.right = tree
                }
            }
        }
    }
}

Because we are simultaneously trying to learn the new tools available in Swift, we implemented a second version of the Binary Tree using a switch statement with a tuple and Swift’s new pattern matching rules instead of if/else statements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class BinaryTree2 {
    var data: Int?
    var left: BinaryTree2?
    var right: BinaryTree2?

    init (n: Int) {
        self.data = n
    }

    func insert (n: Int) {
        switch(self.data, self.left, self.right) {
        case let (.None, _, _):
            self.data = n
        case let (data, .Some(l), _) where data < n:
            l.insert(n)
        case let (data, .None, _) where data < n:
            self.left = BinaryTree2(n:n)
        case let (data, _, .Some(r)) where data >= n:
            r.insert(n)
        case let (data, _, .None) where data >= n:
            self.right = BinaryTree2(n:n)
        }
    }
}

We kept getting an error with this version that we hadn’t covered every possible case, and every time we added a default case or a universal pattern match, XCode would crash. After many attempts, we learned that this is actually due to a known bug in Swift that will hopefully be fixed soon.

I’m looking forward to learning a lot more about data structures with this group. It’s amazing how accelerated my gaining of knowledge is in a co-learning environment like this- it’s like the worlds’ best study group that I get to work with every day. We were getting excited about putting a group together to go through some advanced math textbooks I found online, and I feel sad that Hacker School is only 3 months and I won’t be here learning all of these things for at least the next year!