Analysis and Design of Algorithm, and Programming (System and Network)

1

An algorithm is a finite, well-defined sequence of steps that transforms given input into the desired output to solve a problem.

2

Five defining properties of an algorithm: Finiteness (must terminate after a finite number of steps), Definiteness (each step must be precisely and unambiguously defined), Input (zero or more well-defined inputs), Output (one or more well-defined outputs related to the input), and Effectiveness (each step must be basic enough to be carried out exactly, in principle by hand).

3

The RAM (Random Access Machine) model is the idealized computer used to analyze algorithms: every elementary operation (arithmetic, comparison, memory access) is assumed to take a constant amount of time, O(1).

4

Best case: the minimum running time over all inputs of a given size — e.g. an already-sorted array for Insertion Sort, giving O(n).

5

Worst case: the maximum running time over all inputs of a given size — the usual guarantee quoted for an algorithm — e.g. a reverse-sorted array for Insertion Sort, giving O(n^2).

6

Average case: the expected running time, averaged over all possible inputs of a given size (assuming some input distribution).

7

Time complexity measures how running time grows with input size n; space complexity measures how much extra memory the algorithm uses as a function of n.

8

Big-O, O(f(n)) — upper bound: the algorithm's running time grows no faster than f(n) — commonly used to describe the worst case.

9

Big-Omega, Ω(f(n)) — lower bound: the algorithm's running time grows at least as fast as f(n) — commonly used to describe the best case.

10

Big-Theta, Θ(f(n)) — tight bound: the running time grows exactly as fast as f(n), i.e. it is bounded both above and below by f(n).

11

A recurrence relation expresses a function's value (typically the running time of a recursive algorithm) in terms of its value on smaller inputs — e.g. Merge Sort's running time is described by T(n) = 2T(n/2) + n.

12

Recursion Tree Method — draws the recursive calls as a tree, computes the cost at each level, and sums the costs across all levels to obtain the total running time.

13

Substitution Method — guesses a closed-form solution for the recurrence, then proves the guess correct (and finds any constants) using mathematical induction.

14

Master's Theorem — a direct 'cookbook' method for recurrences of the form T(n) = aT(n/b) + f(n) (a ≥ 1, b > 1), comparing f(n) against n^(log_b a). Case 1: f(n) = O(n^(log_b a - ε)) gives T(n) = Θ(n^(log_b a)). Case 2: f(n) = Θ(n^(log_b a)) gives T(n) = Θ(n^(log_b a) · log n). Case 3: f(n) = Ω(n^(log_b a + ε)) with the regularity condition holding gives T(n) = Θ(f(n)).

1

The divide-and-conquer strategy solves a problem in three steps: Divide the problem into smaller subproblems of the same type, Conquer each subproblem recursively (solving it directly once small enough), and Combine the subproblem solutions into the solution for the original problem.

2

Binary Search repeatedly halves the search interval of a sorted array, comparing the target with the middle element — running in O(log n) time.

3

The Min-Max algorithm finds both the minimum and maximum of a list using divide and conquer, requiring only about 3n/2 comparisons overall, versus about `2n` comparisons for a naive linear scan that finds min and max separately.

4

Merge Sort: O(n log n) in best, average, and worst case; O(n) extra space; stable; divides array in half, recursively sorts, then merges.

5

Quick Sort: best/average O(n log n); worst O(n^2); O(log n) space (recursion stack, in-place partitioning); NOT stable; performance depends heavily on pivot choice.

6

Randomized Quick Sort: expected O(n log n), O(log n) space; picks pivot randomly, avoiding the worst case on already-sorted/adversarial input with high probability.

7

Quick Sort's worst case O(n^2) occurs when the pivot repeatedly splits the array very unevenly (e.g. a sorted array with a fixed first/last-element pivot); its best/average case O(n log n) occurs when the pivot roughly balances the two partitions each time.

8

A heap is a complete binary tree satisfying the heap property: in a Max-Heap, every parent node is ≥ its children; in a Min-Heap, every parent node is ≤ its children.

9

Heap Sort first builds a heap from the input in O(n), then repeatedly removes the root (the max/min) and re-heapifies (O(log n) per removal), giving an overall time complexity of O(n log n); it sorts in-place, needing only `O(1)` extra space.

10

The i-th order statistic of a set is its i-th smallest element; the median is the middle order statistic (or the average of the two middle elements for even-sized sets).

11

Brute-force selection — sort the entire list, then read off the i-th element directly: O(n log n) time.

12

