CHSE Odisha Elective Computer Science cheat sheet

Von Neumann stored-program design uses one memory for both instructions and data; the CPU repeatedly fetches an instruction, decodes it, executes it, and stores results.

CPU parts: the ALU performs arithmetic and logic; the control unit coordinates operations; registers hold operands and addresses. PC holds the next instruction address, IR the current instruction, MAR a memory address, and MBR transferred data.

Memory hierarchy from fastest and costliest to slowest and cheapest: CPU registers, cache, main memory (RAM), secondary storage such as SSD or HDD, and archival storage.

RAM is volatile read/write main memory; ROM is non-volatile and commonly stores firmware. Cache is faster than RAM and holds recently used blocks.

Capacity units: 1 byte = 8 bits; 1 KB = 1024 bytes; 1 MB = 1024 KB; 1 GB = 1024 MB; 1 TB = 1024 GB.

Input devices transfer data into a computer (keyboard, mouse, scanner, microphone, webcam); output devices present results (monitor, printer, speaker, plotter); a touchscreen can do both.

System software includes the operating system, language translators (compiler, interpreter, assembler), loaders and linkers, and utilities; application software performs user tasks such as word processing or browsing.

Operating system roles: process scheduling, memory allocation, file and directory management, device management, security, and user interface. Examples are Windows, Linux, macOS, and Android.

Buses carry information between the CPU and other units: the address bus carries addresses, the data bus carries data in both directions, and the control bus carries read/write and interrupt signals.

In base r, a digit d at position k has value d × r^k; positions increase leftward from 0 at the radix point, and negative indices lie to the right.

Decimal to base r: divide the integer part repeatedly by r, record remainders, and read them from last to first. Multiply the fractional part repeatedly by r and read integer parts from top to bottom.

Binary to decimal: add bit × 2^position for each 1 bit. Decimal to binary can also use repeated subtraction of the largest powers of two.

Binary to octal: group 3 bits from the radix point outward and pad with zeros; binary to hexadecimal: group 4 bits. Each octal digit equals 3 bits; each hexadecimal digit equals 4 bits.

Hexadecimal digits: 0–9 then A=10, B=11, C=12, D=13, E=14, F=15. Example: 10101111₂ = AF₁₆.

For n-bit two's complement, the range is −2^(n−1) to +2^(n−1)−1. Negative x is encoded as 2^n − x, equivalently invert all bits and add 1.

