## iOS Dev Camp DC 2019

Tomorrow morning I brave Washington D.C. traffic to get to iOS Dev Camp DC 2019. And I’m really looking forward to it!

This conference is always a lot of fun. The food is great, the talks are interesting, and the swag is top-shelf. But the thing I really love about iOS Dev Camp DC is the people. We are a smallish group of iOS enthusiasts from all over the country, and every year we have a great time. My friends know to DM me on Twitter so we can get together at the conference.

So what are you waiting for? Buy your ticket already. It’s \$50 for the whole day, and the proceeds go to Women Who Code. If not, at least get on Twitter and follow @iosdevcampdc to keep up with what’s happening.

## Cracking into Rabin Karp

Solving coding puzzles can be fun and rewarding. Try HackerRank or CodeSignal. But solving them on a whiteboard during a job interview can be… more stressful than fun. The book Cracking the Coding Interview comes with high praise and recommendations from some of the industry’s top tech recruiters.

I’ve been on both sides of the tech interview process, and writing code without an IDE is something that every developer should at least try at some point in their career. I recently tackled a basic problem using Java that once stumped me.

A long time ago, a job interviewer asked me to create a string searching algorithm. Given strings A and B, simply find A if it occurs in B. It is always good to start by stating the basic facts and showing that the problem can be solved, even if the naive algorithm is algorithmically complex. I managed to implement a naive string search. Naive search is simple:

• Iterate over B using the index bindex
• Iterate over A using the index aindex
• Compare the character A[aindex] to the character B[aindex+bindex]
• If they are the same, proceed with the inner loop (over A)
• If they differ, break out of the inner loop (over A)
• If A’s loop completes, the string search has found a match

The big problem with this algorithm is that it works in $O(A_{length} * B_{length})$ time complexity. When the interviewer asked me to write an optimized version… I froze. I never did get the job.

I recently read about an optimized string search algorithm, and the old pain of defeat flared up again. I had to implement Rabin Karp.

Rabin Karp optimizes the inner loop in the following way:

• Create a hash-code for A. For example:
```for (int index = 0; index < pattern.length(); index += 1) {
searchHashAccumulator = (searchHashAccumulator + search.charAt(index)) % hashIndex;
}
```
• Create a hash-code array of length B_length
• Iterate over B using the index bindex
• Compute a cumulative hash for each character in B by adding the character at bindex to the cumulative hash value.
• Store this hash in the array
```for (int index = 1; index <= search.length() - pattern.length(); index += 1) {
searchHashAccumulator += search.charAt(index + pattern.length() - 1);
// remove old character
searchHashAccumulator -= search.charAt(index - 1);
searchHashAccumulator += hashIndex;
// modulo
searchHashAccumulator %= hashIndex;
searchHashes[index] = searchHashAccumulator;
}
```
• Iterate over B as before, bindex blah blah blah
• This time, before executing the inner loop over A, check the hash code of A with the appropriate hash code for B at position bindex
• If they don’t match, short-circuit the inner loop. We never execute it.
• If they do match, go ahead and run through A as before to verify a match was found.
```search: for (int searchIndex = 0; searchIndex < search.length() - pattern.length() + 1; searchIndex += 1) {
if (patternHash != searchHashes[searchIndex]) {
System.out.println("Optimize!");
continue;
}
for (int patternIndex = 0; patternIndex < pattern.length(); patternIndex += 1) {
if (pattern.charAt(patternIndex) != search.charAt(searchIndex + patternIndex))
continue search;
}
return searchIndex;
}
```

Our hash code will sometimes match even when the string is not found (false positive), but it usually won’t. If we assume this is the case, then the inner loop basically executes only a few times. This makes our new time complexity $O(B_{length} + A_{length})$ and adds a $O(B_{length})$ memory complexity to the mix. All in all, a lot better than the performance of the naive approach.

I implemented it with some JUnit test code on github. I plan to add code to this repo whenever I get the urge to try one of these coding puzzles to keep my coding tools sharp.

## Simple Cloud

I signed up for Amazon Web Services around a year ago. I remember playing around and being impressed. But I never did much more with it.

