Data Structures and Algorithm, Database System and Operating System

1

A data structure is a way of organising and storing data for efficient access and modification. An Abstract Data Type (ADT) defines operations without specifying implementation — e.g., Stack ADT defines push/pop without saying how they're implemented.

2

Asymptotic Notation: Big-O (O) = upper bound / worst case (e.g., O(n²) means at most n² operations). Big-Omega (Ω) = lower bound / best case. Big-Theta (Θ) = tight bound / exact growth rate (both upper and lower).

3

Stack = LIFO (Last In, First Out). Operations: push (add to top), pop (remove from top), peek (view top). Uses: function call stack, undo operations, infix-to-postfix conversion, postfix evaluation, recursion, backtracking. One end (top) is active.

4

Queue = FIFO (First In, First Out). Operations: enqueue (add to rear), dequeue (remove from front). Uses: CPU scheduling, printer spooler, buffering, BFS traversal. Two ends: front (remove) and rear (insert).

5

Expression Notation: Infix (A+B) — operator between operands, used by humans. Postfix / RPN (AB+) — operator after operands, used by calculators/compilers. Prefix / Polish (+AB) — operator before operands. Stacks are used to convert infix→postfix and evaluate postfix.

6

Linked List — a dynamic data structure where nodes are connected by pointers; stored in non-contiguous memory. Types: Singly (each node has one pointer → next), Doubly (pointers to both next and previous), Circular (last node points back to first). Advantage: dynamic size, easy insertion/deletion. Disadvantage: no random access — O(n) search, unlike arrays.

7

Binary Tree — hierarchical structure where each node has at most 2 children. BST (Binary Search Tree): left child < root < right child. Enables efficient search, insert, delete in O(log n) for balanced trees. Height = longest path from root to a leaf.

8

Tree Traversals: In-order (L-Root-R) — for BST, gives sorted ascending order. Pre-order (Root-L-R) — used to copy a tree. Post-order (L-R-Root) — used to delete a tree or evaluate expressions.

9

AVL Tree — a self-balancing BST where the balance factor (height of left subtree − height of right subtree) is at most ±1. Auto-rebalances via rotations after insert/delete, maintaining O(log n) operations. Named after Adelson-Velsky and Landis.

10

Arrays provide O(1) random access by index (direct computation of memory address). Linked lists require O(n) traversal for access. Arrays have fixed size; linked lists are dynamic.

1

Sorting Algorithm Complexities: Bubble / Insertion / Selection sort — O(n²) average and worst case; simple but slow for large datasets. Merge sort — O(n log n), stable, needs extra O(n) space. Quick sort — O(n log n) average, O(n²) worst case (bad pivot). Heap sort — O(n log n), in-place, uses a max-heap.

2

Stable sort preserves the relative order of equal keys — Merge sort and Insertion sort are stable. Quick sort and Heap sort are NOT stable by default. Internal sort = data fits in RAM. External sort = data too large, must use disk (e.g., external merge sort).

3

Linear Search: checks each element sequentially. O(n) time. Works on unsorted data. Simple but inefficient for large datasets. Binary Search: repeatedly halves a sorted list to find the target. O(log n) time. Requires sorted data — cannot be used on unsorted lists.

4

Hashing maps keys to array indices via a hash function. Average O(1) lookup, insert, delete. A well-designed hash function distributes keys uniformly. Collision occurs when two different keys hash to the same index. Resolution: Chaining (linked list at each bucket) or Open Addressing (probe for another slot — linear, quadratic, double hashing).

5

Graph — a set of vertices (V) connected by edges (E). Directed graph (digraph): edges have direction. Undirected graph: edges are bidirectional. Weighted graph: edges have associated costs/weights.

6

Graph Representations: Adjacency Matrix — V×V boolean matrix; O(V²) space, O(1) edge lookup. Adjacency List — list of neighbors per vertex; efficient for sparse graphs, O(V+E) space.

7

BFS (Breadth-First Search): explores level by level using a QUEUE. Finds shortest path in unweighted graphs. Time: O(V+E). DFS (Depth-First Search): explores as deep as possible using a STACK or recursion. Used for cycle detection, topological sort. Time: O(V+E).

8

Minimum Spanning Tree (MST): a spanning tree with minimum total edge weight. Prim's algorithm — grows MST from a starting vertex (greedy). Kruskal's algorithm — adds edges in increasing weight order, skipping those that form cycles (uses Union-Find). Both are greedy algorithms.

9

Dijkstra's Algorithm — finds single-source shortest paths in a weighted graph with non-negative weights. Greedy approach using a priority queue. O((V+E) log V). Warshall's Algorithm — computes transitive closure (reachability between all pairs of vertices). Related: Floyd-Warshall for all-pairs shortest paths.

10