Subtraction A − B = A + (two's complement of B), discarding the final carry beyond n bits. Overflow occurs when the sign of the result is wrong for the operand signs.

BCD encodes each decimal digit in 4 bits, so 47 is 0100 0111 in BCD, not the ordinary binary value 101111. Patterns 1010–1111 are invalid BCD digits.

Gray code changes only one bit between consecutive values; binary-to-Gray conversion keeps the MSB and XORs each adjacent bit pair, g_i = b_i ⊕ b_(i+1).

AND outputs 1 only if all inputs are 1; OR outputs 1 if any input is 1; NOT inverts. NAND and NOR are their inverted forms.

NAND and NOR are universal gates: each can implement NOT, AND, OR, and therefore any Boolean expression.

XOR outputs 1 when inputs differ: A⊕B = A′B + AB′. XNOR is its complement and outputs 1 when inputs are equal.

Identities: A+0=A, A·1=A, A+1=1, A·0=0, A+A=A, A·A=A, A+A′=1, A·A′=0.

De Morgan: (A+B)′ = A′·B′ and (A·B)′ = A′+B′. Complementing an expression swaps AND with OR and complements each literal.

Absorption: A+AB=A and A(A+B)=A. Distributive: A(B+C)=AB+AC and A+BC=(A+B)(A+C).

SOP sums minterms where output is 1; POS multiplies maxterms where output is 0. A canonical form includes every variable in each term.

K-map simplification groups adjacent 1s in sizes 1, 2, 4, 8, and so on; groups may wrap across edges, and each group eliminates variables that change within it.

Half adder: Sum=A⊕B, Carry=AB. Full adder: Sum=A⊕B⊕Cin, Carry=AB+ACin+BCin. Flip-flops store one bit and are clocked sequential elements.

C is case-sensitive; a program has preprocessor directives, declarations, and function definitions. Execution begins at main(), which normally returns int, with 0 indicating success.

Basic types: char, int, float, double. sizeof(type) gives size in bytes; signed, unsigned, short, and long modify integer ranges.

printf and scanf formats: %d int, %c char, %f float, %lf double in scanf, %s string, %u unsigned, %x hexadecimal. scanf needs & for ordinary variables; array names already give an address.

Precedence from high to low includes postfix, array, and function; unary; multiplicative; additive; relational; equality; logical AND; logical OR; conditional ?:; assignment. Associativity resolves equal precedence.

Control: if/else selects; switch needs an integral controlling expression and constant case labels; for, while, and do...while repeat, with do...while running at least once; break exits and continue skips to the next iteration.

Functions are declared with a prototype, defined once, and called by name; arguments pass by value by default. Pointer parameters let a function modify caller variables.

Arrays store same-type elements contiguously; valid indices are 0 to n−1; C does not check bounds. A 2D array is stored row by row, and an array name usually decays to a pointer to its first element.

A C string is a char array ending in '\0'. strlen excludes the terminator; strcpy copies, strcat appends, strcmp returns 0 when equal; the destination must have enough capacity.

File I/O uses FILE *fp=fopen(name,mode); check for NULL; modes are r, w, a, r+, w+, a+; close with fclose(fp). fgetc/fputc handle characters, fgets/fputs lines, and fprintf/fscanf formatted data.

Linear structures store elements in sequence (array, stack, queue, linked list); nonlinear structures branch (tree, graph).

Stack: LIFO, with push, pop, and top operations at one end; overflow occurs when full, underflow when empty. Uses include expression conversion and evaluation, delimiter matching, recursion, and undo.

Queue: FIFO, with enqueue at the rear and dequeue at the front. A circular queue reuses array slots by wrapping indices; a priority queue serves the highest-priority element first.

A singly linked list node stores data plus a next pointer; the last next pointer is NULL. Doubly linked nodes also have prev. Insert or delete at a known node is O(1); search is O(n).

Array random access is O(1); insertion or deletion in the middle is O(n) because elements shift. Linked list access is O(n) because traversal is required.

Linear search checks elements in order, is O(n) worst case, and needs no sorted data. Binary search needs sorted random-access data and runs in O(log n).

Bubble, selection, and insertion sorts are O(n²) worst and average. Merge sort is O(n log n) but needs O(n) extra space; quicksort is average O(n log n) and worst O(n²).

Infix to postfix uses a stack for operators; postfix evaluation pushes operands and, for each operator, pops two operands, applies the operator, and pushes the result.

Binary tree: each node has at most two children; the root has no parent and leaves have none. BST property: left subtree < node < right subtree; inorder traversal yields sorted order.

DBMS advantages over files: controlled redundancy, shared data, integrity constraints, concurrency control, backup and recovery, and security. Schema is the structure; an instance is data at a moment.

Keys: a super key uniquely identifies tuples; candidate keys are minimal super keys; the primary key is the chosen candidate key (unique, not NULL); alternate keys are unchosen candidates; a foreign key references another relation's key.

Relational terms: relation=table, tuple=row, attribute=column, domain=allowed values. Degree is the number of attributes; cardinality is the number of tuples.

Entity integrity: primary key cannot be NULL. Referential integrity: a foreign key must match an existing referenced key or be NULL. Domain constraints restrict attribute values.

Normal forms: 1NF has atomic attributes; 2NF is 1NF with no partial dependency on part of a candidate key; 3NF is 2NF with no transitive dependency; BCNF requires every determinant to be a candidate key.

SQL DDL: CREATE, ALTER, DROP, TRUNCATE. DML: SELECT, INSERT, UPDATE, DELETE. DCL: GRANT, REVOKE. TCL: COMMIT, ROLLBACK, SAVEPOINT.

SELECT query order: SELECT ... FROM ... WHERE ... GROUP BY ... HAVING ... ORDER BY. WHERE filters rows before grouping; HAVING filters groups after aggregation.

INNER JOIN returns matching rows; LEFT or RIGHT OUTER JOIN keeps all rows from one side; FULL OUTER JOIN keeps both; CROSS JOIN produces the Cartesian product.

Aggregate functions COUNT, SUM, AVG, MIN, and MAX ignore NULL, while COUNT(*) counts rows. Test NULL with IS NULL or IS NOT NULL, never with = NULL.

Network scope: PAN (personal), LAN (building or campus), MAN (city), WAN (countries). Topologies include bus, star, ring, mesh, and tree; a star depends on a central switch.

OSI layers bottom-up: Physical, Data Link, Network, Transport, Session, Presentation, Application. TCP/IP model: Network Access, Internet, Transport, Application.

TCP is connection-oriented and reliable, using acknowledgements, retransmission, and ordering; UDP is connectionless and unreliable with less overhead. IP provides addressing and best-effort delivery.

IPv4 is 32-bit dotted decimal; IPv6 is 128-bit hexadecimal. Private IPv4 ranges: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16; loopback is 127.0.0.1.

A subnet mask or CIDR prefix /n separates network and host bits; the default gateway is the router address used to reach other networks.

Guided media: twisted pair, coaxial cable, optical fiber. Unguided media: radio, microwave, infrared. Fiber has high bandwidth and immunity to electromagnetic interference.

Common protocols: HTTP/HTTPS for web, FTP for file transfer, SMTP for sending mail, POP3/IMAP for retrieving mail, DNS for name-to-IP resolution, DHCP for automatic IP configuration.

Devices by layer: hub (physical, broadcasts), switch (data link, MAC forwarding), router (network, IP forwarding). MAC addresses are 48-bit; IP addresses are logical.

Bandwidth is maximum capacity; throughput is actual rate; latency is delay. Circuit switching reserves a path; packet switching routes independent packets and is typical of the Internet.

HTML document skeleton: , , for metadata, title, and links, and for visible content. Most elements have a start tag, content, and end tag.

Text tags: headings

, line break
, horizontal rule

Lists:

unordered,
ordered with type and start attributes,
1. items; definition list with term and description.

Links: label. Absolute URLs include scheme and host; relative URLs resolve against the current document. target='_blank' opens a new tab; mailto: starts email.

Images: . JPEG suits photos, PNG supports transparency, GIF supports simple animation, and SVG is scalable vector graphics.

Tables:

Forms:

CSS can be inline (style attribute), internal (

CSS box model: content, padding, border, margin. Multimedia combines text, graphics, audio, video, and animation; sampling rate and bit depth affect audio quality, and frame rate affects video.