This semester I am once again teaching a Database Administration course at Christopher Newport University. One of my students shared with me that his summer job heavily utilized Amazon Elastic Compute Cloud, and I decided to take another look into it. AWS enables you to easily deploy a server to support a web application, run data analysis, or even support your own multiplayer video game. And you never have to worry about backups or hardware failures! EC2 is a rich software deployment platform, however, and the array of choices when bootstrapping a new server can be overwhelming to a newcomer.

I needed a quick and dirty solution to a specific problem: I use Docker to teach my database course. It allows the students to deploy containers (virtual machines with fixed software configurations) to host their own relational database (PostgreSQL) interface software (PgAdmin). Later in the semester, they use Docker to deploy a web server hosting Jupyter to enable them to get experience with Python, Jupyter, and Spark. PySpark and The PySpark Cookbook have helped to provide me with a way to introduce the students to basic data analytics in just a few weeks.

Problem: Docker is straight-up painful to install on a student’s laptop running Windows, and it does not reflect a realistic database server at that. I decided to look into web services as a solution, and took a look at Google Cloud, Microsoft Azure, Amazon Web Services, and others. I was surprised to run into an ad for Vultr while searching for resources. They are not one of the big names, so I decided to check them out.

I was delighted to find out that there are \$5 and \$50 one-month free trials available. The basic Docker container is only \$5 per month, so I can essentially try everything I want for free. The startup could not be easier, in part because you are only prompted to select your application, not trying to estimate your performance and capacity needs. There is a built-in option for starting a docker host.

Once setup is complete, I was given an IP address for my server and account details for it. It’s amazing, but that’s really all there is to it! Here is what my first login looked like:

``````Michaels-MacBook-Pro-3:~ michaeljohnson\$ ssh root@11.22.33.44
Welcome to Ubuntu 16.04.5 LTS (GNU/Linux 4.4.0-137-generic x86_64)

* Documentation:  https://help.ubuntu.com
* Management:     https://landscape.canonical.com

89 packages can be updated.

New release '18.04.1 LTS' available.

Last login: Thu Feb 14 16:45:47 2019 from 174.226.24.25
root@dockertest:~# docker version
Client:
Version:           18.06.1-ce
API version:       1.38
Go version:        go1.10.3
Git commit:        e68fc7a
Built:             Tue Aug 21 17:24:56 2018
OS/Arch:           linux/amd64
Experimental:      false

Server:
Engine:
Version:          18.06.1-ce
API version:      1.38 (minimum version 1.12)
Go version:       go1.10.3
Git commit:       e68fc7a
Built:            Tue Aug 21 17:23:21 2018
OS/Arch:          linux/amd64
Experimental:     false
root@dockertest:~#
``````

By next semester, my students will all be subscribing to a web services provider as part of their materials for the database course.

## New Hosting / New WordPress

I’d like to share my #UnpopularOpinion and say that GoDaddy is an excellent hosting provider with impressive tech support. I’ve always been quick to call and ask them questions, and they always explain everything without talking down to me. They know web developers.

I recently took advantage of a sale on GoDaddy’s Deluxe Hosting and secured three years worth of hosting for as many web sites as I like. About six months after making the payment, I finally set about the task of migrating my web sites over to a new server.

My first view of the new hosting service came through the new-hosting-wizard. You’re basically forced to pick one of your domains to migrate before you can access cPanel Admin, the main gateway to hosting management on GoDaddy. In addition to the wizard and cPanel, GoDaddy supplies a minimal management panel (confusingly called cPanel) under My Account / Hosting / cPanel. The wizard does little more than redirect DNS to the new server, so I was going to need to move all of my hosting files and web server configuration over manually or using GoDaddy tools.

If you haven’t played with ssh, you really should. Yes, that’s a link to a nuclear physics experimenter’s guide to using ssh to access a particle accelerator from off site. I have… a colorful background.

In a nutshell, ssh uses something called Public Key Infrastructure to enable a two-key system where one key (a large number encoded into characters kept in file) can be used to encrypt data that the other key can decrypt. Each key can encrypt or decrypt whatever the other key can decrypt or encrypt. One key is labeled public and released while the other key is labeled private and kept secret. This gives us the ability to authenticate (use our private key to encrypt something so that the public key can be used to decrypt it) and to transfer our data in secret (use our public key to encrypt our data and only our private key and decrypt it). In practice, SSH actually uses this secret transfer to pass another temporary secret key for faster encryption.

