Computer Systems Foundations Final (Lecture Material)

What is the propagation latency for a packet traveling 100km through a fiber optic cable?

Latency: 0.5 ms.

What is the height of a B-Tree with a fanout of 100 for 1,000,000 items?

Height is approximately 3.

What is the 'BANG' quartet?

Bits, Atoms, Neurons, Genes.

What is the Von Neumann architecture?

A computer architecture consisting of a CPU (ALU + Registers), Memory, and I/O devices.

What is the range of values for an n-bit unsigned integer?

0 to 2^n - 1.

What is the range of values for an n-bit signed integer (Two's Complement)?

-(2^(n-1)) to 2^(n-1) - 1.

How do you compute the Two's Complement of a binary number?

Flip all bits and add 1 to the result.

What does a logical left shift (<<) do to a binary number's value?

Multiplies it by 2 for each position shifted.

What does a logical right shift (>>) do to an unsigned binary number?

Divides it by 2 for each position shifted.

What is the result of x AND 1?

It isolates the Least Significant Bit (LSB).

What is the result of x XOR x?

0 (Always).

What is the result of x XOR 0?

x (Identity).

What is a 'Mask' in bitwise operations?

A bit pattern used to select, set, or clear specific bits in another binary value.

How do you detect if the n-th bit of a variable flag is set?

if (flag & (1 << n) != 0).

What is the hexadecimal representation of binary 1111?

F (or 0xF).

What is Overflow in binary addition?

When the result of an arithmetic operation is too large to fit in the allocated number of bits.

What are the three basic Boolean operations?

AND, OR, NOT.

What logic gate is considered 'universal'?

NAND (or NOR).

In 0x10, what power of 16 does the 1 represent?

16^1 which is 16 in decimal.

What is the difference between Big-Endian and Little-Endian?

Big-Endian stores the MSB at the lowest memory address; Little-Endian stores the LSB at the lowest address.

What is a Clock Cycle?

The discrete time interval between two 'ticks' of the system clock.

Why is integer arithmetic modular?

Because computers have fixed word sizes, so values 'wrap around' upon overflow/underflow.

What is 0x a prefix for?

Hexadecimal literals (Base 16).

Convert Decimal 10 to Binary.

1010.

Convert Binary 101 to Decimal.

5.

What is the effect of x OR 1?

It forces the Least Significant Bit to 1.

What is the Memory Hierarchy (fastest to slowest)?

Registers → L1 Cache → L2/L3 Cache → Main Memory (RAM) → Disk/Storage.

What is a Data Flip-Flop (DFF)?

A sequential circuit that stores 1 bit of data based on a clock signal.

What is the difference between Combinational and Sequential logic?

Combinational logic output depends only on current inputs; Sequential logic output depends on inputs and previous state/time.

What is SRAM and where is it used?

Static RAM; fast, expensive, used for Cache.

What is DRAM and where is it used?

Dynamic RAM; slower, cheaper, used for Main Memory.

What is Temporal Locality?

If a memory location is accessed, it is likely to be accessed again soon.

What is Spatial Locality?

If a memory location is accessed, locations near it are likely to be accessed soon.

What is a Cache Hit?

When the CPU requests data and it is found in the cache.

What is a Cache Miss?

When the data is not in cache and must be fetched from a lower level.

What is a Direct Mapped Cache?

A cache where each memory address maps to exactly one specific line in the cache.

What is an N-way Set Associative Cache?

A cache divided into sets; a memory block can go into any line within its assigned set.

What is a Fully Associative Cache?

A memory block can be placed in any cache line.

What does 'Byte-Addressable' mean?

Each unique address in memory points to a single byte of data.

How many bits are required to address 64KB of memory?

16 bits.

What happens when an L1 cache miss occurs?

The request is passed down to L2, then L3, then Main Memory until data is found.

What is a Cache Line?

The unit of data transfer between memory and cache.

Why are L2/L3 caches slower than L1?

They are larger and physically further from the execution units.

What is 'Volatile' memory?

Memory that loses its data when power is turned off.

What is 'Non-Volatile' memory?

Memory that retains data without power.

Ideally, where should frequently accessed variables be stored?

In CPU Registers.

What is the purpose of the Program Counter (PC)?

A register that holds the address of the next instruction to be executed.

What is a Bus in computer architecture?

A shared communication channel for transferring data between components.

What is the 'Working Set' of a program?

The set of memory pages/data currently in use by a program.

How does the OS manage memory for multiple programs?

Using Virtual Memory.

What is the downside of a Direct Mapped cache?

Higher collision rate if two active variables map to the same line.

What are the 7 layers of the OSI model?

Physical, Data Link, Network, Transport, Session, Presentation, Application

What is Encapsulation?

Wrapping data with protocol headers as it moves down the network stack.

What is the unit of data at the Network Layer (Layer 3)?

Packet

What is the unit of data at the Data Link Layer (Layer 2)?

Frame

What is the main function of DNS?

Translating human-readable hostnames to IP addresses.

What is a Private IP Address?

An IP address used within a local network that is not routable on the public internet.

What does NAT stand for and what does it do?

Network Address Translation; it allows multiple devices on a private network to share a single public IP address.

What is TCP?

Transmission Control Protocol; a connection-oriented, reliable protocol.

What is UDP?

User Datagram Protocol; a connectionless, unreliable protocol.

What is a Socket?

An endpoint for communication defined by an IP address and a Port number.

What is the difference between a Client Socket and a ServerSocket?

A ServerSocket listens for incoming connections; a Client Socket initiates the connection.

What is Packet Switching?

Data is broken into chunks that travel independently through the network.

What is Circuit Switching?

A dedicated physical path is established for the duration of the connection.

What is Multiplexing?

Transmitting multiple signals over a single communication link simultaneously.

What is a Port Number?

A 16-bit number identifying a specific process or service on a host.

What is a CNAME record in DNS?

Canonical Name; maps an alias hostname to another hostname.

What is an A Record in DNS?

Maps a hostname directly to an IPv4 address.

What is Latency vs Bandwidth?

Latency is the time it takes for a message to travel; Bandwidth is the amount of data that can be transmitted per unit of time.

What is Manchester Encoding?

A signaling method where bits are represented by transitions rather than static voltage levels.

What is the 'Loopback' address?

127.0.0.1 (localhost)

What is the 'Root' of the DNS hierarchy?

The top-level servers that know the locations of TLD servers.

What does the Transport Layer manage?

End-to-end communication, reliability, and flow control.

What does the Network Layer manage?

Routing and logical addressing.

What is a Proxy Server?

An intermediary that acts on behalf of a client.

What is DHCP?

Dynamic Host Configuration Protocol; automatically assigns IP addresses to devices on a network.

What is a Stack Frame?

A section of the stack memory allocated for a single function call.

What data structure manages function calls?

The Stack (LIFO - Last In, First Out).

What happens to local variables when a function returns?

Their stack frame is popped/deallocated, and the data is lost.

What is a Compiler?

Software that translates high-level code into machine code.

What is an Interpreter?

Software that translates and executes code line-by-line during runtime.

What is a Linear Scan?

Searching a list by checking elements one by one from the start.

What is Binary Search?

Searching a sorted list by repeatedly dividing the search interval in half.

What is the prerequisite for Binary Search?

The data must be sorted.

What is the Binary Search Tree (BST) property?

For any node, all values in the Left subtree are smaller, and all values in the Right subtree are larger.

What is the worst-case time complexity of BST search?

O(N) if the tree is unbalanced.

What is a B-Tree?

A self-balancing tree data structure that maintains sorted data.

Why are B-Trees used in Databases/File Systems?

They reduce the height of the tree and minimize expensive disk seek operations.

What is an Index in a database?

A separate data structure that improves the speed of data retrieval operations.

What is a Leaf Node in a tree?

A node with no children.

What is the Root Node?

The single top-most node of a tree.

What is Recursion?

A function calling itself to solve smaller instances of the same problem.

What is a Block in storage systems?

The smallest unit of data that can be written to or read from a disk.

Does an index speed up or slow down Writes?

Slows them down because the index must be updated along with the data.

In a B-Tree, where are data records usually stored?

Only in the Leaf Nodes.

What is Fanout?

The number of pointers/children originating from a single node in a tree.

What is the 'Return Address' in a function call?

The memory address where execution continues after the called function finishes.

What is a Variable?

A named storage location in memory.

Why are Arrays cache-friendly?

They store data in contiguous memory locations.

What is an Assembler?

Converts assembly language into machine code.