ISRO Scientist/Engineer SC (Computer Science) cheat sheet

De Morgan's laws: ¬(p∧q)≡¬p∨¬q and ¬(p∨q)≡¬p∧¬q.

For sets |A|=m and |B|=n, the number of functions from A to B is n^m; injections are P(n,m); bijections exist only if m=n and number n!.

Pigeonhole principle: placing N items into k boxes forces some box to contain at least ⌈N/k⌉ items.

Master theorem: for T(n)=aT(n/b)+f(n), compare f(n) with n^(log_b a); the larger term determines the asymptotic order, with a logarithmic factor when equal.

Eigenvalues satisfy det(A−λI)=0; trace(A) is the sum of eigenvalues and det(A) is their product.

Poisson distribution: P(X=k)=e^(−λ)λ^k/k!, with mean and variance both λ.

Euclid's algorithm uses gcd(a,b)=gcd(b,a mod b); LCM(a,b)=ab/gcd(a,b).

A relation is an equivalence relation iff it is reflexive, symmetric, and transitive; it partitions the set into disjoint equivalence classes.

In any graph the degree sum is 2|E|; a tree on n vertices has n−1 edges; K_n has n(n−1)/2 edges.

An n-bit two's complement integer ranges from −2^(n−1) to 2^(n−1)−1; negation inverts all bits and adds one.

Boolean De Morgan laws: (A·B)'=A'+B' and (A+B)'=A'·B'.

XOR outputs 1 when inputs differ; x⊕x=0 and x⊕0=x.

Karnaugh-map groups must contain 1, 2, 4, 8, or more cells and should be as large as possible; don't-care cells may be treated as 0 or 1.

Setup time is the interval data must be stable before the active clock edge; hold time is the interval after it. Violations can cause metastability.

CPU time = instruction count × CPI × clock period, where CPI = total cycles / instruction count.

Amdahl's law: speedup = 1 / ((1−p) + p/s), where p is the improved fraction and s the improvement factor.

Direct-mapped cache: index bits = log2(number of lines); tag bits = address bits − index bits − offset bits.

Little-endian stores the least significant byte at the lowest address; big-endian stores the most significant byte there.

Array access by index is O(1); linked-list search is O(n), while insertion or deletion at a known node is O(1).

A stack is LIFO and a queue is FIFO; a circular queue reuses slots and avoids false overflow.

Inorder traversal of a binary search tree visits keys in sorted order; average search and insertion are O(log n), worst case O(n).

Hash table load factor α=n/m; separate chaining has average search cost O(1+α), while open addressing probes until an empty slot is found.

AVL balance factor = height(left)−height(right); every node must have balance factor −1, 0, or 1, restored by rotations.

For a 1-indexed heap array, node i has children 2i and 2i+1 and parent ⌊i/2⌋; build-heap is O(n) and extract-min is O(log n).

In C, an array name decays to a pointer to its first element; sizeof(array) gives the array size, while sizeof(pointer) gives pointer size.

Pass by value copies the argument; pass by reference passes an address or alias. C has no reference parameters, while C++ does.

A binary tree with n nodes has n+1 null child links.

Binary search runs in O(log n) and requires a sorted array with O(1) random access.

Merge sort is O(n log n) time and O(n) extra space; quicksort is average O(n log n) but worst-case O(n²).

Stable sorts preserve equal-key order: insertion sort, merge sort, and counting sort are stable; heapsort and usual quicksort are not.

Dijkstra requires nonnegative edge weights and runs in O((V+E) log V) with a binary heap; Bellman-Ford handles negative edges in O(VE).

Kruskal's MST algorithm is O(E log E); Prim's is O(E log V) with a binary heap.

Dynamic programming requires optimal substructure and overlapping subproblems; greedy algorithms require the greedy-choice property.

0/1 knapsack uses O(nW) dynamic programming; fractional knapsack is solved greedily by value/weight ratio.

A topological ordering exists iff the directed graph is acyclic; Kahn's algorithm removes zero-indegree vertices, and DFS uses reverse finish order.

NP-complete means in NP and NP-hard; a polynomial-time solution to any NP-complete problem would imply P=NP.

A DFA is (Q,Σ,δ,q0,F); an NFA accepts if some computation path reaches an accepting state, and subset construction converts an NFA to a DFA.

Regular languages are closed under union, intersection, complement, concatenation, and Kleene star; context-free languages are not closed under intersection or complement.

Pumping lemma for regular languages: there exists p such that every string s with |s|≥p splits as xyz, |xy|≤p, |y|≥1, and xy^i z remains in the language for all i≥0.

A grammar is ambiguous if some string has two distinct parse trees; leftmost and rightmost derivations are canonical derivation orders.

LL(1) parsing requires no left recursion and disjoint FIRST sets for alternatives; if a production derives epsilon, FIRST and FOLLOW must be disjoint.

FIRST(α) is the set of terminals that can begin strings derived from α; FOLLOW(A) is the set of terminals that can appear immediately after A.