But here is how easy it is to copy a site:

``tar cvf - . | ssh foo@myhost.com 'cd public_html; tar xvf -'``

This command works if you have all of your site files in your current working directory on your local machine. I keep a working copy of all of my source files local and use git to revision them. I don’t have a fancy upload tool – I just use git to tell me which files have been updated and ssh to transfer them.

I opted not to buy any email plans. My whole show runs on the cheap. You can set up a free email account through CPanel that forwards any email aimed at your domain to any account. I just forward them all to my GMail account. This tutorial saved me a lot of stress.

Finally, every web site needs to upgrade to HTTPS. Chrome and other browsers are flagging insecure sites. ZeroSSL has a very easy set of online tools to generate your certificates. The only catch is that you need to renew them manually every three months. This tutorial helped me make sense of the various key components. Once you understand which fields go where, it’s just a matter of finding the right panel and pasting in the right value. When it’s time to renew, this video shows what keys go where.

That’s all done! WordPress has been upgraded, and I’m ready for another year of (hopefully more frequently) blogging. The key takeaway here is that you can really get most things for free (email redirection, SSL) and the rest for cheap (domains about \$15/year each, web hosting \$60/year for unlimited sites). All this if you’re willing to do the work.

## Heapsort, because I haven’t posted in a while

This is heapsort in a Swift playground. I needed a stable sort, so naturally I wrote an… unstable sort.

Of course, you can just use `sort()` or `sorted()`, but if you are inclined to roll your own, the Swifty way to do it is to create an extension. Note that an Array extension with a Generic Where Clause is needed to make element comparisons `> < ==` work.

```//: Playground - noun: a place where people can play

import Cocoa

// var elements = [0, 6, 0, 6, 4, 0, 6, 0, 6, 0, 4, 3, 0, 1, 5, 1, 2, 4, 2, 4]

var elements = [10, 6, 0, 1, 2, 5, 4, 3, 7, 8, 9]

extension Array where Element: Comparable {
func heapSorted() -> Array {
var r = self

func parent(_ i: Int) -> Int {
return ((i+1) / 2) - 1
}

func leftChild(_ i: Int) -> Int {
return ((i + 1) * 2) - 1
}

func rightChild(_ i: Int) -> Int {
return leftChild(i) + 1
}

func descend(i: Int, limit: Int) {
let lindex = leftChild(i)
let rindex = rightChild(i)
if rindex > limit || r[lindex] > r[rindex] {
if lindex <= limit && r[lindex] > r[i] {
(r[lindex],r[i]) = (r[i],r[lindex])
descend(i: lindex, limit: limit)
}
} else if rindex <= limit {
if r[rindex] > r[i] {
(r[rindex],r[i]) = (r[i],r[rindex])
descend(i: rindex, limit: limit)
}
}
}

func maxHeapify() {
let lastParent = parent(r.count - 1)
for i in (0...lastParent).reversed() {
descend(i: i, limit: r.count - 1)
}
}

func sortFromHeap() {
for i in (1..<r.count).reversed() {
(r[0],r[i]) = (r[i],r[0])
descend(i: 0, limit: i-1)
}
}

maxHeapify()
sortFromHeap()

return r
}
}

elements.heapSorted().forEach{print(\$0, terminator: " ")}
print()```

On to writing mergesort (stable).

Sigh.

## Matrix Operations in Swift

I recently completed 10 Days of Statistics on HackerRank. Yay!

In the process, I needed some matrix operations for a medium-difficulty problem. And here they are, code style be damned :

