Jin Hyun Park / Qual Exam Prep / Things to remember

Things to remember

Facts that did not fit anywhere else: programming languages, digital logic, memory management, and a little discrete math.

Compiler vs. interpreter

Compiler	Interpreter
Translates the whole program in one pass, before it runs	Translates and runs the program one statement at a time
Translation and execution are separate steps	Translation and execution are interleaved
Higher memory use during compilation	Lower memory use
Reports all errors at once, before running anything	Reports each error when it reaches that line
Example: C, C++	Example: Python

Instance methods vs. static methods

• A static method is declared with the static keyword and belongs to the class itself, so it can be called without creating an object.
• An instance method belongs to a particular object and is called on that object.
• Who can see what:
  • An instance method can use instance methods and variables (it has a this).
  • An instance method can also use static methods and variables.
  • A static method can use static methods and variables.
  • A static method cannot use instance methods or variables directly, because there is no particular object for them to belong to.

Call stack

• A region of RAM, managed by the runtime, that grows and shrinks as functions are called and return.
• It is what makes function calls work: it records where to return to and holds each call's parameters and local variables.
• For garbage collection, the local variables on the call stack are part of the root set: anything reachable from them is alive.

What happens on a procedure call

• What always happens: the program counter changes to the address of the called procedure, and the return address (where to continue after the call) is saved somewhere.
• On most machines the return address is pushed onto the stack, so the stack pointer changes as well. On RISC machines such as MIPS, ARM, or RISC-V, the call instruction instead writes the return address into a link register, and a leaf procedure may never touch the stack at all.
• The stack pointer register keeps track of how far the stack currently extends, so that data can be pushed and popped. When a procedure returns, the stack pointer is moved back by one frame.

Stack frame

• A stack frame is the block of data pushed onto the call stack for one function call.
• In the usual layout the caller pushes the arguments first, then the call instruction pushes the return address, then the callee saves the caller's frame pointer and reserves space for its local variables. Together they make up the frame. That is why arguments sit at positive offsets from the frame pointer and locals at negative offsets.
• The frame is created when the function is called and discarded when the function returns, which is why local variables do not outlive the call.

Functional completeness

A set of logic gates is functionally complete if every Boolean function can be built from it. Each of the following sets is complete:

• {NOT, AND}
• {NOT, OR}
• NAND alone, and NOR alone.
• {XOR, AND, 1} and {XOR, OR, 1}, i.e. XOR with AND or OR plus the constant 1, since NOT x = x ⊕ 1.
• Watch out: {XOR, AND} and {XOR, OR} on their own are not complete. Every one of those gates outputs 0 when all inputs are 0, so any circuit built from them does too, and NOT can never be produced. Exam answer keys that list them as complete are assuming the constant 1 is available.

Sequential vs. combinational circuits

• A combinational circuit's output depends only on its current inputs. Adders, comparators, decoders, and multiplexers are combinational; they do arithmetic, logic, and routing.
• A sequential circuit has memory: its output depends on the current inputs and on its state. Flip-flops, registers, and counters are sequential.
• Decoder: takes an n-bit input and activates exactly one of 2ⁿ output lines. One input, many outputs; it routes a signal to the right line.
• Multiplexer (MUX): the opposite. Takes 2ⁿ data inputs and an n-bit select signal, and passes the selected input through to the single output. Many inputs, one output.

DMA (direct memory access)

• Lets an I/O device transfer data to or from main memory on its own, without the CPU copying every word. The CPU sets up the transfer, goes off to do other work, and gets an interrupt when the transfer is done.

Distributed systems

• A collection of independent computers that appears to its users as a single system.
• Why bother: (1) one machine's resources are limited, (2) the system can keep working when one machine fails, (3) resources can be shared and reached conveniently from anywhere.

Symmetric difference

• A △ B is the set of elements that are in A or in B but not in both. In the Venn diagram it is everything except the overlap.

Static (lexical) scoping vs. dynamic scoping

• With static (lexical) scoping, a name refers to whatever it referred to where the function was written. You can resolve every name by reading the source code. Almost every modern language does this.
• With dynamic scoping, a name refers to the most recent binding on the call stack, i.e. it depends on who called the function. The same function can see different variables depending on where it was called from.

Direct vs. indirect representation

• Direct representation: the variable's data is stored inline, for example on the stack. Accessing a component is fast because there is no pointer to follow.
• Indirect representation: the variable holds a pointer to data that lives elsewhere, for example on the heap. Slightly slower to access, but more flexible.
• One practical benefit of indirection: if the size of some private part of a data type changes, code that only holds a pointer does not need to be recompiled, so fewer source modules are affected.

Ripple-carry adder

• k full adders in a row, each waiting for the carry from the one before it. The carry "ripples" along the chain, so the total delay grows linearly with the number of bits.
• Time until the last sum bit is ready: T_c × (k − 1) + T_s, where T_c is the delay of one carry output and T_s is the delay of a sum output. The final carry-out is ready at k × T_c. Either way the delay is linear in k, which is why faster adders (carry-lookahead) exist.

