Just enough computer science for the busy developer

I studied computer science so you don’t have to

#enoughcs

Just enough computer science for the busy developer

I studied computer science so you don’t have to

#enoughcs

.

Slides

jqno.nl/talks

/enoughcs

Questions?

Check flyer for

instructions

Codesmiths

Unite!

Why

Diversity matters

Science matters

If you remember only 1 thing

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();
}

Truth table

`a`	`b`	`!(a \|\| b)`	`!a && !b`
0	0	1	1
0	1	0	0
1	0	0	0
1	1	0	0

Truth table

`a`	`b`	`!(a && b)`	`!a \|\| !b`
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

If you remember only 2 things

Jan Ouwens

1999 - 2005

│ EqualsVerifier │ jqno.nl │ jqno

#enoughcs

Lots of interesting people

Edsger Dijkstra

1930 - 2002

Edsger Dijkstra

“Testing shows the presence, not the absence of bugs.”

Edsger Dijkstra

“The question of whether machines can think is about as relevant
as the question of whether submarines can swim.”

Edsger Dijkstra

“The teaching of BASIC should be rated as a criminal offence:
it mutilates the mind beyond recovery.”

Precondition + Postcondition

   {Precondition}
    Statement
   {Postcondition}

Precondition + Postcondition

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

Q.E.D.

A simple algorithm

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

A simple algorithm

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


  i := 0

; do b[i] ≠ n →

    i := i + 1

  od

A simple algorithm

  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

A simple algorithm

  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

A simple algorithm

  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

A simple algorithm

  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

A simple algorithm

  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⟩ }

Q.E.D.

What it looked like for me

Proving algorithms is hard

Speaking of algorithms

محمد خوارزمی

? - 850

Muhammad al-Khwarizmi

? - 850

Algorithmi

? - 850

Algorithm

We live in an

age of libraries

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

how?

Have someone do it for you

Katherine Johnson

1918 - 2020

Katherine Johnson

2016

Complexity

How many steps?

Let’s define

N = input size

Complexity

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

N steps

Complexity

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

1 step

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;
}

N² steps

Complexity

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

2^N steps

Complexity

Brute-forcing travelling salesman

N! steps

Complexity

Binary search
Git bisect

log₂ N steps

Complexity

Binary search
Git bisect

log₂ N steps

🤔🤔🤔

Complexity

Binary search
Git bisect

Way less than N steps

Abstraction

over complexity

Donald Knuth

1938 -

Donald Knuth

“Beware of bugs in the above code;
I have only proved it correct, not tried it.”

Donald Knuth

“Premature optimization is the root of all evil.”

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

Big O notation

steps	Big O
1	O(1)
log N	O(log N)
N	O(N)
N²	O(N²)
2^N	O(2^N)

Big O notation

steps	Big O
2N	O(N)
42N² + 2N + 3	O(N²)
log₂ N	O(log N)

Big O notation

N	2	10	100	1000
O(1)	1	1	1	1
O(log N)	1	3,3	6,6	10
O(N)	1	10	100	1000
O(N²)	1	100	10.000	1.000.000
O(2^N)	2	1024	1,2×10³⁰	1,1×10³⁰¹
O(N!)	1	3.628.800	9,3×10¹⁵⁷	🤯

Big O notation

N	name
O(1)	constant
O(log N)	logarithmic
O(N)	linear
O(N²)	quadratic
O(2^N)	exponential
O(N!)	factorial

Big O notation

N
O(1)
O(log N)
O(N)
O(N²)	↑ Polynomial
O(2^N)	↓ Slow
O(N!)

Why do we care about this?

Alan Turing

1912 - 1954

Alan Turing

2014

Disclaimer

Cracking codes

worse than polynomial

Verifying codes

polynomial

NP

“nondeterministic-polynomial”
finding an answer: slow
checking an answer: P

NP

Rubik’s cube
Sudoku
Logistics
Bitcoin

NP

Obviously, P ≠ NP

jè.

Depending on P≠NP

banking
secure messaging
society as a whole

In practice

Grace Hopper

1906 - 1992

Know the big O of your algorithms

Know your

data structures

Array

operation	big O
access	O(1)
search	O(N)
insert	O(N)
append	O(1)

Linked list

operation	big O
access	O(N)
search	O(N)
insert	O(1)
append	O(N)

HashMap

operation	big O
access	n/a
search	O(1)
iteration	O(N)
insert	O(1)

Other data structures

ArrayList
LinkedList
CopyOnWriteArrayList
Stack
~~Vector~~

Other data structures

HashSet
EnumSet
LinkedHashSet
SortedSet
TreeSet

Other data structures

HashMap
EnumMap
LinkedHashMap
SortedMap
TreeMap

Other data structures

Queue
Deque
…

Immutable collections

Vavr, Eclipse Collections, Guava

In Java

No:

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

In Java

Yes:

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

In Java

Yes:

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

In Java

Yes:

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

Let’s

wrap up

Margaret Hamilton

1936 -

Margaret Hamilton

2017

Software engineering

Programming

Analysis
Architecture
UX design
Testing

Computer science

Recap

Thing 1:

De Morgan’s Laws

Recap

Thing 2:

Truth tables

Recap

Complexity

& Big O

Choose wisely

Recap

Data structures

Choose wisely

Now you know enough CS!

What’s next?

Keep this stuff in the back of your mind

What’s next?

Look it up when you need to decide

Tip: Google “Big O cheat sheet”

What’s next?

Experiment

What’s next?

Experiment

Tip:
Implement your own HashMap!

What’s next?

Experiment

Advanced tip:
Implement your own compression algorithm!

Questions?

jqno.nl/talks/enoughcs

#enoughcs

image credits: see website