Just enough computer science for the busy developer

De Morgan’s Laws

Mathy version

 ¬(a ⋁ b) ≡ ¬a ⋀ ¬b

 ¬(a ⋀ b) ≡ ¬a ⋁ ¬b

De Morgan’s Laws

Java version

!(a || b) == !a && !b

!(a && b) == !a || !b

For example

if (!(product.price() <= 10 || order.amount() <= 5)) {
  applyDiscount();
}

For example

if (!(a || b)) {
  applyDiscount();
}

a = product.price() <= 10
b = order.amount <= 5

For example

if (!a && !b) {
  applyDiscount();
}

a = product.price() <= 10
b = order.amount <= 5

For example

if (!(product.price() <= 10) && !(order.amount() <= 5)) {
  applyDiscount();
}

For example

if (product.price() > 10 && order.amount() > 5) {
  applyDiscount();
}

Real talk

Truth table

Truth table

Edsger Dijkstra

Edsger Dijkstra

Edsger Dijkstra

Jacquard Loom

1804

ENIAC

1945 - 1955

Modern supercomputer

present day

Tony Hoare

Precondition + Postcondition

   {Precondition}
    Statement
   {Postcondition}

Precondition + Postcondition

   {x = 3}
    x += 1;
   {x = 4}

Linear Search

Linear Search

Linear Search

Linear Search

Linear Search

Linear Search

  int[] haystack = ...;
  int needle = ...;
  
  
  int i = 0;
  
  while (haystack[i] != needle) {
  
    i += 1;
  
  }

Linear Search

  var b: array[0..N] of int = ...;
  var n: int = ...;


  i := 0

; do b[i] ≠ n →

    i := i + 1

  od

