Scribd
Upload
40 views2 pages

CS Formula Revision Guide

The document is a quick revision sheet for ISRO Scientist/Engineer 'SC' in Computer Science, covering essential topics such as algorithms, data structures, compiler design, operating systems, computer networks, databases, discrete mathematics, theory of computation, and artificial intelligence. It includes key formulas, definitions, and concepts relevant to each area. This sheet serves as a concise reference for exam preparation.

Uploaded by

u21cse1058
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
40 views2 pages

CS Formula Revision Guide

The document is a quick revision sheet for ISRO Scientist/Engineer 'SC' in Computer Science, covering essential topics such as algorithms, data structures, compiler design, operating systems, computer networks, databases, discrete mathematics, theory of computation, and artificial intelligence. It includes key formulas, definitions, and concepts relevant to each area. This sheet serves as a concise reference for exam preparation.

Uploaded by

u21cse1058
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

ISRO Scientist/Engineer ‘SC’ (Computer Science) –

Formula & Quick Revision Sheet

Algorithms & Data Structures


- Max edges in simple graph = n(n−1)/2
- Total possible graphs = 2^(n(n−1)/2)
- Sum of degrees = 2E; Euler formula: V−E+F=2
- MST: Kruskal / Prim (O(E log V))
- Shortest Path: Dijkstra (non-negative), Bellman-Ford (negative allowed), Floyd-Warshall (all-pairs)
- Diameter of binary tree → O(n)
- Heap sort → O(n log n)
- Matrix multiplication (m×n, n×p) → O(mnp)
- Substrings from string length m → m(m+1)/2

Trees & Pointers


- Preorder: Root→Left→Right | Postorder: Left→Right→Root
- Inorder predecessor = rightmost node in left subtree
- If int = 2 bytes, p+3 = p + 3×2 = p + 6

Compiler Design
- Phases: Lexical → Syntax → Semantic → Intermediate Code → Optimization → Code Gen
- LL(1): Left-to-right, Leftmost derivation, 1 lookahead
- Identifier regex: letter (letter|digit)*
- Postfix: A*B+C*D → AB*CD*+

Computer Organization
- Full Adder: 3 inputs, 2 outputs (Sum, Carry)
- Pipeline uses FIFO buffer
- Micro-operation: operation on register data
- Serial reg delay = bits / clock freq → 8/400MHz = 20ns
- NAND/NOR with tied inputs → NOT gate

Operating Systems
- Schedulers: Long-term (multiprogramming), Medium-term (swapping), Short-term (CPU)
- Page fault = non-resident page access
- Trap = software interrupt
- Priority inheritance prevents priority inversion
- Producer–Consumer uses Semaphore

Computer Networks
- Window size ≥ (Bandwidth × RTT) / Packet size
- Header overhead: (5×6)/(270+30) ≈ 10%
- Min frame (CSMA/CD): ≥ 2 × propagation delay × data rate
- IEEE 802.11 speeds: b=11Mbps, a/g=54Mbps, ad=3.5Gbps, ac=7Gbps
Databases
- Durability = permanent after success
- 5NF = Join dependency
- SELECT * FROM R,S → Cross Join
- DELETE ... WHERE dept_name IN (SELECT ...) → Subquery deletion
- Recursive SQL pattern: X→7 ⇒ Y=127

Discrete Mathematics
- Truth table rows = 2^n
- P(E') = 1 - P(E)
- Growth: n log n < n^(3/2) < n(log n)^2 < 2^n

Theory of Computation
- Minimal DFA ≤ 2^n states
- Recursive → complement also recursive
- Regular ∩ CFL = CFL; CFL ∩ Regular ≠ Regular (False)
- Example: L = {a^n b^n} = CFL

Artificial Intelligence
- First-order logic connectives: ¬, ∧, ∨, →, ↔
- <> is NOT a connective

You might also like