```func transpose(_ matrix: [[Double]]) -> [[Double]] {
let rowCount = matrix.count
let colCount = matrix[0].count
var transposed : [[Double]] = Array(repeating: Array(repeating: 0.0, count: rowCount), count: colCount)
for rowPos in 0..<matrix.count {
for colPos in 0..<matrix[0].count {
transposed[colPos][rowPos] = matrix[rowPos][colPos]
}
}
return transposed
}

func multiply(_ A: [[Double]], _ B: [[Double]]) -> [[Double]] {
let rowCount = A.count
let colCount = B[0].count
var product : [[Double]] = Array(repeating: Array(repeating: 0.0, count: colCount), count: rowCount)
for rowPos in 0..<rowCount {
for colPos in 0..<colCount {
for i in 0..<B.count {
product[rowPos][colPos] += A[rowPos][i] * B[i][colPos]
}
}
}
return product
}

// gauss jordan inversion
func inverse(_ matrix: [[Double]]) -> [[Double]] {
// augment matrix
var matrix = matrix
var idrow = Array(repeating: 0.0, count: matrix.count)
idrow[0] = 1.0
for row in 0..<matrix.count {
matrix[row] += idrow
idrow.insert(0.0, at:0)
idrow.removeLast()
}

// partial pivot
for row1 in 0..<matrix.count {
for row2 in row1..<matrix.count {
if abs(matrix[row1][row1]) < abs(matrix[row2][row2]) {
(matrix[row1],matrix[row2]) = (matrix[row2],matrix[row1])
}
}
}

// forward elimination
for pivot in 0..<matrix.count {
// multiply
let arg = 1.0 / matrix[pivot][pivot]
for col in pivot..<matrix[pivot].count {
matrix[pivot][col] *= arg
}

for row in (pivot+1)..<matrix.count {
let arg = matrix[row][pivot] / matrix[pivot][pivot]
for col in pivot..<matrix[row].count {
matrix[row][col] -= arg * matrix[pivot][col]
}
}
}

// backward elimination
for pivot in (0..<matrix.count).reversed() {
for row in 0..<pivot {
let arg = matrix[row][pivot] / matrix[pivot][pivot]
for col in pivot..<matrix[row].count {
matrix[row][col] -= arg * matrix[pivot][col]
}
}
}

// remove identity
for row in 0..<matrix.count {
for _ in 0..<matrix.count {
matrix[row].remove(at:0)
}
}

return matrix
}

let X = [ [1.0, 2.0, 3.0], [4.0, 5.0, 11.0], [7.0, 8.0, 9.0] ]
let XI = inverse(X)
let I = multiply(X,XI)
print(I)
```

That’s the identity matrix popping out at the end, which validates my implementation.

But what’s this? A 60-line method? Uncle Bob would not be pleased.

Comments should not take the place of good variable/method names. Those section comments give clues as to where my methods should be :

```func augment(_ matrix: [[Double]]) -> [[Double]] {
var augmented = matrix
var idrow = Array(repeating: 0.0, count: matrix.count)
idrow[0] = 1.0
for row in 0..<matrix.count {
augmented[row] += idrow
idrow.insert(0.0, at:0)
idrow.removeLast()
}
return augmented
}

func deaugment(_ matrix: [[Double]]) -> [[Double]] {
var deaugmented = matrix

for row in 0..<matrix.count {
for _ in 0..<matrix.count {
deaugmented[row].remove(at:0)
}
}
return deaugmented
}

func partialPivot(_ matrix: inout [[Double]]) {
for row1 in 0..<matrix.count {
for row2 in row1..<matrix.count {
if abs(matrix[row1][row1]) < abs(matrix[row2][row2]) {
(matrix[row1],matrix[row2]) = (matrix[row2],matrix[row1])
}
}
}
}

func scaleRow(_ matrix: inout [[Double]], row: Int, scale: Double) {
for col in 0..<matrix[row].count {
matrix[row][col] *= scale
}
}

func addRow(_ matrix: inout [[Double]], row: Int, scaledBy: Double, toRow: Int) {
for col in 0..<matrix[row].count {
matrix[toRow][col] += scaledBy * matrix[row][col]
}
}

func pivot(_ matrix: inout [[Double]], row pivotRow: Int, col pivotCol: Int, forward: Bool) {
let scale = 1.0 / matrix[pivotRow][pivotCol]
scaleRow(&matrix, row: pivotRow, scale: scale)

if forward {
for toRow in (pivotRow+1)..<matrix.count {
let scaleBy = -1.0 * matrix[toRow][pivotCol]
addRow(&matrix, row: pivotRow, scaledBy: scaleBy, toRow: toRow)
}
} else {
for toRow in (0..<pivotRow).reversed() {
let scaleBy = -1.0 * matrix[toRow][pivotCol]
addRow(&matrix, row: pivotRow, scaledBy: scaleBy, toRow: toRow)
}
}
}

func gaussJordanInverse(_ matrix: [[Double]]) -> [[Double]] {
var matrix = augment(matrix)
partialPivot(&matrix)

for p in 0..<matrix.count {
pivot(&matrix, row: p, col: p, forward: true)
}

for p in (0..<matrix.count).reversed() {
pivot(&matrix, row: p, col: p, forward: false)
}

matrix = deaugment(matrix)

return matrix
}

let X = [ [1.0, 2.0, 3.0], [4.0, 5.0, 11.0], [7.0, 8.0, 9.0] ]
let XI = gaussJordanInverse(X)
let I = multiply(X,XI)
print(I)
```