Linear Search

  var b: array[0..N] of int = ...;
  var n: int = ...;

  { ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
  i := 0

; do b[i] ≠ n →

    i := i + 1

  od

Linear Search

  var b: array[0..N] of int = ...;
  var n: int = ...;

  { ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
  i := 0
  { i = 0 ⋀ ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
; do b[i] ≠ n →

    i := i + 1

  od

Linear Search

  var b: array[0..N] of int = ...;
  var n: int = ...;

  { ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
  i := 0
  { i = 0 ⋀ ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
; do b[i] ≠ n →
    { 0 ≤ i < N ⋀ ⟨∀x : 0 ≤ x ≤ i : b[x] ≠ n⟩ ⋀ ⟨∃x : i < x < N : b[x] = n⟩ }
    i := i + 1

  od

Linear Search

  var b: array[0..N] of int = ...;
  var n: int = ...;

  { ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
  i := 0
  { i = 0 ⋀ ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
; do b[i] ≠ n →
    { 0 ≤ i < N ⋀ ⟨∀x : 0 ≤ x ≤ i : b[x] ≠ n⟩ ⋀ ⟨∃x : i < x < N : b[x] = n⟩ }
    i := i + 1
    { 0 < i < N ⋀ ⟨∀x : 0 ≤ x < i : b[x] ≠ n⟩ ⋀ ⟨∃x : i ≤ x < N : b[x] = n⟩ }
  od

Linear Search

  var b: array[0..N] of int = ...;
  var n: int = ...;

  { ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
  i := 0
  { i = 0 ⋀ ⟨∃x : 0 ≤ x < N : b[x] = n⟩ }
; do b[i] ≠ n →
    { 0 ≤ i < N ⋀ ⟨∀x : 0 ≤ x ≤ i : b[x] ≠ n⟩ ⋀ ⟨∃x : i < x < N : b[x] = n⟩ }
    i := i + 1
    { 0 < i < N ⋀ ⟨∀x : 0 ≤ x < i : b[x] ≠ n⟩ ⋀ ⟨∃x : i ≤ x < N : b[x] = n⟩ }
  od
  { 0 ≤ i < N ⋀ b[i] = n ⋀ ⟨∀x : 0 ≤ x < i : b[x] ≠ n⟩ }

What it looked like for me

Muhammad al-Khwarizmi

? - 850

Algorithmi

? - 850

Libraries

Implement an algorithm

Libraries

Implement an algorithm

Prove an algorithm

Libraries

Implement an algorithm

Prove an algorithm

Test an algorithm

Libraries

Implement an algorithm

Prove an algorithm

Test an algorithm

Choose an algorithm

Katherine Johnson

2016

Linear Search

Binary Search

Binary Search

Binary Search

Binary Search

Binary Search

Binary Search

public static int binarySearch(Comparable[] a, Object key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int cmp = a[mid].compareTo(key);
        if (cmp < 0)
            low = mid + 1;
        else if (cmp > 0)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found
}

Binary Search

Git bisect

Git bisect

Git bisect

Git bisect

Git bisect

Git bisect

Git bisect

Git bisect

❯ ~/my-project ❯ main ❯ git log
13439df  (HEAD -> main) updates dependencies
a50dab8  processes review comments
24908d8  applies formatting
3b6483a  extracts local variable
ebf5221  adds tests
cdfe9ed  replaces MySQL with BlockChain Technology™
77590b0  fixes typo
a0be795  fixes bug
99dc85b  updates README

Git bisect

❯ ~/my-project ❯ main ❯ git log
13439df  (HEAD -> main) updates dependencies
a50dab8  processes review comments
24908d8  applies formatting
3b6483a  extracts local variable
ebf5221  adds tests
cdfe9ed  replaces MySQL with BlockChain Technology™
77590b0  fixes typo
a0be795  fixes bug
99dc85b  updates README

❯ ~/my-project ❯ main ❯ git checkout 99dc85b9

Git bisect

❯ ~/my-project ❯ main ❯ git log
13439df  (HEAD -> main) updates dependencies
a50dab8  processes review comments
24908d8  applies formatting
3b6483a  extracts local variable
ebf5221  adds tests
cdfe9ed  replaces MySQL with BlockChain Technology™
77590b0  fixes typo
a0be795  fixes bug
99dc85b  updates README

❯ ~/my-project ❯ main ❯ git checkout 99dc85b9

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect start

Git bisect

13439df  (HEAD -> main) updates dependencies
a50dab8  processes review comments
24908d8  applies formatting
3b6483a  extracts local variable
ebf5221  adds tests
cdfe9ed  replaces MySQL with BlockChain Technology™
77590b0  fixes typo
a0be795  fixes bug
99dc85b  updates README

❯ ~/my-project ❯ main ❯ git checkout 99dc85b9

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect start

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect good

Git bisect

ebf5221  adds tests
cdfe9ed  replaces MySQL with BlockChain Technology™
77590b0  fixes typo
a0be795  fixes bug
99dc85b  updates README

❯ ~/my-project ❯ main ❯ git checkout 99dc85b9

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect start

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect good

❯ ~/my-project ❯ @99dc85b9 ❯ git checkout main
Previous HEAD position was 99dc85b updates README
Switched to branch 'main'

Git bisect

99dc85b  updates README

❯ ~/my-project ❯ main ❯ git checkout 99dc85b9

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect start

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect good

❯ ~/my-project ❯ @99dc85b9 ❯ git checkout main
Previous HEAD position was 99dc85b updates README
Switched to branch 'main'

❯ ~/my-project ❯ main ❯ git bisect bad
Bisecting: 3 revisions left to test after this (roughly 2 steps)
[ebf5221] adds tests

Git bisect

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect start

❯ ~/my-project ❯ @99dc85b9 ❯ git bisect good

❯ ~/my-project ❯ @99dc85b9 ❯ git checkout main
Previous HEAD position was 99dc85b updates README
Switched to branch 'main'

❯ ~/my-project ❯ main ❯ git bisect bad
Bisecting: 3 revisions left to test after this (roughly 2 steps)
[ebf5221] adds tests

❯ ~/my-project ❯ @ebf52218 ❯ git bisect bad
Bisecting: 1 revision left to test after this (roughly 1 step)
[77590b0] fixes typo

Git bisect

❯ ~/my-project ❯ @99dc85b9 ❯ git checkout main
Previous HEAD position was 99dc85b updates README
Switched to branch 'main'

❯ ~/my-project ❯ main ❯ git bisect bad
Bisecting: 3 revisions left to test after this (roughly 2 steps)
[ebf5221] adds tests

❯ ~/my-project ❯ @ebf52218 ❯ git bisect bad
Bisecting: 1 revision left to test after this (roughly 1 step)
[77590b0] fixes typo

❯ ~/my-project ❯ @77590b0d ❯ git bisect good
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[cdfe9ed] replaces MySQL with BlockChain Technology™

Git bisect

❯ ~/my-project ❯ @ebf52218 ❯ git bisect bad
Bisecting: 1 revision left to test after this (roughly 1 step)
[77590b0] fixes typo

❯ ~/my-project ❯ @77590b0d ❯ git bisect good
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[cdfe9ed] replaces MySQL with BlockChain Technology™

❯ ~/my-project ❯ @cdfe9ed1 ❯ git bisect bad
cdfe9ed1f1f8ad11ec48703e90d482996322ad1a is the first bad commit
commit cdfe9ed1f1f8ad11ec48703e90d482996322ad1a
Author: Jan Ouwens <jan.ouwens@example.com>
Date:   Mon Mar 7 10:19:22 2022 +0100

    replaces MySQL with BlockChain Technology™

Git bisect

[77590b0] fixes typo

❯ ~/my-project ❯ @77590b0d ❯ git bisect good
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[cdfe9ed] replaces MySQL with BlockChain Technology™

❯ ~/my-project ❯ @cdfe9ed1 ❯ git bisect bad
cdfe9ed1f1f8ad11ec48703e90d482996322ad1a is the first bad commit
commit cdfe9ed1f1f8ad11ec48703e90d482996322ad1a
Author: Jan Ouwens <jan.ouwens@example.com>
Date:   Mon Mar 7 10:19:22 2022 +0100

    replaces MySQL with BlockChain Technology™

❯ ~/my-project ❯ @ebf52218 ❯ git bisect reset

How many steps?

Let’s define

Complexity

public int linearSearch(int needle, int[] haystack) {
  for (int i : haystack) {
    if (haystack[i] == needle) {
      return true;
    }
  }
  return false;
}

Complexity

public int get(int[] ints, int index) {
  return ints[index];
}

Complexity

public boolean hasDuplicates(int[] ints) {
  for (int i : ints) {
    for (int j : ints) {
      if (i != j && ints[i] == ints[j]) {
        return true;
      }
    }
  }
  return false;
}

Complexity

public int fibonacci(int i) {
  if (i <= i) {
    return i;
  }
  return fibonacci(i - 2) + fibonacci(i - 1);
}

Complexity

Brute-forcing travelling salesman

Complexity

Binary search

Complexity

Binary search

log₂ N steps

🤔🤔🤔

Complexity

Binary search

Way less than N steps

over complexity

Donald Knuth

Donald Knuth

The full quote

“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.”

Book

Book

Big O notation

Big O notation

Big O notation

Big O notation

Big O notation

Big O notation

Alan Turing

2014

worse than polynomial

polynomial

NP

• “nondeterministic-polynomial”

• finding an answer: slow

• checking an answer: P

NP

• Rubik’s cube
• Sudoku
• Logistics
• Bitcoin

NP

Obviously, P ≠ NP

Depending on P≠NP

• banking
• secure messaging
• society as a whole

Array

Array

Array

Array

Linked list

Linked list

Linked list

Hash map

Hash map

Hash map

Data structures in Java

• ArrayList
• LinkedList
• CopyOnWriteArrayList
• Stack
• Vector

Data structures in Java

• HashMap
• EnumMap
• LinkedHashMap
• SortedMap
• TreeMap

Data structures in Java

• HashSet
• EnumSet
• LinkedHashSet
• SortedSet
• TreeSet

Data structures in Java

• Queue
• Deque
• …

Vavr, Eclipse Collections, Guava

Variable declaration

No:

ArrayList<String> myList = new ArrayList<>();

Variable declaration

Yes:

     List<String> myList = new ArrayList<>();

Variable declaration

Yes:

     List<String> myList = new LinkedList<>();

Variable declaration

Yes:

     List<String> myList = new CopyOnWriteArrayList<>();

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters


}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

Equality

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters


}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters
    // no equals!

}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

cs1.equals(cs2) // false

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters
    public boolean equals(Object obj) { ... }

}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

cs1.equals(cs2) // true 🥳

Equality

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters
    public boolean equals(Object obj) { ... }

}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

cs1.equals(cs2) // true 🥳

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters
    public boolean equals(Object obj) { ... }
    // no hashCode!
}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

cs1.equals(cs2) // true 🥳

cs1.hashCode()  // 253
cs2.hashCode()  // 875

Equality

class ComputerScientist {
    private final String name;

    // constructor, getters & setters
    public boolean equals(Object obj) { ... }
    public int hashCode() { ... }
}

var cs1 = new ComputerScientist("James Gosling");
var cs2 = new ComputerScientist("James Gosling");

cs1.equals(cs2) // true 🥳

cs1.hashCode()  // 253
cs2.hashCode()  // 253 🥳

Equality

Equality

Equality

Margaret Hamilton

2017

Software engineering

Software engineering

Software engineering

Big O notation

Big O notation

Big O notation

Readability

 🙂 Set<T> set;

 🧐 LinkedHashSet<T> set;

John von Neumann

1903 - 1957

Recap

Recap

Recap

Recap

Recap

Linear Search

Recap

Binary Search

Recap

Choose wisely

Recap

Choose wisely

Recap

Implement equals and hashCode

What’s next?

Keep this stuff in the back of your mind

What’s next?

Look it up when you need to decide

What’s next?

What’s next?

Experiment

What’s next?

Experiment

What’s next?

Experiment