<!--

Computer Science nuggets without all the mumbo-jumbo. (Click to expand)

Computer Science nuggets without all the mumbo-jumbo

Learn to calculate run time from code examples

Learn how to compare algorithms using Big O notation. (Click to expand)

Learn how to compare algorithms using Big O notation.

Comparing algorithms using Big O notation

Let's say you want to find the duplicates on an array.

Using Big O notation, we can compare different solutions that solve the same problem but has a massive difference in how long it takes to do it.

- Optimal solution using a map

- Finding duplicates in an array (naïve approach)

8 examples to explain with code how to calculate time complexity. (Click to expand)

8 examples to explain with code how to calculate time complexity

Most common time complexities

<!-- - Constant time: _O(1)_

- Logarithmic time: _O(log n)_

- Linear time: _O(n)_

- Linearithmic time: _O(n log n)_

- Quadratic time: _O(n^2^)_

- Cubic time: _O(n^3^)_

- Exponential time: _O(2^n^)_

- Factorial time: _O(n!)_ -->

Time complexity graph

Understand the ins and outs of the most common data structures. (Click to expand)

Understand the ins and outs of the most common data structures

- Arrays: Built-in in most languages so not implemented here. Array Time complexity

    

- Linked List: each data node has a link to the next (and

    previous).

    Code

    |

    Linked List Time Complexity

    

- Queue: data flows in a "first-in, first-out" (FIFO) manner.

    Code

    |

    Queue Time Complexity

    

- Stack: data flows in a "last-in, first-out" (LIFO) manner.

    Code

    |

    Stack Time Complexity

    

When to use an Array or Linked List. Know the tradeoffs. (Click to expand)

When to use an Array or Linked List. Know the tradeoffs

Use Arrays when…

- You need to access data in random order fast (using an index).

- Your data is multi-dimensional (e.g., matrix, tensor).

Use Linked Lists when:

- You will access your data sequentially.

- You want to save memory and only allocate memory as you need it.

- You want constant time to remove/add from extremes of the list.

- when size requirement is unknown - dynamic size advantage

Build a List, Stack, and a Queue. (Click to expand)

  ---

  #### Build a List, Stack and a Queue from scratch

  Build any of these data structures from scratch:

  - Linked List

  - Stack

  - Queue

  ---

Understand one of the most versatile data structure of all: Hash Maps. (Click to expand)

HashMaps

Learn how to implement different types of Maps such as:

- HashMap

- TreeMap

Also, learn the difference between the different Maps implementations:

- HashMap is more time-efficient. A TreeMap is more space-efficient.

- TreeMap search complexity is O(log n), while an optimized HashMap is O(1) on average.

- HashMap’s keys are in insertion order (or random depending on the implementation). TreeMap’s keys are always sorted.

- TreeMap offers some statistical data for free such as: get minimum, get maximum, median, find ranges of keys. HashMap doesn’t.

- TreeMap has a guarantee always an O(log n), while HashMaps has an amortized time of O(1) but in the rare case of a rehash, it would take an O(n).

Know the properties of Graphs and Trees. (Click to expand)

Know the properties of Graphs and Trees

Graphs

Know all the graphs properties with many images and illustrations.

Graphs: data nodes that can have a connection or edge to

    zero or more adjacent nodes. Unlike trees, nodes can have multiple parents, loops.

    Code

    |

    Graph Time Complexity

Trees

Learn all the different kinds of trees and their properties.

- Trees: data nodes has zero or more adjacent nodes a.k.a.

    children. Each node can only have one parent node otherwise is a

    graph, not a tree.

    Code

    |

    Docs

    

    - Binary Trees: same as a tree but only can have two children at

        most.

        Code

        |

        Docs

        

    - Binary Search Trees (BST): same as a binary tree, but the

        nodes value keep this order left < parent < right.

        Code

        |

        BST Time complexity

        

    - AVL Trees: Self-balanced BST to maximize lookup time.

        Code

        |

        AVL Tree docs

        |

        Self-balancing & tree rotations docs

        

    - Red-Black Trees: Self-balanced BST looser than AVL to

        maximize insertion speed.

        Code

      Implement a binary search tree for fast lookups.

Implement a binary search tree for fast lookups

- Learn how to add/remove/update values in a tree:

- How to make a tree balanced?

From unbalanced BST to balanced BST

0. ```
1. 1                           2
2.   \                       /   \
3.    2        =>           1     3
4.     \
5.      3
6. ```

Never get stuck solving a problem with 7 simple steps. (Click to expand)

Never get stuck solving a problem with 8 simple steps

1. Understand the problem

1. Build a simple example (no edge cases yet)

1. Brainstorm solutions (greedy algorithm, Divide and Conquer, Backtracking, brute force)

1. Test your answer on the simple example (mentally)

1. Optimize the solution

1. Write code. Yes, now you can code.

1. Test your written code

1. Analyse the complexity, both space and time, and make sure to optimize further.

Full details here

Master the most popular sorting algorithms (merge sort, quicksort, etc.) (Click to expand)

Master the most popular sorting algorithms

We are going to explore three essential sorting algorithms O(n^2), which have low overhead:

  - Bubble Sort.

    Code

    |

    Docs

  - Insertion Sort.

    Code

    |

    Docs

  - Selection Sort.

    Code

    |

    Docs

and then discuss efficient sorting algorithms O(n log n) such as:

  - Merge Sort.

    Code

    |

    Docs

  - Quicksort.

    Code

    |

    Docs

Learn different approaches to solve problems such as divide and conquer, dynamic programming, greedy algorithms, and backtracking. (Click to expand)

Learn different approaches to solve algorithmic problems

We are going to discuss the following techniques for solving algorithms problems:

- Greedy Algorithms: makes greedy choices using heuristics to find the best solution without looking back.

- Dynamic Programming: a technique for speeding up recursive algorithms when there are many _overlapping subproblems_. It uses _memoization_ to avoid duplicating work.

- Divide and Conquer: _divide_ problems into smaller pieces, _conquer_ each subproblem, and then _join_ the results.

- Backtracking: search _all (or some)_ possible paths. However, it stops, and _go back_ as soon as notice the current solution is not working.

- _Brute Force_: generate all possible solutions and tries all of them. (Use it as a last resort or as the starting point).