Better. Uncle Bob would be proud (or give me credit for trying, anyway).

One more thing : Thanks to StackOverflow user Alexander, I have an even better way to express that pivot loop :

```func pivot(_ matrix: inout [[Double]], row pivotRow: Int, col pivotCol: Int, forward: Bool) {
let scale = 1.0 / matrix[pivotRow][pivotCol]
scaleRow(&matrix, row: pivotRow, scale: scale)

let range = forward ? AnyCollection((pivotRow+1)..<matrix.count) : AnyCollection((0..<pivotRow).reversed())

for toRow in range {
let scaleBy = -1.0 * matrix[toRow][pivotCol]
addRow(&matrix, row: pivotRow, scaledBy: scaleBy, toRow: toRow)
}
}
```

## iOS Williamsburg – Swift Basics

Do you want to learn Swift syntax, have fun, and meet an enthusiastic group of developers? Come by the Williamsburg Library at 515 Scotland Street, Williamsburg, VA, on Saturday, August 12, 2017. We will be going over Swift basics. We have many experienced developers who are eager to share tips and help newcomers.

### iOS development basics.

Saturday, Aug 12, 2017, 10:00 AM

Location details are available to members only.

11 Members Attending

Room c

I hope to see you there!

## iOS Dev Camp DC 2017

It’s tomorrow! See you at iOS Dev Camp DC on Friday, August 3, 2017.

I am looking forward to meeting many talented developers and learning all about who you are and what you do.

## iOS Swift Developers in Williamsburg, VA

### Get together to meet, discuss our plans for future meet ups and learn some Swift

Saturday, Jul 22, 2017, 10:00 AM

Williamsburg Library
515 Scotland Street Williamsburg, VA

7 Members Attending

Bring your laptop, we can go over the basics of swift and see where everyone is skills wise.

If you are near the Williamsburg Library on Scotland St. this Saturday, July 22 2017, at 10AM, and you have an interest in iOS development using the Swift programming language, please stop by. I will be giving a presentation on language basics and the development environment. We have a diverse group of enthusiasts with newbies and app store veterans alike.

## Swift Fun with ArraySlice

There is a lovely article by Luna An describing ArraySlice objects in more detail than I do here. It covers Swift 3 at the moment, and you should note that Swift 4 includes support for single-ended ranges, so you can create slices ala [..<count].

I found a good use for an ArraySlice while trying to find quartiles in a set of data.

The problem of finding each quartile is essentially the same problem of finding the median from three different data sets, one being the original input set, the other two being the upper and lower half of the set after removing the original median element, if it exists.

Here, I use findMedian to perform all three tasks. I found that I had to do a bit of extra work because the array slice is not indexed starting at zero. I wonder why they chose to implement slices in this way?

```import Foundation

func findMedian(_ data: ArraySlice<Int>) -> (Int, Int, Int) {
let index1 = (data.count-1)/2
let index2 = data.count/2
let sliceIndex1 = index1 + data.startIndex
let sliceIndex2 = index2 + data.startIndex
let median = (data[sliceIndex1]+data[sliceIndex2])/2
return (sliceIndex1, sliceIndex2, median)
}

let data = [0, 1, 2, 5, 11, 17, 19, 21]

let X = data[0..<data.count]
let (q2Index1, q2Index2, Q2) = findMedian(X)
let L = data[0..<q2Index2]
let U = data[(q2Index1+1)..<data.count]
let (_, _, Q1) = findMedian(L)
let (_, _, Q3) = findMedian(U)

print(Q1)
print(Q2)
print(Q3)```