Notes, summaries, assignments, exams, and problems for Computer science

CISC: Complex Instruction Set Computer

The Complex Instruction Set Computer (CISC) architecture packs more complex instructions into the processor. Some instructions might perform several tasks in one go. This design reduces the number of instructions a programmer needs to write but makes the CPU's internal logic more complicated and potentially slower for some tasks.

• Think: “Do more, but it might take longer.”

CISC is commonly found in x86 architectures (e.g., typical laptops or desktops), where compatibility and code density often matter more than raw efficiency.

RISC vs. CISC: Architectural Approaches

Both RISC (Reduced Instruction Set Computer) and CISC architectures aim to solve the same problem—efficient program execution—but they...

Von Neumann Architecture Fundamentals

The Von Neumann Architecture is a foundational computer architecture model where the Central Processing Unit (CPU), memory, and input/output devices share a single communication pathway—the system bus.

This design is characterized by using the same memory space for both instructions (programs) and data, often referred to as the stored-program concept.

We can examine how instructions flow through this architecture and how it compares to other models, such as the Harvard Architecture.

Essential Components for Instruction Execution

Here is a breakdown of three key registers—the Program Counter (PC), Instruction Register (IR), and Memory Address Register (MAR)—all essential for executing instructions in a...

Operating System Memory Management Fundamentals

The Operating System (OS) is responsible for crucial memory decisions: determining which programs reside in memory, where they are placed, how memory is protected, and what actions to take when memory resources are exhausted.

Parkinson's Law Applied to Computing

Parkinson’s Law states that programs expand to fill the memory available to hold them.

Models for Organizing Memory

Three primary models exist for structuring memory:

• Model A (User on Top, RAM on Bottom):
  • Pros: Fast execution.
  • Cons: No protection (e.g., used in MS-DOS).
• Model B (ROM on Top, User on Bottom):
  • Pros: OS protected.
  • Cons: Slow and not flexible.
• Model C (Drivers at Top, User in Middle, RAM at Bottom):
  • Pros: Fast and secure.
  • Cons: Complex

Journaling Motivation and Necessity

File System Check (FSck) ensures metadata consistency after crashes but is slow and requires deep file system knowledge. Recovery time should ideally depend on the number of recent writes.

File System Transactions and ACID Properties

Transactions provide ACID guarantees:

• Atomicity
• Consistency
• Isolation
• Durability

These are used to treat file system operations (like file creation) as transactions. Recovery ensures committed transactions are applied and uncommitted ones are discarded.

ext3 Journaling File System

ext3 is a journaling file system using physical redo logging, adding journaling to existing ext2 structures.

Redo Logging Mechanism in ext3

The process involves writing updates to a journal first, then committing...

C printf Function: Format Specifiers Explained

The printf function in C is used to display formatted output to the standard output (usually the console). It allows programmers to control how data is presented by using **format specifiers**. Format specifiers are placeholders that define the type of data being printed and how it should be formatted. They begin with a % symbol, followed by a character that specifies the data type.

Role of Format Specifiers

Format specifiers serve two main purposes:

1. Data Type Identification: They inform the printf function about the type of data being passed as an argument. For example, %d is used for integers, while %f is used for floating-point numbers.
2. Formatting Control: They allow customization of how the data

Computer Systems Fundamentals Cheat Sheet

Number Systems

• Binary (Base 2): Digits 0 and 1.
• Hexadecimal (Base 16): Digits 0–9 and A–F.
• Decimal (Base 10): Digits 0–9.

Conversions

• Binary to Decimal: Multiply each bit by 2^n from the right.
• Decimal to Binary: Divide by 2 and record the remainders.
• Hex to Binary: Replace each hex digit with its 4-bit binary equivalent.

Two's Complement (Signed Numbers)

• Positive numbers: Same as unsigned.
• Negative numbers: Invert all bits and add 1.
• Range (n bits): -2^(n-1) to 2^(n-1) - 1.
• Overflow: Occurs if carry into the sign bit ≠ carry out.

Boolean Algebra Rules

• Identity: A + 0 = A, A * 1 = A
• Null: A + 1 = 1, A * 0 = 0
• Idempotent: A + A = A, A * A = A
• Inverse: A + NOT A = 1, A * NOT A = 0
• Distributive: A(B + C) = AB +

Support Vector Machines (SVM)

A support vector machine is a supervised method for classification or regression that seeks a boundary in a high-dimensional space which separates classes with the widest possible margin. The training process involves choosing a boundary that maximizes the distance to the nearest training points, known as support vectors. When data are not perfectly separable, slack variables can be introduced to allow some misclassifications or margin violations while balancing margin maximization and classification accuracy. A kernel is a special function that effectively maps data into higher-dimensional spaces without doing the mapping explicitly; it lets the support vector machine handle nonlinear relationships by measuring...

Conditional Control Structures

Conditional control structures dictate the flow of execution by allowing specific blocks of code to run only when certain conditions are met.

1. The If Statement

The If statement executes a block of code only if the specified condition evaluates to true. Otherwise, the block is skipped entirely.

Syntax:

if (condition) {
    // statements (If Block)
}
// other statements

Note: A flow chart typically illustrates the execution path based on the condition.

2. The If-Else Statement

If the condition is true, the If block is executed. If the condition is false, the alternative Else block is executed.

Syntax:

if (condition) {
    // statements (If Block)
} else {
    // statements (Else Block)
}

3. The Else-If Ladder Statement

The...

Tokens

In programming, a token is the smallest meaningful element in code. They are the building blocks of a language's syntax. Common token types include:

• Keywords: Reserved words like if, else, while, and int (for declaring integers).
• Identifiers: Names given to elements like variables (e.g., sum), functions, and arrays.
• Constants: Unchanging values during program execution (e.g., 3.14 for pi).
• Operators: Symbols for mathematical or logical operations (e.g., + for addition).
• Separators: Punctuation like commas (,), semicolons (;), and braces ({}).

Example: int sum = 10 + 5;

In this line, int is a keyword, sum is an identifier, = is an operator, 10 and 5 are constants, and ; is a separator.

Arithmetic Operators

C has nine arithmetic operators for basic...

Lecture 2: Dynamic Dispatch and Interfaces

• Dynamic Dispatch: The process of selecting which implementation of a polymorphic operation to call at runtime.
• Interface: Calling a method that is not in the interface will cause a compilation error.

Lecture 3: N/A

Lecture 4: Method Contracts, Exceptions, and Unit Testing

• Method Contract: Should define pre/post conditions and exceptional behavior. The client is to blame if the precondition is not met, and the service is to blame if the postcondition is not met. Exceptional behavior specifies what the code will do if a precondition is violated.
• Exception: Runtime exception (unchecked) and IO exception (checked). The IO exception must be caught; otherwise, the code won't compile.
• Unit Test: Test boundary