# Chapter 1: Getting ready
###### tags: `epi`

Data structures summary

| Data structure | Summary |
| ------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| Primitive types | Integers, Float, Strings, Boolean. Know common primitive operations. |
| Arrays | Only supports one type in one array, O(1) index lookup, O(n) search lookup, know iteration, resize, partition, merge, ... |
| Strings | Understand what is fastest for comparison, copying, matching, joining, splitting |
| Lists | Supports multiple types in one list, know iteration, insertion, deletion, dynamic allocation |
| Singly linked list | Know how to implement, know iteration, insertion, deletion |
| Doubly linked list | Know how to implement, know iteration, insertion, deletion |
| Stacks | Last-in first-out, know how to implement with array and linked list |
| Queues | First-in first-out, know how to implement with array and linked list |
| Binary trees | Hierarchical data representation. Know how to calculate depth, height, leaves, search path, traversal sequences, successor/ predecessor operations |
| Heaps | O(1) lookup find-max, O(log n) insertion, O(log n) deletion of max, know min and max heap variant |
| Hash tables | O(1) inseration, deletions and lookups. Cannot order, poor worst-case performance, needs resizing to prevent key conflicts, know how to implement, array of buckets, collision chains, hash function for integer, string and objects. |
| Binary search trees | O(log n) insertion, O(log n) deletion, O(log n) lookup, O(log n) find-min, max, successor, predecessor (when tree is balanced by height), know fields, pointer, keeping tree balanced. |

| Algorithm type | Summary |
| -------------- | ----------- |
| Sorting | Sort output |
| Recursion | End condition with self-invoked loop |
| Divide-and-conquer | Divide output in smaller independent subproblems and solve original problem using subproblem solutions |
| Dynamic programming | Use previous solutions of smaller instances for later solutions (cache + performance boost) |
| Greedy Algorithms | Use local optimum at each step for total solution |
| Invariants | Conditions of program that never change and thus prove when something works (or does not) |
| Graph modeling | Problem visualized as graph, use graph algorithm to solve it |

Approach any problem:
1. Manually solve some concrete examples; small inputs, extreme, ...
2. split into several cases and solve in isolation
3. use brute force approach first and then refine
4. use known solutions as subroutine for full problem

Tips:
- Integers in Python3 are unbounded (limited by memory, not implementation of type)
-