# Notes

General computer science concepts, algorithms, data structures, and technical notes.

# Section

• 2-SAT algorithm using SCC
• 3-SAT is NP-complete
• A finite tree that has more than one vertex must have at least two leaf vertices
• A vertex with the highest post order number lies in a source SCC
• Access control list (ACL) filters
• Accuracy
• Action-advantage function (RL)
• Activation function
• Acyclic graph
• Additive increase Multiplicative Decrease (AIMD)
• Address Resolution Protocol (ARP)
• Address space (OS)
• Adjacency list format (graph)
• All linear programmes can be represented in standard form
• Angur
• Anonymous Functions
• Application Programming Interface (API)
• Arithmetic mean
• Arithmetic mean is greater than or equal to the geometric mean
• ARP cache
• Array (data structure)
• ARTEMIS
• Associative array
• Associativity
• ASwatch
• Asynchronous programming
• Atomic instruction
• Automatic Repeat Request (ARQ)
• Autonomous system (AS)
• Autonomous system number (ASN)
• Backward propagation of errors (Back propagation)
• Backwards compatibility
• Bagging
• Balance between library providers and users
• Balanced cut problem
• Battle of the sexes
• Bayes rule
• Bayeses optimal classifier
• Bayesian network
• Bayesian network if and only if it satisfies the local Markov Property
• Bellman equation
• Bellman-Ford algorithm
• BGP Blackholing
• BGP Communities
• BGP Flowspec
• BGP Hijacking
• BGP squatting
• Big-O notation
• Big-Omega notation
• Big-Theta notation
• Binary operation
• Binary step
• Binomial coefficient
• Bipartite graph
• Bit
• Bitrate
• Bitrate adaption
• Bitwise operations in python
• Blackholing (BH)
• Blackholing attack
• Boarder gateway protocol (BGP)
• Boolean function
• Boolean variable
• Boosting
• Breadth-first search (BFS)
• Bridge
• Broadcast (networks)
• Broken tea cup
• Buddy Allocator
• Byte
• Cache
• Cache coherence
• Calculate polynomial regression coefficients for MSE
• Carmichael number
• Causal consistency
• Chain Hashing
• Chain multiply problem
• Chain rule (probability)
• Check if a linear programme is solvable
• Checked exceptions
• Checking if a linear programme is feasible
• Checkpointing
• Checksum
• Checksum in layer 4
• Chinese remainder theorem
• Classes in Python
• Classification problems
• Client
• Client-Server model
• Clique (graph)
• Clique of a given size problem
• Clique of a given size problem is in NP
• Clique of a given size problem is NP-complete
• Cliques in G are independent sets in the complement
• Clustering Problem
• Cocktail party problem
• Coding Principles
• Cohesion
• Comment conventions
• Complement graph
• Complete graph
• Computational Folk theorem
• Concept
• Concept class
• Concurrency
• Conditional entropy
• Conditional Independence
• Conditional probability
• Conditional variables (Mutex)
• Congestion control in TCP
• Conjunctive normal form (CNF)
• Connected (graph)
• Connected components (graph)
• Connection between OSI and IPS models
• Consistency model
• Consistent clustering
• Consistent hashing
• Consistent learner
• Consumer Price Index (CPI)
• Content delivery network (CDN)
• Context content conclusion (CCC)
• Context switch (CPU)
• Conventions
• Coprime
• Copy on write (COW)
• Cost complexity pruning for decision trees (CPP)
• Count to infinity problem
• Coupling
• CPU register
• Credit assignment problem
• Cross validation
• Crossover (genetic algorithms)
• CRUD API
• Cut (graph)
• Cut property
• Cycle (graph)
• Cycles in a graph via the DFS tree
• Data - Object Anti-Symmetry
• Data structure
• DDoS reflection and amplification
• Deadlock
• Decision tree
• Declarative Language
• Default Gateway
• Degree (graph)
• Degrees of freedom
• Demand paging
• Dependency Inversion Principle (DIP)
• Dependency Trees (Bayesian Network)
• Depth-first search (DFS)
• Descriptor table
• Design Patterns
• Device driver
• DFS for finding strongly connected components
• DFS to find connected components in an undirected graph
• DFS to find path in a directed graph
• DFS to find path in an undirected graph
• DFS tree (algorithm)
• Difference between an IP and MAC address
• Dijkstra's algorithm
• Dimensionality reduction
• Direct memory access (DMA)
• Directed acyclic graph (DAG)
• Directed graph
• Discounted rewards
• Distance vector routing algorithms
• Distributed algorithm
• Distributed Denial-of-Service (DDoS)
• Distributed file system (DFS)
• Distributed shared memory (DSM)
• DNS censorship
• DNS injection
• DNS records
• Domain Name System (DNS)
• Dot product
• DSN-based content delivery
• Dual linear programme
• Duplex
• Dynamic Adaptive Streaming over HTTP (DASH)
• Dynamic Host Configuration Protocol (DHCP)
• Dynamic Programming
• Eager learner
• Earliest deadline first (EDF)
• Edge weights
• Edmonds-Karp algorithm
• Eigenvector and Eigenvalue
• Elimination and Nash Equilibrium
• Encapsulation
• End to end principle
• Ensemble learning
• epsilon-exhausted version space
• Epsilon-greedy exploration
• Equivalent tree definitions
• Ergodic Markov chain
• Ergodic Markov chain limiting distrubution
• Ergodic Markov chains have a unique stationary distribution
• Error code
• Error function (modelling)
• Error Handling
• Error rate (modelling)
• Euclid's rule
• Euclidean algorithm
• Euler's theorem (modular arithmetic)
• Euler's totient function
• Eulers product formula (totient function)
• Every min-cut has no flow going backwards along it in a max-flow
• Every min-cut is at full capacity in a max-flow
• Evolutionary Architecture model (EvoArch)
• Exact prefix hijacking
• Exception
• Exclusive or
• Existance of Nash equilibrium
• Existence of a Fermat witness if and only if composite
• Expectation Maximisation
• Expected value
• Explore exploit dilemma
• Extended Euclidean algorithm
• External fragmentation
• F1 score
• Fast API
• Fast retransmit
• Fast-Flux Service Networks (FFSN)
• Fermat witness
• Fermat's little theorem
• File Transfer Protocol (FTP)
• Filtering (feature selection)
• Find connected components in a undirected graph
• Find path in a directed graph
• Find path in undirected graph
• Find strongly connected components for an undirected graph
• Finding rouge networks (FIRE)
• Finding the maximum likelihood estimation for normally distributed noise is the same as minimising mean squared error
• Finite Markov Decision Process
• Firewall
• First in first out (FIFO) queue
• First-class object
• Flow
• Flow control in TCP
• Flow network
• Flows are maximal if there is no augmenting path
• Fold (cross validation)
• Folk Theorem
• Ford-Fulkerson Algorithm
• Forest (graph)
• Formatting conventions
• Fourier Matrix
• Fragmentation
• Frame (networks)
• Function
• Function codomain
• Function conventions
• Function domain
• Function image
• Functions in Python
• Game theory
• Gateway
• Gaussian kernel (SVM)
• Genetic algorithm (meta)
• Geometric mean
• Gini index
• Go back N
• Gradient decent
• Graph
• Graph representations
• Great Firewall of China (GFW)
• Greatest common divisor
• Gridworld
• Grim trigger strategy
• Halting problem
• Happens with high probability
• Hardware protection levels
• Hash function
• Hash table
• Haussler Theorem
• Head of line (HOL) blocking
• Heap (OS)
• Hill climbing
• Host (networks)
• Hot potato routing
• How post order relates to strongly connected components
• HTTP redirection
• Hub
• Hyper Text Transfer Protocol (HTTP)
• Hyperbolic tangent (tanh)
• Hyperplane
• Hypertext Transfer Protocol Secure (HTTPS)
• If a point in a linear programme has equal objective function to a point in its dual linear programme they are both optimal
• If two variables are independent conditional entropy excludes the dependent
• If two variables are independent joint entropy is additive
• Image Segmentation
• Image segmentation by max flow
• Imperative Programming
• Impossibility Theorem
• Imposters syndrome
• Imposture attack (IM)
• Increasing sequence
• Incremental learning
• Independent component analysis
• Independent events
• Independent identically distributed samples
• Independent set (graph)
• Independent set of a given size
• Independent set of a given size is in NP
• Independent set of a given size is NP-complete
• Indicator function
• Induced subgraph
• Inductive bias
• Infeasible linear programme
• Inference
• Information entropy
• Instance-based learning
• Integer linear programming is NP-hard
• Integer linear programming problem
• Integrated Memory Controller (IMC)
• Inter-process communication (IPC)
• Interdomain routing
• Interface
• Interface definition language (IDL)
• Interior gateway protocol (IGP)
• Internal fragmentation
• Internet
• Internet engineering task force (IETF)
• Internet Exchange Points (IXPs)
• Internet Protocol (IP)
• Internet Protocol (IPv4)
• Internet Protocol Stack (IPS) 4 layers
• Internet Protocol Stack (IPS) 5 layers
• Internet protocol stack hourglass shape
• Internet Service Provider (ISP)
• Intradomain routing
• Inverse of the Fourier matrix
• Inverted page tables (IPT)
• IP Anycast
• Iris
• Irreducible
• Irreducible error
• Irreducible Markov chain
• Irrelevant feature
• Iterative algorithms
• Iterative Dichotomiser 3 (ID3)
• Joint distribution
• Joint Entropy
• k-colourings problem (graphs)
• k-means clustering
• k-nearest neighbour
• k-SAT is in NP
• k-SAT is NP-complete for k greater than or equal to 3
• k-satisfiability problem (k-SAT problem)
• Kernel
• Kernel trick
• Knapsack Problem
• Knapsack problem (without repetition)
• Knapsack-search (without replacement)
• Knapsack-search is NP
• Knapsack-search is NP-complete
• Kruskal's algorithm
• Kullback–Leibler divergence
• Lambda functions
• Layer 1 Physical
• Layer 2 Data Link
• Layer 3 Network
• Layer 4 Transport
• Layer 5 Session
• Layer 6 Presentation
• Layer 7 Application
• Lazy learner
• Leaf (graph)
• Learning rate convergence
• Least-recently used (LRU)
• Length of a probability
• Linear dimensionality reduction
• Linear programme
• Linear programme standard form
• Linear programming problem
• Linear regression
• Linearly separable
• Link-state routing algorithms
• Linked lists
• Local Markov property
• Logarithms
• Logging in python
• Logical and
• Logical or
• Loop (graph)
• MAC address
• Machine Learning
• Man-in-the-middle attack (MM)
• Many-one reduction (problem)
• Margin for a linear separator
• Marginalisation (probability)
• Markdown
• Markov chain
• Markov decision process
• Markup Language
• Matrix
• Max clique problem (graph)
• Max clique problem is NP-hard
• Max flow problem
• Max independent set problem (graph)
• Max independent set problem is NP-hard
• Max-flow min-cut Theorem
• Max-k-exact-satisfiability problem
• Max-SAT is NP-hard
• Max-SAT random approximation algorithm
• Max-Satisfiability Problem
• Maximum a posteriori probability estimate (MAP)
• Maximum likelihood estimation (MLE)
• Mean squared error (MSE)
• Memory allocator
• Memory controller
• Memory frame
• Memory Management Unit (MMU)
• Memory page
• Memory segment
• Memory segmentation
• Middleboxes
• MIMIC (meta)
• MIMIC by dependency trees
• Min st-cut problem
• Minimax-Q
• Minimum Spanning Tree problem (MST)
• Minimum Spanning Tree problem is in NP
• Minimum vertex cover problem
• Minimum vertex cover problem is NP-hard
• Minmax decision
• Minmax profile
• Mistake bound
• Mixed strategy
• Model-based reinforcement learning
• Modelling bias
• Modelling framework
• Modelling paradigm
• Modular arithmetic
• Modular exponent algorithm
• Modular exponent problem
• Modular inverse algorithm (extended Euclidean algorithm)
• Modular inverse problem
• Modular multiplicative inverse existence
• Monitors
• MPEG-DASH
• Multi-level page tables
• Multi-processing
• Multi-threading
• Multiplexing
• Multiprotocol label switching (MPLS)
• Mutability
• Mutability in Python
• Mutation (genetic algorithms)
• Mutex
• Mutual information
• Mutual information is symmetric
• Naive Bayes classifier
• Namespaces
• Naming conventions
• Nash equilibrium
• Neighbourhood (graph)
• NeoVim Cheat Sheet
• Network
• Network Address Translation (NAT)
• Network file system (NFS)
• Network mask
• Neural network
• Node (IPv6)
• Non-trivial Fermat witnesses are dense
• Nondeterministic Polynomial time (NP)
• Normal distribution
• Northbridge Memory Controller
• NP-Complete
• NP-hard
• Object
• Objective function
• Occam's razor
• Ones complement
• Open Closed Principle (OCP)
• Open Shortest Path First (OSPF)
• Open Systems interconnection (OSI) model
• OpenFlow
• Operating system (OS)
• Optimisation problem
• Optimistic exploration
• Optimum play exists for 2-player zero-sum games with perfect information
• Overfitting
• P equals NP or P not equals NP
• p-value
• PAC learnable bound with VC-dimension
• PAC-learnable if and only if finite VC dimension
• Packets
• Page rank
• Page rank algorithm
• Page table
• Page table entry
• Paging system
• Pairwise coprime
• Palindrome
• Parallelisation
• Partition (set)
• Passing variables to a function
• Path (graph)
• Pavlov strategy
• PCI Express (PCIe)
• Peer distributed application
• Peer-peer model
• Perceptron (neural network)
• Perceptron rule
• Perfect information
• Periodic Markov chain
• Periodic state (markov chain)
• Peripheral component interconnect (PCI)
• Physical Frame Number (PFN)
• Physical memory
• Pipe
• Plausible threat
• Policy (MDP)
• Policy Iteration (MDP)
• Polymorphism
• Polynomial kernel (SVMs)
• Polynomial regression
• Polynomial time
• Polynomial time is a subset of NP-complete
• Polysemy
• Port
• Portable operating system interface (POSIX)
• POSIX threads (PThreads)
• Pre-commit hooks
• Pre-pruning decision trees
• Precision
• Prediction
• Preference bias
• Prim's algorithm
• Prime
• Principle component analysis
• Prisoner's dilemma
• Probability distribution
• Probably approximately correct learnable (PAC)
• Proccess modes
• Procedural Programming
• Process
• Process control block (PCB)
• Process Identification (PID)
• Product of roots of unity
• Program counter (PC)
• Programmed IO (PIO)
• Programming paradigms
• Proper vertex colouring
• Protocol (networks)
• Pseudo devices
• Pseudo-header
• Pseudo-polynomial time
• Pure strategy
• Python Built-in Functions
• Pythonic
• Q-function (RL)
• Q-learning
• Quality function (RL)
• Quantization
• Quick sort
• Race condition
• Random Access Memory (RAM)
• Random component analysis
• Reader-writer locks
• Recall
• Rectified linear unit (ReLU)
• Recursion
• Refactored
• Reference counting in Python
• Regression problems
• Reinforcement learning
• Reliable transmission of TCP messages
• Remote direct memory access (RDMA)
• Remote procedure calls (PRC)
• Repeater
• Request for Comments (RFC)
• Residual Network (flow)
• REST API
• Restart hill climbing
• Restriction Bias
• Result types
• Retail Price Index (RPI)
• Return (RL)
• Reverse directed graph
• Reversible Markov chain
• Rich clustering
• Rivest-Shamir-Adleman algorithm (RSA algorithm)
• Rooted tree
• Round robin DNS (RRDNS)
• Round trip time (RTT)
• Route summarization
• Router
• Router (IPv6)
• Routing
• Routing Information Protocol (RIP)
• Routing table
• Rudrata cycle
• Rudrata cycle problem
• Rudrata path
• Rudrata path problem
• Run time complexity
• Sample complexity
• SAT is NP-complete
• Satisfiability problem (SAT problem)
• SBRI model
• Scale-invariant clustering
• Search problems
• Secure Socket Layer (SSL)
• Security region
• Segment
• Semaphores
• Semi-wall stochastic game
• Separation of concerns (SoC)
• Sequence
• Sequential consistency
• Server
• Session Initiation Protocol (SIP)
• Side effect
• Sigmoid function
• Sigmoid kernel (SVM)
• Sign function
• Signed or unsigned integers
• Simple Mail Transfer Protocol (SMTP)
• Simplex method (linear programme)
• Simulated Annealing
• Simulated annealing ending probability
• Single linkage clustering
• Single Responsibility Principle (SRP)
• Singleton
• Slab allocator
• Socket
• Soft clustering
• Software defined networks (SDN)
• SOLID principles
• Sorting problem
• Spanning subgraph
• Spanning Tree Protocol (STP)
• Special case pattern
• Special functions
• Spinlocks
• Spoofing
• Spurious wakeups
• st-cut
• Stack (OS)
• Stack Pointer (SP)
• Standard deviation
• Start and end point bias
• Stationary distribution (Markov Chains)
• Step function
• Step function methods
• Stirling's approximation
• Stochastic games
• Stochastic matrix
• Stop and wait ARQ
• Strict consistency
• Strictly dominated strategy
• Strong duality theorem (linear programme)
• Strong duality theorem optimum (linear programme)
• Strongly connected (directed graphs)
• Strongly connected component graph (directed graph)
• Strongly connected components (directed graphs)
• Strongly relevant feature
• Sub-prefix hijacking
• Subgame perfect
• Subgraph
• Subnets
• Subsequence
• Subset-sum problem
• Subset-sum problem is in NP
• Subset-sum problem is NP-complete
• Substring
• Sum of roots of unity
• Supervised learning
• Support vector machines (SVM)
• Switch
• Switching
• Symmetric Markov chain
• Symmetric Markov chains have a uniform stationary distribution
• Synchronization
• Synonymy
• System call
• Taking the reverse respects going to the strongly connected component graph
• TCP 3 way handshake
• TCP connection teardown
• TCP CUBIC
• TCP Reno
• Test Driven Development (TDD)
• Testing conventions
• Testing data
• The 5S Philosophy
• The curse of dimensionality
• The dual dual linear programme is the original linear programme
• The flow across an st-cut is equal to the value of the flow itself
• The Halting problem is undecidable
• The k-colourings problem is in NP
• The k-colourings problem is NP-complete
• The Law of Demeter
• The perceptron rule using binary step converges in finite time if the dataset is linearly separable
• The Satisfiability problem is in NP
• The strongly connected component graph is a DAG
• The strongly connected components are the same in a directed graph and its reverse
• Thread
• Tit for Tat
• Topological sorting (DAG)
• Traffic Engineering Framework
• Traffic Scrubbing Service
• Train Wrecks
• Training data
• Training error
• Trampolining
• Transforming discrete input for regression
• Transitions (MDP)
• Translation Lookaside Buffer (TLB)
• Transmission control in TCP
• Transmission Control Protocol (TCP)
• Transport Layer Security (TLS)
• Trap instruction
• Traveling salesman problem
• Traveling salesman problem (search)
• Tree (graph)
• Trie
• True error
• Two's complement
• Type-0 hijacking
• Type-N hijacking
• Type-U hijacking
• Unbounded linear programme
• Unbounded linear programmes have infeasible duals
• Undecidable problem
• Underfitting
• Unicast
• Uniform distribution
• Uniqueness of inverses
• Unsupervised learning
• Useful feature
• User Datagram Protocol (UDP)
• Using multiple git profiles
• Value function (RL)
• Value iteration (MDP)
• Vapnik-Chervonenkis dimension
• Variables in python
• Variance
• Version space
• Vertex Colouring
• Vertex cover
• Vertex cover if and only if the complement is an independent set
• Vertex cover of a given size
• Vertex cover of a given size is NP
• Vertex cover of a given size is NP-complete
• Vertex degree sum in a graph
• Virtual Local Area Networks (VLAN)
• Virtual machine monitor (VMM)
• Virtual memory
• Virtual page number (VPN)
• Virtualization
• Voice over IP (VoIP)
• Weak consistency
• Weak duality theorem (linear programme)
• Weak learner
• Weakly relevant feature
• Webgraph
• When to Use Error Codes and Exceptions
• Wrap 3rd party libraries
• Wrapping (feature selection)
• Zero-sum game