Semi-space copying collection

• The heap is split into two halves, "from-space" and "to-space". New objects are allocated in from-space by bumping a pointer.
• When from-space fills up, the collector starts at the roots and copies every reachable object into to-space, packed tightly together. Whatever is left behind in from-space is garbage and is simply abandoned. Then the two halves swap roles.
• Because live objects are copied contiguously, there is no fragmentation. The cost is that only half of the heap is usable at any time.

Church–Turing thesis

Also called Church's thesis, Church's conjecture, or Turing's thesis.

• It states that anything that can be computed by a mechanical procedure can be computed by a Turing machine. In other words, every effective algorithm can be run on a Turing machine.
• It is a thesis, not a theorem: "mechanical procedure" is an informal notion, so the claim cannot be proved, only supported by evidence.

Master theorem

• A formula for solving recurrences of the form T(n) = a·T(n/b) + f(n), which is the shape that divide-and-conquer algorithms produce. Compare f(n) with n^{log_b a} and the theorem tells you the running time directly, without unrolling the recursion.

Raymond's tree-based algorithm

• A token-based mutual exclusion algorithm for distributed systems: the processes are arranged in a tree and requests for the token travel toward whoever holds it.
• It guarantees freedom from both deadlock and starvation: each node keeps a FIFO queue of requests, so every request is eventually served. What it does not guarantee is fairness in the sense of serving requests in the global order they were issued.

The four principles of object-oriented programming

• Encapsulation: bundle data and the methods that operate on it into a class, and hide the internals.
• Inheritance: a subclass reuses and extends the behavior of its superclass.
• Abstraction: define common attributes and behavior once, in a general class or interface. This reduces duplication, makes the relationships between classes clearer, and makes maintenance easier.
• Polymorphism: the same call can behave differently depending on the object. Method overloading and overriding are the usual examples.

Distributing quantifiers over "or"

• (∀x P(x)) ∨ (∀x Q(x)) implies ∀x (P(x) ∨ Q(x)), but not the other way round. If everything is P or everything is Q, then certainly each thing is P or Q; but "each thing is P or Q" does not mean they are all the same one.
• (∃x P(x)) ∨ (∃x Q(x)) is actually equivalent to ∃x (P(x) ∨ Q(x)). The original note listed only the left-to-right direction; for the existential quantifier both directions hold.

1's complement vs. 2's complement

• 1's complement: flip every bit. The 1's complement of 0011 is 1100.
• 2's complement: flip every bit, then add 1. This is how computers represent negative integers, and the most significant bit acts as the sign (0 = positive, 1 = negative).
  • Example: to negate 0010 (decimal 2), flip the bits to get 1101, then add 1 to get 1110. So 1110 is −2 in 4-bit two's complement.
  • Check: 0010 + 1110 = 10000. The fifth bit is discarded because we only have 4 bits, leaving 0000. So 2 + (−2) = 0, as it should.
• The advantage of 2's complement over 1's complement is that there is only one zero and addition works with no special cases.

Logic vocabulary

• Tautology: true under every assignment of truth values (A ∨ ¬A).
• Contradiction: false under every assignment (A ∧ ¬A).
• Contingency: true under some assignments and false under others, i.e. neither a tautology nor a contradiction (A ∧ B).
• Satisfiable: true under at least one assignment. Every tautology and every contingency is satisfiable; a contradiction is not.

Static allocation vs. stack allocation

• Static allocation: every variable gets a fixed address at compile time. Simple and fast, but data structures cannot be created dynamically and recursion is impossible, because each call would need its own copy of the locals.
• Stack allocation: locals are allocated in a stack frame at call time. Each call gets fresh storage, so recursive procedures work.

Garbage collection

• Reference counting
  • Each object keeps a count of how many references point to it. A smart pointer, for example, increments the count when it is copied and decrements it when it is destroyed; when the count reaches 0 the object is freed immediately.
  • Downsides: maintaining the counts adds overhead to every pointer assignment, and two objects that point at each other in a cycle never reach 0 even when nothing else can reach them, which leaks memory.
• Mark and sweep
  • Mark: start from the GC roots (globals, the call stack, registers) and mark every object that can be reached by following pointers.
  • Sweep: walk the whole heap and free everything that was not marked.
  • Handles cycles correctly, since an unreachable cycle is never marked. The downside is fragmentation: freed objects leave holes scattered through the heap.
• Stop the world
  • While the collector is figuring out which objects are alive, the application threads have to pause; otherwise they could change the object graph under the collector's feet.
  • That pause is called a "stop-the-world" pause, and keeping it short is one of the main goals of modern collector design.

Overview · Useful materials · Sample questions · Algorithms · Architecture · OS · Networking · Databases · Automata · AI / ML