EM · Short notes
30 short notes in syllabus order, about 182 minutes to read end to end.
Propositional logic studies statements that are either true or false, and how the truth of a compound statement depends on the truth of its parts. It gives a precise language for conditions ("if the cache misses and the bus is free, then fetch"), for specifications, and for correctness arguments.
Propositional logic treats "every prime greater than 2 is odd" as one indivisible proposition. It cannot see the structure inside: the objects (numbers), the properties (prime, odd) and the word "every".
A set is an unordered collection of distinct objects, called its elements or members.
A relation records which elements of one set are associated with which elements of another: "a divides b", "x is a prerequisite of y", "page p links to page q". Formally, a (binary) relation from a set A to a set B is any subset R ⊆ A × B; we write a R b or (a, b) ∈ R.
A function assigns to every element of one set exactly one element of another. Hash functions, encodings, permutations of an array, the transition function of an automaton and the indexing of an array are all functions.
Many collections are ordered, but not totally: subsets ordered by inclusion, tasks ordered by "must finish before", integers ordered by divisibility. In each case some pairs are comparable and others are not. A partially ordered set (poset) captures this.
An algebraic structure is a set together with one or more operations that combine elements. Abstracting away from what the elements are (numbers, strings, permutations, matrices) and keeping only the laws the operation obeys lets one theorem cover all of them.
A graph models objects and pairwise connections between them: computers and links, cities and roads, tasks and conflicts, states and transitions. Graph theory supplies the vocabulary (degree, path, cycle, tree, planar) and the counting facts used in connectivity, matching and colouring.
A network is useful only if its parts can reach each other, and it is robust only if it stays connected when something fails.
A matching pairs up vertices along edges so that no vertex is used twice: assigning workers to jobs they are qualified for, students to projects, or tasks to processors.
Colouring a graph means giving each vertex a colour so that adjacent vertices get different colours.
" without listing. How many passwords of a given form exist, how many ways can tasks be assigned to processors, how many paths cross a grid, how many binary strings avoid a pattern?
A recurrence relation defines each term of a sequence from earlier terms: a_n = a_n-1 + a_n-2, T(n) = 2T(n/2) + n.
A generating function packs an entire sequence a_0, a_1, a_2, ... into one power series. Algebra on the series (adding, multiplying, shifting, differentiating) then corresponds to combinatorial operations on the sequence.") and to solve recurrence relations.
A matrix is a rectangular array of numbers. Matrices represent linear maps, systems of linear equations, graphs (adjacency matrices) and transformations in graphics. Later topics in linear algebra (determinants, rank, eigenvalues, LU decomposition) build on these operations and special types.
The determinant is a single number attached to a square matrix. It tells whether the matrix is invertible (non-zero determinant), how the linear map scales area or volume, and, through the characteristic polynomial, what the eigenvalues are.
A system of m linear equations in n unknowns can have exactly one solution, infinitely many, or none. Rank decides which, and Gaussian elimination computes both the rank and the solutions. The rank-nullity theorem then counts how many free parameters a solution set has.
Gaussian elimination does two jobs at once: it transforms the matrix and it transforms the right-hand side. LU decomposition separates them.
Most vectors change direction when a matrix acts on them.
A limit describes what f(x) approaches as x approaches a point, without caring what happens at the point itself. Continuity, derivatives and definite integrals are all defined through limits, and in computer science limits compare growth rates of running times.
A function is continuous where its graph has no break, and differentiable where the graph also has a well-defined tangent slope.
Finding the largest or smallest value of a function is a main use of the derivative. The method is short: locate the critical points, classify them with a derivative test, and, on a closed interval, compare with the endpoints.
The mean value theorems link the average rate of change of a function over an interval to its instantaneous rate at some interior point. They are the bridge between "the derivative is positive" and "the function increases", and they give quick error bounds.
The definite integral measures accumulated quantity: area under a curve, total probability, an average value. The fundamental theorem of calculus turns its computation into finding an antiderivative.
Probability measures how likely an uncertain outcome is, on a scale from 0 to 1. Impossible events have probability 0 and the certain event has probability 1; in general these values mean almost never/almost surely, not necessarily an empty/full event.
New information changes probabilities. Knowing that a test came back positive, that a packet arrived late, or that the first card drawn was an ace, we should update how likely the other events are. Conditional probability is the rule for that update.
Chance is described with numbers: the number of heads in ten tosses, the number of probes in a hash table, the waiting time until a server responds.
These distributions model the standard counting situations: picking uniformly from a finite set, counting successes in repeated independent trials, waiting for the first success, and counting rare events in a fixed interval.
Continuous random variables describe measurements: a random point on an interval, the lifetime of a component, the time between requests, or exam marks spread around an average. Three continuous distributions cover the GATE syllabus.
Descriptive statistics summarise a data set with a few numbers: where it is centred (mean, median, mode) and how spread out it is (range, variance, standard deviation). These are the sample counterparts of the expectation and variance of a random variable.
