Theoretical Computer Science
Homepage / Notes / Computer Science / Theoretical Computer Science
Algorithms
Thread-safe code is code that will work even if many threads are executing it simultaneously.
Search
| aspect | BFS | DFS |
|---|---|---|
| structure | queue (FIFO) | stack / recursion |
| explores | level by level | deep branches first |
| path | shortest (unweighted) | any path |
| memory | O(w) — max width | O(h) — max depth |
| time | O(V+E) | O(V+E) |
| use when | shortest path, levels | cycles, topological sort, DFS |
BFS
use std::collections::{VecDeque, HashSet};
fn bfs(graph: &Vec<Vec<usize>>, start: usize) {
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
queue.push_back(start);
visited.insert(start);
while let Some(node) = queue.pop_front() {
for &n in &graph[node] {
if !visited.contains(&n) {
visited.insert(n);
queue.push_back(n);
}
}
}
}DFS
fn dfs(graph: &Vec<Vec<usize>>, start: usize) {
let mut visited = vec![false; graph.len()];
let mut stack = vec![start];
while let Some(node) = stack.pop() {
if !visited[node] {
visited[node] = true;
for &n in graph[node].iter().rev() {
if !visited[n] { stack.push(n); }
}
}
}
}Resources
Introduction to Algorithms
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
The Algorithm Design Manual
by Steven Skiena
Data Structures
Arrays
Stride
https://en.wikipedia.org/wiki/Stride_of_an_array
Lambda Calculus
https://en.wikipedia.org/wiki/Lambda_calculus Functions in Lambda Calculus only have an arity of 1.
https://learnxinyminutes.com/docs/lambda-calculus/
Computational Complexity Theory
P=NP…
Asymptotic Notations
https://learnxinyminutes.com/docs/asymptotic-notation/
Big O
https://www.bigocheatsheet.com/
Binary / Low-level
Signed vs Unsigned Integers
Unsigned: only non-negative values. Range: 0 to 2^n - 1. Signed: uses one bit for sign. Range: -2^(n-1) to 2^(n-1) - 1.
Most languages use two's complement for signed integers:
- Invert all bits, then add 1
- Example (8-bit):
5→00000101→ flip →11111010→ +1 →11111011(which is-5) - Avoids two representations of zero, and addition/subtraction work the same way
Endianness
How multi-byte values are stored in memory.
- Big-endian: most significant byte first (
0x1234→12 34). Used in network protocols. - Little-endian: least significant byte first (
0x1234→34 12). Used by x86/ARM.
0x12345678 in memory:
| address | big-endian | little-endian |
|---|---|---|
| +0 | 12 | 78 |
| +1 | 34 | 56 |
| +2 | 56 | 34 |
| +3 | 78 | 12 |
Type Theory
Primitives
https://en.wikipedia.org/wiki/Primitive_data_type
Generic Programming
Generics / Parametric Polymorphism
A function using parametric polymorphism would be written with types to be specified later, and then instantiated when needed with types provided as parameters.
Resources
Types and Programming Languages
by Benjamin C. Pierce
A tutorial implementation of a dependently typed lambda calculus
https://www.andres-loeh.de/LambdaPi/LambdaPi.pdf
Typing Haskell in Haskell
https://web.cecs.pdx.edu/~mpj/thih/thih.pdf
Henk: a typed intermediate language
https://www.microsoft.com/en-us/research/wp-content/uploads/1997/01/henk.pdf
Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism
https://www.cl.cam.ac.uk/~nk480/bidir.pdf
Practical Foundations for Programming Languages
https://www.cs.cmu.edu/~rwh/pfpl/
Computability Theory
Turing Completeness
A machine or language is said to be Turing-complete when it can run any computational problem. Most modern languages are Turing-complete as they all implement the basic features (sum, product, if/else…) needed to compute any program possible.