ISRO Scientist/Engineer SC (Computer Science) flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Pigeonhole principle

If N items are placed into k containers, at least one container holds at least ceiling(N/k) items; if N exceeds k, some container holds at least two.

Equivalence relation

A relation on a set that is reflexive, symmetric, and transitive. It partitions the set into disjoint equivalence classes whose union is the whole set.

Master theorem case 2

For T(n)=aT(n/b)+f(n), if f(n)=Θ(n^(log_b a) log^k n) with k≥0, then T(n)=Θ(n^(log_b a) log^(k+1) n).

Two's complement range

An n-bit two's complement integer ranges from −2^(n−1) through 2^(n−1)−1. Negation is performed by inverting all bits and adding one.

CPI

Cycles per instruction equals total processor cycles divided by instruction count. CPU time is instruction count times CPI times clock cycle time.

Direct-mapped cache tag

Tag bits equal address width minus index bits minus offset bits. The index selects the cache line, and the offset selects the byte within the block.

AVL balance factor

For a node, height of the left subtree minus height of the right subtree. An AVL tree requires this value to be −1, 0, or 1 at every node.

Heap array indexing

In a 1-indexed array, node i has children 2i and 2i+1 and parent floor(i/2). Building a heap bottom-up takes O(n) time.

Hash load factor

Load factor alpha equals stored entries divided by table slots. Chaining average search cost is O(1+alpha); resizing keeps alpha bounded.

Dijkstra limitation

Dijkstra's algorithm requires nonnegative edge weights. Negative edges can invalidate finalized distances, so Bellman-Ford is used instead.

Stable sorting

A stable sort preserves the relative order of records with equal keys. Insertion sort, merge sort, and counting sort are stable; quicksort and heapsort usually are not.

0/1 knapsack complexity

Dynamic programming solves 0/1 knapsack in O(nW) time and O(W) space with a one-dimensional table, where W is capacity and n is item count.

Pumping lemma regular

For every regular language there exists p such that any string s of length at least p can be split xyz with |xy|≤p, |y|≥1, and xy^i z in the language for all i≥0.

LL(1) grammar condition

An LL(1) grammar has no left recursion and, for each nonterminal, productions have disjoint FIRST sets; if a production derives epsilon, its FIRST and FOLLOW sets are disjoint.

Halting problem

The problem of deciding whether an arbitrary Turing machine halts on a given input is undecidable; no general algorithm can solve it for all machine-input pairs.

Deadlock four conditions

Deadlock requires mutual exclusion, hold-and-wait, no preemption, and circular wait simultaneously. Breaking any one condition prevents the deadlock cycle.

Belady's anomaly

With FIFO page replacement, increasing the number of page frames can increase the number of page faults for some reference strings; LRU and optimal replacement do not exhibit it.

Semaphore wait and signal

Wait (P) decrements the semaphore and blocks if the value becomes negative. Signal (V) increments it and wakes a blocked process when appropriate.

BCNF condition

A relation is in Boyce-Codd normal form when every nontrivial functional dependency has a determinant that is a superkey of the relation.

Conflict serializability

A schedule is conflict serializable if its precedence graph, with edges for conflicting operation order, is acyclic; then it is equivalent to some serial schedule.

SQL logical order

SQL clauses are logically evaluated FROM, WHERE, GROUP BY, HAVING, SELECT, then ORDER BY; aliases defined in SELECT are not available in WHERE.

TCP congestion slow start

TCP slow start begins with a small congestion window and doubles it each round-trip time until the slow-start threshold, then switches to congestion avoidance.

ARP purpose

Address Resolution Protocol maps a known IPv4 address to a link-layer MAC address on the local network by broadcasting a request and caching the reply.

Subnet usable hosts

With h host bits, a subnet has 2^h total addresses and 2^h−2 usable host addresses, because the all-zeros network and all-ones broadcast addresses are reserved.

Cyclomatic complexity

Cyclomatic complexity equals E−N+2 for a control-flow graph, or decision points plus one; it gives the number of linearly independent paths.

Cohesion and coupling

Cohesion measures how strongly related a module's internal responsibilities are; coupling measures interdependence between modules. Good design seeks high cohesion and low coupling.

Black-box testing

Testing based on requirements and external behavior without inspecting internal code. Equivalence partitioning and boundary value analysis are common black-box techniques.

Method overloading vs overriding

Overloading defines multiple methods with the same name but different parameter lists, resolved at compile time. Overriding redefines an inherited method with the same signature, resolved at runtime.

HTTP status classes

1xx informational, 2xx success, 3xx redirection, 4xx client error, and 5xx server error. For example, 404 is client error and 500 is server error.

SQL injection defense

Use parameterized queries or prepared statements so user input is treated as data, not executable SQL. Input validation and least-privilege database accounts add defense in depth.

Topological sort condition

A directed graph has a topological ordering if and only if it is acyclic. Kahn's algorithm repeatedly removes zero-indegree vertices; DFS can use reverse finish order.

Two-phase locking

A transaction acquires all locks in a growing phase and releases them in a shrinking phase. Strict two-phase locking holds exclusive locks until commit, preventing cascading rollbacks.