Topological Sort — orders vertices of a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Used for dependency resolution, build systems, course scheduling.

1

A database is an organised collection of related data. A DBMS (Database Management System) provides data abstraction, independence, security, concurrent access, and recovery. Examples: MySQL, PostgreSQL, Oracle, MS SQL Server.

2

Data Independence: Logical data independence — changing the schema doesn't require changes to application programs. Physical data independence — changing storage structure doesn't affect the logical schema. Schema = the structure/design (stable); Instance = the actual data at a point in time (changes constantly).

3

E-R Model: entities (real-world objects), attributes (properties of entities), relationships (associations between entities). Strong entity has its own primary key. Weak entity has no primary key and depends on a strong entity (identified by its owner entity's key plus a partial key).

4

Keys: Primary key — uniquely identifies each row, cannot be NULL. Candidate key — any minimal set of attributes that uniquely identifies a row (primary key is chosen from candidates). Foreign key — references the primary key of another table (enforces referential integrity). Super key — any set of attributes that uniquely identifies a row (may not be minimal).

5

Normalization reduces data redundancy and prevents update/insert/delete anomalies by organizing data into well-structured tables. 1NF — all attribute values are atomic (indivisible), no repeating groups. 2NF — 1NF + no partial dependency (every non-key attribute depends on the whole composite key). 3NF — 2NF + no transitive dependency (non-key attribute does NOT depend on another non-key attribute). BCNF — stronger 3NF: every determinant must be a candidate key.

6

Functional Dependency (A → B): attribute B is functionally determined by attribute A — for each value of A, there is exactly one value of B. This is the basis for normalization.

7

SQL Categories: DDL (Data Definition Language) — CREATE, ALTER, DROP, TRUNCATE (defines schema). DML (Data Manipulation Language) — SELECT, INSERT, UPDATE, DELETE (manipulates data). DCL (Data Control Language) — GRANT, REVOKE (controls permissions). TCL (Transaction Control Language) — COMMIT, ROLLBACK, SAVEPOINT (manages transactions).

8

Relational Algebra operations: Select (σ) — filters rows (horizontal). Project (π) — selects columns (vertical). Join (⋈) — combines rows from two tables. Union, Intersection, Difference — set operations on compatible tables.

9

View = a virtual table defined by a stored query — presents a customized view of data without storing it separately. Trigger = code that auto-executes in response to an event (INSERT, UPDATE, DELETE) on a table.

10

Indexes speed up data retrieval at the cost of storage and slower writes. A clustered index determines physical data order; a non-clustered index is a separate structure. Primary keys automatically have a clustered index.

1

A transaction is a logical unit of work — a sequence of database operations that must execute completely or not at all. Transactions provide reliability in the face of system failures and concurrent access.

2

ACID Properties — the four guarantees of a reliable transaction: Atomicity (all operations succeed, or none do — all-or-nothing), Consistency (transaction takes the DB from one valid state to another), Isolation (concurrent transactions don't interfere with each other), Durability (once committed, changes survive crashes permanently).

3

Serializability — the correctness criterion for concurrent transaction schedules. A concurrent schedule is correct if it produces the same result as some serial (sequential) execution of the same transactions. Ensures transactions don't corrupt each other's data.

4

Lock-based Concurrency Control: Shared (read) lock — multiple transactions can hold concurrently for reading. Exclusive (write) lock — only one transaction at a time, for writing. Two-Phase Locking (2PL) ensures serializability: Growing phase (acquire locks, release none) → Shrinking phase (release locks, acquire none).

5

Deadlock — occurs when two or more transactions each hold a lock the other needs, causing circular waiting. Handling strategies: Prevention (impose lock ordering), Avoidance (use wait-die or wound-wait protocols), Detection & Recovery (detect cycles in wait-for graph and abort a victim transaction).

6

Failure Types: Transaction failure (logic error, constraint violation), System crash (OS/hardware failure — volatile memory lost, disk intact), Disk failure (physical disk damage — most severe).

7

Log-based Recovery: all changes are first written to a log (write-ahead logging — WAL) before modifying the database. Recovery uses: UNDO — rolls back uncommitted transactions (incomplete at crash time). REDO — reapplies committed transactions that hadn't been flushed to disk at crash time.

8

Checkpoint — a point where the DBMS flushes all modified buffers to disk and records which transactions are active. On recovery, only transactions active at the last checkpoint need to be considered, reducing recovery time.

9

Commit and Rollback: COMMIT makes a transaction's changes permanent. ROLLBACK undoes all changes since the last commit or savepoint. These are TCL (Transaction Control Language) commands.

10

Starvation vs Deadlock: Starvation = a transaction waits indefinitely because others keep getting priority (livelock). Deadlock = circular wait where no transaction can proceed without the other releasing resources.

1

An Operating System (OS) is system software that manages hardware and software resources and provides services to application programs. It acts as an intermediary between users and hardware. Services: process management, memory management, file system, I/O management, security, networking.

2

OS Types: Batch OS (jobs submitted in batches, no user interaction). Time-sharing OS (multiple users share CPU via time slices). Multiprogramming OS (multiple programs in memory simultaneously). Multiprocessing OS (multiple CPUs). Real-time OS (strict timing guarantees — medical, industrial). Distributed OS (multiple computers act as one).

3

Kernel = the core of the OS that manages processes, memory, and devices. Always runs in privileged mode. System call = the interface through which application programs request OS services (e.g., open file, allocate memory). Separates user space from kernel space.

4

Process = a program in execution (active, has memory, state, and resources). A program is static (code on disk); a process is dynamic (running instance). PCB (Process Control Block) stores all process information: PID, state, program counter, CPU registers, memory maps, open files.

5

Process States: New (being created) → Ready (waiting for CPU) → Running (executing on CPU) → Waiting/Blocked (waiting for I/O or event) → Terminated (finished). A process moves between states based on scheduling and I/O events.

6

Thread = a lightweight unit of execution within a process. Threads of the same process share code segment, data segment, and heap, but each has its own stack and registers. Multithreading improves responsiveness and resource utilization.

7

CPU Scheduling Algorithms: FCFS (First Come First Served) — non-preemptive, simple, suffers from convoy effect (short jobs wait behind long ones). SJF (Shortest Job First) — optimal for minimum average waiting time, but requires knowing burst times. Round Robin (RR) — preemptive, each process gets a time quantum, good for time-sharing. Priority Scheduling — highest priority runs first, risk of starvation for low-priority processes.

8

Critical Section — a code segment that accesses shared resources and must not be executed by more than one process simultaneously. Requires mutual exclusion. Race Condition — a bug where the outcome depends on the timing/order of concurrent accesses to shared data.

9

Semaphore — an integer variable used for synchronization. Wait (P/down): decrement; if < 0, block. Signal (V/up): increment; if ≤ 0, wake a blocked process. Mutex = a binary semaphore providing mutual exclusion (locked/unlocked).

10

Classic Synchronization Problems: Producer-Consumer (bounded buffer), Readers-Writers (multiple readers OK, only one writer), Dining Philosophers (5 philosophers, 5 forks — illustrates deadlock and starvation). All solved using semaphores or monitors.

1

Memory Management allocates and tracks main memory (RAM) used by processes. Goals: maximize utilization, provide each process with its own address space, enable sharing where needed. Techniques: contiguous allocation, paging, segmentation.

2

Swapping — moves an entire process between main memory and a swap space on disk to free RAM for other processes. Swapped out = moved to disk; Swapped in = loaded back to memory. Slow due to disk I/O.

3

Paging — divides logical memory into fixed-size pages and physical memory into same-size frames. The OS maintains a page table mapping logical pages to physical frames. Eliminates external fragmentation completely. Only internal fragmentation may occur (last page may not be full).

4

Segmentation — divides memory into variable-size logical segments (code, stack, heap, data). More natural (matches programmer's view) but suffers from external fragmentation. Can combine with paging (paged segmentation).

5

Virtual Memory — allows processes to use more memory than physically available by keeping only active pages in RAM and the rest on disk. Implemented via demand paging (pages loaded only when accessed — on page fault).

6

Page Fault — occurs when the process accesses a page not currently in physical memory. The OS suspends the process, loads the page from disk, updates the page table, and resumes the process. Frequent page faults → thrashing (system spends more time paging than executing).

7

Page Replacement Algorithms: FIFO — replace the oldest loaded page (simple but can suffer Belady's anomaly: more frames → more faults). LRU (Least Recently Used) — replace the page not used for the longest time (good approximation of optimal). Optimal (OPT) — replace the page not needed for the longest future time (theoretically best, requires future knowledge — used as benchmark).

8

Fragmentation: Internal fragmentation — wasted space inside an allocated block (e.g., allocating 8KB block for 6KB process wastes 2KB). Occurs in paging/fixed partitioning. External fragmentation — free memory exists but is scattered in small non-contiguous gaps. Occurs in variable-size allocation. Fixed by compaction (moving processes to consolidate free space) or paging.

9

File System — organizes files and directories on storage. A file is a named collection of related data. A directory (folder) organizes files hierarchically. File attributes: name, type, size, location, owner, timestamps.

10

File Allocation Methods: Contiguous — file occupies consecutive disk blocks; fast access but external fragmentation and hard to grow. Linked — each block points to the next; no fragmentation but no random access. Indexed — index block holds pointers to all data blocks; efficient random access, supports files of varying sizes. Used in UNIX (inode). System Administration: user account management, backups, security, monitoring, start-up/shutdown procedures.