Computer Science¶

School¶

Mathematics

Probability and Statistics
Discrete Mathematics
Operations Research
Numerical Analysis
Control systems

Algorithms and Data Structures
Theory of Computation
Compilers and Languages
OS
Computer Networks

C / C++ / Java / Python
Assembly Programming
OOP, Design Patterns
RDBMS
Parallel Computing
Storage Networks

Time Analysis¶

Linear O(n)
Constant O(1)

Logarithm times¶

O(log n) - Binary Search

2, 2^2, 2^ 3 …..
0, 1, 2, 3 …

log (8,2) = number of steps taken on the number line to count the geometric progression.
See vihart’s video.

O(n logn) - Quick Sort

Each step has n comparisons.
Total steps = log n.

Data Structure Optimisations¶

Cache levels
Loop Unrolling
Branch prediction
AoS vs SoA
Slab allocator

Trees¶

parent and child
root and leaf
node and edge
sibling
ancestor and descendants
level
path
height == depth

Degree of node we call the number of direct children of the given node.
Branching factor is the maximum of the degrees of all nodes in the tree.

Tree is a recursive structure.

Depth of node is depth of parent plus 1.
Height of internal node is maximum height of height of internal node is maximum height of children + 1

Graphs¶

Nodes or Vertices
Edges (can be directed or undirected)
Weighted Edges

number of edges in a directed graph can be a maximum of n(n-1).

dense and sparse graphs.

path: each adjacent pair is connected by an edge. (trail)
simple path: vertices are not repeated (walk)
path.

connected graph: a path exists between any vertex.
strongly connected, weakly connected for diagraphs. weak means diagraph as graph is connected.

cycle: first and last nodes are repeated. tree is acyclic.

simple graph if there are no cycles.

representation: edge list
big o for operations - O(n2) where n is number of vertices

represenation: v x v adjacency matrix
representation: list of list of adjacency

proportional to O(v)

simple problems

adjacent
does a path exist

does a path exist can be found by DFS and BFS.
DFS is recursive. recursively goes deeper into the children.

BFS uses a queue and iteratively visits the adjancent nodes.

connected: there is a path b/w/ any two vertices
articulation point - deleting a node means the graph is not two graphs.
biconnected - no articulation points

kosaraju’s algo

G / G transpose

DFS on G transpose. Then sort by denominator.
DFS on G using vertices from previous. Every time you get a strongly connected component set.

tarjans algorithm

prims algo : spanning tree
Kruskal: minimum spanning tree

dijkstra: shortest path

In a game like AoE, divide the map into regions.
Run pathfinding algorithm to see if a path exists.

Dividing a graph into regions.
pick node.
tranverse all edges, while ignoring seen nodes.
if any nodes are remaining, create a group, repeat.

Depth first transverse each node edge first.
Use a stack to keep track.

Breadth first uses a queue but the stack no longer holds path.

Dikstra’s algo works for weighted graphs.
It is breadth first with minimum cost calculation.

Data Sturctures and Algorithms¶

Hash Table¶

Convert a string to a unique number. How ?

Bit operations
polynomial

hash = hashfunc(key)
index = hash % array_size

Collisions¶

Chaining
Open Addressing

For open addressing schemes, the hash function should also avoid clustering

What if array is full ?

While inserting, keep load factor in mind. If it exeeds it, double the size of the array and rehash everything.

Arrays¶

homogenity
random seek
fixed length

Records¶

non homogenous
random seek
fixed length

list¶

homogenous
sequential seek(both directions)
variable length

Common Algoss¶

array
array_reversal
array_duplicate_remover
split
gcd
8 queens
combinations / permutations
itertools

Types of sorting¶

Bubble Sort¶

Move greater element to the right by comparing two elements at a time; always starting from the start. If no moves are made, the list is sorted.

Insertion Sort¶

Compare three elements. Move the lesser to the left. Just like playing cards.

Quick Sort¶

Select a pivot.
Split array into three arrays and sort the lesser and greater array in comparison with a pivot.
Divide the list into two; all less that the pivot and greater than the pivot. Recursively apply.
During each step, the pivot gets sorted to the appropriate position.

Merge Sort¶

Recursively split at mid point.

Split array into 2 or 3 elements each and sort them while merging.

Divid the list into two lists at mid point recursively. Merge sublists into a new list in increasing order by comparing lists pairwise.

Counting Sort¶

Find max,min. k = max - min + 1
Calculate the frequency array which is of the same length as the given array.
Caclulate cumulative frequency.
Get index of input[i] in the final result by using the cumulative frequency table.

Radix Sort¶

It sort does counting sort for each decimal place.

Complexity¶

|—–|——|——|——-|

|Bubble|\(n\)|\(n^2\)|\(n^2\)|
|Insertion|\(n\)|\(n^2\)|\(n^2\)|
|Quick|\(n\\ log(n)\)|\(n\\ log(n)\)|\(n^2\)|
|Merge|\(n\\ log(n)\)|\(n\\ log(n)\)|\(n\\ log(n)\)|
|Counting|\(n + k\)|\(n + k\)|\(n + k\)|

External Sorting

Benchmarks http://sortbenchmark.org/
Algo
K-way merge
K-wat merge with a heap
Partition sort

Hadoop does sorting between map and reduce stage automatically. Map emits and the key is used for intermediate sort.

State Machines¶

Historically computers arose to assist calculations in labs, military or banks. During the initial days, the procedures for calculations had to be fed in manually. However with the advent of programmable storage this became semi-manual.

Through time, these calculations coupled with programmable storage came to be known as Algorithms. Coupled with transmission and display, the Algorithms have become Automatons.

Algorithms + Communication = Automaton.

The impact of Automatons has been dramatic to say the least. At this moment, every business is either becoming a Software business or being replaced by Automatons.

The field of Computer Science is the study of Automatons. Although Robots which are Automatons with a body discussed more widely, Automatons however don’t seem to enjoy the fear and awe although they are even more sickly pervasive.

Automata is about Memory + Computation.

Memory can be stores as a Single Variable. This is called the Accumulator machine.

Memory can be stored as Stack. This is called the Stack machine.

Memory can be stored in RAM or Registers. This is called the RAM / Register machine.

Memory can be stored as Queue. This is called the Queue machine.

Memory can be stored as Tape. This is called the Turing machine.

Memory can be stored as a Token. This is called the Token machine.

Memory can be stored as a Tree. This is called the Tree machine.

State is a Data Structure tht should answer the following queries,

What is the current state ?
What are the next states ?
Is the state at the beginning or is it at the end ?

In fact any Real World object from light to atom that can store this information is fit for use as Memory.

Computation is Reaction to Inputs. Distributed Automata are best modelled by Queue Machines and Token Machines.Automata is about Memory + Computation.

State machines are more central to programming that objects and functions. The biggest failure of language designers for the last 50 years is not producing a language with state machines. From my searching I copuld only find one

https://github.com/p-org/P/

Where are state machines used ?

Games
Control Systems
Network Protocols
Language Parsing
VHDL/Verilog
UI (State Charts)
Gesture detection/interaction
Life cycle management
Process synchronization
Lockfree data structure
REST (https://nordicapis.com/designing-a-true-rest-state-machine/)

Coding Notes