The halting problem is undecidable; recursive languages are a proper subset of recursively enumerable languages.

Compiler phases: lexical analysis, syntax analysis, semantic analysis, intermediate code, optimization, and code generation.

Static single assignment (SSA) gives each variable one definition, simplifying def-use chains and many optimizations.

Process states include new, ready, running, waiting, and terminated; a context switch saves one PCB and restores another.

FCFS scheduling can cause the convoy effect; SJF minimizes average waiting time but requires burst-time knowledge; round robin uses a fixed quantum.

A correct critical-section solution provides mutual exclusion, progress, and bounded waiting.

Semaphore wait/P decrements the value and may block; signal/V increments it and may wake a blocked process. Binary semaphores take values 0 and 1.

Deadlock requires mutual exclusion, hold-and-wait, no preemption, and circular wait simultaneously.

Banker's algorithm grants a request only if the resulting state is safe, meaning some completion order exists for all processes.

FIFO page replacement can exhibit Belady's anomaly; LRU and optimal replacement do not.

Effective access time = (1−p)×memory access time + p×page-fault service time, where p is the page-fault rate.

Thrashing is a high page-fault rate caused by insufficient frames; the working-set model tracks recently used pages to control multiprogramming.

ACID properties: atomicity, consistency, isolation, and durability.

2NF removes partial dependencies on a composite candidate key; 3NF removes transitive dependencies; BCNF requires every determinant to be a superkey.

Relational algebra operators include σ selection, π projection, ⋈ join, and × Cartesian product.

SQL logical evaluation order is FROM, WHERE, GROUP BY, HAVING, SELECT, then ORDER BY; SELECT aliases are not available in WHERE.

NULL comparisons use IS NULL or IS NOT NULL; NULL = NULL evaluates to unknown, not true.

A B+ tree index supports range queries and ordered scans; a hash index supports equality lookups but not efficient ranges.

A schedule is conflict serializable iff its precedence graph is acyclic.

Two-phase locking guarantees conflict serializability; strict two-phase locking holds exclusive locks until commit and prevents cascading rollback.

Armstrong's axioms: reflexivity, augmentation, and transitivity generate all functional dependencies implied by a set.

OSI has seven layers: physical, data link, network, transport, session, presentation, application; TCP/IP commonly groups them into four layers.

TCP is connection-oriented and reliable, using sequence numbers, acknowledgments, sliding-window flow control, and congestion control.

UDP is connectionless and unreliable; DNS typically uses UDP port 53 for ordinary queries.

The IPv4 header is at least 20 bytes; each router decrements TTL, and a TTL of zero causes the packet to be dropped.

With h host bits, a subnet has 2^h addresses and 2^h−2 usable hosts because network and broadcast addresses are reserved.

Ethernet uses CSMA/CD for shared media; Wi-Fi uses CSMA/CA with acknowledgments.

ARP maps an IPv4 address to a MAC address on the local link; DHCP assigns IP configuration automatically.

Stop-and-wait efficiency is 1/(1+2a), where a = propagation delay / transmission time; sliding windows improve utilization.

NAT translates private addresses to public addresses; private IPv4 ranges are 10/8, 172.16/12, and 192.168/16.

SDLC models include waterfall, iterative, spiral, and agile; spiral explicitly emphasizes risk analysis.

Functional requirements describe behavior; nonfunctional requirements describe quality attributes such as performance, security, and usability.

High cohesion and low coupling are desirable because they localize responsibilities and reduce inter-module dependencies.

Black-box testing uses external behavior; white-box testing uses code structure. Equivalence partitioning and boundary value analysis are black-box techniques.

Test levels are unit, integration, system, and acceptance testing.

Cyclomatic complexity V(G)=E−N+2 for a control-flow graph, equivalently decision points plus one.

Regression testing re-runs selected tests after changes to detect newly introduced defects.

COCOMO estimates effort from estimated thousands of lines of code (KLOC) and cost drivers.

Continuous integration merges changes frequently and runs automated builds and tests to expose integration defects early.

Compilers translate before execution; interpreters execute directly; JIT compilation translates hot code at runtime.

Static typing checks types at compile time; dynamic typing checks at runtime. Strong typing restricts implicit coercions, while weak typing permits more of them.

OOP pillars are encapsulation, inheritance, and polymorphism; overloading is compile-time selection and overriding is runtime dispatch.

Java passes arguments by value, including copies of object references; String objects are immutable.

Python uses indentation for blocks; lists are mutable and tuples immutable; the GIL limits parallel execution of Python bytecode threads.

JavaScript uses prototype-based inheritance; == performs type coercion, while === requires equal type and value.

HTTP methods: GET is safe and idempotent; PUT and DELETE are idempotent; POST is neither safe nor generally idempotent.

HTTP status classes: 1xx informational, 2xx success, 3xx redirection, 4xx client error, 5xx server error.

REST is stateless; parameterized queries prevent SQL injection, output encoding prevents XSS, and anti-CSRF tokens prevent CSRF.