Selection in expected linear time — a randomized selection algorithm (similar in spirit to Quick Sort's partitioning) that finds the i-th order statistic in expected O(n) time.

13

Selection in worst-case linear time — the Median-of-Medians algorithm guarantees the i-th order statistic can be found in worst-case `O(n)` time, by carefully choosing a pivot that is guaranteed to give a good split.

1

Dynamic Programming (DP) solves a problem by breaking it into overlapping subproblems, solving each subproblem only once, and storing (memoizing/tabulating) its result for reuse.

2

DP is applicable whenever a problem exhibits **optimal substructure** (an optimal solution is built from optimal solutions to subproblems) AND **overlapping subproblems** (the same subproblems recur many times).

3

Greedy algorithm: makes the locally optimal choice at each step, without reconsidering it — fast, low memory, but does NOT guarantee a globally optimal solution for every problem.

4

Dynamic Programming explores multiple choices and combines optimal solutions of subproblems, guaranteeing an optimal solution whenever the problem has optimal substructure, at the cost of more time/memory.

5

Plain recursion may recompute the same subproblem many times — often exponential time; DP stores subproblem results (memoization: top-down, or tabulation: bottom-up), avoiding recomputation.

6

Elements of the DP approach: identify optimal substructure, identify overlapping subproblems, and build a memoization/DP table to store and reuse subproblem results.

7

Matrix Chain Multiplication: finds the optimal order to multiply a chain of matrices, minimizing the total number of scalar multiplications — O(n^3) time, O(n^2) space.

8

String Editing (Edit Distance): finds the minimum number of insertions, deletions, and replacements to convert one string into another — O(mn) time and space, for strings of length m and n.

9

0/1 Knapsack: maximizes total value of selected items without exceeding a weight capacity W, each item used at most once — O(nW) time and space.

10

Floyd-Warshall: finds shortest paths between every pair of vertices in a weighted graph (handles negative edge weights, NOT negative cycles) — O(V^3) time, O(V^2) space.

11

Travelling Salesman Problem (TSP, DP/bitmask): finds the minimum-cost tour visiting every city exactly once and returning to the start — O(n^2 · 2^n) with DP (Held-Karp), versus O(n!) for brute force.

12

Memoization is the top-down DP technique of caching the results of expensive function calls in a table, keyed by their inputs, and returning the cached result immediately whenever the same inputs recur — turning an exponential-time recursive solution into a polynomial-time one.

1

A loader is system software that takes an object/executable program and prepares it for execution: it performs allocation (reserving memory), linking (resolving references between modules), relocation (adjusting addresses), and loading (placing the program into memory).

2

Absolute Loader — the simplest type; the program is always assembled and loaded at one fixed, predetermined address. Fast and simple but inflexible: no relocation is possible, and the programmer/assembler must manage absolute addresses.

3

Bootstrap Loader — a small program, often stored permanently in ROM, that runs automatically when a machine starts and loads a larger program (e.g. the operating system) into memory.

4

Relocation adjusts all address-dependent locations in a program so it can be loaded and correctly executed at a memory location different from the one originally assumed at assembly time.

5

Program Linking combines two or more separately assembled object programs, resolving external references between them (a symbol defined in one module and used in another).

6

A linking loader's algorithm and data structures typically use two passes: Pass 1 assigns addresses to all external symbols (building an External Symbol Table, ESTAB); Pass 2 performs the actual loading, relocation, and linking using that table.

7

Automatic Library Search — the loader automatically searches designated libraries for any routines needed to resolve external references that the program itself does not define, and includes them automatically.

8

Loader Options let the user control the loading process, e.g. specifying the library search order, an alternate program entry point, or which optional modules to include.

9

A Linkage Editor performs linking before execution time, producing a single linked executable that is stored and can be loaded (and re-loaded) directly without relinking each run — saves relinking time on repeated runs, but duplicates library code in every linked executable, using more disk space.

10

Dynamic Linking postpones linking of external references (e.g. shared library routines) until load time or run time — loads/links a routine only when it is actually called/needed, saving memory and disk space by sharing one copy of a library among many programs.

11

MS-DOS Linker — combines .OBJ files produced by the assembler/compiler into a single .EXE (or .COM) executable file.

12

SunOS Linker — a Unix-based linker supporting dynamic linking through shared objects (.so files), allowing multiple programs to share one loaded copy of a library.

1

A macro is a named block of source code, usually delimited by directives such as MACRO ... MEND, that can accept parameters and be invoked (called) elsewhere in the program.

2

Macro expansion is the process of replacing a macro invocation with the macro's defined body, substituting the actual argument values for its formal parameters, at the point of the call.

3

Macro Name Table (MNT) — lists the names of all defined macros, along with a pointer to where each macro's definition is stored.

4

Macro Definition Table (MDT) — stores the actual body/text of each macro definition.

5

Argument List Array (ALA) — holds the actual argument values supplied at a macro call, used to substitute the formal parameters during expansion.

6

Concatenation of macro parameters — combines a parameter with surrounding characters to build a new identifier (e.g. joining &PARAM with a suffix to form a new variable/label name).

7

Generation of unique labels — automatically produces a distinct label for each macro expansion (e.g. by appending an incrementing counter, such as AA0001, AA0002, ...) to avoid duplicate-label errors when a macro containing a label is expanded more than once.

8

Conditional macro expansion — uses directives similar to IF / ELSE / ENDIF inside a macro body to control which statements are actually generated, based on given conditions.

9

Keyword macro parameters — parameters referenced by name (e.g. PARAM=value) instead of by position, allowing arguments to be supplied in any order and to have default values.

10

Recursive macro expansion — allows a macro to call/expand other macros, including (with appropriate termination conditions) itself.

11

A general-purpose macro processor operates independently of any specific programming language, since macro processing is fundamentally textual substitution. A macro processor combined with a language translator is instead integrated directly into the assembler/compiler, expanding macros line-by-line as source code is read and translated.

12

MASM (Microsoft Macro Assembler) includes its own built-in macro processor for x86 assembly language programming; the ANSI C macro language is implemented by the C preprocessor, using directives such as #define and #ifdef to perform textual substitution before the source code is actually compiled.

1

TCP: connection-oriented, reliable & ordered — establishes a connection (3-way handshake) before sending a byte stream.

2

IP: connectionless, unreliable (best-effort) — handles logical addressing and routing of packets between networks.

3

UDP: connectionless, unreliable & unordered — very low overhead; used where speed matters more than guaranteed delivery.

4

SCTP: connection-oriented, reliable & message-oriented — supports multi-streaming and multi-homing, combining strengths of TCP and UDP.

5

TCP's connection lifecycle: CLOSED → LISTEN/SYN_SENT → SYN_RCVD → ESTABLISHED (via the 3-way handshake: SYN, SYN-ACK, ACK), then FIN_WAIT/CLOSE_WAIT → TIME_WAIT → CLOSED during connection teardown (a 4-way exchange of FIN/ACK segments).

6

A socket is an endpoint for network communication, identified by an IP address and port number; the UNIX (BSD) socket API and Winsock (Windows Sockets) provide largely equivalent functionality on their respective platforms.

7

A socket address structure (e.g. sockaddr_in for IPv4) holds the address family, port number, and IP address, and is used with calls such as bind() and connect().

8

Network byte order is standardized as big-endian; a host's own byte order may be big-endian or little-endian depending on its CPU architecture. htons()/htonl() convert a value from host to network byte order; ntohs()/ntohl() convert from network back to host byte order (for 16-bit and 32-bit values respectively).

9

Key socket system calls: socket() creates a new socket (returns a descriptor), bind() associates it with a local IP/port, listen() marks it passive/ready to accept connections, accept() accepts an incoming connection (returns a new socket), connect() initiates a connection (client-side), send()/recv() transfer data, and close() terminates the socket and releases its resources.

10

A concurrent server handles multiple clients at the same time, typically by forking a new process or spawning a new thread for each accepted connection — unlike an iterative server, which serves only one client at a time.

11

Five I/O models: Blocking I/O (the calling process blocks/waits until the operation completes), Non-blocking I/O (the call returns immediately even if not ready; the process must poll repeatedly), I/O Multiplexing (a single thread monitors multiple sockets via select()/poll()/epoll() and handles whichever becomes ready), Signal-driven I/O (the kernel sends a signal, e.g. SIGIO, to notify the process once I/O is ready), and Asynchronous I/O (the kernel performs the entire operation, including copying the data, and notifies the process only upon full completion — no blocking at all).

12

UNIX domain sockets provide inter-process communication (IPC) between processes on the same host, addressed via file-system paths; Internet domain sockets communicate across a network using IP addresses and ports.

13

Winsock (Windows Sockets) is implemented as a DLL (historically WINSOCK.DLL, now WS2_32.DLL for Winsock 2), providing a BSD-socket-compatible API on Windows; Windows Socket Extensions add Windows-specific capabilities beyond standard BSD sockets, such as asynchronous notification via window messages and overlapped I/O.