Sixteen courses with question linked reading sections
Use this guide to learn the rule behind a question, then solve a fresh example without looking.
It brings together the Ministry blueprint, course readings, revision notes and practice questions to support systematic study.
Use the searchable guide to find the reading section for a practice question.
Select the course and enter its question number or stable ID.
Use each reference to learn the concept, then check whether the question provides enough information for a unique answer.
Check for missing information, conflicting assumptions and equivalent choices before selecting an answer.
The guide follows the 2015 E.C. blueprint and includes historical and mock examination practice.
Use historical and mock papers for practice; verify a paper’s official status independently of its label or answer key.
Future examinations can change; the guide develops methods and comparisons so you can transfer knowledge to unfamiliar questions rather than memorize answer letters.
Find what to read
Select a course and enter its question number, or search by stable ID or words from the question.
3485 questions indexed across 16 courses.
START01 A practical study cycle
Start with a small set of questions before reading.
Mark the exact thing that stopped you: an unknown term, a rule, a calculation, a trace or a choice between alternatives.
Use the question lookup to open the relevant section.
Read one section, close it, and explain the rule in your own words.
Solve the question again and say why each other choice fails.
Then change one assumption or input and solve the variation.
This checks understanding beyond recognition.
A useful 60-minute session: 10 minutes of cold questions, 20 minutes of focused reading, 20 minutes of closed-book solving and 10 minutes updating an error log.
Adjust the timing to your needs.
Revisit mistakes after a gap, for example the next day, several days later and the following week.
These intervals are a practical starting plan, not a fixed learning law.
Record the section ID, your mistaken rule, the corrected rule and one boundary case.
Keep the log short enough to review.
Mix related courses during revision: programming with data structures; databases with security; networking with administration.
Explain how the same word changes meaning across contexts.
An algorithm gives precise, executable steps and terminates for every legal input.
Definiteness means each step has an unambiguous meaning; effectiveness means a step can actually be performed.
Inputs may be absent, but a useful algorithm specifies a result.
Correctness means the result meets the specification.
Efficiency is desirable and measurable, but an inefficient terminating algorithm is still an algorithm.
Efficiency is also a desirable property of an algorithm.
Procedural programming organizes operations in procedures; structured programming combines sequence, selection and iteration; object oriented programming organizes state and behavior in objects; functional programming emphasizes function evaluation.
A conditional statement is a construct, not a separate programming paradigm.
In the basic ASCII identifier rules, start with a letter or underscore; continue with letters, digits or underscores.
Do not use a keyword.
C++ is case sensitive: exitExam and ExitExam differ; delete and float are keywords, but FLOAT is a legal identifier. variable_1234 is valid; 4thInput, T-3 and names containing spaces are not single identifiers.
Avoid reserved underscore patterns in application code.
Comments use // to the line end or /* ... */ for a block.
They explain intent and assumptions for maintenance; ordinary comments do not execute or automatically improve speed, reliability or portability. main is the conventional entry function name, not a C++ keyword.
CP06 Declarations, initialization, constants and types
Write type name; or type name = value; for ordinary variables: int age = 20;.
Declaration introduces a name and type; initialization gives its initial value; later assignment replaces a value. a=b copies a scalar value, so later changes to b do not change a. A pointer or Java object reference instead copies an address/reference.
Use int for whole numbers, float/double for fractional approximations, char for a character and bool for logical values in C++.
Type sizes depend on the implementation; do not import Java widths into C++. short n, short int n and int short n denote the same signed short type. const int n=5 and int const n=5 are equivalent; an ordinary const int needs initialization. typedef creates an alias, not a distinct new type.
Single quotes denote a character literal, such as 'A'; double quotes denote a string literal, such as "A".
A string includes more storage than just its visible characters when a terminator is required. sizeof reports size in bytes, with sizeof(char)==1; the byte width and other sizes are implementation dependent. sizeof(array) gives total array storage before conversion to a pointer.
With int x=5,y=2, x/y is 2.
Assigning that quotient to double gives 2.0, not 2.5. static_cast<double>(x)/y performs floating division and yields 2.5.
Converting an in-range fractional floating value to int truncates toward zero.
Cast before the operation if a fractional result is needed.
Prefix ++x changes x and yields the new value; postfix x++ yields the previous value and also increments x. Separate the value used in the expression from the stored value after it.
A traditional C++ switch selects using an integral or enumeration value. case labels are constant expressions.
Execution starts at the matching label, then continues through subsequent statements until a break, return or the end. default handles an unmatched value but need not be the last physical label.
If case 2 prints Bus. and case 3 prints Truck. before the first break, input 2 prints Bus.Truck.
A break exits the nearest switch or loop; it does not by itself terminate the entire program.
A case label is an entry point, not an automatically isolated if branch.
while(condition) checks before each body execution and may run zero times. do {body;} while(condition); runs the body once before checking; it repeats while the condition remains true.
Use it when a menu or input attempt must occur at least once.
for(initialization; condition; update) executes initialization once, then condition → body → update → condition.
A missing condition in for(;;) acts as true.
A for loop is convenient for a known count but can also be condition controlled.
To print indices 0 through n-1, use i=0; i<n; ++i. Starting i=0 with i<5 and i+=2 prints 0 2 4.
break exits the nearest enclosing loop or switch. continue skips the rest of the current loop iteration: a for loop then runs its update; a while loop goes directly to its condition. return leaves the current function and may supply a result.
In main it ends the program normally.
A goto transfers to a label within its function; follow the label reached rather than reading lines in source order.
In the sequence a: print Graduating; goto b; c: print Year; goto a; b: print fourth;, entry at a prints Graduating fourth and reaches the end.
Year is not printed.
Structured alternatives usually make such logic easier to reason about.
Overloads share a name but differ in parameter count or types/order.
Return type alone cannot distinguish them.
Choose a candidate using argument types, then required conversions; report ambiguity if there is no unique best match. int sum(int x,int y,int z=0) allows two or three arguments; defaults occupy trailing positions in ordinary declarations.
inline does not compel the compiler to copy a function body at a call.
Small frequently used functions may be good optimization candidates, but actual expansion is the optimizer’s decision.
Inline also has language linkage/definition rules, so it is not simply a speed command.
A recursive function calls itself directly or indirectly.
It needs a base case and progress toward it for all supported inputs. factorial(0)=1 and factorial(n)=n*factorial(n-1) for positive n. factorial(3) expands to 3*2*1*1=6.
Negative inputs require rejection or a separate definition; they do not reach zero under n-1.
Evaluate conditions before expanding a recursive call.
A built-in C++ array has a fixed number of same-type elements in contiguous storage: int a[4]={10,20,30,40};.
Valid indices are 0 through 3. a[4] is outside the array; accessing it has undefined behavior.
Java checks bounds and throws ArrayIndexOutOfBoundsException.
Do not predict a C++ out-of-range value from nearby memory.
A standard built-in array bound must be a compile-time constant; variable-length local arrays are compiler extensions. int a[5]={1,2,3}; fills the remaining elements with zeros.
An uninitialized automatic array of int is different. a[i] equals *(a+i), so elements can be accessed using pointer notation without explicitly writing brackets.
A C string is a character array ending in '\0'. "Hello" needs six char positions; strlen counts five visible characters and excludes the terminator. sizeof a fixed char array reports its allocated bytes, which can exceed strlen+1. cout<<a prints a terminated char sequence, not its numeric address.
<cstring> supplies strcpy(destination,source), strcat(destination,source), strlen and strcmp.
Supply enough destination capacity; strcmp returns zero for equal content, otherwise a sign, not necessarily exactly -1 or 1.
C++ std::string in <string> owns resizable text; + concatenates, == compares content, size()/length() counts stored characters and substr(start,count) extracts a segment.
Standard std::string has no Java-style toUpperCase() or trim() member.
int x=10; int* p=&x; stores x’s address in p. *p reads or writes x; &p is the address of the pointer variable itself.
With p=&a,q=&b, p=q redirects p to b and leaves a and b unchanged.
By contrast *p=*q copies the pointed-to value.
Never dereference an uninitialized, null or dangling pointer.
An array expression commonly converts to a pointer to its first element, but the array is not itself an assignable pointer variable.
A pointer-to-pointer int** pp=&p allows **pp to reach x. A void* can hold an object address but requires conversion to a suitable object pointer before dereferencing in C++.
CP26 Scaled pointer arithmetic and dynamic allocation
If p points inside an array, p+k advances k elements, or k*sizeof(*p) bytes.
Under the explicit assumption sizeof(float)==4 and first address 7000, p+3 has numeric address 7012. cout<<p++ displays the old address then advances p; cout<<*p++ displays the old element then advances p. ++*p changes the element.
Pointer addition p+q is invalid; subtracting pointers within the same array gives an element distance.
Arithmetic must stay within an array or its one-past position; one-past may not be dereferenced.
C++ new T creates a dynamic object, delete releases it; new T[n] pairs with delete[].
Prefer resource-owning standard containers in real programs.
Allocation does not automatically initialize every primitive value unless initialization is requested.
A struct groups named members, possibly of different types. struct House{double price; int rooms;}; defines a type; House h{150000,3}; creates an object. h.rooms uses a dot.
House* p=&h; p->rooms is equivalent to (*p).rooms.
The pointer must refer to a live object before member access.
A type definition alone does not create an ordinary instance.
Aggregate initialization assigns members in declaration order.
Modern C++ permits default member initializers such as int rooms=3;.
C++11 list initialization rejects narrowing; a constant floating value exactly representable in the target floating type can be permitted, so 25.00 to float is not necessarily narrowing.
Use 25.0f for clarity and check the language version.
Structures can be copied, passed and returned; a structure cannot contain a full instance of itself, but may contain a pointer to its own type.
Include <iostream> and qualify std::cin/std::cout or introduce the names explicitly. cout is the standard output stream; << inserts values. cin is standard input; >> extracts formatted values. std::endl inserts a newline and flushes.
C++ names are case sensitive: Cout, Int and std: :cout are not equivalent valid spellings of cout, int and std::cout.
Read a full line with getline(cin,text).
After formatted numeric extraction, consume the pending newline before a line read when required.
Input failure must be tested before trusting a value.
Console output formatting matters: by default a double storing an exact 4 may print 4 rather than 4.0.
Text, spaces and newlines are part of an output trace.
Include <fstream>. ofstream writes, ifstream reads, and fstream can do both.
The constructor’s default ofstream mode argument is ios::out; its ordinary effect is to create/truncate the file.
Distinguish the default mode argument from effective out|trunc behavior. ios::app places each write at the end; ios::ate initially seeks to the end; ios::binary requests binary mode.
Check if(!file) after opening.
Read using while(file>>record) or while(getline(file,line)), because end-of-file is discovered by an attempted read. while(!file.eof()) can process an invalid extra record.
Close or rely on stream destruction to release the resource. “ofstream” is a class, whereas <fstream> is the header.
Use <cmath> for sqrt, pow, floor and ceil; integer abs is also provided by <cstdlib>. sqrt(16)=4; pow(3,4)=81; abs(-7)=7. ceil(x) is the least integer-valued result >=x; floor(x) the greatest <=x. Thus ceil(-2.7)=-2 and floor(-2.7)=-3; truncation toward zero differs from floor for negatives.
C++ has no built-in exponentiation operator: ^ is bitwise XOR and ** is not a power operator.
To compute b^e for a nonnegative integer e, start r=1 and repeat r*=b exactly e times; b=4,e=3 gives 64.
Large powers and factorials can overflow fixed-width types; specify a valid input range.
CP31 Correctness by logic, invariants and induction
To prove an implication P⇒Q, a direct proof derives Q assuming P; a contrapositive proves not Q⇒not P; a contradiction assumes the claim false and derives an impossibility.
A single counterexample disproves a universal claim.
Induction proves a base case and proves P(k+1) assuming P(k).
For sum=0,i=1; while(i<=n){sum+=i;++i;}, use invariant sum=(i-1)*i/2.
It holds initially.
Adding i gives i*(i+1)/2, then incrementing i restores the invariant.
Exit gives i=n+1 and sum=n*(n+1)/2.
Termination needs a separate decreasing nonnegative measure n-i+1 while the guard holds.
CP32 Debugging, errors, exceptions and maintenance
A syntax error violates grammar; a type error can be syntactically well formed but rejected during semantic checking.
A runtime error occurs during execution; a logic error gives the wrong behavior.
A bug is a defect; debugging locates and corrects it.
Read the first useful compiler diagnostic, inspect nearby tokens and declarations, repair and rebuild; a debugger is useful after a runnable program exists.
Test ordinary, boundary and invalid inputs and trace the first point where actual state differs from expected state.
Exceptions transfer control to a matching handler for exceptional conditions; they do not make arbitrary undefined behavior recoverable.
Refactoring improves internal structure while preserving observable behavior.
Version control records changes, supports comparison and rollback; documentation explains use, design and maintenance assumptions.
A program trace requires the complete code, and a diagram question requires its edges, conditions and labels.
When entry reaches the body rectangle before the decision diamond and a decision branch returns to the body, the body executes before the condition is tested.
This is a post-test do-while loop.
Check that a program is valid before tracing it; state any syntax changes before analyzing the resulting program.
Match pointer-member names exactly: Cout/Cin, C1 and car_mode do not match cout/cin, c1 and car_model.
In the goto sequence above, Year is not printed because control does not reach its label.
With valid C++ syntax for the stated assignments, the trace yields z=5 then a=1.
Printing Z when only z is declared refers to a different, undeclared identifier.
Use <0 for a less-than-zero comparison and the standard int main() declaration for a C++ entry point.
Check int and cout case, quotation marks and comma-expression punctuation before tracing a C++ expression.
Predict output only after the program and its execution conditions are clear.
For an aggregate with no default member initializers, empty braces initialize its members recursively. Numeric scalar members become zero, and the elements of a character-array member become zero characters. A zero character at the beginning of such an array makes it an empty, terminated C string. This differs from leaving an ordinary automatic scalar or array uninitialized.
Python is a high-level programming language with built-in high-level data types. Calling a language a scripting language describes a common way it is used; it does not make that language machine code or assembly. Language level and execution style are different classifications.
A keyword is a reserved word with a predefined meaning in the language grammar. It cannot be repurposed as an ordinary variable or function name. An identifier is a name used to refer to a data object or function; its spelling must obey the identifier-character rules and avoid keywords.
CP-S04 Java print and println preserve output layout
Java System.out.print writes the supplied value without automatically ending the line. System.out.println writes its value and then a line separator. Successive println calls therefore place their values on separate lines, even when each printed expression also contains a trailing space.
CP-S05 An assignment expression can accidentally become a condition
In C++, simple assignment changes its left-hand object, and the assignment expression refers to that updated object. When an ordinary numeric assignment is used as a condition, the newly assigned value is converted to truth: zero is false and nonzero is true. Equality testing with == instead produces a Boolean result without assigning either operand. Confusing the two can both change program state and choose an unintended branch.
A data model supplies concepts for structure, relationships, constraints and operations.
Conceptual ER models describe entities and relationships.
Relational models use tables; hierarchical models organize records in a parent–child tree; classic network models connect records through pointer-based owner/member links, allowing multiple parents.
Object models represent objects with identity, state and behavior.
A physical model specifies record layouts and access paths.
These are different representation choices, not stages of one query.
PostgreSQL, MySQL, Oracle Database, Microsoft SQL Server and IBM Db2 are relational DBMS products.
MongoDB is a document DBMS.
Java is a programming language.
IBM alone names a vendor, not a database product.
Distinguish a vendor such as IBM from a specific database product.
FDB04 Three-schema architecture and data independence
The external level gives each user group a selected view.
The conceptual level describes the whole logical database: entity types, relationships, data types and constraints.
The internal/physical level describes files, record placement and access paths.
These are abstraction levels, distinct from client/server deployment tiers.
Physical data independence permits changing internal storage without changing the conceptual schema, for example adding an index.
Logical data independence permits conceptual changes while preserving affected external views and application interfaces, for example splitting a table while maintaining a compatible view.
It is harder because applications depend on logical meaning.
Data abstraction hides irrelevant details; program–data insulation separates data definitions from application code.
Cardinality specifies maximum associated occurrences: 1:1, 1:N or M:N. Minimum cardinality specifies optional/partial participation (zero permitted) or mandatory/total participation (at least one).
A maximum of one does not mean participation is compulsory.
If each employee belongs to one department and each department has many employees, Employee→Department is N:1; Department→Employee is 1:N. Building→Location could also be N:1, so names alone cannot select a unique example.
Under the common arrow convention, arrows from advisor to both Instructor and Student impose maximum-one at both ends, giving 1:1.
Without a notation convention, arrows are unsafe evidence.
For 1:N, place the one-side key as a foreign key in the many-side table; store relationship attributes there.
Department(DeptID) and Employee(EmpID,DeptID,HireDate) implement many employees per department.
If participation is total, make the reference NOT NULL.
If partial, a nullable reference can represent no assignment.
For 1:1, one side may hold the other key with a UNIQUE constraint.
Prefer the totally participating side to reduce NULLs; NOT NULL enforces that side's mandatory reference.
Merging entities is reasonable only when their lifecycle and participation rules permit it.
For A→B many-to-one, A can absorb the relationship reference under either total or partial participation; requiring total participation as the only possible case overstates the rule.
A binary M:N relationship needs an association table in addition to the two entity tables.
Enrollment(StudentID,CourseID,Grade) references Student and Course; (StudentID,CourseID) is a key if one enrollment per pair is allowed.
Repeated attempts require Term or AttemptNo in the key.
This ordinarily produces three tables.
A recursive M:N friendship uses UserLink(UserID,OtherUserID), two foreign keys to User; decide whether links are directed and whether self-links are allowed.
A recursive 1:N supervision uses a nullable SupervisorID reference in Employee.
For a ternary Supply(SupplierID,PartID,ProjectID,Quantity), preserve all participating references; binary replacements can lose which triple occurred.
Choose the association key from actual cardinalities rather than automatically assuming every reference is necessary.
Total specialization requires every superclass member in some subclass; partial specialization does not.
Map Person(PersonID,Name) and Student(PersonID,Program) with Student.PersonID both primary key and foreign key to Person.
This preserves inherited identity.
A category/union subclass draws members from a union of different superclasses, such as Owner drawn from Person or Company; it differs from an intersection subclass requiring membership in both.
Object models also support inheritance; distinguish basic ER notation from EER when comparing models.
Structural EER inheritance alone does not define executable object methods.
A fan trap occurs when two 1:N relationships fan from a common entity and a path suggests an association it cannot determine.
Department→Employee and Department→Project do not reveal which employee works on which project; joining through Department pairs every employee with every project in that department.
Record WorksOn explicitly when that is the fact needed.
A chasm trap occurs when an apparently useful path fails for some occurrences because an optional relationship breaks it.
For example, a branch's property may be lost from a path that requires an assigned staff member when some properties have none.
Add the required direct relationship or revise the model.
Multiple 1:N relationships are legitimate; eliminating all fans is not a universal repair.
A missing path describes a chasm, not the defining ambiguity of a fan.
Domain integrity restricts type and allowed values.
Key integrity enforces uniqueness.
Entity integrity requires every primary-key component to be non-NULL.
Referential integrity requires a non-NULL foreign-key value to match an eligible referenced unique/candidate key; self-references are allowed.
A parent need not have a child.
Inherent constraints come from the data model; schema-based constraints are declared through the DDL; semantic/application rules may need triggers or application logic when DDL cannot express them.
Integrity improves data validity; authorization controls who may access it.
Uniqueness and domain validation are both integrity mechanisms.
If a Department primary key is NULL and Manager=107 lacks a referenced employee, entity integrity certainly fails and referential integrity also fails if that foreign key is declared.
Example: CREATE TABLE Enrollment (StudentID INTEGER NOT NULL REFERENCES Student(StudentID), CourseID INTEGER NOT NULL REFERENCES Course(CourseID), Grade INTEGER CHECK (Grade BETWEEN 0 AND 100), PRIMARY KEY (StudentID,CourseID)); Each column declaration gives its name then type, with commas between declarations.
CHECK is a constraint clause, not a standalone GRANT-like statement.
POSITIVE is not a general SQL constraint keyword; CHECK (Amount > 0) expresses positivity.
PRIMARY KEY implies uniqueness and non-NULL.
UNIQUE does not generally imply NOT NULL; NULL treatment differs by DBMS.
A CHECK can pass when its result is unknown, so add NOT NULL if missing values must be forbidden.
Parent updates/deletes may use NO ACTION/RESTRICT, CASCADE or SET NULL.
A referenced key is not inherently unchangeable: legality depends on matching children and the declared action.
For R(A,B,C,D), let C→D, C→B and B→C. A never appears on a right-hand side, so every key needs A. (AB)+ gives ABCD through B→C→D; (AC)+ also gives ABCD.
AB and AC are minimal keys.
BC cannot derive A and is not a key.
A, B and C are prime; D is nonprime.
D depends on C alone and also on B through transitivity, proper subsets of those keys.
Thus 2NF fails; assuming atomic values, the highest form is 1NF.
Use the stated functional dependencies to justify each key and normal-form conclusion.
Confirm the actual dependency set before calculating closures; do not infer dependencies from unclear symbols.
For every nontrivial FD X→A, 3NF permits it when X is a superkey or A is prime.
BCNF requires X to be a superkey.
The mnemonic whole key and nothing but the key describes the common single-key case; it cannot replace the full tests when keys overlap.
Remove dependencies of nonprime facts on nonkey determinants.
In Sale(Date,Customer,Product,Vendor,VendorCity,SalesRep), assume key (Date,Customer,Product), Product→Vendor and Vendor→VendorCity.
Product is a proper subset of the key, so Vendor and VendorCity violate 2NF.
With atomic values the highest form is 1NF, even though a transitive dependency also exists. 4NF addresses nontrivial multivalued dependencies with nonsuperkey determinants; 5NF addresses join dependencies.
Do not confuse a multivalued dependency with a list stored inside a cell.
FDB22 Decomposition: lossless and dependency preserving
A lossless decomposition reconstructs exactly the original legal tuples by joining its parts; a lossy one creates spurious combinations.
For a binary decomposition into R1 and R2 under FDs, it is lossless when their common attributes determine all of R1 or all of R2.
Sharing a column without this condition is insufficient.
Dependency preservation means the original constraints can be enforced on the individual relations without joining them.
Losslessness and dependency preservation are separate properties.
A practical 3NF synthesis uses a minimal FD cover, creates a relation for each determinant and its dependent attributes, removes contained relations, and adds a relation containing a candidate key if none already does.
BCNF decomposition removes an offending X→Y by separating XY and the remaining attributes with X; it can sacrifice dependency preservation.
FDB24 Records, pages and primary file organization
A page/block is a unit of database I/O and holds several records.
For fixed unspanned records of size r in usable page space B, the blocking factor is floor(B/r), and n records occupy ceil(n/blocking factor) pages.
Page headers and slots reduce usable space.
A heap has no search-key order and supports simple inserts, but searches may scan all pages.
A sorted file supports efficient range scans and binary search on the ordering field, with more costly insertions or overflow handling.
A hashed file chooses a bucket by hash(key), supports equality lookup well and requires collision/overflow handling; hash order does not support ordinary ranges.
Choose organization from actual reads, writes and predicates.
Partitioning splits a large dataset; replication copies it; migration moves it; archiving removes older data from active service.
Use single quotes for SQL string literals: WHERE ID = 'B001'.
Standard double quotes delimit identifiers, although some vendor modes accept them for strings.
Qualify ambiguous columns with aliases such as E.Department.
Conditions use =, <>, <, >, AND, OR and NOT; use parentheses to make precedence clear.
LIKE 'Ab%' matches a prefix, and BETWEEN includes its endpoints.
NULL represents a missing/unknown value.
Comparisons such as Salary = NULL are unknown, not true; use IS NULL or IS NOT NULL.
WHERE retains only true conditions.
An index-friendly year predicate for timestamps is BirthDate >= DATE '2000-01-01' AND BirthDate < DATE '2001-01-01', avoiding omitted times on December 31.
Expression indexes can support functions, so functions do not universally prevent indexing.
INSERT INTO Hotel(HotelID,HotelName,SubCity) VALUES (1,'Hilton','Yeka'); pairs each named column with a compatible value.
Counts and types must match; keys and other constraints still apply.
Without a column list, values must follow the table's declared column order.
UPDATE Book SET Price = 600 WHERE ID = 'B001'; changes matching rows.
UPDATE without WHERE targets every row.
DELETE FROM Publisher WHERE Name = 'XWZ'; deletes matching publisher rows, subject to reference policies.
DELETE FROM r; removes every row but leaves r defined.
Both clear relation entries and delete rows describe that effect.
Several UPDATE statements can all be valid while performing different tasks; most appropriate requires a requested change and a specified quoting dialect.
COUNT(*) counts rows, COUNT(x) counts non-NULL x values; SUM and AVG summarize non-NULL numeric values.
SQL's usual average function is AVG, not AVERAGE.
GROUP BY creates one group per distinct grouping value; HAVING tests aggregate groups after WHERE has filtered individual rows.
SELECT Department, AVG(Salary) FROM Employee WHERE Department <> 'Sales' GROUP BY Department HAVING AVG(Salary) > 35000; lists qualifying department averages.
An ordinary AVG(Salary) predicate cannot be placed directly in WHERE.
Selecting EmpID, FirstName and LastName while grouping only by Department is also invalid unless the DBMS can establish the required functional dependence.
The grouping column need not itself appear in SELECT; check the functional dependence of other selected columns.
A transaction groups operations into one logical unit.
Atomicity applies all its effects or none.
Consistency means a correct transaction preserves declared invariants.
Isolation controls interference between concurrent transactions; serializable isolation provides behavior equivalent to some serial execution.
Durability preserves committed effects after a crash, typically through durable logging rather than forcing every data page immediately.
For a transfer, subtracting 100 from one balance and adding 100 to another must commit together; losing either half violates atomicity and may violate the total-balance invariant.
BEGIN starts work, COMMIT completes it, ROLLBACK undoes uncommitted work and SAVEPOINT marks an intermediate rollback point.
A failed transaction may roll back while other users' committed transactions remain.
SQL transaction syntax and error-handling constructs differ by DBMS; @@ERROR/IF is SQL Server-specific.
Denormalization deliberately repeats or precomputes facts to reduce selected read costs, increasing maintenance work.
Partitioning divides rows or columns; replication creates copies to improve locality or availability while complicating updates.
These techniques can coexist.
An e-commerce or gaming label alone does not select one.
Privacy requires a threat model.
Authentication verifies identity; role-based authorization limits allowed records/actions; encryption protects data at rest or in transit; auditing records activity.
Both encryption and access control can protect patient data.
Scalability, availability, fast retrieval, redundancy control and security are all reasonable design considerations.
Functional requirements describe behavior; nonfunctional requirements quantify qualities such as 99.9% uptime or response time.
Authentication and encryption mechanisms alone do not uniquely establish that distinction.
In a CMS, tags/categories describe meaning, while foreign keys preserve valid references between content and tags.
A ContentTag(ContentID,TagID) association models multiple tags per item; these functions complement each other.
FDB39 Integrated design: student registration and dormitory allocation
State the rules first: each student belongs to one department, may enroll in many courses, and has at most one current dorm assignment.
Each course accepts many students; each dorm holds at most six students.
Identify Department, Student, Course and Dorm entities; Enrollment is the M:N relationship with Grade.
Use Department(DeptID,Name), Student(SID,Name,DeptID,DormID), Course(CID,Title), Enrollment(SID,CID,Grade) and Dorm(DormID,FloorNumber).
Declare all entity IDs primary keys; Student.DeptID and Student.DormID reference their parents; Enrollment has composite key (SID,CID) and both references.
Make DormID nullable until assignment.
Separate StudentPhone(SID,Phone) for multiple contacts.
Normalize repeated department/course facts into their owning tables.
A simple foreign key does not enforce the six-student capacity; use a concurrency-safe trigger, allocation transaction or explicit slot design with six unique slots per dorm.
Justify each answer using the schema, SQL rules and stated assumptions.
Owner and strong entity can both describe the entity supporting a weak entity; row and record are synonyms in a relational table; difference and set-difference are the same operator.
DELETE, UPDATE and the invalid command REMOVE are not DROP; a question asking which is not DROP can therefore admit several choices.
Compare all choices with the relevant rule before selecting an answer.
For invalid SQL, identify the syntax error and validate the corrected statement before analyzing its result.
For unsupported cardinalities, request business rules and direction.
For best/efficient/important questions, specify workload, quality goal or comparison baseline.
A diagram-dependent conclusion needs the missing diagram or an explicit description of its relevant symbols.
Identify the smallest clarification needed when a question does not support a unique answer.
FDB-S01 Algebra operator lists and derivable operations
A list of basic relational-algebra operators is a teaching convention, distinct from a claim that every listed operation is logically indispensable. The course module uses selection, projection, Cartesian product, set difference, union and intersection as its basic-operation list. Natural join and assignment are not members of that particular list.
Under set semantics, union includes tuples from either compatible input, intersection retains tuples common to both, and difference keeps first-input tuples absent from the second. Intersection can be expressed using difference, while a matching join can be expressed as selection over a Cartesian product. A smaller primitive basis may therefore omit intersection even when it is introduced as a basic operation.
An object-relational DBMS retains relational data management while supporting richer extensions such as user-defined data types, functions and operators. PostgreSQL is an example. Richer relational types do not by themselves require all data to form a parent–child tree; that representation is the defining concern of hierarchical modeling.
Object Definition Language (ODL) is the ODMG schema-definition language for object databases; it describes interfaces/classes, attributes, operations and relationships.
Object Query Language (OQL) expresses queries.
Host-language bindings connect these definitions and operations to languages such as Java or C++.
Defining a logical schema is different from implementing its storage.
An inverse declaration pairs opposite directions of the same relationship.
Conceptually, Department.employees is inverse to Employee.department: when an employee belongs to department D, the corresponding employee appears in D's collection.
The declaration expresses relationship consistency; it is not an inheritance keyword or an ordinary scalar attribute.
An MCQ calling ODL both a DDL and a language for developing logical schemas offers overlapping true descriptions, so its exact wording matters.
A transaction is a logical unit of database work, including read-only work.
Atomicity means all effects or none; consistency means correct work preserves integrity rules; isolation controls concurrent interference; durability preserves committed effects despite failure.
A DBMS cannot automatically make incorrect business logic consistent.
Active means operations are executing.
Partially committed means the last operation finished but durable commitment is not yet assured.
Committed means commitment succeeded.
A failure leads to Failed, then Aborted after rollback; a transaction may terminate or be restarted as a new attempt.
Concurrency control primarily enforces isolation; recovery supports atomicity and durability.
Transaction management is the broader subsystem, so both it and recovery management can be legitimate answers to broad responsibility questions.
ADB07 Read/write operations, buffers and log records
read_item(X) locates X's page, brings it into a buffer if absent, and copies X into a program variable. write_item(X) copies the new program value into the buffered page, marking it dirty.
Writing that page to disk can occur later according to the buffer policy; write_item is not inherently an immediate disk flush.
Insert and delete also modify data; sorting is a query-processing operation rather than a primitive item update.
A conceptual log can contain START, UPDATE(T,X,old,new), COMMIT, ABORT and END records.
Before-images support undo; after-images support redo.
Real systems may use physical or logical records, and need not log every read.
COMMIT records successful completion; an ABORT record can mark the start of rollback rather than prove every undo step is complete.
Lost update: T1 and T2 both read 500; T2 adds 200 and writes 700; T1 adds 100 to its stale value and writes 600.
Correct serial execution yields 800.
Dirty read: T2 reads a value written by uncommitted T1; if T1 aborts, dependent work must be reconsidered.
Reading one's own changes is not a dirty read.
Nonrepeatable read means a repeated read of one row sees a committed change.
A phantom means repeating a predicate query finds a changed qualifying set after another transaction inserts, deletes or changes matching rows.
Incorrect summary mixes mutually inconsistent versions: a transfer moves 10 from A=100 to B=100; a sum reading old A=100 and new B=110 gets 210 instead of the invariant 200.
A single committed update from B=20 to B=50 does not alone prove an invalid summary of 90.
ADB09 Serial schedules, conflicts and precedence graphs
A serial schedule executes each transaction's operations consecutively.
A serializable schedule is equivalent to some serial order; it may interleave transactions.
Equality of one final value is insufficient evidence because different executions can accidentally coincide.
Two operations conflict when they belong to different transactions, access the same item and at least one writes.
Read/read pairs do not conflict.
For conflict serializability, make one graph vertex per transaction.
For every earlier conflicting operation of Ti and later operation of Tj, add Ti→Tj.
Acyclic means conflict-serializable; a topological ordering gives a valid serial order.
Cyclic means not conflict-serializable.
This test is stronger than view serializability, which also compares read-from relationships and final writers and may permit some schedules with blind writes.
Basic 2PL has a growing phase that acquires/upgrades locks and a shrinking phase that releases/downgrades them.
Once any lock is released, no new lock may be acquired.
The lock point is the instant the final lock is obtained. 2PL guarantees conflict serializability for well-formed transactions, but can deadlock and basic 2PL alone need not prevent cascading aborts.
Strict 2PL retains exclusive locks until commit/abort.
Rigorous 2PL retains both shared and exclusive locks until that point.
Conservative/static 2PL obtains all needed locks before execution and does not begin while only a subset is available, preventing hold-and-wait deadlock.
It requires knowing the lock set and can reduce concurrency.
Two-phase locking orders access to data; two-phase commit coordinates a distributed commit decision.
ADB13 Deadlock detection, prevention and starvation
Deadlock requires a waiting cycle: T1 holds X and wants Y; T2 holds Y and wants X. In a wait-for graph, an edge Ti→Tj means Ti waits for a lock held by Tj.
A cycle indicates deadlock under the ordinary lock-wait model.
Abort a suitable victim, undo its effects and release its locks; repeat if other cycles remain.
Aborting every deadlocked transaction also breaks cycles but wastes more work.
Fixed resource ordering and conservative 2PL prevent cycles.
A no-wait policy aborts immediately on an incompatible lock request and needs no age timestamp.
A timeout aborts long waits but may mistake slow progress for deadlock.
Starvation is indefinite postponement while other work proceeds, without a required cycle.
Fair queues, sensible victim selection and retaining original transaction timestamps on retry reduce starvation; deadlock freedom alone does not prove fairness.
ADB16 Optimistic control, versions and lock granularity
Optimistic/validation control reads and computes privately, validates its read/write sets against overlapping transactions, then publishes if validation succeeds; otherwise it retries.
It works well when conflicts are uncommon, but high contention wastes work on aborts.
Multiversion control keeps versions so a reader can use an appropriate snapshot.
Snapshot isolation is not automatically serializable: concurrent writes to different rows can violate a shared invariant.
Fine-grained row locks permit more independent operations but require tracking many locks.
Coarse table/database locks simplify management but block unrelated rows and reduce concurrency.
Intention locks advertise planned descendant locks in a hierarchy; escalation replaces many small locks with a coarser one.
Small granularity does not inherently cause more logical conflicts.
Choose granularity from contention and management overhead, not a universal rule.
Heuristics reduce intermediate work: push selective row filters toward base tables; replace product followed by a join predicate with a join; project unneeded columns away while retaining join/filter columns; reorder inner joins when equivalence permits; reuse common expressions when worthwhile.
Split conjunctive selections when each predicate can be applied earlier to its own input.
Semantic optimization additionally uses trusted constraints, such as a key proving a join cannot multiply matching rows.
Cost-based optimization estimates candidate plans instead of relying on rules alone.
Outer joins, NULLs, duplicates and aggregation restrict equivalences: moving a right-table filter from ON to WHERE after a left join may delete its preserved unmatched rows.
Fewer intermediate rows is a useful heuristic, not proof of minimum runtime.
ADB19 Estimate costs, cardinalities and selectivity
A cost model estimates resources for a candidate plan: page I/O, CPU, memory, temporary storage and network traffic.
Catalog statistics include row/page counts, distinct values and distributions.
Selection with fraction s predicts s×N rows.
For non-NULL equijoin keys, a common estimate is |R|×|S|/max(V(R,k),V(S,k)), assuming uniform values and containment of the smaller distinct-value domain within the larger.
Adjust counts for NULLs; if either non-NULL input is empty, the result is zero.
Skew, correlations or incomplete domain overlap can invalidate this estimate; known disjoint domains give zero matches.
For a simple rotating-disk model, cost = seeks×seek_time + transferred_blocks×block_transfer_time.
Five seeks at 5 ms plus ten blocks at 1 ms cost 35 ms.
Disk I/O often dominates textbook local-disk examples; CPU can dominate in-memory work and network can dominate distributed plans.
State the assumed cost objective before ranking strategies.
Compare only plans returning the same result under the same assumptions.
Add scans, probes, sorting, intermediate writes and communication as applicable; do not count an omitted cost in only one plan.
Record memory limits and whether inputs are already ordered.
Choose the lowest estimated cost for the specified objective, then test estimates against actual execution.
Example: R has 100 pages, S has 1,000 pages and M=12 buffers.
Block nested loops with R outer cost 100+ceil(100/10)×1,000=10,100 reads; S outer costs 1,000+ceil(1,000/10)×100=11,000.
If a selective R index costs 3 reads and returns 20 outer tuples, with each S index probe costing 4 reads including matches, indexed nested loops cost 3+20×4=83 reads.
That wins under these stated assumptions; it is not a universal join ranking.
Materialization stores an intermediate result before the next operator consumes it.
Pipelining passes tuples as they become available, overlapping producer and consumer work and reducing temporary I/O. A sort is normally blocking; a hash join must build its hash table before probing can output, though later probe/output can stream.
Pipelining does not require separate CPUs.
Parallel execution uses multiple workers, for example partitioned scans/joins, independent subplans or operator pipelines.
Interleaving on one CPU is concurrency; simultaneous cores provide parallelism.
Result caching reuses answers and needs invalidation when underlying data changes.
Plan caching reuses an execution strategy, not the rows returned.
Buffer caching keeps data pages; materialization retains intermediate rows.
Specify the kind of query caching being discussed.
GRANT SELECT ON Catalogue TO Mohammed; permits reads.
REVOKE DELETE, UPDATE (Price,Year) ON Catalogue FROM Mohammed; removes the specified table deletion and column update grants in SQL dialects supporting that form.
DELETE applies to rows/table access rather than particular columns; UPDATE can be column-scoped.
REVOKE removes permission, whereas GRANT gives it.
Roles group privileges.
WITH GRANT OPTION permits a recipient to grant a privilege onward; removing an upstream grant can cascade or be restricted according to the chosen command and DBMS.
Removing one direct grant may leave effective access through another role or grant path.
A view is a stored query definition, not encryption.
Least privilege assigns only the access needed for the task.
ADB26 Classify failures and choose the starting resource
Transaction failures include invalid operations, constraint violations and concurrency-control aborts.
Enforcing concurrency can deliberately abort work; it does not prevent every transaction failure.
A system crash loses volatile memory while disks may survive.
Media failure damages persistent storage and normally requires restoring a backup, then replaying available archived logs.
Human mistakes may require point-in-time restoration before the bad committed operation.
Restart recovery restores a valid database after a crash while preserving durable commits and removing incomplete effects.
Rollback handles failed/uncommitted work; redo preserves committed work missing from pages; checkpoints reduce log-search work; backups provide another stored copy.
These are cooperating mechanisms, not four mutually exclusive complete alternatives.
Buffer management is not durable backup.
Generic recovery-manager terminology should not be mistaken for an exact MySQL component specification.
A full backup copies the database to separate storage; scheduled backups plus archived logs support restoration to a chosen recoverable point.
Steal permits a page with uncommitted changes to be written to disk; hence recovery may need undo.
No-steal prevents those uncommitted effects reaching the persistent database.
Force writes a transaction's updated data pages at commit; no-force permits committed dirty pages to remain buffered, hence recovery may need redo.
For the conventional page/log model: steal/no-force needs undo and redo; steal/force needs undo but no redo; no-steal/no-force needs redo but no undo; no-steal/force needs neither data-page undo nor redo after a system crash.
Logging/atomic commit machinery may still be necessary.
These policies are independent of whether an update overwrites an old page or uses a separate location.
Immediate update alone does not uniquely specify every recovery requirement.
ADB29 Deferred, immediate, in-place and shadow updates
Deferred update keeps uncommitted changes outside the persistent database; in the usual no-force setting it is NO-UNDO/REDO.
Redo-only and NO-UNDO/REDO mean the same thing, so those cannot be separate unique answers.
Immediate update allows persistent changes before commit and therefore may require undo; it need not flush every write_item immediately.
In-place update overwrites the original location.
Shadow/copy-on-write update writes a new location while preserving the committed version.
Shadow paging keeps an unchanged committed page map and a modified map; commit durably installs a new root/map pointer atomically after required pages are durable.
Before commit, a crash uses the old map.
It is an alternative to conventional log-based recovery, with allocation, fragmentation and concurrency costs; it is not primarily a special action done only during recovery.
A checkpoint records enough durable recovery state to avoid scanning all old history.
In a simple quiescent/checkpoint exercise, specified flushing may make earlier committed work unnecessary to redo.
Active transactions can span the checkpoint, so their relevant earlier updates can still need undo.
Do not assume every transaction before a checkpoint needs no processing.
A fuzzy checkpoint permits ongoing transactions and records active-transaction and dirty-page information without forcing all pages simultaneously.
Recovery may start analysis at the checkpoint but redo from an earlier required log position.
A checkpoint is neither a full backup nor an automatic commit of active transactions.
Without checkpoints or another valid truncation boundary, long-running systems may need expensive log scans; deferred update does not avoid that problem.
Assume steal/no-force, durable WAL and a simple undo/redo method.
Initially X=100,Y=50.
The durable log contains START T1; UPDATE T1 X 100→120; COMMIT T1; START T2; UPDATE T2 Y 50→70; crash.
T1 is a winner and T2 a loser.
Redo X=120 if needed; undo Y=50 if T2's change reached disk.
Under no-steal, Y never reached the persistent database, so no undo of it is needed.
To solve larger cases, list transactions and durable commit status, identify the checkpoint type and buffer policy, select the algorithm, apply redo/undo in its required order and recompute final values.
Transactions active at failure are not automatically restarted and committed.
Business-level retries require a new controlled attempt; idempotency prevents duplicate effects when the client is unsure whether a commit succeeded.
ADB33 Distributed, homogeneous and heterogeneous systems
A distributed database contains logically related data across networked sites, managed as a coordinated system.
A homogeneous system uses compatible DBMS technology across sites; a heterogeneous system integrates differing DBMSs, data models, schemas or interfaces.
Different operating systems are possible but do not define the distinction.
Same DBMS does not imply identical local schemas, automatic replication or immediate synchronization.
Heterogeneous design must reconcile naming, types, units, identifiers, query capabilities and transaction semantics.
ODBC and JDBC provide connectivity interfaces; they do not automatically solve semantic differences or create one distributed transaction.
Locality, expansion and replicated availability are potential benefits.
Distribution adds communication, coordination and security costs; a site outage can still make needed data unavailable if no usable replica exists.
In client/server architecture, clients submit requests while servers manage shared data, execute operations and enforce supported integrity/transaction rules.
In collaborating-server designs, servers cooperate on subqueries and transactions.
Middleware can translate requests, locate data, coordinate operations and combine results across independent servers.
These describe communication responsibilities, not fragmentation types.
A tightly integrated distributed system can present one global schema and shared control.
A federation integrates autonomous databases through mappings; a loosely coupled multidatabase system may preserve more independence without one complete global schema.
State how much schema, transaction and administrative autonomy local sites retain.
Calling a system heterogeneous does not require all sites to surrender autonomy or to copy every row everywhere.
ADB36 Fragmentation: correctness and reconstruction
Horizontal fragmentation selects row subsets by predicates; their union reconstructs the relation.
Check completeness so every original row is represented and disjointness if no overlap is intended.
Define an explicit fragment for NULL/other values when needed.
Vertical fragmentation projects column subsets and repeats a key or row identifier so joining on it reconstructs the original rows without spurious matches.
Hybrid fragmentation combines row and column splits in either suitable order.
Reconstruct by reversing the operations: key joins for corresponding vertical pieces and unions for horizontal pieces.
A full outer join is not universally required.
Partitioning improves locality and parallelism but alone creates no spare copy.
Losing the only site containing a fragment makes that fragment unavailable, even while other sites continue.
Full replication places the whole database at every relevant site; partial replication copies selected fragments to selected sites; nonredundant allocation stores each fragment once.
Copies improve read locality and can improve availability but require storage and update propagation.
They can also spread mistakes, so replication does not replace independent backups.
Eager/synchronous replication coordinates propagation before the specified commit/acknowledgment point, increasing update latency.
Lazy/asynchronous replication propagates later and may expose stale reads or need conflict resolution.
Snapshot replication transfers a copy at intervals; incremental replication transfers changes.
These dimensions can coexist, so commonly used does not identify one unique policy.
Full replication does not inherently mean every copy is updated simultaneously; its synchronization rule must be stated.
ADB38 Distributed query plans and semijoin arithmetic
Distributed processing decomposes a logical query, localizes referenced relations to fragments/replicas, chooses global placement/order and optimizes local subplans.
Include bytes moved, message latency, bandwidth and local work.
Apply filters and projections before shipping when equivalent.
A semijoin retains only rows of one input that have a match in the other, returning that input's attributes.
Suppose R at A occupies 100 MB and S at B 20 MB; compute the result at A. Shipping all S costs 20 MB.
A semijoin can send 0.2 MB of distinct R join keys to B, then return 1 MB of matching S rows: 1.2 MB before other costs.
It wins on transferred bytes, but extra messages may dominate on high-latency links.
If nearly all S matches, key shipping may not help.
ADB40 Construct homogeneous and heterogeneous designs
For a bank using one compatible DBMS at three branches, horizontally fragment branch accounts by BranchID; keep each account at its home branch and replicate selected read-mostly reference data.
For cross-branch transfers, use global identifiers, coordinated commit and a stated isolation policy.
Choose replica placement so the required service remains available after the specified failure.
Verify reconstruction, capacity, latency and recovery procedures.
For a merger retaining different branch DBMSs, add mappings for AccountID, currency, time zones and numeric precision, plus middleware/gateways for supported operations.
Decide whether all engines support atomic distributed commits; if not, define an explicit compensating workflow and its intermediate-state limits.
Compare retaining autonomy against coordination and availability requirements.
A good design answers who owns each fact, where copies live, what a failed link permits and how conflicting writes are resolved.
OLTP handles frequent operational transactions, such as account updates; OLAP scans and summarizes large datasets for analysis.
A warehouse integrates data for historical analysis, often through extraction, transformation and loading.
These are workload tendencies: OLTP can retain history and warehouses can be updated.
A star schema places measurements at a declared grain in a fact table linked to descriptive dimensions, such as time, product and store.
A snowflake normalizes dimension structure further.
Columnar storage groups values by column, reducing unnecessary column reads and aiding compression in scans; row-oriented storage groups each record's fields.
Neither physical layout alone determines whether the logical model is relational.
Indexes and denormalization choices depend on workload.
Key-value stores retrieve values by key; document stores hold structured documents; wide-column/column-family systems organize sparse rows and related column families; graph systems model nodes and edges for relationship traversal.
Wide-column systems such as Cassandra are not simply interchangeable with analytic columnar relational engines.
Flexible schema does not mean no schema rules, and NoSQL does not imply no transactions.
CAP states that under a network partition, a distributed service cannot guarantee both linearizable consistency and availability for every request at nonfailed nodes.
It is not a universal menu saying casually pick any two forever.
Systems choose failure behavior and may vary it by operation.
CAP consistency is a single-copy visibility/order property, distinct from ACID consistency's preservation of application invariants.
CRISP-DM starts with business understanding: define the decision and success criteria.
Then understand data, prepare it, model, evaluate and deploy; the process is iterative.
Cleaning, integration and feature selection occur during preparation, not before the business problem exists.
Within modeling, split data appropriately, train on training data, tune using validation and evaluate once on a held-out test set before deployment.
Testing and evaluation are sometimes overlapping labels rather than universally distinct sequential phases.
If an MCQ asks training→testing→evaluation→deployment, state that convention; another valid workflow can evaluate during model selection before final testing.
Deployment includes monitoring and may trigger another preparation/modeling cycle.
Do not leak future or test outcomes into training.
ADB45 Compare database mechanisms under explicit assumptions
Database mechanisms can overlap: ARIES and deferred update can both be log-based; restart recovery can use checkpoints, rollback and redo; NO-UNDO/REDO equals redo-only.
Questions using best, important, common or faster need a workload and comparison criterion.
Read the literal scope rather than treating one familiar term as automatically unique.
State the minimum missing information: exact DBMS/version for vendor behavior; OID/type convention for object constructors; requester/holder ages for waiting; durable log, page state and policy for recovery; fragment definitions and network cost for distribution.
Evaluate each description separately when several database mechanisms apply.
Use the stated assumptions to explain which database mechanisms apply to each question.
ADB-S01 Query representations and relational operators
A relation is represented by a table of tuples. Selection filters its rows by a predicate; projection retains chosen columns. A Cartesian product constructs every pair of input tuples. A matching join combines tuples satisfying its predicate, and can be represented as a selection over a product. Sorting orders results, while grouping collects rows sharing grouping values; these are different operations.
A query tree corresponds to a relational-algebra expression: base relations appear at leaves and operators at internal nodes. A query graph represents the predicate relationships of a relational-calculus expression without itself prescribing an operator execution order. An optimizer can transform the representation and choose access paths; the representation is not the query result.
In SQL transaction-block notation, BEGIN starts a block, COMMIT completes it successfully, and ROLLBACK cancels its uncommitted changes. Committing requests a durable transaction outcome; it is distinct from merely finishing the last read or write operation.
SAVEPOINT marks an intermediate position inside the current transaction. ROLLBACK TO discards changes made after that position while retaining earlier work in the transaction. A savepoint is not an independent durable commit, and rolling back to it does not itself commit the retained changes.
ADB-S03 Availability and evidence against false denial
Availability concerns keeping services and resources accessible to their authorized users. Non-repudiation concerns evidence that an event or action occurred and who originated it, so a participant cannot falsely deny it. Neither property specifies which particular user has permission to change a database row; that is the separate authorization decision.
ADB-S04 Elementary binary locks and shared-lock compatibility
An elementary binary lock has two states: free and held. A request on a free item sets the lock to held; a request on an already-held item waits until release. That simple model does not distinguish shared readers from a writer. Shared/exclusive locking adds modes so multiple shared readers can coexist while incompatible exclusive access is excluded.
A software failure originates in erroneous program behavior, such as a logical programming defect, invalid operation or operating-system fault. A hardware failure originates in malfunctioning physical equipment; loss of disk contents is media failure. An accidental user deletion is human error even if the software executes the requested command correctly. Physical catastrophes such as fire can also cause failure. The observed symptom of a crash does not alone identify which cause occurred.
Design with objects, then trace the Java rules that make the design run.
Java 17 is the baseline for these examples; modern interface rules and Java 25 constructor differences are explained where relevant.
The official allocation is six items.
Draw separate boxes for reference variables and objects, then trace constructor and field state changes.
For a call, check visibility and declared type first, overload selection second, runtime overriding third.
Practice one small interface hierarchy with valid implementations, a checked exception and a safe downcast; repair compiler errors before predicting output.
Sections in this course
OOP01 Objects, classes and responsibilities
An object has identity, state and behavior.
State is stored in fields; behavior is provided by methods.
A Rectangle object may hold width and height and answer getArea() or getPerimeter().
Two objects can have equal fields and still be distinct objects.
A class defines their common structure and behavior; an object is a particular instance.
Choose classes around responsibilities: an account controls its own balance, a transaction records a payment, and a service coordinates them.
Objects send messages through method calls such as obj.add().
They can delegate work to other objects; saying that objects cannot manage their own state is misleading.
Procedural and object oriented designs both support reuse; global shared data is not compulsory in procedural programming.
OOP02 Four principles and the difference between hiding and abstraction
Encapsulation groups related state and operations and controls access.
Information hiding keeps implementation decisions behind a stable interface.
Abstraction presents the essential operations while omitting details irrelevant to the caller.
These ideas overlap: a private balance plus deposit(amount) can demonstrate all three, depending on what the question emphasizes.
Inheritance forms a subtype relationship and may reuse implementation.
Polymorphism lets code using a common type invoke behavior appropriate to different concrete objects.
Prefer a precise mechanism over a vague slogan: wrapping fields and methods points to encapsulation; showing what an operation does while hiding how points to abstraction.
OOP03 Create objects and distinguish references from instances
Student s; declares a reference variable; it creates no Student object.
Student s=new Student(); allocates and initializes an instance.
Member access uses s.name or s.study(), subject to visibility.
Assignment t=s copies a reference, so both can refer to the same object; changing that object through t is observable through s.
Java passes all arguments by value.
Passing a reference copies it: a method may modify the shared object, but assigning its parameter to a new object does not reassign the caller’s reference.
The runtime may reclaim unreachable objects; collection timing is unspecified.
Reachable object cycles can matter for retention, but an unreachable cycle can be collected.
Java has byte, short, int, long, float, double, char and boolean.
Signed integer widths are 8,16,32,64 bits respectively. byte ranges from -128 to 127; short from -32768 to 32767. char is an unsigned 16-bit UTF-16 code unit and can hold a digit, letter or symbol, not a whole String. enum and String are reference types.
A compatible widening conversion often needs no cast; narrowing usually needs an explicit cast and may lose information.
Widening an int to float can lose precision, so “widening never loses information” is false.
Arithmetic promotes char, byte and short to int in many expressions. boolean does not convert to or from numeric truth values; if(0) and for(...;0;...) are invalid.
static gives one field per loaded class, shared by its instances.
If count starts at zero and every constructor increments it, three creations leave count=3.
Prefer ClassName.count and ClassName.utility().
A static method has no current instance, but can still use instance members through an explicit object reference.
A static initializer runs during class initialization, before the class’s first relevant active use, not simply whenever a file is loaded. final prevents reassignment of a variable, overriding of a method or extension of a class.
A final reference may still refer to a mutable object.
A shared mathematical PI is a good static final candidate; a student name normally belongs to an instance.
A calculation using only parameters may be static.
For ordinary members: private restricts access to the declaring class/nest; no modifier grants package access; protected grants same-package access plus qualified subclass access; public is widest, provided the declaring type itself is accessible.
Top-level classes/interfaces may be public or package-private, not protected/private.
Member types have additional visibility possibilities.
Across packages, a subclass accessing a protected instance member must do so through its own inherited context or an appropriate subclass-typed receiver, not any arbitrary superclass object. protected therefore does not mean “subclasses only”: unrelated classes in the same package also have access.
A class’s own main method can access private fields of an instance of that class.
OOP09 Constructors and missing default constructors
A constructor has the class’s exact name and no return type, not even void.
It initializes the new object and can be overloaded or private.
A private constructor can support a factory or controlled singleton creation; it does not mean the class can never create an object internally.
If a class declares no constructor, Java supplies a default constructor.
If Circle(double r) is declared, new Circle() fails unless a no-argument constructor is also declared.
Constructors are not inherited or overridden.
They may contain return; but cannot return an expression.
Fields get their default values before ordinary constructor initialization, rather than receiving defaults only because a default constructor was generated.
OOP10 Constructor chaining and initialization order
Under Java 17 rules, an explicit this(args) or super(args) invocation must be the first constructor statement. this invokes another constructor in the same class; super invokes the immediate superclass constructor.
A constructor cannot explicitly invoke both.
If there is no explicit delegation, an implicit super() is inserted; a matching accessible no-argument parent constructor must exist.
Trace parent construction first, then subclass field initializers and instance blocks in order, then the relevant subclass constructor body.
With consistent class and constructor names and this(5) chaining in the FinalExam example, the parent sets num1=4, the subclass initializes num=3, this(5) sets num=25, and the no-arg body sets num1=num, leaving 25.
Java 25 permits restricted statements before explicit constructor invocation; the older first-statement rule must be version qualified.
OOP12 Method overloading and compile-time selection
Overloaded methods share a name but have different parameter types, counts or type order.
Return type alone is insufficient in Java and C++.
Overloads can also arise through inherited methods; “same class only” is a teaching simplification. f(int), f(double) and f(int,int) are distinct, but changing a parameter name does not create an overload.
The compiler selects the applicable signature from the declared argument types and conversions. int arguments usually choose an exact int overload rather than a wider double overload.
A return type is not part of an ordinary Java method signature.
Distinguish a different signature from overriding an inherited signature.
A subclass overrides an eligible inherited instance method with the same signature and a compatible return type; a covariant reference return may be a subtype.
Visibility cannot become more restrictive, and checked exceptions cannot be broadened incompatibly. @Override requests compiler checking; Java has no override keyword.
Constructors, final methods, static methods and private parent methods are not overridden.
A same-signature child method matching a private parent method is an independent declaration, not runtime overriding and not ordinary static-method hiding.
An abstract inherited method is implemented by an overriding method in a concrete subclass.
Merely reusing a name in two unrelated classes does not establish overriding.
OOP15 Dynamic dispatch: declared type versus actual type
For Animal a=new Dog(), Animal is the declared type and Dog the actual type.
The declared type determines which member operations compile.
If fetch() exists only in Dog, a.fetch() fails compilation.
For an eligible overridden sound(), a.sound() invokes Dog.sound() at runtime.
To solve dispatch questions: check the declaration and visibility, determine the compile-time signature, then identify the object’s runtime class and its most specific override.
An array Animal[]{new Dog(),new Cat()} can call speak() on each using one loop.
New subclasses can supply behavior without rewriting this generic loop, which is the practical meaning of extensibility.
Java this denotes the current object; this.name=name distinguishes a field from a parameter. super.name selects a hidden superclass field; super.sound() directly requests the parent implementation.
It does not create a second parent object.
An unqualified instance call may dispatch dynamically; an explicit super call is different.
Fields are hidden rather than dynamically overridden, and same-signature static methods hide rather than override.
With Animal a=new Dog(), a.staticMethod() resolves using Animal’s compile-time type.
Prefer Animal.staticMethod() for clarity.
Java this and super are unavailable as current-instance references in static context.
OOP18 Abstract classes and concrete implementations
An abstract class cannot be directly instantiated but can define fields, constructors, abstract methods and concrete methods.
It need not contain an abstract method.
An abstract method has no body; abstract and final conflict because an operation cannot require overriding while forbidding it.
A concrete subclass must provide or inherit implementations of all required abstract methods; otherwise it must itself be abstract.
If parent declares abstract String welcome(), a String welcome() implementation is required; int welcome() is incompatible, and welcome(int) merely adds an overload.
A valid class can contain both the required implementation and an unrelated overload.
interface Payable{double getPaymentAmount();} declares an abstract public operation. class Invoice implements Payable must provide public double getPaymentAmount(), perhaps returning getQuantity()*getPricePerItem().
A class can extend a superclass and implement zero or more interfaces.
An interface can extend several interfaces.
No interface instance fields or constructors exist; fields are implicitly public static final.
A method declaration without private, default or static is implicitly public abstract.
Modern interfaces may also have default/static method bodies, and Java 9+ private helper methods.
Not every interface method must lack a body in modern Java.
Implementations must satisfy all inherited abstract contracts; they may inherit suitable public implementations.
Interfaces cannot be instantiated directly, but references may hold implementing objects, anonymous implementations or suitable functional-interface lambdas.
OOP20 Conflicting interface methods and abstract class choice
Use an abstract class for shared state, construction and common implementation; use an interface for a capability across unrelated classes and multiple type inheritance.
A concrete inherited class method takes precedence over an interface default.
An inherited abstract class declaration can require a concrete subclass to implement the operation rather than silently adopting a default.
Unrelated interfaces providing conflicting defaults require an explicit resolution; interfaces do not remove every diamond ambiguity.
If two compatible interfaces merely declare the same abstract signature, one public implementation can satisfy both.
If return types or other contracts conflict, additional declarations may still be impossible.
The answer to “same method in abstract class and interface” depends on whether each is abstract or implemented and whether their signatures are compatible.
Upcasting a subclass reference to a superclass is implicit and does not change the object.
A downcast may pass compile-time type checks yet fail at runtime.
Car a=new Car(); Ferrari f=(Ferrari)a; throws ClassCastException before subsequent drive() or brake() calls.
It does not turn a plain Car into a Ferrari.
Use if(a instanceof Ferrari) before narrowing when the dynamic type is uncertain. null instanceof Ferrari is false; casting null yields null, although dereferencing it fails.
For Object obj="Hello", (String)obj succeeds and (Integer)obj throws ClassCastException.
A literal 'Hello' is invalid Java syntax; use double quotes for a string literal before tracing the program.
OOP22 Identity, equals, toString and immutable strings
For object references, == tests identity; equals invokes the class’s equality policy.
Object.equals uses identity unless overridden; String.equals compares character content.
Equal objects must have equal hashCode values when that contract is implemented. toString gives a textual representation, not an equality test.
Java String objects are immutable. text += " World" assigns a reference to a new concatenated result and can print Hello World without mutating the original String object. final class String prevents subclassing; final alone does not make arbitrary objects immutable. charAt(index) returns a char; length() counts UTF-16 units; substring(begin,end) excludes end.
Character.toUpperCase(ch) converts a character, and matches(String regex) takes a regular-expression parameter named regex.
Java evaluates operands left to right while respecting precedence.
With n=6,m=15,p=3, n-=m then n*=p leaves -27. 6-2+10%4+7 is 13.
In 8-2*5*(3+9/3)+6/3, the result is -50.
Integer 6/4 is 1; double 6.0/4 is 1.5.
Unlike C++, Java % also accepts floating-point operands.
For bitwise values, write binary columns: 11&9=9; 9^3=10; 10|12=14. && and || short circuit Boolean operands; & and | can also operate on Boolean values without short circuiting.
Printing Boolean true gives lowercase true, not 1 or uppercase TRUE.
while and for pre-test and may execute zero times; do-while post-tests and executes once. break exits the loop; continue skips its remaining body and then runs a for update.
Traditional colon-style switch labels fall through without break.
Choice 1 printing Hello then case 2 printing you and breaking is followed by Goodbye outside the switch; default is skipped.
Count executions independently from printing.
For i=0..4, if(i%2==0) print(i+" "); followed unconditionally by print(i+1); produces "0 122 344 5".
A loop summing j=1..10 yields 55.
In if(a)... else if(a&&b)..., the second condition can never be true on a path reaching it because a is already false.
int[] a=new int[5]; and int a[]={1,2,3}; are valid. int[] a={}; creates a zero-length array; explicit new is unnecessary in a declaration initializer. int a[],b; makes only a an array; int[] c,d; makes both arrays.
Array objects have fixed length after creation, although the reference may be reassigned.
Elements have a declared common component type, which may be a superclass/interface.
Valid indices are 0..a.length-1; an invalid access throws ArrayIndexOutOfBoundsException.
Java two-dimensional arrays are arrays of arrays and may be ragged: {{12,-9,8},{7,14},{-32,-1,0}} has row lengths 3,2,3.
Java does not expose a portable physical contiguity guarantee, so a language-level answer should not rely on raw addresses.
For int[] a=new int[4], setting a[i]=i*3 and accumulating yields 0+3+6+9=18.
To average an array, sum every element and divide by its length using floating arithmetic; handle zero length separately.
Floating representations and printing can differ from a rounded mathematical result.
For the six-value example, the mathematical average is 98.8/6, approximately 16.46666667; the exact printed string also depends on floating representation and formatting.
java.util.Arrays.sort(a) sorts in place.
System.arraycopy(src,srcPos,dst,dstPos,length) copies into an existing array; its exact spelling uses lowercase c. Arrays.copyOf(a,n) creates a copy. a=b merely aliases the same array.
Random access is the reliable array advantage; size is bounded by implementation/resources, not unlimited.
package p; precedes imports; imports precede top-level type declarations. import p.*; imports accessible types from p as needed, not types in p.sub automatically.
Packages organize names and control access; hierarchical spelling does not grant special access between a package and its subpackages. java.lang is implicitly imported; java.util supplies utilities; java.io supplies I/O; java.awt includes Button and Checkbox.
Ordinary compilation uses javac Test.java, producing bytecode, then java Test launches the class.
Modern Java can also launch a source file using java Test.java; distinguish source-file launch from running a compiled class.
For ordinary public top-level types, filename and type name match.
Capitalized class names and lowercase method names are conventions, not universal syntax requirements.
Java identifiers are case sensitive; $ is allowed but @ is not an identifier character.
Throwable is the root of throwable values, with Exception and Error branches.
RuntimeException and Error subclasses are unchecked; other throwable classes are checked.
IOException, FileNotFoundException and SQLException are standard checked examples.
ArithmeticException, NullPointerException, ClassCastException and array bounds exceptions are unchecked.
A missing semicolon or undeclared variable is a compile-time source error, not a checked exception.
Checked does not mean the exception occurs at compile time: the compiler checks an obligation to catch or declare it, while an actual throw occurs at runtime.
A custom exception can extend Exception or RuntimeException.
Error normally signals serious conditions for which routine recovery is inappropriate; it is not technically impossible to catch an Error.
throw new IOException("message") actively throws a value; throws IOException in a signature declares a possible checked exception.
A caller must handle or propagate checked obligations. try encloses guarded operations; a matching catch handles the thrown type or a subtype.
Execution skips the remainder of the try when a throw occurs.
Catch blocks are considered in source order.
Place FileNotFoundException before IOException and IOException before Exception; a general catch before a subtype catch makes that later handler unreachable and prevents compilation.
If no catch matches, the exception propagates outward and an uncaught exception terminates its thread.
Multiple catch blocks are allowed; catch(IOException | SQLException e) handles alternatives, which must not be related by subclassing.
finally normally executes after try and any selected catch, including when leaving by return or propagating an exception.
It is not guaranteed if the process/JVM exits or crashes, or control never leaves the try.
A return expression is evaluated before finally; a finally return overrides the pending return and can suppress an exception, so avoid that pattern.
try-with-resources closes AutoCloseable resources even on exceptional exit. getMessage returns the message, toString normally includes type and message, and printStackTrace shows exception information and recorded call frames for diagnosis.
Tests should cover expected success, caught failures and propagation.
Exception handling does not replace validation or correct an algorithm’s logic automatically.
A JDBC operation obtains a Connection, prepares SQL, binds values, executes and processes results, then closes resources.
For PreparedStatement ps=con.prepareStatement("SELECT name FROM Student WHERE id=?"), ps.setInt(1,id) binds the first parameter. executeQuery returns a ResultSet; rs.next() moves to each row before reading columns. executeUpdate returns an affected-row count for updates.
Parameter binding keeps values separate from SQL syntax.
Catch or declare SQLException.
When several writes form one operation, disable auto-commit, commit on success and roll back on failure.
A GUI handler should delegate a slow database operation away from its UI thread, then display the result through the appropriate UI mechanism.
In the historical applet model, Java code was embedded in an HTML document and executed by a compatible JVM host/plugin or applet viewer. init initializes once; start follows initialization and resumes activity; stop suspends activity when the host deactivates it; destroy performs final cleanup before unloading. paint draws content and is not a constructor.
Study applets as historical Java concepts rather than modern browser deployment tools. destroy is not defined exclusively as “browser shuts down”: the host may destroy an applet on unloading, and abrupt process termination does not guarantee cleanup.
A JVM alone is also not the complete browser embedding environment.
OOP35 Android Activity, Intent, manifest and layouts
An Android Activity is a component providing an entry point for user interaction, often corresponding to a screen.
An Intent describes a requested action or explicit target; extras carry values between activities.
For example, putExtra("id",17) attaches an ID for the destination to read.
A content provider shares structured data, while a broadcast receiver handles broadcast messages; neither is the ordinary mechanism for starting an activity with parameters.
AndroidManifest.xml declares essential app metadata such as components, permissions and intent filters.
It is not executable code and does not contain all source or layout details.
Traditional view-based layout containers such as LinearLayout and RelativeLayout derive from android.view.ViewGroup, which contains child views.
An .apk is an Android package archive used for installation and runtime contents. “Android Package Kit” is a common exam expansion; Android’s documentation calls it an Android package.
A manifest describes the package, while layout resources describe views.
Use these distinctions to compare Android application structure with Java language concepts.
Check exact Java spelling and syntax: extends differs from Extends, println differs from printIn/printin, constructor names must match class names, and braces and operators such as <= and == affect validity and behavior.
Java is case sensitive: an invalid program may not compile even when a possible trace seems clear.
For a valid Java loop with i=2,4,6,8,10 that prints i*i only when i%4==0, the printed values are 16 and 64.
A valid implementation can define public String welcome() and additionally overload welcome(int).
Identify an implementation by its complete declarations and method bodies.
Check the required signature before selecting an implementation.
A rounded mathematical mean is not necessarily the exact Java printed output.
Several Java statements can be valid at once: a static constant and a parameter-only utility may both be suitable static members; multiple array declarations/initializers can be legal; an abstract class may contain a complete interface implementation.
Encapsulation and abstraction overlap, so choose only when the requested emphasis is specific.
An interface supports multiple type inheritance and abstraction. “All methods are public abstract” applies only under a restricted abstract-declaration or legacy interpretation. Java protected also grants access within the same package, so it cannot enforce “only subclasses.”
No keyword implements overriding: it is recognized from compatible declarations, and @Override is an annotation.
For C++ this, ordinary non-static member functions have an implicit object; variables do not receive a hidden argument.
Under the conventional introductory generation taxonomy, general-purpose high-level languages such as C++, Java, Python and Perl are third generation.
The taxonomy is separate from object orientation and from compilation versus interpretation.
Java source normally compiles to JVM bytecode, and a compatible JVM plus libraries supports portability across systems.
Portability still depends on compatible APIs, versions and environment assumptions; it is not an unconditional guarantee for any program on any device.
Java supports objects and classes but also primitive values. “Difficult to learn” is a subjective judgment rather than a technical language property.
Syntax conventions, bytecode portability and runtime implementation must be distinguished.
An identifier is a programmer-chosen name for an entity such as a class, method or variable. A reserved keyword has a language-defined role and cannot be used as an ordinary identifier. A literal writes a value directly, such as an integer, floating-point number, quoted character, quoted string or Boolean value.
A single-line Java comment begins with // and continues to the end of that line. A block comment begins with /* and ends with */. A documentation comment begins with /** and ends with */ and can be processed by Javadoc. Comment text does not execute as program statements.
For ordinary ASCII Java identifiers, the first character is a letter, underscore or dollar sign; later characters may also be digits. A reserved keyword is not an ordinary identifier, and a lone underscore is not a valid identifier in Java 17.
OOP-S02 Java 17 floating-point evaluation and printed doubles
Java 17 float uses IEEE 754 binary32, and double uses binary64. Successive multiplications group from left to right. Each floating-point operation rounds to its representable result, using nearest-value rounding with ties to even; regrouping a product can change its result.
PrintStream.print(double) converts the stored value through String.valueOf and Double.toString. For finite nonzero magnitudes from 0.001 inclusive to 10000000 exclusive, the standard decimal form uses at least one fractional digit and only the further digits needed to distinguish the value from adjacent doubles. println(double) also adds a line terminator. This is not fixed-decimal-place formatting.
A print call emits its value without inserting a separator or ending the line. A println call emits its value followed by a line terminator. Spaces must come from the supplied text or explicit output operations; adjacent calls do not automatically separate their values.
OOP-S03 Expression results, assignment and control headers
Java relational comparisons (<, <=, >, >=) and equality tests (==, !=) produce primitive boolean truth values. Their result is not an integer truth code or a value of the numeric operand type.
The conditional expression condition ? whenTrue : whenFalse requires a boolean or Boolean condition. It evaluates only the selected alternative. An integer or floating-point first operand is a compile-time error.
Assignments group right to left: a=b=c assigns c to b, then the resulting value to a. A later assignment overwrites an earlier value. Compound assignments update the left variable using the indicated operation.
Prefix ++ and -- update a variable before supplying its value; postfix forms supply the old value before the update. Multiplication, division and remainder bind before addition and subtraction; same-level binary arithmetic groups left to right. Integer division truncates toward zero. Unary plus preserves its numeric operand’s value.
A while header is while(condition). A basic for header is for(initialization; condition; update). A do-while statement places its condition after the body. An if selects its true branch or, when present, its else branch; only the selected branch executes.
For Boolean values, ! reverses true and false, && is true only when both operands are true, and || is true when at least one is true. Short-circuit evaluation skips an unnecessary right operand. For each binary column, integral & produces 1 only for two 1 bits, | produces 1 for either 1 bit, and ^ produces 1 for differing bits.
An unlabeled break leaves the innermost enclosing loop or switch. continue moves to the next iteration step, while return leaves the current method and may supply a return value. These transfers have different destinations; return is not merely a loop exit.
The base Exception class is java.lang.Exception. It does not belong to java.io merely because some subclasses represent I/O failures. Package membership and position in an inheritance hierarchy are separate facts.
Calendar and Date are classes in java.util; Collection is an interface in that package. java.util also contains Arrays and Scanner. java.net supplies networking facilities; java.awt supplies the Button and Checkbox UI controls described in the package overview.
A String represents a sequence of UTF-16 code units. A single char represents one code unit rather than an entire String. String objects are immutable; changing a reference to another String does not modify the original text value.
A double-quoted string literal denotes a String object. new String(existingString) creates a String with the same text; new String(charArray) copies the array’s characters into an immutable String. A single-quoted literal denotes one char, so several characters enclosed together in single quotes cannot supply a String.
Character.toUpperCase(ch) supplies the uppercase equivalent where one exists; Character.toLowerCase(ch) supplies the lowercase equivalent. Character.isDigit(ch) tests whether a character is a digit and returns boolean. Character.toString(ch) supplies a one-character String rather than converting letter case.
OOP-S05 Inheritance boundaries and whole-part relationships
In Java’s class-declaration terminology, constructors are not members and are not inherited. A subclass can invoke superclass construction; this does not turn the superclass constructor into an inherited subclass method.
Aggregation models one instance grouping other instances as a whole with parts. It is an object-relationship concept, not a method-dispatch rule. Inheritance instead relates a specialized class to a general class; overridden operations can then provide polymorphic behavior.
Java is commonly characterized as object oriented, platform independent and simple. Its architecture-neutral bytecode is executed by a compatible platform-specific JVM. “Simple” is a teaching characterization relative to language design, not a promise that every learner finds every Java program easy.
Understand how representation, registers, memory, control and I/O cooperate to execute a program.
Use the stated machine model: architectural labels alone do not fix timing, power, word size or core count.
For each problem identify the representation, operand width, addressing mode and timing assumptions before calculating.
Practice Boolean simplification, signed subtraction, effective addresses, cache traces, register transfers and pipeline timing; comparisons should explain the mechanism.
Give the four blueprint outcomes equal attention: hardware/software structure, CPU operations, I/O communication and performance enhancement.
Use historical architecture facts as a small supplement to the core principles.
Sections in this course
COA01 Architecture, organization and system structure
Architecture describes programmer-visible behavior: instructions, registers, data types, address spaces and I/O conventions.
Organization is the implementation: control signals, internal buses, pipelines and memory technology.
Different organizations can implement the same architecture; neither definition imposes a maximum lifetime.
Microarchitecture names the internal processor design.
CPU, main memory, I/O and their interconnection are the major structural parts.
The CPU contains an ALU, control unit and registers; a microcontroller is a complete integrated control system, not another mandatory CPU subunit.
A motherboard physically connects components.
Gates are fundamental logic building blocks; distinguish that level from CPU, memory, disk and motherboard components.
In the textbook Von Neumann model, instructions and data share an addressed memory system; the CPU normally advances sequentially unless control flow changes.
Harvard separates instruction and data memories or paths.
Modern systems may combine a unified address-space view with separate instruction/data caches, so “architecture used nowadays” is not an exclusive choice.
Separate program/data regions within one memory do not make a Harvard machine.
An operating system manages resources and provides services.
Applications solve user tasks.
A compiler translates source into target code; assembly is a symbolic form of machine instructions.
JIT compilation happens during program execution, often translating intermediate code.
Translation before execution alone does not distinguish JIT from an ahead-of-time compiler.
Machine-language programming depends on the register set, supported types and memory/addressing structure.
Useful identities are A+0=A, A·1=A, A+A=A, AA=A, A+A'=1, AA'=0, A+AB=A and A(A+B)=A. De Morgan gives (AB)'=A'+B' and (A+B)'=A'B'.
Check a proposed simplification with a truth table if uncertain.
NAND and NOR are each universal: feeding the same input to both inputs constructs NOT; combine complemented gates to construct AND or OR.
For Karnaugh maps, use Gray-code order, group adjacent 1s in rectangles of powers of two, allow wraparound and overlap, cover every required 1, and remove variables changing within a group.
A control condition P:R2←R1 performs the transfer only when P is true at the relevant clock event.
Simultaneous transfers read old register values; sequential statements can use a newly written value.
A common bus selects one source at a time, while destination load signals select receivers.
A read places an address in MAR/AR, asserts read, waits for memory and captures data in MDR/MBR/DR. A write supplies both address and data and asserts write.
The ALU computes; the control unit sequences and enables the transfers.
A microoperation is one elementary operation on register contents.
IR holds the fetched instruction; MAR holds an address used for the current memory access; MDR holds transferred data.
The accumulator holds operands/results, SP tracks the stack, and status flags report conditions. “Address of the instruction” without a phase can describe PC or MAR.
Registers and cache both store temporary information, but registers are explicit execution operands and cache holds copies of memory blocks.
A control word chooses ALU sources, destination and operation.
Use the machine’s encoding table rather than guessing opcodes.
In this 14-bit control-word example, SELA, SELB and SELD each have 3 bits, followed by a 5-bit operation field.
PUSH adds an item and POP removes the logical top.
A register stack uses registers; a memory stack uses RAM and a stack pointer.
Check whether SP points to the top or the next free location, whether addresses increase or decrease, and whether the update occurs before or after access.
Overflow means pushing a full stack; underflow means popping an empty one.
Zero-address arithmetic typically pops the second operand first, then the first operand; subtraction therefore needs careful order.
PUSH and POP may still contain an explicit address even on a stack machine.
Let A be an instruction field, R a register value and M[x] the contents at x. Immediate uses value A; direct uses EA=A and operand M[A]; indirect uses EA=M[A] then operand M[EA].
Register uses operand R; register-indirect uses EA=R. Indexed/base displacement uses EA=R+A; PC-relative uses the architecture-defined PC plus a signed displacement.
Auto-increment/decrement also updates the register by operand size.
A transfer between a register and memory does not uniquely specify addressing mode; either direct, indexed or indirect addressing may produce it.
TEST/CMP examine values and set condition information, often without retaining the arithmetic result.
Branch instructions choose a target, conditionally or unconditionally.
CALL saves a return point; RETURN restores it.
SKIP, where supported, bypasses the next instruction when its condition holds. “Jump to the next instruction” does not clearly mean skip.
External interrupts arise from devices or timers; synchronous internal exceptions arise from the executing instruction, such as divide errors, illegal opcodes or access violations.
A software interrupt is deliberately requested by an instruction.
Arithmetic overflow trapping depends on architecture and instruction; ordinary overflow flags need not trigger an interrupt.
CISC commonly supplies more complex operations, richer addressing modes and variable lengths.
Hardwired control directly generates control signals; microprogrammed control sequences stored control words.
These are tendencies, not universal guarantees.
One instruction completing per pipeline cycle is throughput, not proof that every instruction has one-cycle latency.
Modern RISC instructions can take multiple cycles and modern CISC processors can translate instructions into simpler internal operations.
Neither label guarantees lower power, cost or execution time.
The semantic gap is the distance between high-level constructs and machine operations; reducing it is associated with richer instructions, not a universal shared objective of both design approaches.
COA22 x86 instruction legality and implicit operands
Assume Intel destination-first syntax and ordinary legacy x86 forms.
MOV AL,BP is invalid because operand widths differ (8 versus 16 bits).
INC CX and DEC CX are valid word operations.
Segment-register MOV has register/memory forms, not a direct immediate-to-segment form: load an immediate into AX, then MOV DS,AX.
Unsigned MUL with a byte operand multiplies AL by that byte and writes AX.
With a word operand it multiplies AX and writes DX:AX.
Thus AL=8 and BH=10 gives AX=80 after MUL BH; CL is irrelevant.
MOVS and LODS are string transfer operations, XCHG exchanges operands, and INC is arithmetic. “Different” requires the transfer-versus-arithmetic criterion.
Virtual memory gives processes translated address spaces and protection; backing storage can hold nonresident pages.
The MMU translates virtual/logical addresses to physical addresses, using page tables and often a TLB of recent translations.
Virtual memory is not just extra disk disguised as RAM.
With page size P, page=floor(virtual_address/P), offset=virtual_address mod P and physical_address=frame×P+offset.
A valid nonresident page access faults and may require loading data; invalid or forbidden accesses can also fault.
A cache miss, TLB miss and page fault are different events; not every page fault reads a disk, since zero-fill and already-resident shared pages exist.
An HDD stores magnetic patterns on tracks divided into sectors; reads/writes access addressed blocks while platters rotate.
A head normally stays over a track while reading but moves radially for seeks.
It does not need continuous power to preserve stored bits.
SSDs use nonvolatile semiconductor storage without mechanical seek.
Optical media use lasers; tape is suited to sequential streaming and archives.
An Ethernet cable is a communication medium, not a disk or RAM.
In textbook access taxonomy, tape is sequential, disk is direct access with positioning delay, RAM is random access with broadly address-independent timing, and associative access matches content. “Random-access disk” is also common informal usage; specify the taxonomy when comparing direct and random access.
Optical access ranges such as 100–300 ms are historical examples, not universal device specifications.
A peripheral performs input, output or storage outside the CPU’s execution core; CPU itself is not a peripheral.
Input units encode external information and output units present processed results.
A device controller handles device protocol/timing; its interface commonly exposes data, status and control registers.
Buffers absorb speed differences and error/status bits report conditions.
Control commands start actions, test/status commands inspect readiness or errors, read commands bring device data toward the system, and write/output commands send system data to the device. “Issue” describes sending a command, not a standard fourth command category.
A controller is hardware; a driver is software that operates it.
COA31 I/O address spaces, priorities and handshaking
Memory-mapped I/O assigns device registers addresses in the memory address space and uses suitable load/store operations.
Isolated/port-mapped I/O has a separate port space and special instructions such as IN/OUT.
MMIO must respect device access widths, ordering and side effects; a status read is not necessarily a harmless RAM read.
Asynchronous handshaking uses request/ready and acknowledgement signals to tolerate unequal speeds: sender presents data and requests, receiver accepts and acknowledges, then each withdraws its signal.
A single strobe lacks this feedback.
Interrupt priority selects among simultaneous requests, using schemes such as polling, daisy chains or priority hardware.
Serial sends bits over time; parallel transfers multiple bits on multiple lines, without guaranteeing higher real-world speed.
USB is a serial peripheral interconnect used by keyboards and external storage; RS-232 specifies a traditional point-to-point serial electrical/interface standard.
Both RS-232 and USB use serial communication; distinguish their interface roles and specifications.
HDMI carries digital video and audio.
Ethernet connects network devices; it is not memory.
SATA is a storage interface; legacy IDE/PATA and SCSI represent other storage connections, while iSCSI carries SCSI commands over IP.
PCI is a peripheral expansion interconnect, not a disk protocol; connecting unlike bus segments requires suitable bridge/controller logic. “Extends processor-bus connectivity” without topology does not uniquely identify PCI or Multibus.
POSIX is a software interface standard with operations such as open/read/write/close; ASCII is a character encoding.
An unqualified “standard PC disk interface” needs an era or device requirement.
COA33 Analog interfaces and component identification
An ADC measures an analog input and produces a digital code; a DAC produces an analog output from a digital code.
ADC080x parts are 8-bit successive-approximation analog-to-digital converters; DAC0830 is a digital-to-analog converter, while 82C55 denotes a programmable parallel I/O interface, not an ADC.
Component names are not interchangeable with the direction of conversion.
For an ideal n-bit converter spanning a voltage range V, one code step is approximately V/2^n; actual endpoint conventions and specifications must be stated.
Quantization rounds an analog range into discrete codes; sample rate and resolution measure different properties.
A pipeline overlaps stages of different instructions; it primarily improves throughput.
In an ideal k-stage single-issue pipeline, n instructions take k+n−1 cycles when stages are balanced and there are no stalls.
Without overlap, comparable work takes nk stage cycles.
The ideal steady-state completion rate is one instruction per cycle, while an individual instruction still spans multiple stages.
Choose the pipeline clock using the slowest stage plus register overhead.
Fill/drain overhead matters for short streams. “Fetch/decode one instruction while executing another” describes pipelining, whereas issuing several instructions in one cycle requires multiple-issue resources.
COA37 Multiprocessing, vectors and Flynn classification
Flynn classifies instruction and data streams: SISD has one of each; SIMD applies one instruction stream to multiple data elements; MIMD uses multiple instruction and data streams; MISD has multiple instruction streams for a common data stream and is uncommon.
A vector instruction describes an operation over a sequence of elements; physical lanes may process them in batches, not all in one instant.
SMP processors share memory/I/O and have peer roles under an OS.
Distributed-memory systems communicate between separate address spaces.
More cores increase available parallel work, but serial dependencies and coordination limit speedup. “Core i7” is a product family rather than one core count; a model number is essential.
COA38 Historical conventions and processor-width caveats
The familiar generation convention associates first with vacuum tubes, second with transistors, third with integrated circuits and fourth with microprocessor/VLSI-era personal computers.
Stored-program machines arose in the first era.
High-level languages became prominent around the transition into the second; introduction dates do not fit every generation boundary.
Magnetic-core memory spanned more than one era, so “witnessed use” cannot identify exactly one.
Several generations improved performance.
Integration generally reduced individual component dimensions while capacity, density and processor performance grew; these are trends rather than guarantees for every model.
Intel’s 80386 introduced 32-bit x86 execution in 1985, before 80486/Pentium; the 80286 was a 16-bit predecessor.
An n-bit processor label does not force its PC, IR or address register to be n bits.
COA39 Identify architecture assumptions before answering
Main memory, registers and cache can all provide temporary storage; identify the scope and role. Memory can also include nonvolatile ROM/flash, so distinguish RAM when comparing power-off data retention with disk storage.
Architecture lifetime, power efficiency and generational improvements require assumptions; definitions alone do not make these exclusive.
For a TEST-instruction question, identify the instruction and the complete statements being compared before drawing a conclusion.
Identify a logic gate from its actual graphical symbol.
An opcode can be identified from an explicit description of its operation-field role even without a figure.
Check that the question includes the phrase, choices or diagram needed to apply the relevant architecture rule.
Intel’s desktop comparison chart lists the Core i7-920 with four physical cores and eight hardware threads. Core count and thread count are distinct specification fields: use the exact processor model and the field requested rather than inferring a count from the Core i7 family name.
A bus is a set of common signal lines used to transfer binary information among connected units. In a parallel register bus, one line carries each bit position; control signals select a source and enable the intended destination. Storage registers and memory retain information, while the bus provides a transfer path.
COA-S03 The basic single-accumulator memory instruction
In the textbook single-accumulator organization, a memory-reference instruction has an operation part and an address part. The address locates a memory operand; the operation combines that operand with the accumulator as required. The address field is not the operand value itself, and this simple format does not describe every addressing mode or instruction set.
COA-S04 Textbook instruction-set and control tendencies
RISC means Reduced Instruction Set Computer; CISC means Complex Instruction Set Computer. The textbook RISC design pairs a relatively large register set, load/store access and easily decoded instructions with hardwired rather than microprogrammed control and an efficient pipeline. These are design tendencies, not guarantees of one-cycle latency or lower power for every implementation.
COA-S05 Instruction and stack pointers in 64-bit x86
In Intel 64-bit mode, RIP holds the offset of the next instruction to execute. RSP is the 64-bit stack pointer, extending the ESP/SP stack role. These pointers are distinct from CS and SS, which are code and stack segment registers.
The circled plus symbol ⊕ denotes exclusive OR. For two Boolean inputs, A⊕B is 1 exactly when the inputs differ; an overbar or output inversion would complement this result.
A flip-flop is bistable: it has two stable states representing 0 and 1. While powered, it can retain one bit until an input or designated clock event changes its state. Multiple flip-flops are required to represent a multi-bit counter state.
Learn how signals become frames, packets and application data, then practise address plans with explicit masks.
This chapter develops all four blueprint outcomes through networking concepts and practical procedures.
Trace one message down and up the layers; distinguish MAC, IP and port addresses.
Calculate masks, network/broadcast bounds and capacity before looking at choices.
Allocate largest LANs first and validate the full plan.
Use comparison tables and microexamples for retrieval practice, then explain why competing answers fail.
Check the protocol, addressing and scope assumptions before selecting an answer.
Sections in this course
NET01 Communication components and quality
Data are raw representations; information is data interpreted for a purpose.
Communication requires a message, sender, receiver, medium and agreed protocol.
A source creates data; a transmitter converts it to a signal; a receiver reconstructs data.
Distance affects engineering but is not a sixth component.
Delivery means reaching the intended recipient; accuracy means preserving content; timeliness means meeting a deadline; jitter means variation in arrival delay.
A call can have acceptable average delay yet sound broken because of jitter.
Throughput measures achieved transfer rate, reliability measures dependable operation, and security concerns unauthorized actions.
Scalability means accommodating growth without unacceptable service degradation.
Transmission delay is packet bits divided by link bit rate; propagation delay is distance divided by signal speed.
Processing and queueing add delay.
A 1000-byte packet takes 0.8 ms to serialize at 10 Mbit/s; increasing line rate does not reduce propagation time.
Attenuation reduces signal strength.
Distortion changes shape, often because frequencies have different delays.
Noise adds unwanted energy: thermal noise comes from random thermal motion, crosstalk leaks from nearby channels, and impulse noise is a short disturbance.
Amplifiers amplify noise too; digital repeaters regenerate decisions but cannot reconstruct every corrupted bit.
Simplex is one way, half duplex alternates directions, and full duplex permits simultaneous sending/receiving.
A walkie-talkie is half duplex; a telephone conversation uses full duplex.
Serial sends sequential bits; parallel uses multiple conductors and may suffer skew.
A NIC supplies a computer’s network interface and commonly implements both physical and link functions.
Calling a NIC a physical interface does not mean all its functions are layer 1.
Physical specifications include connectors, signaling, voltage, timing and physical coding/modulation; the PHY interface to MAC handles hardware signaling.
A repeater regenerates layer-1 signals without inspecting destination addresses.
An active hub is a multiport repeater: it repeats incoming signals onto other ports, placing half-duplex endpoints in one collision domain.
A passive hub is a connector.
A hub neither learns MAC addresses nor eliminates collisions.
An endpoint such as a network printer consumes services; routers, hubs and access points are intermediary devices.
In the legacy IEEE 802.3 architecture with an attachment unit interface (AUI) and medium attachment unit (MAU), the MAC interfaces to the Physical Signaling (PLS) sublayer.
For this legacy MAC interface, the relevant sublayer is PLS.
This name is architecture-specific: other PHY designs use reconciliation (RS), physical coding (PCS), physical medium attachment (PMA) and related sublayers.
Do not present PLS as a universal OSI sublayer name.
A bridge or ordinary Ethernet switch operates at layer 2.
It learns source-MAC-to-port mappings, looks up the destination, forwards a known unicast to its port, filters it if the destination is on the incoming segment, and floods an unknown unicast or broadcast within its VLAN.
A switch does not always send only to one destination port.
Wireless access points normally bridge wireless and wired link-layer traffic.
Each switch port separates collision domains; full-duplex point-to-point Ethernet has no collisions and does not use CSMA/CD.
Routers forward IP packets between networks using destination prefixes and next hops.
They separate broadcast domains and normally do not forward local link broadcasts.
A default gateway is usually a router, while a protocol gateway can translate application formats; therefore a gateway is not inherently a device that implements every OSI layer.
A firewall allows, rejects or inspects traffic under a security policy; it does not necessarily encrypt.
A VPN, Virtual Private Network, provides a logical private connection over another network; a secure VPN authenticates/encrypts its tunnel.
A modem modulates outgoing and demodulates incoming carrier signals.
These functions may coexist in one home router but remain conceptually distinct.
Sending proceeds from application data to transport segment/datagram, network packet, link frame and physical bits/symbols; receiving reverses the order.
Each layer serves the layer above.
A router removes a received link frame, inspects IP, and creates a new link frame for the next hop.
MAC addresses usually change across routed hops; end-to-end IP addresses ordinarily remain until translation.
Layer
Main duty
Typical unit/address
7 Application
Network services for applications
Message/data
6 Presentation
Representation, compression, encryption roles
Data
5 Session
Dialog setup, checkpoints, recovery
Data
4 Transport
Process delivery, segmentation; protocol-dependent reliability
TCP segment or UDP datagram; port
3 Network
Logical addressing and routing
Packet; IP
2 Data link
Hop delivery, framing, MAC access and error detection
Link-layer LLC identifies or multiplexes upper-layer protocols and may supply link control; MAC handles medium-dependent addressing/access and frame delivery.
Network addressing belongs to layer 3.
Ethernet, PPP and HDLC are link protocols.
Frame headers may carry addresses and control/type fields; synchronization and exact framing depend on the protocol.
Detection adds redundancy but does not guarantee correction.
Even parity adds a bit so the total number of ones is even: 1011 needs parity 1.
It detects every odd number of bit flips but misses even counts.
CRC treats bits as a polynomial and appends the XOR-division remainder; the receiver repeats the division.
Internet checksums add words with end-around carry and complement the sum.
A burst spans from the first corrupted bit through the last, including unchanged interior bits.
Retransmission or sufficient forward-error-correcting redundancy is needed for recovery.
PCM digitizes analog input by sampling, quantizing and encoding.
Sampling must exceed twice the highest retained baseband frequency in practical designs; b-bit samples have 2^b quantization levels and uncompressed rate fs×b. PAM/PWM are pulse modulation methods; pulse amplitude or width alone is not a binary PCM code.
OSI session roles establish/manage dialogs and can coordinate checkpoints so transfer resumes after interruption.
Presentation roles translate encodings and handle compression/encryption.
Compression reduces representation size; encryption hides content and need not shrink it.
Application protocols provide services directly to applications.
Practical implementations distribute these functions differently; TLS is not proof of a separate physical presentation-layer device.
The four-layer TCP/IP model folds OSI layers 5–7 into application, retains transport, calls layer 3 Internet, and combines link/physical as network access.
A model is a guide to functions, not a guarantee that every application gets a reliable network.
Distinguish end-to-end application service from its underlying process-to-process transport.
DNS resolves names to records, including IPv4 A and IPv6 AAAA addresses; it can use UDP or TCP port 53.
DHCP dynamically leases IPv4 settings, commonly address, mask, gateway and DNS server.
Its basic exchange is discover, offer, request, acknowledge.
IP itself does not assign addresses.
ARP resolves an on-link IPv4 next hop to a link address, using a broadcast request and normally unicast reply.
For an off-subnet target, ARP resolves the gateway, not the remote target’s MAC.
It bridges the network/link addressing boundary and is often classified at the link layer; calling ARP simply a network protocol uses a loose textbook convention.
RARP reverses hardware-to-IP lookup; BOOTP/DHCP support boot configuration.
ICMP reports errors and diagnostics; IGMP manages IPv4 multicast membership.
These are separate companion protocols, not four pieces whose combination is IP.
RFC1918 private blocks are 10.0.0.0/8, 172.16.0.0/12 (through 172.31.255.255), and 192.168.0.0/16.
They can be reused internally but are not globally routed as public destinations.
A LAN may also use legitimately assigned public addresses; private is common, not mandatory. 127.0.0.0/8 is IPv4 loopback, commonly 127.0.0.1, for local protocol access without an external link. 255.255.255.255 is limited broadcast; 0.0.0.0 can identify an unconfigured source.
Link-local/APIPA uses 169.254.0.0/16, with edge /24 blocks excluded from normal automatic selection.
IPv6 has 128-bit hexadecimal addresses, flexible prefixes and no IPv4-style broadcast.
Sources, not routers, fragment IPv6 packets.
IPv6 does not automatically encrypt traffic or make authentication unnecessary.
Compare IPv6’s larger 128-bit address space and encryption support separately; specify the property being evaluated.
A /p IPv4 prefix has p leading one bits followed by 32-p zeros.
Partial octet masks are 128,192,224,240,248,252,254. /19 is 255.255.224.0; /20 is 255.255.240.0; /21 is 255.255.248.0, correcting the study guide’s 255.248.0.0 mistake.
Compute network=address AND mask.
Host bits zero identify the block start; host bits one give broadcast.
With 172.16.28.252/20, the third octet is grouped in blocks of 16, so the network is 172.16.16.0 and broadcast 172.16.31.255.
A written host/prefix such as 172.105.180.0/21 need not be an aligned block label: masking yields 172.105.176.0/21.
For ordinary broadcast LANs let h=32-p. Total addresses=2^h; usable hosts=2^h-2, reserving network and directed broadcast.
Find the changing octet’s increment as 256-mask octet, round the address down to a multiple, and extend through the next boundary minus one.
192.168.2.64/26 spans .64–.127; usable .65–.126 gives 62 hosts. 192.168.10.25/28 spans .16–.31, so its network is .16. 172.17.128.0/21 spans 172.17.128.0–172.17.135.255; .128.255 and .135.0 are valid interior hosts, but .135.255 is broadcast. /27 gives 32 total and 30 usable, not 32 usable.
VLSM assigns different masks to different LAN sizes.
Sort demands largest first, round each to a power-of-two address block including reservations, allocate aligned nonoverlapping blocks within the parent, and leave the remaining space explicit.
For a /24 with LAN demands 100,60,29: allocate .0/25 (hosts .1–.126), .128/26 (.129–.190), and .192/27 (.193–.222); .224/27 remains.
Two remote LANs of 100 each fit .0/25 and .128/25 within a separate /24.
Count router interfaces as hosts if not already included in the demand.
Implementation assigns unique usable IPs/masks, puts each default gateway in its local subnet, configures router interfaces/routes and DHCP exclusions, then tests local reachability, gateway reachability, remote routing and DNS separately.
Check duplicate addresses, overlap and return routes before blaming an application.
A conventional /30 has four addresses and two usable endpoints; check the link and addressing assumptions when selecting a WAN prefix.
RFC3021 permits /31 on supported point-to-point links: both addresses are endpoints, so the subtract-two rule does not apply. /32 identifies one address/host route.
Do not claim /30 is universally the smallest valid link prefix.
CIDR, Classless Inter-Domain Routing, replaces rigid class allocation and supports aggregation.
Combine contiguous aligned blocks sharing leading bits; unrelated adjacent-looking labels may not aggregate cleanly.
Four consecutive /26 blocks covering a /24 summarize to /24.
More-specific routes must remain available where the aggregate would otherwise send traffic to the wrong next hop.
Static NAT gives a fixed address mapping; dynamic NAT allocates mappings from a pool.
PAT/NAPT maps address-plus-port combinations so multiple private clients share a public address.
It is translation, not ARP resolution and not encryption.
Return traffic must match the translation state or a configured inbound mapping.
A private host such as 10.0.0.1 commonly reaches the public Internet through NAT at a gateway, together with valid routing and a public external address.
NAT alone does not supply a physical connection or DNS.
A public address does not automatically grant permission to use it; both public and private unicast addresses can be used on a LAN under the correct allocation and subnet.
Routing computes paths; forwarding chooses a next hop for an individual packet.
Select the matching route with the longest prefix, then apply the routing system’s tie-breaking criteria.
A default /0 matches when nothing more specific does.
Static routes are configured; dynamic protocols exchange reachability.
Distance vector uses neighbor estimates, while link state distributes link information and computes shortest paths.
Interior protocols operate within an autonomous system; BGP exchanges routes between systems.
Flooding sends copies on eligible outgoing links with duplicate/lifetime controls; random walk picks a neighbor probabilistically.
Unicast targets one destination, broadcast all in a scope, multicast a subscribed group and anycast one member sharing an address, normally nearest under routing metrics.
Multi-destination packets can list multiple targets; this is not necessarily identical to broadcast.
Group multicast trees use mechanisms such as reverse-path checks; Ethernet spanning tree is a different layer-2 mechanism.
Circuit switching sets up a path with reserved resources, transfers data, then releases it.
Predictable allocated bandwidth trades against setup/blocking and wasted reservation during silence.
A traditional telephone call is the standard example.
Packet switching divides data into packets that share links statistically; queueing can add variable delay and loss.
This does not make modern voice-over-packet impossible: buffering, scheduling and capacity planning manage it.
Datagram packets are forwarded independently.
Virtual circuits establish forwarding state, but resource reservation is optional, not a necessary property of every virtual circuit.
Message switching stores a complete message before forwarding, without a dedicated end-to-end path.
Packet store-and-forward waits for the full packet/frame; cut-through starts after enough header arrives; fragment-free historically waits through the initial collision-sensitive portion.
No routing algorithm guarantees that every packet always takes the geometrically shortest route.
Multiplexing combines multiple input streams onto a shared link; demultiplexing separates them at the receiver.
It differs from broadcasting one message to many destinations.
FDM assigns distinct frequency bands with suitable guard spacing; WDM assigns different optical wavelengths.
TDM allocates time slots: synchronous TDM reserves recurrent slots even if an input is idle, while statistical TDM allocates according to demand and needs identification.
FDMA and TDMA allocate frequencies or time among users; CDMA separates coded signals.
Physical multiplexing is different from transport port multiplexing.
Combining signals onto a shared link is multiplexing; distinguish it from point-to-point connectivity, broadcast, synchronization and multicast.
NET33 Identify networking layers and addressing assumptions
First identify the exact layer, protocol and scope.
Flow/error control can exist at both link and transport layers; MAC addresses can be locally administered; bridges and switches both operate at layer 2.
A LAN can use public or private unicast space.
UDP and IP are both connectionless.
Session dialogs and TCP connections are distinct senses of connection.
Distinguish the protocol, layer and scope before treating these descriptions as exclusive.
A host address without a prefix does not determine capacity unless the question explicitly assumes historical classful addressing.
A subnet count needs a parent block.
Excluding subnet zero and the all-ones subnet is an obsolete convention; apply it only when explicitly stated.
Choose a networking concept by its definition rather than by repeated distractors.
Read complete, unambiguous option labels before matching them to networking concepts.
Adaptive or dynamic routing changes routes in response to updated network information; nonadaptive or static routing uses configured choices. Distributed routing means routers perform computations using exchanged information instead of requiring one central route computation. These properties do not imply random next-hop selection: the path-selection rule is a separate classification.
NET-S02 Management, traffic service and application transport bindings
SNMP means Simple Network Management Protocol. Its management applications monitor and control managed devices, such as hosts and routers, by exchanging management information with their agents. This device-management role differs from transferring email, resolving names or mapping an IP address to a MAC address.
In the conventional service bindings, FTP control, SMTP mail transfer and Telnet remote terminals use TCP. DNS supports both UDP and TCP on port 53; it is not exclusively a UDP service. The application protocol’s service role is distinct from the transport carrying its messages.
Quality of service (QoS) controls traffic treatment to meet objectives such as throughput, delay, jitter or loss. Classification, queue scheduling and allocation of buffer or bandwidth resources implement such treatment. QoS concerns delivered service behavior; scalability concerns accommodating growth, and security concerns unauthorized actions.
The finite IPv4 address space has faced allocation scarcity. Private addressing with NAT conserves public IPv4 addresses, while IPv6 provides a much larger address space.
A computer network connects computers or other devices so they can exchange information and share resources such as files, storage and printers. The interconnection uses both hardware and software; neither hardware alone nor software alone is the definition of the whole network.
NIC expands to Network Interface Card. It is the host’s network interface, providing the connection through which the host sends and receives network signals. A cable connector attaches the medium to that interface; it is distinct from an intermediary switch or router.
NET-S05 Network-access technologies and geographic use
Ethernet and Token Ring are traditional LAN technologies. X.25 and Frame Relay are traditional WAN technologies. TCP/IP can run over different network-access technologies; its Internet-layer packet service does not require one particular link medium or frame format.
NET-S06 Interface addresses and transport-number namespaces
An IP address identifies a network interface rather than limiting a whole computer to one address. A computer or router can have several interfaces and addresses. Under a supplied IPv4 prefix, leading bits identify the network and the remaining bits identify an address within that network; a MAC address is a separate link-layer identifier.
TCP and UDP port fields are 16 bits, allowing numbers from 0 through 65535. Well-known ports are 0–1023, registered ports are 1024–49151, and dynamic/private ports are 49152–65535. Client endpoints can use dynamically selected ports instead of every application requiring a well-known assignment. These port numbers are distinct from the IP version and upper-protocol fields.
A bridge or switch’s MAC address table is its learned forwarding database: it associates MAC addresses with ports for frame forwarding. It differs from an ARP cache, which associates an IPv4 next hop with a link address, and from a routing table, which selects next hops for IP prefixes.
A common IPv6 unicast subnet uses a 64-bit subnet prefix and a 64-bit interface identifier. This split does not make the complete address 64 bits: it remains 128 bits. Special uses and explicitly different prefix lengths must be considered separately.
NET-S07 Physical signaling and legacy Ethernet cable roles
Fiber-optic links can use near-infrared light. The selected optical wavelength is part of the link’s physical signaling specification, just as connectors and electrical signal levels are physical-interface specifications. This does not require every fiber link to use the same wavelength.
For legacy fixed Ethernet port roles, PCs and router Ethernet endpoints use the same endpoint role, while ordinary switch ports use the opposite role. Thus a direct router-to-PC link uses crossover wiring; PC-to-switch or router-to-switch uses straight-through wiring. Automatic MDI-X can remove the need to choose the crossover manually.
Ethernet switches can have fiber-optic interfaces with suitable optical transceivers. A forwarding role therefore does not impose a copper-only restriction: distinguish what the device does with frames from the physical medium used by its ports.
Intermodulation distortion occurs when multiple signals interact through a nonlinear component and generate unwanted combination-frequency products. Its mechanism differs from random thermal motion, adjacent-channel leakage and an isolated impulse disturbance.
Learn each structure through its rules, representation and operation traces.
The seven blueprint items require understanding common structures, implementing searching and sorting, and selecting structures for practical problems.
This chapter develops core data structures and algorithms through definitions, traces and cost comparisons.
Draw the representation, label indices or pointers, and state the empty/full convention before tracing.
Compare costs under the same assumptions: fixed capacity or resizing, balanced or arbitrary tree, expected or worst case.
Practise without answer keys, then justify every choice using an invariant or a short calculation.
Sections in this course
DSA01 Start with the data and the required operations
An abstract data type (ADT) defines values and operations; representation supplies implementation.
Arrays or linked nodes can implement the same LIFO stack.
Abstraction keeps relevant details: patient urgency and arrival order matter for service; hair colour does not.
Arrays, linked lists, stacks and queues are linear.
Trees model hierarchies; graphs model general connections.
A record grouping integer, character and floating fields is heterogeneous; an ordinary array has one element type.
For eventually nonnegative functions, f(n)=O(g(n)) means f(n)≤c g(n) for some positive c beyond a threshold k. Omega reverses the inequality; Theta requires both.
Little-o means f/g tends to zero; little-omega means it grows without bound.
These relations can describe best-case, average-case, worst-case or space functions.
For n≥1, 3n²+4n+1≤8n²: c=8,k=1 witness O(n²).
Constants and lower-order terms disappear from tight polynomial growth.
Transitivity multiplies witnesses: f≤c g≤cd h beyond both thresholds.
Infix places an operator between operands and uses precedence and parentheses.
Prefix places it first; postfix places it last.
Their fixed operator arity determines grouping.
To convert infix to postfix, output operands immediately and hold operators on a stack.
Pop higher-precedence operators before pushing a new operator; also pop equal precedence for left-associative operators.
Parentheses temporarily override this order.
To evaluate postfix, push operands.
At a binary operator, pop right operand first, then left, and push left op right.
Build an expression tree for either prefix (preorder) or postfix (postorder); a stack is useful but is not the only possible conversion representation.
DSA15 Circular buffers: logical order differs from physical slots
A simple noncircular array queue may report overflow when rear reaches the final index despite released slots at the front.
A circular queue reuses slots with modulo arithmetic.
Use a count convention: front points to the next removal, size counts items, and insertion slot is (front+size)%C. Empty means size==0; full means size==C.
Dequeue reads A[front], sets front=(front+1)%C and decreases size.
An alternative reserves one unused slot and uses next(rear)==front for full; its empty test and capacity differ.
DSA17 Priority queues serve by priority, with an explicit tie rule
A priority queue returns the smallest or largest priority key under its convention.
Urgent patients may precede earlier arrivals.
Insertions and extractions can interleave.
Binary heaps support constant peek and logarithmic insert/extract.
Arrays and lists can also implement priority queues: an unordered sequence gives cheap insertion but linear extremum removal; an ordered sequence reverses that tradeoff.
Equal priorities have no inherent FIFO guarantee.
If stable service is required, compare (priority, arrival_counter).
Choose the priority direction and tie rule before tracing.
DSA21 BST deletion preserves every subtree restriction
A leaf can be detached by clearing its parent link.
For one child, make the parent bypass the node and point to the child.
For two children, copy the inorder predecessor (left-subtree maximum) or successor (right-subtree minimum), then delete that replacement from its original location.
That second deletion has at most one child.
Deletion by merging is another approach.
Promote the right subtree and attach the entire old left subtree to the minimum node in the promoted right subtree; or use the symmetric left promotion.
Update root itself when deleting root.
Copying values and reconnecting subtrees can yield different valid shapes, so a trace must name its deletion method.
DSA25 Hash addresses, uniformity and random function choice
Direct addressing reserves a position for every possible key in a finite universe U, costing Theta(|U|) slots.
A hash table uses h(key) in 0..m-1 and stores only actual entries plus bucket capacity.
With h(k)=k mod 6, key 36 has home address 0; collisions may move its final storage position.
Determinism means repeated equal keys get the same address for the chosen function.
Uniformity means expected keys spread evenly.
Universal hashing chooses one function randomly from a suitable family for the table, independently of a fixed key set; it does not choose a fresh unrelated function for each lookup.
Random choice controls collision probability, not a promise of zero collisions.
DSA31 Compare sorting rules, not just algorithm names
Stable sorting preserves the input order of equal keys.
An in-place element algorithm uses a fixed amount of extra element storage; a recursive call stack may still matter when total auxiliary space is requested.
There is no single algorithm identified by stable or in-place alone.
State the implementation, input case and resource being compared.
DSA37 Merge sort and internal versus external sorting
Split into halves, sort them, then merge by advancing the smaller current front.
With left-first tie handling, equal keys retain order.
Ordinary array merging needs a linear auxiliary buffer.
There are logarithmically many levels with linear merge work per level, giving n log n time even on sorted input unless an optimization skips merges.
Top-down mergesort recurses; bottom-up merges runs of widths 1,2,4,… iteratively.
In-place merging variants exist with different tradeoffs; linear merge names an operation, not a universally standardized sort variant.
Internal sorting fits the working dataset in memory.
External sorting builds sorted runs and merges buffered streams from disk, aiming to reduce I/O. Reverse order alone does not characterize maximum merge comparisons.
Mark a vertex, then recursively visit each unmarked neighbour before continuing with later neighbours.
An explicit stack can store pending work instead.
Both implement latest-pending-work first; a queue would change that discipline.
Marking prevents infinite repetition around graph cycles.
Using the same graph and alphabetical neighbours, recursive DFS can discover A,B,D,C. Its path is a valid reachability witness but not necessarily shortest.
Adjacency-list cost is O(V+E), with O(V) visited state and possible stack depth.
DFS supports cycle and connectivity analysis; a directed cycle test distinguishes active recursion vertices from already completed ones.
DSA43 Shortest paths and spanning trees solve different objectives
For nonnegative weights, standard Dijkstra initializes source distance zero and others infinity, repeatedly finalizes the unsettled vertex with smallest distance, and relaxes each outgoing edge: dist[v]=min(dist[v],dist[u]+w(u,v)).
A min-priority queue supports the next choice.
BFS is enough when every edge has equal cost; negative edges require another justified method, such as Bellman–Ford.
An MST minimizes the total cost of connecting all vertices of a connected undirected weighted graph.
Prim adds the cheapest edge crossing from its current tree to an outside vertex.
Kruskal processes edges by increasing weight and rejects those joining vertices already connected.
An MST need not give shortest source-to-vertex routes, and equal weights can permit several MSTs.
DSA45 State trace data and representation assumptions
A trace needs the complete operation sequence, initial state, capacity and output orientation.
State these assumptions before calculating.
Evaluate all choices against the rules; a selected answer does not make other valid choices false.
Specify whether a question asks which structure can implement something or which is best under stated costs.
ADTs do not force one representation, and serial-access memory is not inherently LIFO.
A heap file is an unordered database record file, unrelated to a binary heap: insertion uses available space, scanning can find records, and ordered output requires sorting or an index.
DSA-S01 Best, average and worst compare equal-size inputs
Fix the input size before comparing cases. Best-case cost is the minimum resource use over legal inputs of that size; worst-case cost is the maximum. Average-case cost averages costs using a stated input distribution. These three input-case functions can each be described using upper, lower or tight asymptotic bounds; the case name does not select the bound notation.
For successful binary search with all stored positions equally likely, average probes have order Theta(log n). The probe decisions form a binary tree: only a bounded number of positions occur in shallow levels, while a constant fraction require logarithmic depth. Interval halving also gives the logarithmic upper bound. A distribution concentrating on an immediate midpoint hit would give a different average.
An interrupt service routine may need to record work quickly and defer its completion. Operating systems can queue that deferred work for later processing; Windows deferred procedure calls are one concrete example. This is a queue application, but it does not imply that every interrupt system uses a single FIFO service policy.
A linked binary-tree node stores a payload and two child pointers, one for the left child and one for the right child. A null child pointer means that child is absent; a root pointer gives access to the whole tree. In a dynamically allocated version, insertion can allocate a node and attach it through the appropriate child link.
A B-tree is a balanced multiway search tree. Its allowed branching factor can exceed two, so a general B-tree is not the binary-tree family. Balanced describes a height discipline; it does not by itself restrict every node to two children.
Divide and conquer reduces a problem to smaller instances of the same kind, solves the required smaller instances and obtains the original result from them. Mergesort recursively sorts two halves and merges; quicksort partitions and recursively sorts the resulting ranges. This course also classifies binary search as divide and conquer: an ordered comparison selects the only half that can contain the target. This is different from simply repeating adjacent swaps, choosing successive minima, or making stable LSD digit passes.
Build a connected model of browser markup, CSS, JavaScript, server processing and persistent data.
Read code literally before tracing it.
Unless a section explicitly discusses legacy syntax, JavaScript means modern ECMAScript in a browser and PHP means PHP 8.x; database examples use MySQLi or PDO with a configured MySQL connection.
Trace input → request → server validation → database → response → DOM update, including failures and permissions.
Practise CSS winner/box calculations and small JS/PHP traces; record values and types after every statement.
Compare GET/POST, browser/server state, callbacks/concurrency and parameterization/output encoding.
Check task assumptions and code validity before selecting an answer.
Sections in this course
WEB01 Browser, server and technology roles
The Internet connects networks; the Web is a resource system commonly using HTTP.
A browser/user agent requests resources and renders HTML/CSS, then runs permitted JavaScript.
A web/HTTP server receives requests and returns representations, sometimes invoking application code.
Client and server are roles and can run on the same machine.
HTML supplies structure/meaning; CSS controls presentation; JavaScript supplies programmable interactivity.
PHP, Python, JSP/Java and ASP.NET applications generate server responses and access databases; C# is commonly used with ASP.NET.
Node.js is a JavaScript runtime, not a separate language.
JavaScript can run on either side.
Browser scripts are sandboxed, but may access selected files/devices through permission-based APIs.
They are not inherently limited to trivial programs, nor can they freely access arbitrary client hardware.
WEB02 Hosting, URLs and static versus dynamic content
Hosting supplies an environment where a site is served; domain registration reserves a name, and DNS maps names to network records.
An ISP provides connectivity.
A URL identifies scheme, host, optional port, path, query and fragment; the host identifies the machine/service name, while a fragment selects a local document location.
A basic static server returns stored files; dynamic processing constructs a representation from logic, requests or data.
Static pages can still run interactive browser scripts, and dynamic generation need not change visible text every time.
A website groups resources; a page is one document/resource.
Open standards do not guarantee identical support for every feature in every browser.
Historical editor-name items refer to Microsoft FrontPage and Macromedia HomeSite5, not languages or required modern tools.
HTML means HyperText Markup Language. <!DOCTYPE html> selects modern standards mode; <html> is the document root, <head> holds metadata, and <body> contains document content. <title> supplies the page/tab title.
Meta charset declares encoding; description summarizes the page; viewport controls mobile viewport behavior.
Heading levels h1–h6 express hierarchy, with h6 conventionally smallest in default styling, not a mandatory CSS size.
<p> marks paragraphs; <br> is a line break and <hr> a thematic break. <pre> preserves source whitespace; <code> marks code. <strong> indicates importance and <em> stress; <b>/<i> have other text semantics and are not identical to importance/emphasis. <sub>/<sup> mark sub/superscripts. <!-- comment --> is not displayed but remains visible in source.
Use <a href="page.html">Read</a> for a link; href is the destination, not url/link.
A fragment such as href="#details" links to an element with id="details". target="_self" uses the current context, _blank a new context, _parent its parent and _top the top-level context.
Browser preferences determine tab versus window.
<img src="photo.jpg" alt="Students in a lab"> supplies source and alternative text.
Use empty alt for purely decorative images; informative images need meaningful alternatives.
Width/height reserve dimensions; title is not a replacement for alt.
An anchor may wrap an image.
Give controls programmatic labels, clear link text and keyboard access; visual styling alone does not establish accessibility.
Attributes belong in opening tags, with unique IDs when used for document identification.
Unordered <ul> and ordered <ol> contain <li> items.
Ordered lists can specify start and numbering type; use CSS list-style-type for presentation.
A definition list uses <dl>, <dt> terms and <dd> descriptions.
Navigation can be a semantic <nav> containing a list of links.
<table> contains rows <tr>, header cells <th> and data cells <td>; a td is not the table itself. colspan spans columns; rowspan spans rows.
Account for occupied cells before placing the next cell, and use header associations for accessible data.
CSS handles borders, background, cell padding and collapsed borders; legacy bgcolor/bordercolor are not preferred styling.
Resetting nav ul with list-style-type:none; margin:0; padding:0 removes bullets and default spacing only; it does not itself arrange links horizontally or create a dropdown.
A form’s action identifies its processing URL, method its submission method, and enctype its encoding.
The default method is GET.
Named enabled successful controls contribute values: unchecked checkboxes/radios are usually absent.
A label’s for matches the control’s id; name identifies its submitted field.
Same-name radio buttons form a single-choice group; checkboxes permit independent selections. <select> contains <option>; textarea accepts multiple lines.
For a text input, size indicates approximate visible width, whereas maxlength limits entered text length.
Neither means a server security bound. type="password" masks display but does not encrypt. submit submits; button has no submission action by itself. type=email/required give browser validation feedback; arbitrary clients can bypass it.
No GET/POST method universally means “parse one element at a time.”
An external sheet uses <link rel="stylesheet" href="styles.css"> in head; an internal sheet uses style; an inline declaration uses an element’s style attribute.
External CSS promotes reuse, consistent design and caching; it does not guarantee that every page becomes smaller or accessible.
A rule is selector { property: value; }.
Comments use /* ... */.
Type p selects paragraph elements, .notice selects a class, #logo an ID, h1,h2 groups selectors, nav ul selects descendants and nav>ul direct children.
Attribute selectors match properties such as [type="email"], pseudo-classes states such as :hover/:focus, and pseudo-elements parts such as ::before.
A selector chooses where declarations apply; it is not itself the property that sets a color.
WEB12 Resolve cascade, specificity and inheritance
First compare applicable declarations in their cascade origin, importance and layer context; then compare specificity and order within the relevant context.
In an ordinary same-origin/same-layer author example, an ID outweighs class/attribute/pseudo-class selectors, which outweigh type/pseudo-element selectors.
Compare counts lexicographically, not as an unlimited base-ten total.
Equally specific applicable rules use later source order.
An important declaration outranks a competing normal declaration in that context.
For <p id="intro" class="note">, #intro{color:blue} beats .note{color:red}.
A competing p{color:green!important} beats those normal declarations.
Inherited color/fonts apply when the element lacks a stronger specified value; margin/padding/borders do not normally inherit. :not() contributes the specificity of its argument rather than universally zero.
color sets text color; background-color sets background; font-size size, font-family face, font-style italic, font-weight weight, text-align inline-content alignment, and text-decoration effects such as underline.
Flexbox arranges direct children on a main axis; justify-content follows that axis, align-items the cross axis.
With row direction in ordinary horizontal writing, cross-axis alignment is vertical.
Grid organizes rows and columns with explicit tracks, such as grid-template-columns:1fr 2fr. vertical-align applies to inline/table-cell contexts and does not center every block. align-content distributes tracks/lines when there is applicable extra space, not arbitrary single-child centering.
Relative positioning offsets a box while retaining its flow space; absolute removes it and uses its containing block, often established by a positioned ancestor; fixed commonly uses the viewport.
Responsive design combines flexible layout, images, viewport metadata and media queries, for example @media(max-width:600px){.cards{grid-template-columns:1fr}}.
A min-width768px query targets wider viewports, not mobile alone.
Browser compatibility requires feature testing and fallbacks; responsive size handling is a different issue.
WEB15 JavaScript syntax, inclusion and declarations
Use <script src="app.js"></script> for an external .js file; script content has no HTML closing-tag syntax inside its JavaScript source.
A deferred script runs after parsing and before DOMContentLoaded.
JavaScript originated at Netscape; it is distinct from Java and supports sophisticated applications through prototype-based objects and first-class functions.
Identifiers are case-sensitive and may start with letters, underscore or $, not digits or spaces. var has function/global scope; let/const are block-scoped. const prevents rebinding but not mutation of an object’s contents. // comments end at line end; /* */ span a block.
Semicolons delimit statements, although automatic insertion exists.
Whitespace usually separates tokens but newlines can affect parsing, especially after return. “use strict” is a directive string, not a reserved statement keyword.
JavaScript primitives are undefined, null, Boolean, Number, BigInt, String and Symbol; objects include arrays, functions and dates.
Float is not a separate Number primitive type.
Arrays are objects, even though informal texts call them an array data type. typeof new Date() is "object"; typeof null is historically "object".
An unassigned declared variable or missing ordinary object property evaluates to undefined; directly reading an undeclared variable usually throws ReferenceError.
Strings use either quote style, with appropriate escaping. + can concatenate when a string is involved; arithmetic / converts ordinary numeric strings. "abc"/"def" produces NaN; nonzero Number divided by zero produces signed Infinity, while 0/0 produces NaN. parseInt("12.8",10) reads12, stopping at the dot; this is parsing, not rounding.
Global isNaN converts first; Number.isNaN does not.
Math.abs(-9)=9, Math.floor(5.9)=5, and Math.sqrt(36)=6.
A JS string’s substring(start,end) includes start and excludes end: "exitexam".substring(2,6) is "itex".
Indexes start at zero.
Array push/pop add/remove at the end; unshift/shift act at the beginning. slice returns a selected shallow copy; splice(start,deleteCount,...items) mutates by removal/insertion. reverse reverses in place. reduce combines sequentially from left to right; reduceRight combines sequentially from right to left with an accumulator, not simultaneous parallel execution.
For [1,2,3].reduceRight((a,v)=>a-v,0), accumulator values are -3,-5,-6.
An absent initial value uses the last present item first; an empty array without one throws.
for(initialization;test;update) initializes once, checks before each iteration, then updates after each body. while checks before its body; do...while executes at least once. break exits and continue advances to the next iteration.
A loop from n=1 while n<7 prints a message only at n=5 when testing n%5==0.
function f(x){return x*2;} has a parameter and returns a value; functions can be passed/stored like other values.
Arrow syntax is compact but differs in this/constructor behavior.
Runtime argument limits mean “no limit whatsoever” is too absolute. try/catch handles thrown errors during execution; throw signals one; finally runs cleanup.
Parse-time syntax errors and logical errors are different. bool ans=true is not JavaScript declaration syntax; use let ans=true.
A literal type of expression is not the typeof operator.
The DOM is a hierarchy of nodes representing the document. document.getElementById("x") returns the matching element or null; querySelector(".item") returns the first match, and querySelectorAll returns a static NodeList.
Other plural lookup methods can return live collections.
Guard missing elements and run code after the relevant markup exists.
To add a div: const el=document.createElement("div"); el.textContent="Hello"; document.body.appendChild(el);.
Creation alone does not insert it. createTextNode makes text; appendChild attaches an existing node. innerHTML parses/replaces descendants, so += reparses/replaces the prior descendant content too and can destroy listeners/state.
Use textContent for untrusted plain text. element.style.backgroundColor sets a style property; classList.add changes a class. getElementByld with a lowercase l replacing I is a different, nonexistent method.
An event handler runs when an event occurs: click, input, keydown, mouseover, submit and load are examples. addEventListener("click",handler) registers a function without calling it immediately.
Multiple listeners may coexist; once removes one after use, capture selects an earlier propagation phase and passive promises no default cancellation.
Event bubbling is distinct from the browser’s default action.
For submission, form.addEventListener("submit",e=>{if(!valid()){e.preventDefault();}}) stops the default only on failure.
Returning false from an addEventListener callback does not cancel it; return false works in an appropriate inline/onsubmit property handler whose caller uses that return.
For cancelable keyboard defaults, call preventDefault rather than assuming a different key event itself disappears.
Browser checks improve feedback; repeat validation and authorization on the server.
In a normal browser page, window exposes the browsing context and document is its document property. alert displays information, confirm returns a Boolean, and prompt requests text or returns null on cancellation. console.log logs diagnostics. location.reload() reloads the current page. screen.availHeight, screen.availWidth and screen.colorDepth have exact camelCase spelling; ColorsDepth is not the property.
window.onload is a handler property for the load event, typically after dependent resources finish.
Global let/const are not window properties like classic top-level var bindings. document.write is a method/function property; writing after document load can replace the document. document.bgColor is a legacy property; Document.bgcolor has wrong object/case.
Use document.body.style.backgroundColor for current styling.
Browser workers support concurrent computation, but DOM access normally remains on the page’s main thread.
echo is a language construct with no return value and can emit comma-separated expressions. print takes one expression and returns1.
They are two basic output constructs, not the only output mechanisms; printf, print_r and others exist.
Neither automatically inserts spaces/newlines.
Two prints of5 emit55; "I"."am" emitsIam.
Dot concatenates; + is arithmetic.
Double-quoted strings interpolate variables and escapes such as \n; single quotes normally preserve dollar names literally.
To emit literal $lfc use echo '$lfc'; or escape the dollar in double quotes.
String offsets start at zero: "maroon"[2] is r when the surrounding PHP is valid. strlen counts bytes; strpos can return integer0 or false, requiring ===false for failure. strrev reverses bytes and str_replace replaces matching content.
PHP 8==8.0 is true, but 8===8.0 is false because types differ; echo false emits an empty string, echo true emits1.
PHP sends markup as response characters; a browser then interprets it. echo "A<br>B" emits a tag in raw output but normally displays two text lines.
The invalid </br> markup depends on HTML error recovery, so specify raw versus rendered output.
Numeric arrays start at index0 unless keys are supplied: [20,12,23,19,18] has19 at index3.
Associative syntax uses a contiguous => operator: ["top"=>"black"] stores black under key"top".
Splitting it as = > is a parse error, not valid array syntax.
foreach($items as $key=>$value) iterates entries; for and while use tests/updates much like the corresponding JS forms. $sub-=$sub is $sub=$sub-$sub, not decrement.
For $sum=0; foreach([2,4] as $v){$sum+=$v;} the result is6.
A function can receive arguments, return a value, or produce output; classes/objects/variables also support server processing, so no single one of these mechanisms alone defines “dynamic PHP.” Use braces to make nesting explicit.
WEB27 Request data, server validation and injection
$_GET contains query parameters; $_POST contains supported form POST data; $_FILES upload metadata; $_SERVER request/environment details; $_COOKIE cookie values; $_SESSION session data after startup. $GLOBALS is the actual global-symbol array; $_GLOBAL is not the built-in name. $_REQUEST may combine GET/POST/cookie data according to configuration; it is not a database interface and has ambiguous precedence, so prefer the intended source. isset tests existence and non-null, not truth or valid syntax.
Read input, check required fields/type/length/range, authenticate and authorize, then process.
Bind SQL parameters to keep values separate from commands.
Encode output for HTML/attribute/JS context; textContent handles plain browser text.
A security test can detect SQL injection or XSS but does not itself fix either.
Client validation, encryption and a database connection do not replace these controls.
WEB29 Server sessions and the authorization trust path
session_start() starts/resumes PHP session handling and makes $_SESSION available.
Normally the browser holds an opaque session identifier while data resides in server-controlled storage.
A counter initializes missing $_SESSION["views"] to1 and increments on later requests. unset removes one entry; destroying stored session data is distinct from clearing the browser cookie/current variables, so logout must handle the full lifecycle.
A client cookie logged_in=1 is attacker-controlled.
If the server trusts it alone, authorization can be bypassed.
If the server checks a valid session ID and its server-side user/role on every protected action, editing that unrelated flag does not grant rights.
HTTPS does not make client-generated claims trustworthy.
Determine which server-side check is performed before judging whether a session-handling design is secure or vulnerable.
Protect session IDs, regenerate after login, expire appropriately and avoid putting sensitive tokens in URLs.
Uploads ordinarily use method="post", enctype="multipart/form-data" and a named file input. accept hints to the browser which file types to offer; it does not enforce the server’s policy.
Validate server-side size/content, inspect upload errors, use the temporary upload path, choose a safe generated destination and use move_uploaded_file.
Avoid executable storage and trusting a client filename/extension.
file_exists tests files or directories; is_file narrows to regular files. fopen returns a stream or false: r reads an existing file, r+ reads/writes without truncation, w truncates/creates for writing, w+ adds reading, a appends/creates, and x exclusively creates. fclose releases it. readfile emits content and returns a byte count, so echo readfile(...) also prints that count.
Check failures before reading/writing and constrain paths to permitted locations.
MySQL is a relational DBMS; a database persists structured application data and supports concurrent clients.
PHP8 uses MySQLi or PDO; the old mysql_* extension was removed, so migrate older snippets to a supported API. mysqli_connect(host,user,password,database,port,socket) opens a connection; selecting a database can be deferred, and defaults make several arguments technically optional.
Do not reduce the full signature to exactly one optional field.
Configure MySQLi TLS options through mysqli_init(), mysqli_ssl_set(...) and mysqli_real_connect(...) with the required verification configuration.
mysqli_ssl_connect(), pdo_connect_ssl(), mysql_ssl_connect() and secure_connect() are not substitutes for the MySQLi TLS configuration sequence above.
PDO uses an appropriate driver DSN/options instead.
MySQLi procedural functions, object methods and PDO methods have distinct signatures; affected_rows() alone is not a generic PHP function.
WHERE limits affected/matching records; omitting it from DELETE ordinarily targets every row, subject to constraints, permissions and errors.
CREATE DATABASE/TABLE defines storage; a primary key identifies rows.
AUTO_INCREMENT generates numeric values but gaps and explicit values are possible; do not promise gapless consecutive business numbering.
mysqli_query returns a result object for successful result-producing queries, true for other successful statements, or failure/exception depending on settings.
Fetch associative rows with mysqli_fetch_assoc, positional rows with mysqli_fetch_row, or objects with mysqli_fetch_object. mysqli_num_rows counts a result’s rows; mysqli_affected_rows($conn) counts changed/inserted/deleted rows under its options; mysqli_insert_id($conn) reports a generated AUTO_INCREMENT value from the connection.
Escape rendered cell text; use prepared statements for submitted values; mysqli_close closes the connection.
include evaluates another file in the current scope and warns on failure; require fails critically.
In PHP8 a failed require raises Error, which can be caught; uncaught it stops normal execution.
The source’s E_COMPILE_ERROR description belongs to older PHP. include_once/require_once avoid repeated inclusion.
Do not include a user-selected arbitrary path.
A class defines properties/methods; new creates an object, $obj->field accesses a property, and $obj->method() calls a method. public is externally accessible, private is class-restricted, and a constructor initializes an instance.
Use $this inside instance methods.
DateTime/DateTimeZone represent time and zone; diff returns a DateInterval and DatePeriod iterates intervals.
Time calculations require explicit zones and calendar assumptions, not an assumed server-local timezone.
AJAX means Asynchronous JavaScript and XML, but responses can be JSON, text, HTML or XML.
It is a technique, not a language, standalone framework or mandatory XML protocol.
Configure an XHR with open("GET",url,true), register response/error handlers and call send(). onreadystatechange may run several times; readyState4 means completion, after which status and data must be checked.
A callback is a function invoked later by the runtime/API.
The browser invokes its response handler when the response is available; the remote server does not directly execute browser code.
With fetch, await fetch(url) obtains a response, then check response.ok and parse await response.json().
Handle network/parse errors.
Starting an asynchronous operation does not make its result synchronously available to the next statement.
Avoid overwriting a newer search result with an older response that arrives late.
Long polling holds one client request until an event or timeout, returns a response, then the client reconnects; it is not continuous unsolicited streaming on that same finished response.
WebSocket establishes a persistent bidirectional message channel after its handshake.
Either HTTP-based AJAX or WebSockets can support nonblocking user interaction and carry JSON, so generic questions may be nonexclusive.
JSON represents objects, arrays, strings, numbers, Booleans and null; keys/strings use double quotes, and functions/undefined are not JSON values.
XML is another valid interchange format.
A REST API can return either.
Select transport by latency, direction, connection cost and recovery requirements, not merely the occurrence of “asynchronous.” Validate incoming messages and enforce authorization per operation.
A minimal CommonJS Node server can use const http=require("node:http"); http.createServer((req,res)=>{res.writeHead(200,{"Content-Type":"text/plain"});res.end("Hello");}).listen(8000);.
The request listener runs for incoming requests; end completes the response.
Define every variable used in startup logging, including hostname, before using it.
Node schedules JavaScript callbacks through an event loop and uses OS/worker facilities for asynchronous work.
Concurrency means overlapping progress; parallelism means execution at the same instant.
One event-loop thread can handle many waiting requests, but long CPU loops or synchronous I/O block its callbacks.
Workers/processes and a load balancer distribute work across server instances; they do not automatically coordinate shared data or session state.
Multiple clients, or one client with overlapping requests, can both create concurrency.
Suppose two requests read a stock count1, both decide it is available and both write0: two sales consumed one item.
Correctness depends on interleaving, even if each callback has only a short synchronous body.
A mutex protects one critical section; semaphores can coordinate bounded access; spinlocks busy-wait and are unsuitable for blocking a browser/event-loop thread.
Several listed mechanisms can synchronize, so mutex is not the only possible answer.
In a relational database use an atomic conditional UPDATE stock SET qty=qty-1 WHERE id=?
AND qty>0, check affected rows, and combine related writes in an appropriate transaction.
A row lock or serializable transaction can protect multi-step logic; handle rollback/retry on conflicts.
A process-local lock does not cover all load-balanced servers.
Idempotency tokens with unique storage constraints prevent a retried payment from becoming a duplicate transaction.
A framework supplies conventions and reusable structure; a library supplies callable capabilities. jQuery simplifies DOM operations; React builds component interfaces; Angular is a component platform, distinct from older AngularJS; Vue also builds interactive interfaces.
Each can contribute to a responsive interface, so those generic descriptions do not identify one unique framework.
React props pass inputs; state records changing component data; JSX needs transformation rather than being ordinary browser JavaScript syntax.
Bootstrap supplies layout/components.
The jQuery→Popper→Bootstrap dependency order is version4-era guidance; Bootstrap5 drops required jQuery.
Angular CLI commands include ng new, ng serve, ng build, ng generate and ng test, with e2e support depending on configuration. Use ng serve to start the development server.
Create React App is deprecated; recognize it as historical tooling rather than a universal current recommendation.
A CMS gives editors content creation, publishing, roles and media management without editing every source file.
A database stores persistent facts; it is not itself the whole server application.
A VCS records source history, branches and merges to support review/collaboration; deployment publishes a chosen build and is a separate operation.
SEO improves discoverability through meaningful content, headings, metadata, accessible links and crawlable structure; keyword metadata alone does not guarantee ranking.
Caching reuses a representation/result and requires validity/invalidation rules.
Server caching can hold rendered pages or expensive query results; never share private user content under an unsafe common key.
For a course-search page, write semantic headings/navigation and a labeled search form.
Use a responsive grid with a single-column fallback, then register a submit handler after parsing.
Prevent default only when implementing asynchronous submission; encode search values in the query and send GET /courses?q=.... Show loading and useful error feedback without inserting untrusted HTML.
The server validates query length/type, authenticates where required, runs a parameterized SELECT with a bounded result size, and returns JSON with an appropriate status/content type.
The client checks status, parses data and builds nodes with textContent.
For an enrollment action use POST with CSRF controls, server authorization, capacity checks and a transaction; show success only after commit.
A trace requires syntactically valid source, known initial values, execution context and output representation. x=4+"4"5 is a syntax error because an operator is missing; bool ans=true and type of new Date() are syntax errors too.
PHP with >> instead of ?> may fail parsing; analyze output only after checking the closing syntax.
The PHP array operator is =>; splitting it as = > is invalid syntax.
Distinguish response text from browser rendering: PHP may emit markup that the browser interprets, and visual line breaks need not appear in a plain-text choice.
For the assignment example above, the correct output is 60 even if it is absent from the choices.
Multiple storage techniques, interface libraries, script-capable languages and cryptographic channels often satisfy broad descriptions.
State the missing distinction before selecting an answer when the question admits several interpretations.
With x=4+"4";, JavaScript produces 44; x=4+"4"5 is invalid because an operator is missing.
The PHP string-offset example closes with ?> and prints r; using >> instead introduces a syntax error.
Check the complete code and closing delimiters before tracing output.
Apply each output prediction to the exact program being analyzed.
WEB-S01 Java and JavaScript object-oriented models
Java organizes object-oriented programs using classes, objects, inheritance and interfaces. A class describes the state and behavior of its instances; inheritance relates a subclass to a superclass, and an interface specifies operations a type agrees to provide.
For a text input, the value attribute supplies its initial text value; it does not specify the control’s width. The type attribute selects the kind of input control.
A form’s target identifies the window or frame in which the submitted result is displayed. The action identifies the processing URL, so changing the destination context is different from changing the handler.
In an input element, type="text" creates text entry, type="checkbox" an independently selectable checkbox, type="radio" a radio choice, and type="submit" a submit button. A hidden input carries a value without displaying an editable text field; it is not a password-masking control.
WEB-S03 Message display versus response collection
alert(message), confirm(message) and prompt(message) all present a supplied message. Alert is a notification; confirm additionally asks for an OK/Cancel decision, while prompt additionally offers a text field. A general message-display description therefore differs from an information-only notification.
PDOStatement::rowCount() is a method on a PDO statement object that reports affected rows for its DELETE, INSERT or UPDATE statement. It is not a procedural MySQLi function, and its behavior for SELECT result counts is driver-dependent rather than a portable row-count guarantee.
With an initialized PDO connection, $pdo->query($sql) executes an SQL statement without placeholders and returns a PDOStatement for processing its results. The connection’s configured driver determines the database; the method name alone does not mean MySQL.
MySQL is an open-source SQL database management system. Its relational data-management role is distinct from the PHP API used to connect to it.
The procedural MySQLi query form is mysqli_query($conn, $sql), using a MySQLi connection and the correctly spelled function name. The pg_query function belongs to PHP’s PostgreSQL extension; it is not a MySQL connection API.
WEB-S05 JavaScript execution, statement forms and error categories
JavaScript implementations may interpret or compile source; interpretation and compilation are execution strategies rather than competing language identities.
An if statement conditionally executes code. The legacy with statement temporarily extends name lookup and is forbidden in strict mode. A debugger statement may invoke an active debugging facility. These are keyword-introduced statement forms, unlike the quoted use-strict directive.
A syntax error prevents source from being parsed successfully. A runtime error arises while executing a program. A logical error is a defect in the algorithm or expression that can produce an incorrect result without throwing an exception.
WEB-S06 PHP statement boundaries and string escapes
A complete ordinary PHP assignment statement ends with a semicolon. A string’s closing delimiter must match its opening delimiter; a single quote can appear inside a double-quoted string without ending it.
In double-quoted PHP strings, backslash-n represents a line feed and backslash-r represents a carriage return. The written sequences are \n and \r; forward-slash sequences such as /n are ordinary text. A backslash before a dollar sign preserves that dollar sign rather than starting variable interpolation.
The basic print and echo constructs can be written with or without parentheses when their syntax permits it. Parentheses do not add spaces or change the value of the emitted argument.
WEB-S07 Default text rendering and legacy frame fallbacks
In the browser’s default presentation, an i element typically displays its text in italics. This is a rendering convention: its text semantics are distinct from the stress emphasis represented by em, and CSS may override appearance.
A legacy frameset document could include noframes content for user agents that did not support frames or were configured not to display them. Frame support was therefore not universal even in that historical model.
For finite numeric arguments, Math.abs(x) gives the nonnegative magnitude, Math.floor(x) gives the greatest integer no larger than x, and Math.sqrt(x) gives the nonnegative square root for nonnegative x. These operations differ from ordinary nearest-integer rounding; floor moves toward negative infinity.
Global isNaN(value) tests whether conversion to Number produces NaN. Number.isNaN(value) tests specifically for the Number value NaN without coercion. NaN is itself a special numeric value, not a callable checking function.
session_destroy() removes the data associated with the current PHP session. It does not itself unset every current script variable or delete the browser’s session cookie; destroying stored data, clearing $_SESSION and expiring the identifier cookie are separate parts of a complete logout.
The first digit of an HTTP status code identifies its class: 2xx means successful handling, 3xx means redirection or further action, 4xx indicates a client-error condition, and 5xx indicates a server-error condition. Classifying a code is different from identifying the precise condition represented by its last two digits.
Authentication verifies a claimed identity. Authorization checks whether a particular entity is permitted to perform a requested action. Establishing identity does not grant every permission, and neither check alone repairs unsafe SQL construction or unsafe output encoding.
The keywords metadata name supplies terms relevant to the page, while description supplies a page summary. Robots metadata supplies crawler indexing or search-presentation instructions. These roles differ from mobile viewport control.
For nonnegative integers n and positive d, n % d gives the remainder after division; zero tests divisibility. With Boolean operands, && is true only when both operands are true; it is a logical operator, not a comment delimiter.
WEB-S14 Application protocols and underlying communication
HTTP defines web application requests, response status codes and representations. An HTTP exchange can use underlying TCP connections and IP addresses; naming that network stack does not identify the application-level method or status semantics.
FTP is a file-transfer application protocol. SMTP transports electronic mail. These service roles differ from the HTTP resource request/response semantics used by a web browser. HTTPS adds TLS protection to HTTP rather than replacing its resource semantics.
A program is stored instructions; a process is an executing instance with address space and resources.
A process does not universally “manage applications” or “provide a user interface.” The PCB records identity, state, PC/registers, scheduling information, memory/accounting details and I/O/open-resource state.
A saved PC identifies where execution resumes.
A context switch saves one execution context and restores another; useful application work is interrupted by this overhead.
An interrupt or system call can switch privilege without switching process.
Task is OS-specific terminology: it may mean process, thread or schedulable entity.
No universal process-versus-task distinction follows from the word alone.
Processes arise during initialization, user requests, service requests or a running process’s creation call.
In POSIX-style systems fork() creates a child: zero is returned in the child and the child PID in the parent on success.
The two have distinct address spaces, although resources may be shared through explicit mechanisms. exec replaces the current process image; it does not itself create another process.
Normal completion and a program-detected error exit are voluntary; an unrecoverable fault or being killed is involuntary. exit() terminates normally through the runtime; abort() requests abnormal termination.
A reference to nonexistent/protected memory is a fatal fault, unlike an application deciding to exit after bad input. “Terminate exit” is not a precise standard category.
Parent termination does not universally kill all descendants.
Shared memory lets processes access a common region and requires synchronization for conflicting updates.
Message passing exchanges data through send/receive operations.
Pipes provide streams; message queues preserve messages; sockets connect endpoints; RPC requests a remote operation.
HTTP is an application protocol over a communication mechanism and can carry interprocess communication, so it is not universally “not IPC.”
Blocking send waits for the required handoff/buffering/receipt condition defined by its API.
Blocking receive waits for a message.
Nonblocking operations return promptly with data, progress or a would-block result. “Sender blocked until received” identifies blocking send under rendezvous semantics.
File locks coordinate access rather than transfer arbitrary payloads, though locking is synchronization within IPC.
Do not equate asynchronous messaging with no synchronization ever.
For arrival A, first start S and completion C, response=S−A and turnaround=C−A. For a single CPU burst B with no I/O, waiting=C−A−B. With I/O, subtract all CPU and blocked time to isolate ready-queue waiting.
Throughput=completed jobs/elapsed time; CPU utilization=busy time/elapsed time.
Minimize response/turnaround/waiting under the selected goal and maximize useful throughput/utilization.
First construct a time line with arrivals, idle gaps, preemptions and overhead, then calculate per-process values before averages.
Do not confuse first response with final completion.
Non-preemptive SJF/SJN chooses the shortest next burst among currently ready jobs.
SRTF reconsiders on arrivals and selects the shortest remaining work; a shorter newcomer can preempt.
Future burst lengths normally need estimates.
SJF minimizes average waiting for the usual fixed simultaneous ready set with known bursts and no preemption/switch cost; that theorem is not a workload-independent comparison against every preemptive policy.
Repeated short arrivals can starve a long job.
The shortest total original burst is not necessarily the shortest remaining burst after execution has begun.
Priority scheduling chooses the highest-priority ready job.
Check whether a smaller or larger numeric value means higher priority.
State whether a high-priority arrival preempts.
Fixed-priority scheduling can starve low-priority jobs under continued high-priority load.
SJF can also starve long jobs; starvation is not exclusive to fixed-priority scheduling.
Aging increases waiting jobs’ effective priority according to a rule, reducing indefinite postponement when the priority scheme and workload permit.
It is not a deadlock cure.
Priority inversion occurs when urgent work waits on a resource held by lower-priority work; priority inheritance can temporarily raise the holder’s priority.
A multilevel queue separates classes, such as foreground interactive and background batch, and chooses both between queues and within them.
Fixed interqueue priority may starve lower queues; allocating time shares between classes can avoid this.
A multilevel feedback queue allows movement according to observed behavior, commonly demoting CPU-intensive jobs and periodically boosting priority.
Do not infer movement from a simple multilevel-queue label.
State initial class, quantum per level, promotion/demotion rules and interqueue policy before tracing.
A binary search tree is a data structure that might implement a queue; it is not itself a CPU selection policy. “Infinite” is not a standard scheduling-policy category.
Share a resource where safe to remove mutual exclusion; request all needed resources before holding any to remove hold-and-wait; permit safe resource withdrawal/restart to attack no-preemption; impose a global acquisition order to remove circular wait.
Not every physical resource is shareable or safely preemptable.
“If waiting, release all held resources and try again” removes simultaneous holding while waiting.
Distinguish voluntary resource release from forced preemption when describing resource reclamation.
Prevention can waste utilization or cause starvation; avoiding deadlock is not the same as treating every process fairly.
Detection asks whether the current state is deadlocked.
Recovery can terminate selected processes or reclaim safely preemptable resources and roll affected work back to a checkpoint.
Termination and rollback are both possible recovery tools; choose according to the resource and process conditions.
Repeatedly sacrificing the same victim can cause starvation.
Checking on every request versus periodically trades overhead against detection delay; no universal best interval exists.
Ignoring a sufficiently rare problem is sometimes called the ostrich policy, but real systems still prevent or detect selected deadlocks. “Deadlock acceptance” can mean intentional ignoring, not necessarily an invalid approach.
A detection graph, avoidance safety graph and ordinary scheduling queue solve different problems.
Compile-time binding uses absolute addresses if placement is known.
Load-time binding relocates when placed into memory.
Execution-time binding translates while running and permits movement with hardware support.
Logical/virtual addresses are generated for a process; physical addresses select RAM.
An MMU translates logical addresses to physical addresses, not the reverse.
Dynamic loading brings a routine in when needed.
Dynamic linking resolves references to external libraries at load/runtime, allowing suitable library code pages to be shared; static linking copies selected code into the executable.
Swapping traditionally moves a whole process to backing store; paging moves individual pages.
These differ from a context switch, which primarily changes execution state.
A contiguous allocation gives a process one continuous region.
In the standard base/limit model, base is that process’s physical starting address and limit is its permitted length.
Check 0≤logical_offset<limit, then physical=base+offset.
The relocation register does not normally hold the OS base.
If limit instead means last valid offset, the inequality changes; specify the convention.
First-fit selects the first adequate hole; next-fit continues from the previous search position; best-fit selects the smallest adequate hole; worst-fit selects the largest.
No policy universally optimizes both search time and future storage utilization.
Pages and physical frames have equal fixed size P. Divide virtual address v into page=floor(v/P) and offset=v mod P. The page table maps a page to a frame and protection/status flags.
Physical address=frame×P+offset.
A TLB caches translations; a TLB miss may require a table walk while the page is already resident.
Table size depends on the number of virtual pages and entry size, not just physical RAM.
Protection and present bits must be checked before access.
A page-table lookup is not a CPU scheduling operation.
Segmentation uses logical variable-length units such as code, stack and arrays.
A segment-table entry provides base, limit and permissions.
For (segment,offset), validate the segment and check the bound, then add base+offset.
An out-of-range offset traps; it must not spill into the next segment.
Under the basic models, paging uses fixed units/page tables and can waste space internally; segmentation uses variable logical units/segment tables and can fragment externally.
Segments reflect program structure whereas ordinary pages are largely transparent to applications.
Apply all three contrasts when comparing paging and segmentation.
Virtual memory provides translated, protected address spaces and allows nonresident portions of a program to be backed by storage.
It does not add physical RAM or remove all capacity constraints.
Demand paging brings a page in when accessed.
On a nonresident access: trap, validate mapping/permissions, find a frame or choose a victim, save a dirty victim if needed, obtain contents, update mapping and restart.
Not every fault reads a disk: some allocate zero-filled pages or establish shared mappings.
An illegal access is rejected, not automatically loaded.
Excessive active-page demand can cause thrashing: repeated faults dominate useful computation.
Reducing active load or adding suitable memory can help.
Polling checks readiness repeatedly; interrupts request CPU attention; DMA transfers blocks after setup without CPU work for every byte.
Both the kernel and drivers participate in I/O; specify the abstraction level being discussed.
Plug-and-play discovers/configures compatible new hardware but may still require a driver.
Input/output/storage/NIC devices are OS-managed hardware; user accounts are identities.
Printer-paper and network errors can be handled/reported, but continued operation during total power loss requires hardware support, not OS software alone.
A file has content and metadata such as name, size, owner, permissions and timestamps. open obtains an open-file reference, read/write transfer bytes, seek changes an offset, close releases a reference, truncate changes size and unlink removes a name.
A file descriptor is a process-local integer handle; the associated open-file state contains the current offset and access mode.
Descriptor and offset are not synonyms.
Read advances the offset on seekable files and may return fewer bytes than requested; zero normally indicates end-of-file.
Sockets also support ordinary read/write, alongside socket/connect/send operations, so read is not uniquely “not a network call.” FAT32, NTFS and ext4 are filesystem formats; HTTP is an application communication protocol.
A single-level directory requires unique names in one namespace.
Two-level directories separate users.
A tree allows nested directories and absolute/relative paths; links can create shared graphs.
Modern general-purpose systems commonly present hierarchical namespaces, but a feature name alone does not prove that every system excludes simpler arrangements.
A hard link is another name for the same underlying file object, usually within one filesystem; a symbolic link stores a pathname and can point across filesystems or become dangling.
Removing one hard link does not erase content while other names/open references retain it.
Mounting attaches a filesystem at a mount point; it does not format the device.
NFS provides remote filesystem access; FTP transfers files rather than itself mounting a local filesystem.
OS38 Contiguous, linked and indexed file allocation
Contiguous allocation uses consecutive blocks; logical block i is start+i and supports direct access, but growth and external fragmentation are problems.
Extents allow several contiguous runs.
Linked allocation chains blocks and supports growth without reserving a complete contiguous file; locating block i requires traversing preceding links.
FAT stores chains in a table; caching that table does not change the chain into a direct arithmetic mapping.
Indexed allocation uses a per-file array/tree of block pointers and supports direct lookup with metadata overhead.
A Unix inode can combine direct pointers with indirect levels.
Check pointer size, block size, index capacity and whether metadata reads are cached.
An ACL lists principals and rights; owner/group/other bits are a simpler policy model, not universal defaults granting all owners full access or everyone read.
Read, write, execute, append and delete are different rights, with filesystem-specific rules.
Least privilege limits damage.
Password hashing verifies secrets without storing plaintext; one-time passwords expire after use.
Encryption protects confidentiality under correct key use but does not automatically provide integrity.
Trojans masquerade as useful software, worms propagate independently and viruses attach to hosts; denial of service harms availability.
Modern OS families can support cryptography, authentication and firewalls, but support/configuration depends on product.
CLI, GUI, speech/natural language and VR are possible interfaces, not a closed list excluding the last two.
Linux is a Unix-compatible kernel written from scratch by Linus Torvalds; a distribution combines it with userland, libraries and tools.
Android’s base kernel layer is Linux; its framework and applications are higher layers.
AOSP is open source, while a shipped device can include proprietary applications/services.
Windows and macOS are both proprietary products, although macOS contains open-source components, so “which is not open source?” offering both is ambiguous.
Microsoft Office is an application suite.
Windows is the Microsoft family commonly described as succeeding the MS-DOS desktop era; Solaris originated at Sun. “First widely used OS,” “first multitasking OS,” and generation/function pairings require a definition and historical evidence; UNIX was not the first system ever to multitask. “Most mobile devices” needs a population and date; architecture facts do not prove market share.
OS-S01 UNIX origins and the first four historical generations
UNIX development began at Bell Labs in 1969, led by Ken Thompson and Dennis Ritchie with other collaborators. Ritchie is therefore a co-creator, not the sole inventor of the first operating system.
The later UNIX time-sharing system described by Ritchie and Thompson is multiuser and interactive and supports asynchronous processes. Its later versions incorporated multiprogramming. This history does not make UNIX the first system ever to multitask.
In the first four generations of the cited NYU teaching taxonomy, the first generation uses vacuum tubes and manual single-user operation without a separate resident OS. The second generation pairs transistors with uniprogrammed batch systems; the resident OS starts successive jobs without being reloaded for every job.
The third generation pairs integrated circuits with multiprogramming. The fourth emphasizes personal computers. These are characteristic-era associations, not claims that each feature existed exclusively in one era.
OS-S02 Thread management costs and execution privilege
In the conventional library-thread comparison, user-level thread creation and switching can avoid entering the kernel. Kernel-managed thread creation and management commonly incur additional kernel work and are therefore generally slower to create and manage in this comparison. This is a typical comparison, not a universal speed or reliability guarantee.
Being scheduled or managed by the kernel does not give application thread code kernel privilege. Ordinary applications and supporting utilities execute in restricted user mode and request protected services through libraries and system calls. Kernel component code executes in privileged kernel mode and performs permitted low-level hardware operations.
OS-S03 Memory allocation and page-policy decisions
Memory management tracks which primary-memory regions are free or in use, assigns memory to processes and data, and deallocates it when no longer needed or when a process terminates. Allocation and deallocation concern memory ownership; CPU selection belongs to scheduling.
A buddy allocator manages power-of-two block sizes. It takes a smallest sufficient block, splitting larger blocks when necessary, and can merge a freed block with its free buddy. This is not the worst-fit rule of selecting the largest arbitrary hole.
A fetch policy decides when contents are brought into memory; demand paging fetches a valid nonresident page when it is accessed. A cleaning policy concerns writing modified contents to backing storage. A replacement policy chooses which resident page to evict. These decisions can cooperate during one page fault, but they are different decisions.
OS-S04 Communication endpoints and timed I/O events
In the descriptor-based socket API, socket() creates a communication endpoint and returns its descriptor. connect() associates the socket with the requested peer address; send() transmits data to another socket. Receiving through read() uses the ordinary descriptor-input interface described in the file-services lesson.
IRQ means interrupt request. A controller can raise an interrupt to request CPU attention. In a clock-tick scheduler, the scheduler initializes a running process’s quantum counter; each clock interrupt decrements it, and reaching zero triggers scheduling. Clock support also maintains time of day and usage accounting.
Direct message communication names the receiving process explicitly. Indirect communication uses a mailbox or port. This naming distinction is independent of whether a send or receive blocks: naming a destination does not determine synchronization semantics.
OS-S05 Compilation versus operating-system execution services
A compiler translates source code toward an executable representation. For example, the conventional GCC toolchain distinguishes preprocessing, compilation proper, assembly and linking. A compiler uses operating-system services as a development tool; it is not the runtime kernel component that selects ready processes, manages memory or handles protected service requests.
Linux provides link() to create another hard-link name for an existing file. The old and new names identify the same file, so hard links are not a Windows-only facility. unlink() removes a filesystem name; when that name is a symbolic link, it removes the link itself. Removing a name and erasing the target’s contents are different operations.
A common lifecycle names requirements, design, implementation, testing, deployment and maintenance.
Analysis clarifies the problem; system design chooses architecture; object/detail design specifies interfaces and algorithms; implementation writes code; testing evaluates behavior; deployment puts it into service.
These activities may overlap and repeat.
Select a process using requirement stability, technical risk, delivery urgency, stakeholder availability, team skills and assurance needs. “Team has little experience” alone does not uniquely identify a process.
A risk-driven cycle, prototype or carefully planned staged process may each help, depending on the actual uncertainty.
No process eliminates the need for testing or documentation.
Agile favors people collaborating, useful working results, customer participation and adaptation over rigid adherence to procedures, exhaustive documents, contracts or fixed plans.
The latter still have value.
Agile does not mean no planning or no documentation.
A user story states a small user need and value, supported by acceptance criteria; an epic groups broader work.
Scrum uses timeboxed Sprints of at most one month, with a Sprint Goal, selected work and a usable Increment meeting a Definition of Done.
Scope is discussed before and during planning; it is not forbidden to agree scope.
Timeboxes tend to stay fixed while content is adapted without endangering the goal.
Agile can be combined with required assurance/documentation; safety-critical context alone cannot prove it is unsuitable.
Each cycle identifies objectives and alternatives, assesses and reduces important risks, develops/verifies an appropriate next result, and plans further commitment.
A prototype may test a risky technology before a large investment.
The amount and type of work depend on the risks.
Use risk emphasis to distinguish spiral from a generic changing-requirements scenario.
Spiral can incorporate incremental, prototyping or sequential activities, but calling it the uniquely “most general” process is a textbook convention rather than a universal theorem.
Risk analysis requires skill and may impose excessive overhead on a small low-risk project.
SE07 Prototypes, RAD and reuse-oriented development
A prototype explores requirements, usability or technical feasibility.
A throwaway prototype is discarded after learning; an evolutionary prototype is deliberately refined toward production.
A quick prototype may omit robustness, security or architecture, so do not deploy it unchanged without evaluation.
Coding may occur during prototyping even if a diagram labels that activity construction rather than coding.
RAD uses rapid construction, timeboxing, user participation and often reusable components; it requires available users and skilled designers/developers.
Reuse-oriented development searches components, evaluates fit, may adjust requirements, designs around interfaces and builds missing parts.
Product-line assets may include requirements, architecture, components and tests; all are potentially reusable.
Feasibility asks whether a proposal is worth doing and can be delivered within technical, economic, operational and schedule constraints.
Examine existing limitations, organizational impacts, benefits, cost, available skills and integration risk.
System analysis studies the problem and needed behavior in more detail; the activities inform each other.
Business requirements explain why the project exists and its goals.
User requirements describe stakeholder needs at a useful high level; system requirements specify detailed services and constraints.
The Software Requirements Specification (SRS) organizes the agreed requirements.
A natural-language specification communicates with clients while analysis models formalize it for technical discussion; real specifications can also contain diagrams.
SE09 Functional requirements include prohibited behavior
A functional requirement states an observable service or behavior, including reactions to inputs, errors and forbidden actions. “When the sensor detects intrusion, send an alert” is functional. “Only a manager may approve refunds” also specifies permitted/prohibited behavior.
A negative statement is not automatically nonfunctional.
Write one clear obligation with an actor/trigger, action and observable result. “The system shall generate a PDF report” is functional. “The system shall not reveal another customer’s balance” can be a security-related functional rule.
Security as a broad quality goal and the functions implementing it must be distinguished.
Words such as must, should and not work do not by themselves determine a requirement’s classification.
SE10 Nonfunctional qualities and measurable constraints
Nonfunctional requirements include quality attributes and constraints.
Performance concerns response time, throughput and resource use; reliability concerns failure-free service; availability concerns being ready for use; usability concerns task success and ease of learning.
“Search responds within two seconds under 100 concurrent users” is measurable performance. “New users finish checkout within one minute without help” is usability. “Use Java” is a technology/pseudo-requirement, often separately classified as a system constraint.
Dependability includes reliability, safety and robustness; portability is not its usual central category.
Performance degradation at peak load primarily concerns performance, not automatically reliability.
Interviews ask stakeholders about needs; document analysis examines manuals, contracts and current records; observation/ethnography studies actual daily work.
Prototypes reveal tacit expectations.
Workshops/JAD bring users, managers and developers together with a facilitator and recorder to build consensus.
Use several sources and check assumptions against observed work.
In the taught FAST technique, participants list environment elements, outputs and inputs, consolidate lists and develop smaller specifications.
QFD prioritizes customer value: normal needs are explicitly stated, expected needs are assumed, and exciting needs provide unanticipated benefit.
Brainstorm first to generate ideas, then evaluate and prioritize; do not confuse that with letting every idea become a committed requirement.
Entity objects represent domain information such as Incident; boundary objects mediate interaction, such as ReportForm; control objects coordinate a use case.
A UI form is normally boundary, not entity.
Use nouns as candidate objects, possessive descriptions as candidate attributes, and verbs such as manages/reports-to as candidate associations.
These are heuristics, not automatic parsing rules.
CRC means Class, Responsibilities, Collaborators.
A control per use case or participating actor can be a useful starting point, not a mandatory UML rule or fixed object lifetime.
Record name/goal, actors, trigger, preconditions, main success flow, alternatives/exceptions and postconditions.
Use active subject–verb steps at one abstraction level; separate errors from the normal flow.
Example: Submit Incident.
Precondition: officer authenticated. 1 Officer supplies location and description. 2 System validates details. 3 System records the incident. 4 System returns its ID.
Alternative 2a: location missing → report the problem and request correction; save nothing.
Success postcondition: incident and ID persist; failure guarantee: no partial record.
An alternate flow is a conditional variation; an exception flow handles a failure.
Preconditions hold before entry, while a trigger starts the use case.
SE16 Include, extend, generalization and abstract use cases
Include factors required reused behavior: Submit Order includes Validate Order, with the dashed arrow from the including/base use case to the included one.
Extend adds conditional behavior at extension points: Apply Discount extends Checkout, with the arrow from the extension to the base.
The base is meaningful independently.
For an extension, draw the arrow from the extending use case to the base use case.
Generalization relates a specialized actor/use case to a more general one, with a hollow triangle toward the general element.
An abstract use case specifies behavior for specialization and is not directly instantiated as a complete use case.
It is not defined merely by reuse or lack of a direct actor line.
Included behavior is incorporated where the inclusion is reached; do not infer every conditional branch in the base always executes.
A class box lists name, attributes and operations; + public, - private, # protected and ~ package indicate visibility.
A class diagram shows static types and relationships, while an object diagram shows particular instances/links.
UML is maintained and standardized by OMG; it is a modeling language, not a lifecycle process.
Structural things describe conceptual or physical structural elements.
Multiplicity at one end counts how many objects there may correspond to one object at the opposite end: 1 exactly one, 0..1 optional, 0..* any nonnegative number, 1..* at least one.
A one-to-many association does not automatically mean composition.
Read each end separately before choosing cardinality.
SE18 Association, aggregation, composition and generalization
Association connects related instances.
A dashed dependency arrow means a client uses a supplier.
Generalization uses a solid line and hollow triangle pointing to the superclass/general element.
Shared aggregation uses a hollow diamond at the whole end and weak whole-part meaning; it does not by itself define a detailed lifecycle policy.
Composition uses a filled diamond at the whole end and strong ownership: a part is in at most one composite at a time, and parts still owned are destroyed with that composite.
Parts may be detached/transferred under a defined model.
Thus “cannot ever exist independently” is an oversimplification.
For Car composing Engine, the diamond belongs beside Car; saying it points to Engine is imprecise.
SE19 Sequence diagrams and the emergency-report example
Sequence diagrams show interactions across lifelines, with order/time generally downward.
Messages cross between participants; activation rectangles show execution.
A creation message starts a lifeline; an X marks modeled destruction, not a guarantee about when a garbage collector runs.
Synchronous calls wait for completion; asynchronous messages permit the sender to proceed.
One interaction-diagram layout heuristic puts the initiating actor first, boundary second, control third, then entities.
This is not a required UML column order.
In ReportEmergency, FieldOfficer activates ReportEmergencyButton, enters details through EmergencyReportForm, and later sees AcknowledgmentNotice; DispatcherStation belongs to the dispatcher side.
Choose the button for initiating this particular scenario.
An activity diagram models workflow: filled circle start, rounded actions, guarded decision diamond, thick fork/join bars and partitions/swimlanes for responsibility.
A diamond can also merge alternative flows; a join synchronizes concurrent flows.
A state machine models states and transitions triggered by events, often with guards/actions, for one object’s lifecycle.
Choose a sequence diagram for message order between participants, a state machine for event-dependent state changes, and activity for workflow.
Both sequence and state diagrams describe behavior over time.
State machines are useful for objects with significant states, whether entity or control.
A DFD shows data stores/flows and transformations from inputs to outputs; it is not a UML diagram.
System design turns the analysis model into architecture: design goals, subsystem responsibilities, dependencies, hardware mapping, data management, access control, control flow and startup/shutdown/error policies.
SE22 Cohesion, coupling, modularity and refactoring
Cohesion measures how well elements inside a module serve a related purpose; coupling measures dependency between modules.
Seek high cohesion and low coupling.
Shared mutable data and knowledge of another module’s internal representation increase coupling.
Information hiding exposes stable operations while concealing changeable decisions.
Logical cohesion groups similar-category operations, often selected by a flag; temporal cohesion groups operations done at the same time; functional cohesion focuses on one task.
Splitting an unrelated three-purpose component improves modularity.
If behavior is preserved, the restructuring is refactoring; the words are not mutually exclusive answers.
Smaller modules can aid understanding, independent work, reuse and maintenance, but too many interfaces also create complexity.
A layer is a logical abstraction level; a tier is a deployment separation.
A closed layered architecture permits calls only to the immediately lower layer; an open one permits approved skipping.
For top-to-bottom A,B,C,D, A→B obeys closed layering, A→C skips, and lower-to-upper calls violate the simple dependency rule unless explicitly mediated by a defined mechanism.
A structure is the elements/relations themselves; a view represents selected aspects.
Module structures show code organization, component-and-connector structures runtime interaction, and allocation structures map software to hardware, teams or environment.
Processes/threads belong in concurrency views.
Evaluate architectures against quality attributes and scenarios; processor allocation, decomposition and style selection can all be architectural concerns.
Save and ID assignment must succeed together, or roll back.
Derive tests from the model: missing location saves nothing; valid input returns a saved ID; a storage failure yields an error without a partial record; unauthorized input is rejected.
Factory Method lets subclasses choose a concrete product through a creation operation, reducing coupling to concrete constructors.
A simple factory centralizes creation but is not identical to Factory Method.
Singleton controls access to one instance; Observer notifies subscribers; Memento stores/restores state while hiding representation; Iterator traverses; Decorator adds behavior through wrapping. The pattern name is Memento, not Momento.
Variability can use selectable features, omission/inclusion and extension points; overloading supplies alternate signatures in code but is not every variability mechanism.
Testability improves with controllable inputs, observable outputs, replaceable dependencies and limited structural complexity.
A sandbox can isolate execution.
Assess each design claim independently before evaluating a combined statement.
Planning is continuous: identify scope/deliverables, decompose work, estimate effort/duration/cost, assign resources, sequence dependencies and revise as evidence changes.
A WBS is hierarchical and covers project scope without adding unrelated work.
Tools help coordinate ownership, dependencies and progress; they do not replace judgment or automatically fix bugs.
Function points estimate functional size using inputs, outputs, inquiries, internal logical files and external interface files, weighted under the chosen method.
They are not just lines of code and are not a direct exact measure of complexity.
Git tracks versions; issue trackers such as Jira track work/defects; CI tools such as Jenkins automate checks; Docker packages application/runtime dependencies into containers.
Early start/finish values alone do not determine slack without successor relationships and the project completion constraint.
If C3→D6 is a complete path parallel to A4→B5 and both finish at day9, C has zero float.
That network cannot be silently inferred from four unrelated ES/EF rows.
Traditional CPM uses point durations; PERT models uncertainty with optimistic a, most-likely m and pessimistic b. The classic estimate is TE=(a+4m+b)/6 and variance=((b-a)/6)^2.
For 3,6,15 days, TE=42/6=7 days and variance=4 days².
Do not replace the weighted estimate by a simple average.
These formulas are approximations, not guaranteed actual completion times.
SE31 Business value, risks and resource optimization
With benefits and costs already discounted to a common date, ROI=(benefits-costs)/costs*100%.
Birr120000 benefits and Birr100000 costs give 20%, not 120%.
Identify project risks to resources/schedule, product risks to quality, and business risks to the organization.
Analyze likelihood and impact, plan responses and monitor.
Avoidance changes the plan to remove a risk, mitigation reduces likelihood/impact, transfer assigns consequences contractually, and retention/acceptance keeps the risk; passive acceptance may take no action.
Resource leveling adjusts dates to respect resource availability and can change project finish; smoothing uses available float within schedule constraints.
SE33 Configuration, change control and version control
Configuration management identifies controlled items, versions/baselines, change procedures, status and audits.
Items may include source code, requirements, manuals, test plans, environments and build configurations.
A team’s ordinary browser is usually a tool rather than product CI, but a controlled test-browser version may be an environment CI.
Change management handles request, impact assessment, decision/prioritization, implementation and validation; configuration management keeps all affected versions consistent.
Distributed Git gives each clone local history and supports independent branches followed by merging; it does not eliminate merge conflicts or approvals.
Plan test configuration management early and apply it throughout testing, not at just one exclusive phase.
SE34 Quality assurance, verification and validation
Quality assurance establishes and checks processes/standards; quality control evaluates work products.
An SQA plan identifies standards, responsibilities, evaluations, reviews, audits and assurance records.
Quality of conformance means following the design/specification; a product can conform to a poor specification.
Verification asks whether specified obligations are implemented correctly; validation asks whether the product meets intended stakeholder needs.
Both can use reviews, analysis or execution, so “human-only versus computer-only” is false.
A fault/defect is an underlying problem; an error may be an incorrect internal state; a failure is an externally observed departure from required service.
Reliability is a product quality attribute; low cost or short development time are project outcomes.
Tests increase confidence and reveal defects but cannot generally guarantee correctness over every possible input.
Unit testing isolates a function, class or small component, often replacing dependencies with stubs/mocks; a driver invokes the unit and a stub substitutes a called dependency.
Integration testing exercises interfaces and interactions among combined parts.
System testing checks the complete integrated system against functional and nonfunctional requirements in a representative environment.
Acceptance testing supports the customer/user’s acceptance decision against agreed needs and criteria.
Alpha typically happens in a controlled developer setting with selected users; beta uses external users in their environments.
None of these levels is universally the longest.
Unit is a level, while white-box is a technique; a unit can be tested using black-box cases too.
Functional tests check required behavior against the SRS and acceptance criteria.
Performance tests assess speed, throughput and resources under a specified workload; load uses expected demands and stress exceeds normal limits.
Usability, security, compatibility and reliability tests target their respective qualities. “Normal operating conditions” alone does not distinguish functional from performance testing.
Black-box techniques derive cases from specified behavior; white-box techniques derive them from internal structure; grey-box uses partial internal knowledge.
Regression testing checks for unintended effects after change; confirmation testing checks the particular defect repair.
Exploratory testing combines learning, design and execution and is experience based.
Manual/automated describe execution support, not a compulsory black-/white-box classification.
Statement coverage is the number of distinct executable statements exercised divided by the total executable statements in the declared test scope.
Unreachable statements can prevent100%; any justified exclusions must be documented with the adjusted scope.
Decision coverage counts decision outcomes; branch coverage counts control-flow edges, including unconditional edges under the stated convention.
Testing both true and false of each decision may need more than two overall test cases when branches nest.
Coverage is evidence of exercised structure, not proof of all behavior.
In the width/length/height program, the outer if has separate inner decisions in each branch.
Need outer true with inner true and false, and outer false with its inner true and false: four tests, for example (w,l,h)=(3,2,4),(3,2,1),(2,3,4),(2,3,1).
One run cannot exercise both outer branches.
All paths may be infeasible or infinite with loops; specify the chosen coverage target.
Plan objectives, scope, resources, schedule, risks and entry/exit criteria.
Analyze the test basis for testable features and defects; design cases/expected results; implement data, scripts and environment; execute and compare; report defects; evaluate completion.
Analysis asks what to test and assesses testability; design asks how.
Monitoring/control run across these activities.
A test plan describes intended work; incident/defect reports are normally execution outputs.
A defect report should identify build/environment, steps, expected versus actual behavior, evidence and severity.
Anyone finding a fault should record it; testers often coordinate reporting, but it is not their exclusive permission.
Configuration control makes the tested version reproducible.
SE42 Context-dependent claims and model limitations
Context matters: no test level is always most time consuming; no process is determined by team inexperience alone; no waterfall rule makes every later change impossible.
Requirements may describe required and prohibited behavior, including interface functions as well as usability qualities.
Identify an interface requirement’s exact obligation before classifying it as functional or nonfunctional.
Sequence/state diagrams both show dynamic behavior.
Composition needs the diamond’s placement and ownership semantics. “Agile least suitable for safety-critical government work” assumes a particular lightweight process without required assurance; it is not universally true.
Treat the guide’s conventions as scenario hints and keep the stronger engineering rules explicit.
SE43 Design choices, evidence and economical improvement
Choose designs by their effect on stated goals.
Fine-grained self-contained components, separation of producers/consumers and limited shared mutable data often improve maintainability.
Trade-offs remain: interfaces can add latency, isolation can complicate transactions, and global state can simplify one operation while coupling many others.
Prefer measurable quality scenarios to counting components alone.
Pareto’s 80/20 rule is a prioritization heuristic: a small subset of causes may account for much of the observed impact.
It does not guarantee 80% of defects can be fixed with exactly 20% effort.
Refactor to preserve behavior while improving structure; optimize only against measured needs; record rationale and update traceability and regression evidence after change.
SE-S01 Scope, understanding and changing requirements
Elicitation difficulties have several distinct sources. Scope problems concern agreeing on system boundaries and the appropriate level of detail. Understanding problems arise when stakeholders and analysts have different domain knowledge, omit tacit needs or communicate conflicting interpretations. Volatility means that requirements change as circumstances and understanding develop.
These difficulties call for repeated communication, explicit boundaries, negotiated meanings and controlled revision. They can occur together; resolving one does not automatically remove the others.
An object-oriented approach can use a consistent vocabulary of objects, classes and relationships across analysis, design and implementation. Models are refined for different purposes rather than being identical artifacts. This continuity can reduce translation errors and effort; reusable classes can shorten suitable projects, but neither shorter duration nor good design is guaranteed.
Generalization places common concepts in a more general superclass and specialized concepts in subclasses. Available inherited attributes and operations are shared by subclasses, which may extend or override behavior. Defining common features once can reduce duplicated maintenance. The top of the hierarchy is more general, not more specialized.
Encapsulation groups state with operations and hides representation behind an interface. Polymorphism permits different object types to respond differently through a common operation or interface. Abstraction exposes the relevant contract while omitting unnecessary detail. Reusability means using suitable existing classes or components in new contexts rather than writing them again. These ideas support each other but name different properties.
In the course’s UML building-block terminology, structural things describe static conceptual or physical elements. Behavioral things describe dynamic interactions and state behavior. Grouping things organize model elements into packages. Annotational things attach explanatory remarks or constraints, usually as notes.
An entity–relationship diagram models entity types, their attributes and the relationships between them, commonly for data design. Its focus differs from a use-case diagram of external roles and goals, a class diagram of classes and their features, or a deployment diagram mapping artifacts to execution nodes.
In a plan-driven process, activities are planned in advance and progress is assessed against that plan. Agile planning is incremental and adapts to changing needs. This distinction concerns planning strategy; a process can combine advance planning with staged deliveries and feedback.
SE-S05 Exploration artifacts and collaborative implementation
A storyboard sketches a sequence of moments in a proposed interaction, helping people explore how a concept would be used. A wireframe sketches interface structure and the arrangement of content or controls. Both can inform requirements, but neither automatically supplies a complete use-case description with actors, preconditions, flows and postconditions.
Pair programming is a way for two programmers to work together on the same implementation task, commonly sharing a workstation with complementary writing and reviewing roles. It is an implementation collaboration practice rather than a replacement for modeling a user goal.
SE-S06 Distinguish a requirements specification from neighboring terms
A Software Requirements Specification records agreed software services and constraints. A Capability Development Document is a defense capability-requirements artifact describing needed capability characteristics and performance parameters; its specialized acquisition context differs from the ordinary software SRS. Domain-driven design is an approach that organizes software models around the business domain, not the name of an agreed requirements specification.
SE-S07 Scalability and robustness are different qualities
Scalability is the ability to accommodate additional workload while maintaining the required service, often by increasing available resources. It concerns growth in demand. Compatibility concerns supported cooperating environments, such as browsers and devices; usability concerns successful and learnable user tasks.
Robustness concerns reliable operation across varied or difficult operating conditions and controlled failure outside the supported range. It is different from usability, which concerns people successfully learning and carrying out tasks. Improving an interface’s task success does not by itself establish robustness under adverse conditions.
Design an algorithm by specifying its states, choices and correctness argument, then count its work and peak storage.
A familiar strategy name is not enough: independent subproblems, reuse, safe local choices, feasibility pruning and objective bounds lead to different methods.
For cost questions fix input size, case, primitive operation and arithmetic model.
Write the sum or recurrence before selecting an asymptotic bound.
For each design technique practice a small trace and explain why its discarded alternatives cannot improve the required answer.
Distinguish an exact algorithm from a heuristic, a decision problem from an optimization problem, and a tight bound from a merely valid upper bound.
Sections in this course
DAA01 Specify the problem and prove correctness
State inputs, output, constraints and empty-solution policy.
Algorithms are finite, definite executable methods independent of source language; feasible satisfies constraints, optimal is best feasible.
Conditional branches are legitimate control flow.
Prove an invariant initially, after each step and at termination; for recursion prove base cases and the inductive reduction.
Testing finds failures but finite tests do not prove correctness for all inputs.
For eventually nonnegative f, g, f∈O(g) means f(n)≤c·g(n) for all n≥n 0, with fixed c>0. Ω reverses that inequality; Θ requires both bounds.
Little-o means f/g→0, and little-ω means f/g→∞ where the ratio exists. Θ specifies growth up to constant factors, not exact seconds or identical best/worst cases.
Prove the inequality for the whole tail, not selected values.
Transitivity allows chained upper bounds; sums are dominated by the largest nonnegative growth term.
A dependent loop requires summation. n iterations of a constant body give Θ(n); ∑i=1.. n i=n(n+1)/2 gives Θ(n²).
Doubling i=1,2,4,… until i≥n takes ceil(log 2 n) iterations for n>1.
A 10n loop is linear under constant-cost output.
If m operations each have expected cost f(n) at the same fixed size, expected total is m f(n), by linearity of expectation; independence is unnecessary.
If sizes change, sum f(n_i).
Exact coefficients depend on whether tests, increments, arithmetic and assignments count separately.
DAA07 Analyze conditional nested loops and code validity
For the loop i=0.. n−1, j=i.. i²−1, and k=0.. j−1 only when j%i==0, i=0 and 1 have empty j ranges, so no remainder by zero is evaluated.
For i≥2, successful j values are i,2i,…,(i−1)i. The inner work is i∑m=1.. i−1 m=i²(i−1)/2=Θ(i³).
Summing over i gives Θ(n⁴); condition checks add only Θ(n³).
Neither n⁵ nor n⁷ is tight for this loop, though both are valid Big-O upper bounds.
This assumes mathematical integers and constant-cost output; literal signed C++ overflow in i*i is undefined, and executable runtime analysis requires valid syntax in a specified language.
Redeclaring parameter n and using return @;3 are syntax errors; neither establishes logarithmic complexity.
Space complexity measures peak simultaneously live storage, not the sum of every allocation ever made.
Count input, auxiliary structures and stack according to the requested convention. n active recursion levels with constant-size frames need Θ(n) stack; depth log n with constant frames needs Θ(log n).
The number of total calls does not determine peak depth.
Slicing/copying arrays can add storage omitted by an index-based pseudocode analysis.
Tail-call elimination is language/runtime-dependent and cannot be assumed for ordinary C++/Java recursion.
Resource tradeoffs include caching subproblem results to save time while consuming memory.
For T(n)=aT(n/b)+f(n), a≥1, b>1, let p=log_b a. Level i has a^i nodes of size n/b^i. Compare f with n^p: a polynomial gap below gives Θ(n^p); f=Θ(n^p) gives Θ(n^p log n); a polynomial gap above gives Θ(f(n)) if a f(n/b)≤c f(n) for fixed c<1.
The third case needs this regularity condition.
A log-factor boundary may need an extended theorem or explicit summation.
State base work and include leaves.
This version does not apply to T(n)=T(n−1)+n or unequal-split quicksort.
Divide and conquer solves smaller largely independent instances and combines results.
DP reuses a defined set of subproblem states.
Greedy commits to a feasible local choice only when a safety argument supports it.
Backtracking grows/retracts candidates when constraints fail; branch and bound also rejects candidates whose best possible objective cannot beat an incumbent.
“Breaks into subproblems,” “sequence of choices,” “incremental,” or “optimization” alone describes several strategies.
Exponential runtime is an outcome, not enough information to select a method.
Specify overlap, local-choice safety, revisability, exactness and usable bounds.
Ordinary selection sort repeatedly selects one minimum; it is not a divide-and-conquer algorithm.
DAA15 Quicksort: partition variants and worst cases
Choose a pivot, partition, then sort the resulting smaller ranges.
In a two-pointer scheme, advance i while values are below pivot and j while above; when i≤j, swap and advance both.
Bound the scans and ensure progress on equal values.
Recurse on the resulting ranges.
Hoare-style partition boundaries need not put the pivot at its final position; Lomuto-style partition commonly does.
Do not mix their return conventions.
Balanced splits give Θ(n log n); repeatedly highly unbalanced splits give Θ(n²).
Random pivots give expected Θ(n log n), not a deterministic guarantee.
Median-of-three does not eliminate adversarial cases; three-way partitioning helps repeated keys.
Standard quicksort is unstable, uses expected Θ(log n) stack but worst Θ(n); recursing on the smaller side and iterating on the larger bounds stack by O(log n).
DAA19 Greedy correctness, limits and counterexamples
A greedy algorithm repeatedly selects a locally attractive feasible option without later undoing it.
Optimal substructure alone does not prove this safe.
An exchange proof inserts the greedy choice into an optimum without worsening cost; recurse.
MST cut proofs use this exchange.
Advantages are often simple decisions and low overhead; limitations are irrevocable errors and problem-specific applicability.
A heuristic has no approximation guarantee merely because it is greedy.
For coins{1,3,4} and target 6, largest-first gives 4+1+1 while 3+3 uses fewer coins.
Activity selection instead has a safe earliest-finish rule for maximizing the number of nonoverlapping unweighted intervals; replacing the first chosen activity in an optimum with an earlier-finishing one leaves at least as much room.
DAA20 Fractional knapsack versus indivisible items
For positive weights/profits and divisible items, sort by decreasing value/weight, take complete items while they fit, then the fitting fraction of the next.
The exchange argument replaces lower-density selected weight by available higher-density weight; value cannot decrease.
Sorting costs O(n log n), followed by a linear scan.
Handle zero-weight beneficial items separately rather than divide by zero.
This proof depends on divisibility.
With capacity 10 and items(6,12),(5,8),(5,8), ratio-greedy chooses value 12; the two weight 5 items give 16 under 0/1 rules.
Specify whether the knapsack problem is fractional,0/1 or unbounded.
DAA24 Dijkstra: relaxation and the nonnegative condition
Initialize dist[source]=0, others∞ and predecessors unset.
Repeatedly extract the unsettled vertex u of minimum distance; relax each edge by dist[v]=min(dist[v], dist[u]+w(u, v)), updating predecessors when improved.
Once the minimum is∞, remaining vertices are unreachable.
A destination may be finalized before stopping, not merely discovered.
Nonnegative edges ensure a later path through unsettled vertices cannot improve a finalized distance.
With s→a=2, s→b=5, b→a=−4, finalizing a at 2 misses the later distance 1.
DAA28 Floyd–Warshall, reachability and negative cycles
For all-pairs distances initialize D[i, i]=0, D[i, j] to the minimum direct edge weight, and missing edges to∞.
Preserve a negative self-loop by taking min(0, its weight).
For k outermost, update D[i, j]=min(D[i, j], D[i, k]+D[k, j]); before phase k, intermediates are restricted to earlier vertices.
Guard unreachable sums and numeric overflow.
Three loops give Θ(V³) time and Θ(V²) storage.
A negative diagonal afterward identifies a negative cycle; pairs able to traverse it have no finite minimum walk distance.
Warshall reachability replaces min/+ by OR/AND.
Floyd’s cost is not a universal best-achievable bound for all APSP settings; sparse nonnegative graphs permit repeated Dijkstra and other models permit other methods.
For integer capacity W, K[i, w] is maximum value using the first i items within capacity w. Initialize K[0, w]=0.
If weight_i>w, use K[i−1, w]; otherwise take max(K[i−1, w], value_i+K[i−1, w−weight_i]).
The previous-row reference ensures each item is used at most once.
Backtrack changed values to recover chosen items.
Time O(nW) is pseudo-polynomial because W takes only O(log W) binary input bits.
Storage can be O(W); update capacities downward for 0/1 selection.
Upward iteration allows reuse and solves an unbounded variant.
In sparse(weight, profit) states, discard an option dominated by another with no greater weight and no smaller profit, provided both have the same remaining items.
A subsequence preserves order but need not be contiguous.
For prefixes of lengths i, j define L[i, j].
Empty-prefix rows/columns are 0.
If X[i−1]=Y[j−1], set L[i, j]=1+L[i−1, j−1]; otherwise use max(L[i−1, j], L[i, j−1]).
Keep prefix lengths i and j distinct from the zero-based character indices i−1 and j−1.
Fill rows/columns in increasing order.
Reconstruct by taking matching characters diagonally or following a neighbor with the same optimal value; ties may produce different LCSs.
Time Θ(mn), table storage Θ(mn); two rows reduce value-only storage to O(min(m, n)), while ordinary reconstruction needs retained decisions or another technique.
For matrix A_i of size p[i−1]×p[i], M[i, i]=0 and M[i, j]=min over i≤k<j of(M[i, k]+M[k+1, j]+p[i−1]p[k]p[j]).
Fill by increasing interval length and store the split.
Three matrices 10×30,30×5,5×60 cost 4500 under(AB)C versus 27000 under A(BC).
Time O(n³), space O(n²); multiplication order stays fixed while parentheses change.
For an OBST use sorted-key success weights p_i and gap failure weights q_i.
Let W(i, j)=∑p_i.. p_j+∑q_(i−1).. q_j.
Under the comparison-count convention, C(i, i−1)=0 and C(i, j)=W(i, j)+min_r(C(i, r−1)+C(r+1, j)); store r. CLRS-style dummy-node depths instead initialize empty cost to q_(i−1); final values differ by the fixed total gap weight.
Held–Karp uses O(V²2^V) time and O(V 2^V) space, improving factorial enumeration but remaining exponential.
Greedy nearest-neighbor is a heuristic without a general exactness guarantee; backtracking and branch and bound can also solve exact TSP.
Specify the problem variant and algorithm before choosing a solution method.
For Held–Karp, S contains the start s. Initialize F({s},s)=0 and impossible states to infinity; for larger sets, evaluate endpoints j other than s. These boundary cases prevent using a nonexistent predecessor state.
DAA35 Articulation points and biconnected components
An articulation vertex increases the number of connected components when removed.
In an undirected DFS, disc[u] is discovery time and low[u] is the smallest discovery number reachable from u’s subtree using downward tree edges and at most one back edge.
Update low from children and nonparent back edges.
A root is articulation if it has at least two DFS children; a nonroot u is articulation if some child v has low[v]≥disc[u].
Such a child cannot reach an ancestor of u without u. A bridge has the stricter condition low[v]>disc[u].
An edge stack can output a vertex-biconnected block when low[v]≥disc[u], popping through edge(u, v).
With adjacency lists these checks cost O(V+E).
Distinguish vertex-biconnectivity from strong connectivity in directed graphs.
For a simple undirected graph initialize disc[u]=low[u]=++time on entry.
For an unvisited neighbor v, push tree edge(u,v), DFS(v), then low[u]=min(low[u],low[v]).
For a visited nonparent ancestor v, push the back edge once when disc[v]<disc[u] and use low[u]=min(low[u],disc[v]).
After a child returns with low[v]>=disc[u], pop through(u,v) to output one block.
Keep the separate root-child articulation rule and bridge test low[v]>disc[u].
Restart DFS at each unvisited vertex.
For multigraphs skip the parent edge by identity rather than skipping every edge to the parent.
Fix a start vertex to avoid rotational duplicates.
Extend a path with an unused vertex adjacent to its current end.
At V vertices require an edge back to the start; otherwise backtrack.
A Hamiltonian cycle visits vertices once, while an Euler cycle concerns visiting edges.
Fixing the start leaves up to(V−1)! candidate permutations, with polynomial checking overhead.
For a simple undirected graph with at least 3 vertices, a degree 1 vertex or articulation point rules out a Hamiltonian cycle, but their absence does not prove one exists.
TSP optimizes a weighted Hamiltonian tour; the decision existence search alone does not minimize its cost.
Reversed undirected tours may be equivalent if enumerating unique cycles.
Sort positive-weight/value items by decreasing density and branch include/exclude.
Reject overweight nodes.
To bound a node’s possible profit, fill its remaining capacity fractionally from remaining items; this relaxation can only improve on 0/1 feasibility, so its value is an upper bound.
A whole-item feasible completion updates the incumbent; the fractional result itself is not a legal 0/1 answer.
With capacity 10 and items(6,12),(5,8),(5,8), the root fractional bound is 18.4: take the first and 4/5 of the second.
The first-item-in branch has whole-item value 12; excluding it permits the two other items, value 16.
Continue until every live upper bound is≤16 to certify optimality.
Avoid downward floating-point rounding that could invalidate the bound; worst-case search remains exponential.
For directed TSP, set diagonal/forbidden entries to∞.
Subtract each finite row minimum, then each finite column minimum, accumulating reductions.
Every tour uses one entry per row/column, so their sum is a lower bound; the relaxed assignment may contain disjoint subtours.
When including edge i→j, remove its used row/column, prevent premature subtours, reduce again and add the selected reduced-edge cost and new reductions to the parent bound.
Compare bounds with the best complete tour and expand a promising live node.
Never treat a reduced matrix’s zeros as proof of a complete valid tour.
Branch on an undecided edge i->j. The include child deletes row i/column j and adds its selected reduced cost plus new reductions to the parent bound.
The exclude child sets that entry to infinity and adds only new reductions.
Keep forced in/out-degree at most one.
Track each forced path from head h to tail t and forbid t->h until the path contains every vertex; this blocks premature cycles.
A required residual row/column with no finite choice is infeasible and pruned.
Accept only one complete cycle through every vertex, not a set of disjoint cycles.
P contains decision problems solvable deterministically in polynomial input-bit time.
NP contains decision problems with polynomial-length certificates verifiable in polynomial time, equivalently solvable by a nondeterministic polynomial-time machine.
NP does not mean non-polynomial; P⊆NP.
Whether P=NP remains open.
A polynomial many-one reduction A≤p B transforms each A-instance into a B-instance preserving yes/no. To prove B NP-hard, reduce a known hard A to B, not the reverse.
NP-complete means NP-hard and in NP; optimization TSP is normally called NP-hard, while its bounded-tour decision form is NP-complete.
A valid proposed tour and its cost are easy to check, but certifying global optimality is another task.
Pseudo-polynomial O(nW) knapsack is not polynomial in the bit length of W.
An agent perceives an environment through sensors and acts through actuators or effectors.
Cameras sense; motors move.
Software sensors may be incoming messages and software actions may be API requests.
Humans are agents but are not artificial agents.
A percept is one observation; a percept sequence is the entire observation history.
An agent function maps percept sequences to actions: f:P*→A. An agent program implements that mapping on an architecture; agent = architecture + program.
Environment means the setting in which it senses and acts, not merely the search space.
Autonomy means relying substantially on experience rather than only a designer’s prior instructions.
PEAS means Performance measure, Environment, Actuators, Sensors.
Specify all four before designing an agent.
For a taxi: performance includes safety and travel time; environment includes roads, traffic and passengers; actuators include steering, brakes and displays; sensors include cameras, positioning and speed readings.
A sensor is not an actuator just because it influences a decision.
The performance measure is not the percept sequence: one defines success, the other supplies evidence.
Separate what the agent can observe from what a designer knows about the world.
A simple reflex agent matches condition–action rules against the current percept only: if dirty, clean.
It has no persistent world-state memory.
This is adequate when the current observation contains everything needed for its rule, but partial observability can make the same percept require different actions.
A model-based reflex agent maintains internal state using the previous state, previous action, current percept, and models of world change and action effects.
It then applies rules to that state.
Both kinds can use condition–action rules; memory and a world model distinguish them.
The learning element changes the agent to improve future performance.
The critic evaluates behavior against a performance standard and supplies feedback.
The problem generator suggests exploratory actions likely to yield useful experience.
Learning is improvement on task T, measured by P, through experience E. For spam filtering, T is classifying email, E is past labeled messages, and P might be recall at a required precision.
Exploration trades immediate reward for information; exploitation uses the best action currently known.
Learning can improve reflex, goal-based or utility-based agents.
First formulate the goal; then formulate the problem by specifying initial state, legal actions, transition model, goal test, and action costs.
Search selects a sequence; execution applies it.
A state abstracts away irrelevant world details.
In route finding, states are cities, actions are roads, successors are neighboring cities, and path cost is accumulated distance or time.
A solution is a legal path ending at a goal; an optimal solution has minimum cost.
Automatic programming or program synthesis searches for a program satisfying a specification; conditional plans and loops require richer representations than a fixed action list.
UCS uses a priority queue ordered by actual accumulated path cost g(n).
Remove a minimum-g node; accept a goal when removed, not when first generated.
Relax each edge: if a cheaper path is found, update its frontier cost and parent.
With finite branching and each step at least ε>0, UCS is complete and optimal.
Finite graphs permit nonnegative edges with proper duplicate handling.
Dijkstra uses the same minimum-distance principle, often computing all reachable distances; UCS commonly stops at a goal and generates states on demand.
Queue initialization is an implementation choice, not a fundamental distinction.
Negative edges invalidate the usual finalized-distance argument.
AI16 Depth limits, iterative deepening and two directions
DLS runs DFS to depth ℓ and reports cutoff separately from failure.
It misses goals deeper than ℓ.
Iterative deepening runs DLS with limits 0,1,2,…; for finite b it finds the shallowest solution with O(b^d) time and O(bd) frontier space, optimal for equal step costs.
Repeated shallow work is small compared with the deepest level.
Bidirectional search grows from start and goal until frontiers connect.
With suitable reverse actions, meeting tests and equal-cost BFS, time and space may fall to O(b^(d/2)).
Weighted variants require a sound stopping bound; the first intersection need not be cheapest.
IDA* deepens an f=g+h threshold rather than only a depth limit.
For S→A cost 2, S→B cost 1, A→G cost 2, B→G cost 10, set h(A)=2, h(B)=1, h(G)=0.
After expanding S, greedy chooses B because 1<2 and can then choose G, returning cost 11.
A* compares A:f=2+2=4 and B:f=1+1=2; after B, its G entry costs 11.
It next expands A and replaces G with cost 4, which is removed and accepted.
For a sliding puzzle with unit moves, misplaced-tile count and summed Manhattan distances excluding the blank are lower bounds.
Straight-line distance is a lower bound on road distance; it is not automatically a lower bound on travel time without conversion using a valid speed bound.
Propositional atoms represent whole true-or-false claims. ¬P negates; P∧Q requires both; P∨Q requires at least one; P→Q is false only when P is true and Q false; P↔Q requires matching truth values.
Thus P→Q ≡ ¬P∨Q. De Morgan gives ¬(P∧Q) ≡ ¬P∨¬Q.
A model is an interpretation making a sentence true.
Valid means true in every interpretation; satisfiable means true in at least one; unsatisfiable means true in none.
Invalid means not valid, and may still be satisfiable.
P∨¬P is valid; P is satisfiable but not valid; P∧¬P is unsatisfiable.
Entailment KB⊨α means every model of KB also satisfies α.
First-order logic adds objects, predicates, functions and quantified object variables.
Human(a) is a property; Likes(a,b) a relation; father(a) a function term.
Propositional logic has no object quantifiers, but its truth still depends on the assigned atom values.
Use ∀x(Human(x)→Mortal(x)) for all humans, and ∃x(Student(x)∧Tall(x)) for at least one tall student.
These are useful translation patterns, not rules forbidding other connectives. ∀x∃y Likes(x,y) allows a different y for each x; ∃y∀x Likes(x,y) requires one shared y. Negation swaps quantifiers: ¬∀x P(x) ≡ ∃x¬P(x).
Only occurrences within the correct quantifier’s scope are bound.
Modus ponens derives Q from P and P→Q; modus tollens derives ¬P from P→Q and ¬Q. Affirming Q does not prove P. Universal instantiation substitutes an object for a universally quantified variable.
Unification finds a consistent substitution: Knows(x,Ada) and Knows(Ben,y) unify with x=Ben,y=Ada.
Distinct constants cannot be unified by renaming them.
Resolution combines clauses P∨Q and ¬P∨R into Q∨R. To prove α, add ¬α to KB in clause form and derive contradiction.
Forward chaining starts with facts and fires rules; backward chaining starts with a query and proves required premises.
Sound inference preserves truth; completeness means finding all entailed conclusions in its specified setting.
Bayes gives P(H|E)=P(E|H)P(H)/P(E): posterior equals likelihood times prior divided by evidence probability.
For mutually exclusive exhaustive hypotheses, P(E)=ΣiP(E|Hi)P(Hi).
A Bayesian network is a directed acyclic graph with conditional probability tables; its joint distribution factors as the product of each node’s probability given its parents.
A Markov model assumes the next state depends on the current state rather than the entire past.
These represent uncertainty; fuzzy membership represents a different issue.
AI32 Unsupervised, semi-supervised and active learning
Unsupervised learning seeks structure without target labels: clustering groups similar examples; association finds co-occurrence; dimensionality reduction compresses features.
Good clusters have high within-cluster similarity and low between-cluster similarity under an appropriate distance.
K-means alternates assignment to nearest centroids and centroid updates.
Semi-supervised learning combines some labels with additional unlabeled data.
Active learning chooses informative cases for an oracle to label; it still uses labels. “Exploratory learning” is not an exclusive standard synonym: it can mean unsupervised exploration or active data acquisition, so define the feedback.
A task named summarization or time-series analysis is not automatically supervised; its training targets determine that.
An RL agent observes state information, takes an action, receives reward and a new observation, and improves its policy to maximize expected cumulative reward.
Rewards evaluate outcomes rather than supply the correct action label.
Rewards may be delayed; not every correct-looking action receives immediate reward.
An illustrative discounted return is Gt=rt+1+γrt+2+γ²rt+3+…, with 0≤γ<1.
The policy maps states or histories to action choices.
Exploration gathers information; exploitation pursues currently estimated reward.
RL is part of machine learning, which is part of AI. “No labels” alone fits both unsupervised learning and RL; reward-driven interaction distinguishes RL.
Overfitting means fitting training-specific details so performance drops on unseen data; underfitting means the model is too limited or poorly fitted even on training data.
A learning curve plots performance against training size or training progress.
Complexity control, regularization, pruning and more representative data can help.
Train data fits parameters; validation data selects models or settings; a held-out test set estimates final performance.
In k-fold validation, train k models, each on k−1 folds and evaluate on the remaining fold, then average scores.
Stratification approximately preserves label proportions.
Fit preprocessing within each training fold.
Time-ordered data needs splits respecting time; repeated tuning on the final test set leaks information.
Morphology studies meaningful word parts: un-happi-ness contains a prefix, stem and suffix; cats contains cat and plural -s. It differs from tokenization, which identifies processing boundaries.
Phonetics studies physical speech sounds; phonology studies a language’s sound patterns and contrasts.
Prosody concerns stress, rhythm, timing, prominence and intonation across syllables and phrases.
A pitch rise can help signal a question; shifting stress can change emphasis.
These cues assist dialogue and speech processing.
Pragmatics concerns intended meaning in context, not the internal components of words.
Computer vision interprets images or video: classification names image content, detection locates objects, segmentation labels pixels, and recognition identifies objects or people.
Occlusion, lighting change, noise, unfamiliar conditions and incomplete context make open-world perception difficult even when a face detector works well.
Robotics combines mechanical, electrical, control and computing systems to sense, plan and act physically.
Components include sensors, controller, power supply, actuators and an end effector.
Locomotion may be legged, wheeled or tracked, with trade-offs in terrain, stability and efficiency.
Software can act autonomously without being a robot.
Humanoid shape is not evidence of general intelligence.
An expert system applies specialized knowledge to a domain such as equipment diagnosis.
The domain expert supplies expertise; the knowledge engineer elicits and encodes it; the inference engine reasons over a knowledge base and working facts.
The user interface handles interaction; an explanation facility presents why or how a conclusion was reached.
Rules offer inspectable domain reasoning but can be brittle and costly to maintain.
Learned models handle data-rich patterns but depend on representative data and validation.
A* is forward best-first search combining actual past cost with estimated future cost; it does not inherently run a backward frontier.
Both A* and IDA* can have exponential worst cases and optimality under their conditions. “Minimum heuristic” and “estimated closest” describe the same greedy choice.
LIFO and FILO are synonyms.
Using information from the current state alone does not establish that a search uses a heuristic.
Ask whether remaining cost is estimated.
Both “invalid iff unsatisfiable” and “satisfiable implies valid” are false in general; distinguish validity from satisfiability.
Evaluate each validity claim separately, or identify all false statements when several are offered.
The common teaching list contains five agent classes when learning agents are included, or four decision architectures before learning is added.
State the convention when counting agent types. “Target-based” can mean goal-based; “unity-based” is not utility-based.
A generic rule does not distinguish simple from model-based reflex without specifying memory.
A goal declaration unused by the action policy does not establish goal-based behavior. “Sensors and effectors” describes interaction, not omniscience or intelligence by itself.
Define the mechanical distinction when comparing effectors and actuators as acting components.
AI-S01 Programmed computation and learned patterns
A conventional computer manipulates digital information according to a program or sequence of instructions. Programs can implement storage, retrieval and learning operations. Neural networks can learn pattern recognition from examples, so executing instructions and learning patterns are not mutually exclusive descriptions. This provides no universal claim that every machine is better or worse than every human at completing missing information.
AI algorithms are not exclusive to one programming language. Rumale is a Ruby machine-learning library with classification and clustering implementations, demonstrating that Ruby can implement learning algorithms as well as the general-purpose languages already discussed. Language choice and learning regime are different decisions.
AI-S02 Ordered lookup versus state-space traversal
Binary search exploits the order of a sorted sequence: a comparison narrows the remaining candidate interval instead of exploring arbitrary successor states. Array bisection therefore differs from breadth-first or depth-first traversal of a general state-space graph. A storage container such as an array does not by itself specify FIFO or LIFO frontier behavior.
An AI task is modeled as an agent interacting with its environment: observations enter through sensors and selected actions affect the environment through actuators. This task-level description differs from an agent implementation, which combines a program with a computing architecture.
In ordinary usage, rationality means reasonable, sensible judgment. For an AI agent, the operational criterion is the action with the best expected performance given its percept history and available knowledge, rather than guaranteed success or knowledge of the actual future.
Planning constructs actions to reach a goal. Scheduling additionally assigns activities to times and resources while respecting constraints such as resource conflicts and precedence. It is an AI application when search or constraint reasoning chooses feasible or useful assignments; automated telescope experiment scheduling is an example.
AI-S04 Attributing the name of artificial intelligence
John McCarthy is credited with coining the term artificial intelligence in the 1955 proposal for the Dartmouth summer research project. The Dartmouth workshop took place in 1956 and helped establish the field. Naming the field does not mean that one person invented all its ideas or methods.
Simulated annealing follows a current candidate and randomly samples a neighboring move. It accepts improvements and sometimes accepts worse moves according to a temperature that decreases over time. Unlike genetic search, its defining mechanism is not a population undergoing parent selection, crossover and mutation.
For two admissible heuristics, h₂ dominates h₁ when h₂(n)≥h₁(n) for every node. Dominance compares estimates; it is not itself a condition ensuring that an arbitrary heuristic never overestimates. Both estimates must separately satisfy the relevant admissibility assumptions.
A Monte Carlo game simulation samples possible continuations and uses their outcomes to estimate position value. An evaluation function is the scoring mapping itself; sampling is one way of obtaining an estimate, while minimax backs values up and alpha–beta removes branches that cannot affect that backed-up decision.
AI-S06 Prediction, transfer and explicit representations
Transfer learning reuses representations or a model learned on an earlier task for a new task, for example adapting pretrained image features to new image classes. This is a reuse strategy, not a specification that the new task has no labels or rewards.
Support-vector machines include supervised classification and regression methods. They use support vectors in their decision function rather than being defined by a next-state conditional-dependence assumption. In estimation, variance measures how predictions change across different training samples; overfitting instead names poor generalization caused by fitting training-specific details.
An ontology describes entities or individuals, classes and properties and may state logical relationships and restrictions. It organizes explicit conceptual knowledge. Conditional probability tables and a probabilistic factorization are additional modeling commitments, not inherent in the word ontology.
An application programming interface (API) exposes defined operations through which software requests functionality. It can be an interface used by an agent, but the interface alone is not the general entity that perceives an environment and selects actions.
AI-S07 Behavior tests, understanding and software tests
Searle’s Chinese-room argument challenges whether executing formal symbol-manipulation rules is sufficient for understanding. It is a philosophical argument about understanding, not the conversational judge-and-hidden-participant procedure of the Turing test.
Black-box software testing examines externally visible functionality without inspecting implementation internals. A specification may concern any software behavior; this testing method does not by itself require conversational indistinguishability from a human.
An asset is something valuable: data, software, hardware, service or reputation.
A threat is a potentially harmful circumstance; a vulnerability is an exploitable weakness; an attack is an actual attempt; a control reduces likelihood or impact.
A software flaw is not automatically an active attack.
Risk concerns likelihood and consequence, not a universally meaningful numeric product of two unmeasured labels.
Phishing impersonates a trusted source to obtain secrets or induce an unsafe action; spear phishing targets a specific person.
Verify a request through an independently known channel.
Shoulder surfing observes entry; pretexting invents a reason for disclosure.
Monitoring software used with authorization is not necessarily an attack merely because it records activity.
Masquerade claims another identity.
ARP spoofing poisons local IPv4-to-MAC associations; DNS spoofing/cache poisoning supplies false name resolutions; IP spoofing falsifies a source address.
An intermediary attack intercepts and can alter exchanges.
A replay reuses a valid old message; nonces, timestamps and sequence checks can reject it.
Session hijacking steals or predicts a valid session token.
Protect transport, regenerate session IDs after login, restrict cookies and check authorization server-side on every sensitive request.
SEC06 DoS, wireless attacks and layer-specific defenses
DoS exhausts or disables a resource; distributed DoS uses multiple sources, often bots or reflected/amplified responses.
A SYN flood leaves many incomplete TCP handshakes occupying state.
DNS flooding targets query capacity; NXDOMAIN attacks generate queries for nonexistent names to stress resolvers.
Fragment floods abuse reassembly or packet-processing resources.
Rate limits, SYN cookies, filtering and upstream capacity controls address different bottlenecks.
Rogue access points imitate or bypass approved wireless service.
Bluesnarfing steals Bluetooth information; bluejacking sends unsolicited Bluetooth messages.
Phishing is not specific to wireless.
Match a defense to its layer: authenticated IPsec can resist IP impersonation, DNSSEC authenticates DNS data, TLS authenticates/protects application transport, and bounds-safe code prevents overflows.
HTTPS cannot fix an unsafe memory copy in a server.
A common access sequence is identify the subject, authenticate the claim, authorize the operation, then record relevant events.
Identification is the username/claim, not its proof.
When a sequence begins with authentication, distinguish it from the preceding identification stage.
User-to-host means a user proves identity to a host; host-to-user means the host proves its identity to a user; the arrow names the prover and verifier.
Knowledge is a password/PIN, possession is a token/card, and inherence is a biometric such as a fingerprint.
Behavioral biometrics include typing rhythm or handwriting; some textbooks call these “something one does.” A body characteristic is not “three-factor authentication”: one biometric is one factor.
Password plus PIN remains one factor class; card plus PIN is two.
An OTP’s factor depends on its delivery/generation mechanism.
Brute force enumerates guesses; dictionary attacks prioritize likely words; credential stuffing tries previously leaked credentials on another service.
Online attempts face server rate limits; offline attacks against stolen verifiers do not.
Short passwords can fail in either setting.
Use unique long secrets and password managers, rate limiting and suitable MFA; store salted slow password hashes, not reversible plaintext passwords.
A salt prevents shared precomputed lookup, but is not secret.
OAuth is an authorization framework: a client obtains limited access tokens, the authorization server authenticates/obtains approval from the resource owner, and the resource server validates tokens for protected data.
The authorization server can delegate identity checks.
OAuth alone does not define a complete end-user login identity protocol; OpenID Connect adds an identity layer.
An ACL associates an object/resource with allowed subjects or actions; a network ACL matches traffic such as address, protocol and port.
Classification and filtering are direct effects; high availability or malware detection is not guaranteed by an ACL.
DAC lets owners grant permissions; mandatory control enforces labels and policy that ordinary owners cannot override.
RBAC gives permissions to roles and assigns users to roles.
ABAC evaluates subject, object, action and environment attributes.
Rule-based controls apply explicit conditions, such as time or source network.
Least privilege gives only needed rights, for needed time.
Separation of duties splits sensitive steps across parties.
Deny by default, mediate every access and revoke stale permissions.
Allowing SELECT but denying UPDATE is an access-control decision that helps integrity; it does not by itself enforce all valid business-state transitions.
The simple-security rule prohibits reading above a subject’s level; the star rule prohibits writing down.
The strong-star variant permits writing only at the same level.
With TS>S>C>U, an S subject can read C under the simple rule but cannot write C under star; compartments and discretionary restrictions may still deny access.
Strict Biba protects integrity by preventing read down and write up: untrusted lower-integrity input should not contaminate higher-integrity results.
Clark–Wilson protects integrity through certified well-formed transformations, integrity checks and separation of duties.
It is not a confidentiality model. “MAC” is an enforcement category and does not force every system to use Bell–LaPadula rather than another label policy.
Protect equipment against theft, unauthorized connections, heat, humidity, water, electrical surges and fire.
A UPS supplies temporary conditioned power; it is normally protective, but faulty installation/battery failure can itself be hazardous.
A disconnected machine loses many network attack paths yet remains exposed to insiders, removable media, supply-chain attacks and physical access.
There is no universal “most secure computer” without a threat model.
Defense in depth layers independent controls.
Minimization removes unnecessary software and services; compartmentalization limits blast radius.
Fail securely means errors do not silently grant permission.
Uniform configurations simplify patching and prediction but create correlated failures; diversity may reduce common-mode compromise while raising administration cost.
Choose protection proportional to asset value and credible threats.
SEC12 Cryptographic vocabulary and security assumptions
Plaintext is the original message, ciphertext its encrypted representation, a key is input to an algorithm, encryption computes C=E_k(P), and decryption recovers P=D_k(C).
The five conventional symmetric ingredients are plaintext, encryption algorithm, secret key, ciphertext and decryption algorithm.
Cryptanalysis seeks recovery or other breaks without the authorized secret; cryptology includes cryptography and cryptanalysis.
Steganography hides that a message exists; encryption hides its meaning.
Assume the algorithm is known and protect keys: secrecy of implementation is not the main security argument.
A b-bit key has 2^b possibilities; exhaustive search averages roughly half the space if keys are uniformly random.
Security depends on algorithm, key size, randomness, mode and implementation.
Symmetric cryptography is not inherently less secure than public-key cryptography, and speed ratios are not fixed constants.
DES has a 64-bit block, 56 effective key bits (eight other bits serve parity), and 16 Feistel rounds.
After initial permutation, each round computes L_i=R_(i-1), R_i=L_(i-1) XOR f(R_(i-1),K_i).
Its right-half expansion makes 48 bits, XOR mixes a 48-bit subkey, eight S-boxes each map six bits to four, and permutation rearranges the 32 output bits.
The outer S-box input bits select a row and the inner four select a column.
The nonlinear S-boxes resist simple linear descriptions.
Feistel inversion uses the same overall structure with reversed round keys; f need not itself be invertible.
Final swapping/permutation completes DES.
DES and triple DES are legacy algorithms, not choices for new protection.
Triple DES repeats DES operations but does not provide 168-bit effective security merely because three 56-bit keys are supplied.
A certificate binds a public key to a named subject through an issuer signature.
Validate the chain to a trusted root, intended hostname, time validity and applicable key usage/revocation policy.
A genuine certificate is not proof that a business is honest.
TLS succeeds obsolete SSL and supplies an authenticated protected channel.
A handshake negotiates parameters, authenticates the server and sometimes the client, and establishes keys; record protection uses symmetric authenticated encryption.
Exact messages depend on TLS version: the old ChangeCipherSpec narrative is not a universal TLS1.3 sequence.
HTTPS is HTTP over TLS.
It protects HTTP paths, headers and content on the channel, but does not hide all metadata such as IP endpoints and traffic timing, nor protect data after a compromised endpoint decrypts it.
SSH protects remote login, commands and file transfer such as SFTP; it supports host keys and several client-authentication methods.
IPsec protects IP traffic at network layer.
AH provides integrity/origin authentication, not encryption; ESP can provide confidentiality and integrity; IKE negotiates security associations and keys.
Transport mode protects upper-layer payload; tunnel mode encapsulates an inner IP packet inside an outer header.
A VPN is a logical private connection; its actual security depends on the chosen authenticated tunnel.
PGP/OpenPGP combines symmetric content protection with public-key key handling and signatures.
S/MIME uses certificates for signed and/or enveloped MIME content.
Signatures can be sent separately/clear-signed without confidentiality; enveloped data encrypts content and wraps content keys for recipients.
SET, Secure Electronic Transaction, was a Visa/Mastercard-led specification for protecting card transactions using certificates and signatures; it is distinct from a payment-processing system or ordinary HTTPS.
One signed-and-encrypted S/MIME construction first signs the MIME entity, packages its content and signature, then encrypts that signed entity with a fresh symmetric content key.
Protect a copy of that key for each recipient.
A recipient recovers the key, decrypts the signed entity and verifies its signature using the validated signer certificate/public key.
Signing is not generic private-key encryption.
S/MIME permits other nesting orders; specify the order and resulting coverage.
Stateless packet filtering matches headers such as source/destination, protocol and ports.
Stateful inspection tracks permitted connection context; application proxies terminate and relay application exchanges and can inspect their content.
A circuit gateway relays connections, commonly SOCKS, without full application-content interpretation; textbooks associate it with session/transport functions.
Such a gateway need not encrypt and is not automatically a VPN.
Host firewalls protect individual machines; network firewalls segment networks and can create a DMZ for public-facing services.
Rules should be explicit, ordered as implemented, least-privilege and logged appropriately.
Stateful and next-generation devices can also filter ports; port filtering is not exclusive to one firewall category.
Bypass paths, insiders, encrypted uninspected content and infected removable media limit firewall protection.
Hardware firewall does not imply any fixed number of ports.
Signature detection recognizes known patterns; anomaly detection compares with a baseline and may detect novel behavior.
Neither guarantees every attack is detected; anomaly detection can raise many false positives, and signatures can sometimes match variants.
A true positive is a real attack detected, false negative is a missed attack, false positive is innocent activity flagged, and true negative is innocent activity accepted.
Recall=TP/(TP+FN); precision=TP/(TP+FP).
Detecting 90 of 100 spam messages with five innocent messages flagged gives recall90%, precision90/95≈94.7%.
Obfuscation makes code harder to understand and can hamper analysis, but does not reliably protect embedded secrets or remove vulnerabilities.
A buffer overflow writes beyond allocated bounds and can corrupt data or control information; code execution is a possible consequence, not its definition or an inevitable outcome.
An array of eight bytes cannot store eight text characters plus a terminating zero.
Bounds-check lengths and indexes, consider integer overflow, use safe abstractions and validate library return values.
Canaries, non-executable memory and address randomization reduce exploitability but do not repair the underlying write.
Validate expected type, length, range and structure at trust boundaries.
Server validation is essential because clients are controllable.
Encode output for its destination; validation is not a universal substitute for query parameterization or HTML-context encoding.
Security patches repair known weaknesses; a zero-day may lack a vendor fix, but segmentation and other mitigations can still help.
SEC28 Trusted OS requirements and reference mediation
A trusted OS is relied on to enforce a stated security policy.
Relevant mechanisms include identification/authentication, process and memory isolation, controlled privileges, object access enforcement, protected auditing, safe resource reuse, trusted boot/update paths and recovery behavior.
The trusted computing base comprises components whose failure can violate policy; smaller, analyzable boundaries simplify assurance.
A reference monitor is an abstract access-checking mechanism: it must mediate every relevant access, resist tampering and be sufficiently small/simple to analyze.
A security kernel implements core enforcement.
A firewall can mediate its traversing traffic but cannot enforce every host-memory access.
Assurance is justified confidence that controls implement the claims; functionality is what controls claim to do.
A GUI or multitasking support alone does not establish trust.
SEC29 Independent evaluation, certification and assurance
Under Common Criteria, define the Target of Evaluation (TOE), its configuration and environment.
A Security Target (ST) states threats, assumptions, objectives, functional requirements and assurance requirements; a Protection Profile describes reusable requirements for a product category.
Evaluators examine developer evidence, test and analyze vulnerabilities against those claims.
A certification body oversees/reviews the evaluation and issues the certification decision; sponsors commission work and developers supply product/evidence.
An Evaluation Assurance Level packages assurance requirements; EAL1–7 express increasing evaluation rigor, not a universal ranking of security functions.
A higher number does not make a product with different scope automatically safer.
CCRA is a mutual-recognition arrangement, not a single worldwide testing laboratory.
A certificate applies to a specified product/configuration and claims, not immunity to all future attacks.
Transactions group a transfer’s debit and credit atomically; concurrency control prevents unsafe interleavings.
Roles/ACLs limit who may update, but constraints and transaction logic determine whether an authorized update is valid.
Write-ahead logging persists recovery records before dependent data-file changes, supporting recovery after a crash.
Backups, restore tests and separately protected logs recover from deletion/corruption; replication provides alternate service capacity but does not replace backups.
Redundancy improves availability only with appropriate failover and independent failure handling.
Distinguish confidentiality controls from reliability controls and from integrity constraints.
Inference reveals protected facts by combining individually permitted outputs with other knowledge.
If a report gives a two-person salary total and one salary is known, subtraction reveals the other.
Blocking direct SELECT of a salary column does not stop that inference.
Restrict small groups and overlapping queries, track query history, coarsen/suppress results, or introduce carefully designed noise; each trades utility against leakage.
A multilevel database stores items at different labels and enforces mandatory policy using subject clearances, classifications and compartments.
Bell–LaPadula-style read/write restrictions prevent direct downward confidentiality flow; trusted declassification is a separate controlled action.
Views alone are not proof of multilevel isolation.
Covert channels, query results and error messages may still reveal information, so evaluate both direct access and indirect inference.
SEC33 Policy, incident response and recovery objectives
A security policy states responsibilities and rules; a procedure supplies the steps.
Policies coordinate protection, reduce risk and define acceptable use, access review, incident handling and recovery.
They do not prescribe merely “passive system use.” Awareness training teaches reporting and independent verification; enforcement and usable procedures make it operational.
Prepare response roles/tools, detect and analyze, contain the incident, eradicate the cause, restore verified service and learn from the evidence.
Preserve useful protected logs.
Disaster recovery restores IT after disruption; business continuity sustains business functions through workarounds and alternate facilities.
RTO is a recovery-time target; RPO measures the tolerable age of lost data.
A backup schedule must satisfy the required recovery point, and a restore test must demonstrate that data can actually be recovered.
SEC-S01 Command injection and the data-to-command boundary
OS command injection occurs when an application lets untrusted input affect a command executed by the host operating system, often through unsafe construction of a shell command. The command runs with the application's effective privileges. This is an injection flaw in command interpretation, unlike fuzzing, which supplies varied inputs to discover defects.
Prefer a suitable library API over constructing a shell command. Where command execution is required, keep the executable and arguments under strict control and validate against the expected permitted structure; merely blocking a few suspicious characters is not a general proof of safety.
WannaCry, also known as WannaCrypt, is ransomware with worm-like propagation. It encrypts files and demands payment to restore access. Its name identifies malicious software rather than a network-security protocol. Malware names must be distinguished from defensive controls such as intrusion detection, intrusion prevention and physical protection.
SEC-S03 Distinguish network roles and protocol names
A router forwards IP packets between networks; forwarding alone is different from detecting suspicious behavior or enforcing a firewall's security policy. SNMP means Simple Network Management Protocol and provides a framework for monitoring and controlling managed devices through management information. It is not a remote-shell service.
AAA names authentication, authorization and accounting functions, rather than a particular remote-shell channel. SSH expands to Secure Shell and provides secure remote login and related network services. PGP expands to Pretty Good Privacy; its message-protection design combines conventional and public-key encryption with digital signatures. Protocol purpose matters when several technologies all contribute to security.
Use a scope matching the subnet, exclude manually assigned server/router addresses, set correct options and provide a relay when client broadcasts must cross a router.
Static assignments and DHCP can coexist; avoid address conflicts.
DHCP lowers repetitive administration but availability/security depend on deployment and protection from rogue replies.
It does not guarantee connectivity whenever a device changes location.
For a returning client, inspect current lease/address, reachable server/relay, free pool capacity and logs.
New devices can exhaust a pool, but absent observations this is only a hypothesis.
Some clients self-configure IPv4 link-local addresses such as 169.254.2.33 after DHCP failure; these support same-link communication, not ordinary routed Internet access. 0.0.0.0 is unspecified and 255.255.255.255 is limited broadcast.
Forward resolution obtains an address from a name, using A for IPv4 and AAAA for IPv6.
Reverse lookup uses a PTR record in the reverse namespace to obtain a name from an address.
CNAME aliases a name, MX identifies mail exchangers and NS identifies authoritative name servers.
Forward and reverse records need not both exist or be perfect inverses.
Resolvers cache answers for their TTL.
Query nslookup name or specify the DNS server explicitly; compare the configured resolver with the authoritative answer when appropriate.
A successful ping by address but failed name lookup suggests naming/configuration trouble.
Ping by name may display a resolved address, but nslookup is the direct DNS diagnostic. “Resolving” is a general term that includes forward resolution.
NSA07 Choose the command that exposes the required state
Windows ipconfig shows addresses, mask and gateway; ipconfig /all adds complete adapter configuration including physical/MAC address, DHCP and DNS information. /renew requests renewal, /release releases a dynamic address and /flushdns clears the client DNS cache.
Linux ip addr and ip route show interface addresses and routes; exact persistent configuration varies by distribution.
netstat displays connections/endpoints/protocols and TCP states; netstat -ano displays numeric addresses/ports and PIDs.
Use the exact command name netstat rather than netstart. ping probes IP reachability; traceroute/tracert reveals responding hops using TTL/hop-limit expiry.
ICMP filtering can prevent replies without proving the service is down. nslookup inspects DNS.
Define the symptom, scope, time and recent changes; gather the configuration, baseline and logs.
Form a testable hypothesis, test the least disruptive explanation, isolate the failing component, apply a targeted fix, verify the user service and document the result.
Change one relevant factor at a time when possible.
A reboot can hide evidence and is not a diagnosis by itself.
Use bottom-up checks from physical link, top-down checks from application errors, or divide-and-conquer by testing a middle layer.
Divide-and-conquer narrows the working/failing boundary; it is not random trial-and-error.
Rebooting, updates, resetting settings and scanning can all be troubleshooting actions in suitable circumstances; use fault evidence to choose among them.
Check power, cable/connector and link state, then NIC/driver state, VLAN membership, address/prefix, local gateway, route, DNS and finally application port/authentication.
A recognized NIC makes a missing driver less likely, not proof of a working physical link.
Ethernet commonly uses RJ45 connectors; an RJ11 telephone jack is not the expected Ethernet connection.
If same-subnet traffic works but remote traffic fails, compare gateway/routes and filtering.
If ping fails but the application connection works, ICMP filtering is plausible.
If an application port is refused, the destination is reachable enough to reject it; inspect service/listener policy.
A timeout can result from loss, filtering or a down host and needs more evidence.
DNS resolves names; DHCP supplies host configuration.
SMTP sends/relays mail, while IMAP/POP retrieve it.
FTP is a named file-transfer protocol; HTTP also transfers files, so “transfers files” is not an exclusive FTP description.
HTTP/HTTPS serve web resources.
SSH provides encrypted remote login; SFTP transfers files over SSH and differs from FTP or FTPS.
A VPN extends private connectivity over another network; secure tunneling commonly encrypts/authenticates traffic but depends on protocol/configuration.
RTP carries real-time media timing/sequence information, often over UDP; it does not guarantee timely delivery.
Network printers expose services shared by clients.
Provide accounts, permissions, configuration, monitoring and recovery for each service, not just its protocol name.
A workgroup has locally managed accounts on individual machines; sharing may require local credentials and per-host configuration.
A domain centralizes identities and policies through directory infrastructure.
These are administrative arrangements, not physical topologies.
Avoid treating an old recommended workgroup size as a hard protocol limit.
HomeGroup is a historical Windows sharing feature, not another name for an AD domain.
A domain controller runs AD DS, authenticates domain accounts and participates in directory replication.
Redundant controllers improve service continuity only if dependencies and failure domains are considered; two virtual controllers on one failed physical host are not independent availability.
Provisioning requires correct addressing, DNS, time and supported OS/hardware; version-specific minimum sizes are not universal architecture rules.
A directory object represents a user, computer, group or resource and has schema-defined attributes.
Security principals have SIDs; display names are not the sole security identity.
A domain groups directory objects and a replicated domain database.
A tree groups domains in a contiguous DNS namespace; a forest groups trees with a shared schema/configuration and global-catalog framework.
OUs organize objects and provide convenient scopes for delegated administration and Group Policy; they are not separate forests/security boundaries.
Use groups to assign access and OUs to structure policy/delegation.
Schema changes require care because they propagate broadly; ordinary directory objects can be deleted, unlike the special restrictions on schema definitions.
Apply schema restrictions to the specific directory object type being discussed.
Sites group IP subnets to model network locality, influence controller selection and manage replication traffic.
They are distinct from domains/OUs.
AD replicates directory changes among controllers; notification can trigger pulls within a site while schedules/link costs influence traffic between sites.
Replication is not an independent backup of previous good states.
If domain A trusts B, B’s identities can be authenticated for resources in A, subject to permissions.
Trust alone grants no automatic file access.
Direction (one/two way) and transitivity (extends/does not extend) are independent.
An explicit trust is not necessarily one-way or nontransitive; the trust type/configuration determines that.
State the direction in words before drawing arrows.
Create named accounts, assign only needed groups/rights, disable departed users and audit privileged activity.
Authentication verifies the account; authorization permits operations.
A user right such as remote logon differs from a permission on one file.
Group-based administration is easier to review than many hidden individual grants.
If only one domain user cannot change a password, inspect that account’s cannot-change-password setting and relevant policy/permission before blaming all directory infrastructure.
Other possibilities include minimum password age, password rules or account state; the setting is a plausible exam cause, not a conclusion from failure alone.
Membership in Administrators does not inherently prohibit changing one’s password.
Privileged reset and user-initiated password change are different operations.
Windows file/folder permissions include read, write, read/execute, modify and full control, plus more granular rights such as delete.
Inherited and explicit entries, group membership, deny entries and object scope affect effective access; use the effective-access view for a real account rather than adding labels informally.
Network access can be constrained by both share and filesystem permissions.
Deleting can be an explicit permission in Windows; specify the operating system before comparing permission names.
Modify and full control are not identical: full control includes changing permission/ownership capabilities.
Separate data access from logon rights.
A user allowed to read a file is not necessarily allowed to write it or administer its parent folder.
/ is the filesystem root; /root is the administrative user’s home. /etc stores configuration, /home ordinary user homes, /var variable data/logs, /dev device nodes, /proc kernel/process information, /boot boot material and /tmp temporary files.
Cleanup/mount layouts vary; do not assume every partition has lost+found or every reboot erases every temporary directory.
ext2 is a Linux filesystem; ext4 is a later filesystem; HPFS is historically associated with OS/2, while swap is backing space rather than an ordinary user-file filesystem. fsck checks and optionally repairs filesystems through filesystem-specific tools; it is not init, halt or an inittab file.
Repairs require the filesystem’s supported offline/safe procedure.
Mount attaches a filesystem to a directory; partitioning, mounting, quotas and capacity belong to storage administration.
Linux can access some foreign-origin filesystems, including HPFS when its driver is available.
Filesystem origin and Linux driver support are different questions.
Swap is a paging area rather than an ordinary user-file filesystem.
ext2 is a native Linux-filesystem example; broader Linux filesystem support can also include HPFS, so distinguish origin from driver support.
RAID0 stripes for capacity/throughput with no disk-failure tolerance.
RAID1 mirrors; a two-disk mirror has one disk’s usable capacity and survives one disk failure.
RAID2 uses bit striping/Hamming-code redundancy, RAID3 byte striping with dedicated parity, RAID4 block striping with dedicated parity and RAID5 block striping with distributed parity.
RAID6 distributes dual parity and tolerates two disk failures.
RAID10 stripes mirrored pairs; survival depends on which disks fail.
With N equal disks of capacity D, RAID0 usable=ND, paired RAID1/10≈ND/2, RAID5=(N−1)D and RAID6=(N−2)D. Hardware RAID may offload work to controller resources/cache but does not universally outperform software RAID.
Rebuilds consume bandwidth; parity writes have overhead.
A large university/bank alone does not select a level.
Striping plus parity is not uniquely RAID5 unless distributed block parity is specified.
A security policy states required behavior, scope, accountable roles and enforcement.
Begin with assets/service objectives, assess threats and weaknesses, choose controls, define exceptions/incident procedures, approve/communicate, monitor and periodically review.
CIA means confidentiality, integrity and availability; neither sensitive-data protection nor availability alone is the universal primary goal.
A policy can require password controls, approved encryption, restricted administrative access, backups and patch deadlines; firewall rules implement part of it.
Open unrestricted wireless access conflicts with controlled internal access unless intentionally isolated as a guest service. “Use the system passively” is not a purpose of security policy.
Policies coordinate action and reduce risk; they do not guarantee every attack will fail.
Unspecified encryption alone does not guarantee both properties.
A password hash supports verification without recovering the original password; it is not a reversible credential store.
Encryption can protect a recoverable credential only if its key is separately protected.
Keep reusable secrets out of source code and routine logs; obtain them from an appropriately protected credential service or restricted runtime source.
Environment variables and configuration files are transport/storage choices, not automatic encryption.
A script that must authenticate to another service often needs the actual credential/token, so replacing it with a one-way hash will not work.
State whether the question is about password verification or recoverable service credentials.
Segmentation separates groups of systems and enforces allowed flows with routing/filtering policies; VLAN membership alone does not establish complete security.
NAC assesses device/user admission and can reject or quarantine unauthorized/noncompliant devices.
Authentication proves an identity, while access rules decide which resources it may use.
Use authenticated protected remote administration such as SSH or properly secured management services, with restricted source access and auditing.
VPNs provide protected connectivity under their defined security model; they are not packet analyzers.
Firewall filtering permits/blocks traffic according to policy; it is not inherently encryption.
Losing remote connectivity while changing a management route/firewall is an operational risk to plan for.
Python subprocess is a module, not a universal shell command. run launches a child program and returns its result; capture_output collects stdout/stderr, text=True decodes text, timeout bounds waiting and check=True raises for nonzero exit.
Pass an argument list to avoid accidental shell interpretation; quote handling differs from composing a shell string.
Echo prints, grep searches text and ipconfig/ifconfig reports/configures networking; none is the general Python child-process abstraction.
Specify the scripting language before selecting subprocess for process execution.
File I/O, string operations and regex can all help manipulate configuration; choose according to the task.
Use the format’s parser for structured JSON/INI rather than blindly replacing every matching substring.
Open text with an explicit encoding and use with so files close even when processing fails.
For changes, validate the desired output, preserve a known-good copy, write to a temporary file in the same filesystem, then atomically replace the target where supported.
Check permissions and configuration syntax, reload the affected service, verify and retain a rollback.
Merely appending the same setting on every run is not idempotent.
Regex recognizes textual patterns; it does not encrypt, compress or rotate logs. search finds a match anywhere, while fullmatch requires the entire string to fit.
Use raw Python strings for backslash-heavy patterns, capture only the needed fields and treat unmatched/malformed lines explicitly.
Log rotation bounds file size and preserves historical segments; it is complementary to parsing.
Count the event actually requested, use timestamps/hosts to correlate, and separate absence of matches from failure to read the log.
Logs support security and performance analysis, so neither purpose is universally exclusive.
Separate argument parsing, preconditions, copying/archive creation and result reporting.
Require a source directory, avoid putting the backup inside that source, create unique output names and ensure a failed partial file is not mistaken for a completed backup.
Real backup policies also need application consistency, capacity checks, retention and independent protected copies.
The following teaching script packages a directory; it does not silently install a scheduled job.
NSA-S01 Operations principles versus development and delivery models
Least privilege limits an account or process to the rights its task needs. Agile development instead organizes frequent delivery and adaptation of software. Object-oriented programming organizes software around objects with state and behavior. Cloud computing supplies on-demand access to a shared pool of configurable computing resources. A development approach or hosting model does not itself define an access-rights principle.
Disaster recovery planning prepares for restoring systems and data after disruptive loss. Regular protected backups and tested restoration are part of that plan. Continuing operation despite a component failure is a fault-tolerance objective; possessing extra components alone does not establish that older valid data can be recovered.
NSA-S03 Initialization, shutdown and filesystem-check tools
In a traditional SysV-style system, init starts and supervises configured processes; /etc/inittab is its configuration file. The halt command stops the system through the supported shutdown procedure. Neither initialization, shutdown nor their configuration file is a filesystem-consistency check; fsck supplies that separate checking and optional repair role.
NSA-S04 What an ICMP reachability probe actually tests
Ping uses ICMP echo messages to test IP reachability. A reply shows that the addressed host and path support that exchange; no reply alone does not prove the host is disconnected, because filtering or loss can suppress responses. Traceroute instead discovers responding intermediate hops through packet-lifetime expiry; it is a path-discovery diagnostic, not the same question as an end-to-end echo test.
NSA-S05 Distinguish scripting features by their responsibility
Exception handling transfers control from a failing operation to a matching handler. A try block contains the attempted work; an except clause handles specified raised exceptions. A loop repeats operations, a conditional chooses an ordinary branch, and a function packages reusable work; these constructs do not by themselves intercept exceptions.
A module groups definitions and statements that can be imported. A class bundles data with functionality for its objects. These organize a program, while command-line parsing interprets the arguments and flags supplied at invocation. Their implementation can use functions or classes, but organization alone does not parse arguments.
A signal handler responds when a process receives a specified asynchronous event notification. Handling such a notification is distinct from reading CPU or memory measurements through an OS interface, a performance counter or a log that actually records the metric.
Write G=(V,Σ,P,S): finite variables V, terminals Σ disjoint from V, productions P and start variable S∈V. A production replaces its left side by its right side.
The language is L(G)={w∈Σ*:S⇒*w}.
A recognizer processes a word and accepts exactly the language members.
Grammars generate languages; automata recognize languages, not grammars.
Two grammars are equivalent when their generated languages are equal, regardless of rule counts or variable names.
One common word, equal alphabets or one-way inclusion is insufficient.
A regular expression denotes a language but is not itself the set of matched words.
Natural languages such as English are not the intended formal-language examples; give a precisely specified set instead.
AUT05 Chomsky hierarchy and the epsilon convention
Type 3 regular grammars correspond to finite automata; type 2 CFGs to nondeterministic PDAs; type 1 context-sensitive/noncontracting grammars to nondeterministic LBAs; type 0 unrestricted grammars to Turing recognizers.
In an unrestricted production α→β, α contains at least one variable; unrestricted does not mean any meaningless rewrite is allowed.
Use REG ⊊ CFL ⊊ CSL ⊊ DECIDABLE ⊊ RE, under the usual convention allowing S→ε with S absent from right sides when needed.
A deterministic finite automaton (DFA) is M=(Q,Σ,δ,q₀,F), with finite nonempty Q, start q₀∈Q, accepting set F⊆Q and total δ:Q×Σ→Q. Exactly one next state is specified per state/symbol pair; this does not mean the whole machine has one transition.
F may be empty, recognizing ∅.
State names q₀,q₁,… do not determine accepting status.
Start at q₀ and consume the entire input.
Accept iff the ending state is in F; visiting an accepting state earlier is insufficient. ε is accepted exactly when q₀∈F. A nonaccepting sink loops on every symbol and cannot reach acceptance; it still finishes after finite input.
Finite automata have finite memory encoded by states, not no state or no ability to remember any history.
AUT08 Minimum states: prefix, suffix and valid alphabets
For a fixed valid word w of length n, a DFA for strings ending in w needs n+1 states representing the longest consumed suffix that is a prefix of w. Overlapping prefixes determine fallback transitions.
Distinct prefixes are distinguishable by suitable continuations, proving the lower bound; do not add an unnecessary rejecting sink.
For strings starting with w, a complete DFA ordinarily has n matched-prefix stages, an accepting continuation state and a rejecting sink: n+2 when n≥1 and the alphabet allows mismatches.
Over a unary alphabet the sink may be unreachable.
If w contains a symbol outside Σ, the language is empty, whose minimal complete DFA has one rejecting state.
Thus starting abc over {a,b} needs one state, not five; five requires an alphabet containing a,b,c.
A nondeterministic finite automaton (NFA) permits zero, one or many successors: δ:Q×Σ→𝒫(Q).
An ε-NFA additionally permits moves without consuming input, using domain Q×(Σ∪{ε}).
Some books include ε moves in the term NFA; state the convention.
An NFA accepts iff at least one finite path consumes the complete word and finishes in F, including permitted ε moves before/after symbols.
Other paths may get stuck.
An NFA is not more expressive than a DFA: both recognize exactly REG.
Nondeterminism can make a description smaller.
A DFA is a special NFA after interpreting its unique successor as a singleton set. ε is a zero-input move, not an ordinary input character or permission to accept with unread input.
AUT11 Equivalence, minimization and diagram checks
First discard unreachable DFA states.
Partition remaining states into accepting/nonaccepting blocks; repeatedly split a block when two states transition on some symbol into different blocks.
Stable blocks are equivalence classes and can be merged.
Equivalent states have identical acceptance for every continuation; current acceptance alone is insufficient.
For DFA equivalence build pairs of states and search from the start pair.
Any reachable pair with exactly one accepting component supplies a distinguishing word; if none exists, the languages agree.
A partial diagram must first be completed consistently with a sink.
To reject a proposed RE quickly, compare ε and the shortest cycles: an accepting start plus an ab return cycle forces ε and ab into the language.
Classical expressions use ∅, ε, symbols, union, concatenation and star.
A union B is written A|B or A+B; postfix r⁺ means one-or-more r repetitions and is a different use of +.
Parenthesize when conventions might clash.
Star binds tightest, concatenation next, union last. r? means r|ε; r⁺=rr*.
(a|b)*a denotes words ending a; 0*10* denotes exactly one 1; a*(b|c) gives zero-or-more a's then exactly one b or c, so aab belongs but aaa and aaabc do not. (0|ε)(0|1)* is simply all binary words because ε permits any suffix.
Programming regex features such as backreferences may exceed classical regular-language power; wildcard dot is an extra notation, not a basic alphabet-independent theorem.
AUT13 Build expressions and convert representations
To require at least one a anywhere over {a,b}, use (a|b)*a(a|b)*. b*ab* requires exactly one a. At least two zeros uses (0|1)*0(0|1)*0(0|1)*; the zeros need not be adjacent.
Testing 010 distinguishes it from a requirement for substring 00.
For S→aS|ε, any number of a's is generated, giving a*.
RE→automaton uses ε-NFA fragments: parallel alternatives for union, connect accepting ends to the next fragment for concatenation, and add bypass/repetition ε moves for star.
Then apply subset construction.
For automaton→RE, eliminate a state k while updating edge i→j as rᵢⱼ | rᵢₖ(rₖₖ)*rₖⱼ; include new start/final nodes where required.
These operations preserve the whole language, not just tested examples.
If L is regular, some p≥1 satisfies: every s∈L with |s|≥p has a split s=xyz, |xy|≤p, |y|≥1, and xyⁱz∈L for every i≥0.
To disprove regularity, assume an arbitrary pumping length p, choose s, then show every allowed split can be broken by some i. Finding one bad split proves nothing; satisfying this necessary condition alone does not prove regularity.
For L={aⁿbⁿ:n≥0}, choose aᵖbᵖ.
Every allowed y=aᵏ with k≥1; pumping i=0 leaves fewer a's than b's. The contradiction excludes every DFA.
For an n-state DFA, an accepted word of length at least n repeats a state along its path, giving an accepted cycle that can be repeated indefinitely.
Thus a fixed DFA's language is infinite iff it has an accepted word of length at least its state count.
Use a recursive rule to enforce matched structure and a base rule to stop.
S→aSb|ε generates exactly aⁿbⁿ for n≥0: n recursive steps add n a's on the left and n b's on the right.
Derive aabb by S⇒aSb⇒aaSbb⇒aabb.
For n≥1 replace ε by base ab.
For aⁿbᵐ with n>m≥0, use S→aSb|A and A→aA|a: each S recursion adds a matched pair, then A adds at least one extra a. For balanced parentheses use S→(S)S|ε.
Validate soundness—each rule preserves the intended property—and completeness—decompose any desired nonempty word into pieces matching a production.
Merely producing several examples does not establish exact language equality.
Greibach normal form requires A→aA₁…Aₖ, k≥0: one leading terminal followed only by variables.
Handle ε separately through a fresh start that never appears on a right side.
A nonempty word of length n takes exactly n leftmost rule applications because each contributes one terminal to the prefix.
A constructive route removes ε/unit/useless rules, orders variables, substitutes rules beginning with earlier variables, removes left recursion, and substitutes until every rule begins with a terminal.
Some algorithms first convert to CNF; this is a method choice, not a universally mandatory first step.
Direct A→Aα|β can become A→βR, R→αR|ε, then further normalization handles ε.
GNF cannot retain direct or indirect left recursion.
A question demanding the first step must name its chosen algorithm.
CFLs are closed under union, concatenation, star, reversal and intersection with a regular language.
For CFL∩REG combine PDA control with DFA control, using the original stack; each consumed symbol updates both states, while an ε move leaves the DFA state unchanged.
The result is guaranteed context-free, not necessarily regular: intersect aⁿbⁿ with a*b* to get aⁿbⁿ.
CFLs are not closed under arbitrary intersection.
Both {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ} are context-free; their intersection aⁿbⁿcⁿ is not.
Nor are CFLs closed under complement or arbitrary difference.
CFL minus a regular language remains CFL by intersecting with the regular complement.
A failed construction of one proposed PDA proves only that construction fails, not that every PDA fails.
AUT26 Classify languages with justified boundaries
a*b* and {aⁿb:n≥0} are regular. aⁿbⁿ is CFL but not regular.
Over a two-symbol alphabet, wwᴿ is CFL, ww is not CFL; both are decidable. aⁿbⁿcⁿ is CSL but not CFL, and therefore decidable.
Every finite language is regular.
A stronger grammar or TM can still recognize any of these lower-family languages.
Unary prime length {aᵖ:p prime} is nonregular: choose prime q above pumping length p; if pump piece has length k≥1, using exponent q+1 gives length q(k+1), composite.
Every unary CFL is regular, so this language is not CFL either.
It is nevertheless context-sensitive: count the input in bounded workspace and test divisors.
The balanced-three-count, prime-length, palindrome and aⁿb examples above are all recursive languages.
To decide aⁿbⁿcⁿ, repeatedly mark matching triples, resetting the head between scans, then verify no unmatched symbol remains.
Each round marks additional input cells, so finitely many rounds suffice.
To decide ww, reject odd length, locate the midpoint using marks/counters, and compare corresponding symbols of the two halves; writable tape permits access a single stack lacks.
State both the acceptance test and why every input halts.
An off-line TM has a read-only input tape and separate read/write work tape.
Multitape, multihead, two-way-infinite-tape and nondeterministic TMs have the same language-recognition power as standard TMs, though simulation costs differ.
Two unbounded stacks can simulate a tape.
Turing completeness means ability to simulate general TM computation, not polynomial speed or literally using infinitely many cells in a finite run.
The Church–Turing thesis connects effective procedures to this formal model; it is not a proved runtime theorem.
A decider halts on every input and accepts exactly its language; these languages are recursive/decidable.
A recognizer must halt and accept every member, but on a nonmember may halt-reject or loop.
Its languages are recursively enumerable (RE), Turing-recognizable or semidecidable.
Looping is nonacceptance, not a rejecting halt.
An undecidable language may still have a recognizer.
Every decidable language is RE, and the containment is strict.
If L and its complement are both RE, simulate their recognizers in dovetailed steps until one accepts, obtaining a decider.
Conversely complementing a decider works because it always halts.
Flipping final states in an arbitrary recognizer fails to handle nonmembers that loop.
Recursive function theory's total computable functions are not merely programs written with recursive self-calls; partial computable functions may be undefined where computation does not halt.
HALT={⟨M,w⟩:M halts on w} is recognizable: simulate and accept upon any halt.
Suppose a decider H determines halting.
Construct D(x) that loops if H(x,x) says halt, otherwise halts.
Running D on its own description contradicts H in both cases.
Thus HALT is undecidable and witnesses RE beyond DECIDABLE.
Its complement is not RE, or both recognizers would yield a decider.
Rice's theorem makes every nontrivial semantic property of a TM's recognized language undecidable.
Nontrivial means some recognized languages have it and some do not.
Empty language, contains ε and at least three accepted words qualify.
Number of states and whether a particular symbol is written are machine-behavior/syntactic properties, not automatically language properties; prove such claims separately.
Undecidable means no general decider exists, not merely no algorithm is currently known.
DFA/NFA word membership is decidable by simulation or reachable state sets.
FA emptiness is reachable-accepting-state search; DFA equivalence searches the product for an acceptance disagreement.
CFG membership is decidable by parsing/CYK and emptiness by marking variables that can generate terminal strings.
These procedures halt and are not the same as deciding arbitrary TM membership.
TM acceptance on input is RE-complete and undecidable; HALT is undecidable.
General CFG ambiguity and CFG equivalence are undecidable even though membership for a given CFG and word is decidable.
A concrete grammar's two parse trees can establish that particular grammar is ambiguous; this does not give an algorithm deciding ambiguity for every grammar.
FORTRAN/programming-language questions must distinguish CFG-style syntax, semantic restrictions and Turing-complete computation; a language's name alone does not choose one formal classification.
A many-one reduction A≤mB is a total computable transformation f satisfying x∈A iff f(x)∈B. If B had a decider, compute f and invoke it to decide A. Therefore known-undecidable A reduced to B proves B undecidable.
Showing B≤mA alone does not establish B's hardness.
Example HALT≤mA_TM: given ⟨M,w⟩, construct N that ignores its input, simulates M(w), and accepts if M ever halts, including rejecting halts.
Then ⟨N,ε⟩ is accepted iff M(w) halts.
Construction of N's finite description terminates; the simulation inside N may not.
Reductions require both yes and no directions and a computable mapping, not just a resemblance between two problems.
Time counts computation steps; space counts cells/memory used, specifying whether read-only input is excluded.
For a deterministic decider use the maximum over all length-n inputs; for a time-bounded nondeterministic decider every branch meets the bound.
Big-O is an asymptotic upper bound, not inherently a worst-case label: it can describe a worst-, average- or best-case function. Θ adds a matching lower bound.
Growth typically orders 1,log n,n,n log n,n²,2ⁿ,n!.
A fixed polynomial nᵏ differs from exponent 2ⁿ.
Encoding matters: the number N in binary has Θ(log N) bits, so O(N) work is not polynomial in its binary input length.
Pseudopolynomial algorithms depend on numeric magnitude rather than encoding length.
A polynomial of enormous degree need not be practical.
Complexity classes here contain decision languages.
P consists of deterministic polynomial-time decidable languages; NP consists of nondeterministic polynomial-time decidable languages, equivalently polynomially verifiable yes-instances with polynomial-size certificates.
A verifier must accept some certificate exactly for yes-inputs; no certificate may falsely establish a no-instance.
NP means nondeterministic polynomial, not non-polynomial.
For CLIQUE, the certificate lists k vertices; verify they are distinct and every pair is an edge.
This is polynomial in the graph encoding.
P⊆NP because a verifier can ignore its certificate and run the P algorithm.
P=NP remains open; NP does not mean definitely hard or definitely outside P. Finding versus verifying is an intuition for witnesses, not a rule that all NP instances need exponential search.
First CLIQUE belongs to NP by the pairwise-edge certificate check.
For a 3-CNF formula with m clauses, make one vertex for each literal occurrence.
Connect two vertices iff they come from different clauses and are not complementary literals.
Ask whether the graph has a clique of size m. Construction takes polynomial time and space.
A satisfying assignment supplies one true literal per clause; they are mutually consistent and form a clique.
Conversely an m-clique selects one occurrence per clause, with no variable chosen both positively and negatively, so assign those literals true and extend remaining variables arbitrarily.
Both implications prove equivalence.
For (x₁∨¬x₂)∧(¬x₁∨x₂∨x₃)∧¬x₃, the assignment (true,true,false) satisfies all clauses because ¬false is true.
PSPACE is ⋃kSPACE(nᵏ), using deterministic polynomial workspace.
NP⊆PSPACE because candidate polynomial witnesses can be enumerated and checked one at a time, reusing memory; exponentially many candidates do not require retaining them all.
Savitch's theorem gives NSPACE(s)⊆DSPACE(s²) for appropriate s≥log n, hence NPSPACE=PSPACE.
It does not prove P=NP.
TQBF asks whether a fully quantified Boolean formula is true and is PSPACE-complete.
Evaluate ∃x by trying one branch or the other; evaluate ∀x by requiring both.
Depth-first evaluation stores assignments and recursion state using polynomial space despite potentially exponential time.
For example ∀x∃y(x↔y) is true, but ∃y∀x(x↔y) is false.
PSPACE-complete means membership plus hardness for every PSPACE language under the stated reduction.
Here L/NL use logarithmic workspace; EXPTIME is ⋃kTIME(2^(nᵏ)), an upper-bound class that also contains P, not a statement that every member requires exponential time.
Suitable hierarchy theorems prove P⊊EXPTIME and PSPACE⊊EXPSPACE.
They do not establish every adjacent containment strictly.
P versus NP, NP versus PSPACE and PSPACE versus EXPTIME remain unresolved. coNP contains complements of NP languages; P⊆NP∩coNP, and NP=coNP is open.
If any NP-complete language is in P, all NP collapses to P. This does not make every decidable language polynomial or make undecidable problems decidable.
Avoid blanket claims about all cryptography or all problems becoming easy; the class and encoding matter.
For S→11S|0A|1A and A→0|1|0S, every reachable form has at most one variable, at the right end.
A complete terminal word is still a sentential form.
For example S⇒11S⇒1111S⇒111111S⇒1111110A⇒11111101.
Returning to S appends a pair 11,00 or 10; use that invariant to rule out impossible prefixes rather than guessing from string length.
For A→aB|bA|bBa and B→bB|cA|b, specify a start variable first.
With A assumed, a terminating membership test recursively removes the required a/b prefix or b…a wrapper; B either matches b or removes b before B/c before A. Every recursive residual is shorter.
Apply the membership test to every candidate word; none qualifies in this four-word example under the assumed start A.
Use the membership test to justify whether a candidate word belongs to the language.
AUT-S01 Computability, complexity and abstract machines
Computability theory asks whether an effective algorithm can solve a problem at all. For a decision problem, a decision procedure must terminate with the correct yes-or-no result on every input.
Computational complexity theory studies the time and memory resources required to solve problems as functions of encoded input size. Automata theory studies abstract machine models and the languages they recognize; these subjects overlap but ask different questions.
AUT-S02 The stack discipline and its queue contrast
A stack is last-in, first-out: push adds an item at the top and pop removes the top item, so the most recently pushed item is removed first. A PDA accesses this top rather than an arbitrary interior position.
A queue is first-in, first-out: insertion at the rear and removal at the front returns the oldest waiting item. A linked list can implement a storage discipline, but the implementation container is different from the abstract push/pop or enqueue/dequeue access rule.
AUT-S03 Why satisfiability was the first NP-complete problem
Boolean satisfiability was the first problem proved NP-complete, through the Cook–Levin theorem. Its hardness proof starts directly from an arbitrary nondeterministic polynomial-time computation and constructs a Boolean formula that is satisfiable exactly when an accepting computation exists.
This starting point matters: once one NP-complete problem is available, later hardness proofs can reduce that known problem to a new target. Membership in NP remains a separate obligation. Checking a satisfying assignment is efficient; whether finding one is always polynomial-time remains unresolved.
AUT-S04 Finite procedures are different from undecidable tasks
Sorting a finite numeric list is a terminating computation. Quicksort, for example, chooses a pivot, partitions the other entries and recursively sorts the smaller sublists. Each recursive subproblem has fewer entries. A large running time does not make the task undecidable.
A finite linear system with exactly represented rational coefficients can be processed by Gaussian elimination and back substitution. Row exchanges handle unsuitable pivots; row reduction detects inconsistency or leaves free variables describing multiple solutions. These finite algebraic procedures differ from a general halting decider, which does not exist.
The conventional sequence is lexical analysis → syntax analysis → semantic analysis → intermediate-code generation → optimization → target-code generation.
Scanning turns characters into tokens; parsing builds structure; semantics checks declarations and types; synthesis produces implementation code.
A phase is a logical activity; a pass is a traversal that can combine activities.
The front end handles source-language rules; a middle end analyzes and transforms IR; the backend handles target details.
Symbol-table management and error reporting support multiple phases rather than forming one mandatory seventh final phase.
Optimization can occur at several levels, including after instruction selection. “Final phase” means code generation in the standard six-phase teaching pipeline.
Regular expressions use concatenation, alternation r|s, Kleene star r* for zero or more, and r+ for one or more.
In a simplified alphabet, identifier = Letter(Letter|Digit)*; it permits a single letter and forbids a leading digit.
A C-like ASCII rule commonly also allows underscore:
[A-Za-z_][A-Za-z0-9_]*
State the convention instead of claiming this covers every language’s identifiers.
Letter(Letter+|Digit*)* denotes the same language as Letter(Letter|Digit)* under ordinary regular-expression semantics: repeated blocks can contain any trailing letter/digit sequence.
At each input position, choose the longest matching lexeme; if equal lengths match multiple flex rules, choose the earliest rule.
Thus ifx is an identifier rather than if followed by x; <= and ++ are each one operator token.
An implementation may recognize an identifier first and then consult a keyword table.
For the ordinary C++ header:
for (int i = 0; i <= 10; i++)
The tokens, split into two display lines, are:
for, (, int, i, =, 0, ;
i, <=, 10, ;, i, ++, )
There are 14 tokens, irrespective of spacing.
The increment operator is one token.
A comment contributes no ordinary parser token after preprocessing.
For the loop header above, 4,5,9 and 10 are incorrect token counts; the count is 14.
A grammar is ambiguous if at least one terminal string has two different parse trees, equivalently two leftmost derivations.
Merely changing derivation order on the same tree does not establish ambiguity.
E→E+E|E*E|id allows different trees for id+id*id.
Use E→E+T|T, T→T*F|F, F→(E)|id to give * higher precedence and both operators left associativity.
For subtraction, a−b−c then groups (a−b)−c. The dangling-else grammar permits else to attach to either nested if; a nearest-unmatched-if rule or grammar rewrite resolves it.
Taking a leftmost derivation by itself does not resolve ambiguous interpretation.
For A→Aα|β, where β does not start with A, introduce a new nonterminal A′ and use:
A→βA′
A′→αA′|ε
This preserves the generated language; tree shape changes, so semantic actions must preserve intended associativity.
Indirect left recursion follows a cycle through other nonterminals and also needs removal for ordinary predictive descent.
Left factoring rewrites A→αβ|αγ using:
A→αA′
A′→β|γ
It postpones a choice until after the common prefix.
It does not by itself remove ambiguity or guarantee LL(1).
LR parsers can handle suitable left-recursive grammars; ordinary unmodified recursive descent can recurse forever before consuming input.
Bottom-up parsing starts from input and reduces toward S, constructing a rightmost derivation in reverse.
A handle is a production RHS occurrence whose reduction is the next step of that reverse derivation.
Not every substring matching a RHS is a handle in the current context.
Shift pushes the next input token and a state; reduce replaces a recognized RHS by its LHS and consults GOTO; accept recognizes completion; error reports an invalid situation.
For A→XYZ, pop three grammar symbols and their states, expose state q, then push A and GOTO[q,A]. “Go” is not a separate standard shift-reduce ACTION, although GOTO is essential table machinery.
LL, LR and recursive-descent parsers can all handle nested parentheses for suitable grammars.
An explicit or implicit stack, not the LR label alone, supports unbounded nesting.
Both LL and LR can use parsing tables.
Deterministic LL/LR grammars must be unambiguous; a general ambiguous grammar requires rewriting, disambiguation policy or a generalized method such as GLR.
An operator grammar conventionally forbids adjacent nonterminals on a RHS and usually ε productions.
Ordinary right-linear regular grammars also lack adjacent nonterminals, so that property alone does not uniquely identify the operator-grammar category.
A symbol table maps names or symbol identities to attributes: type, scope, width, storage offset, parameter signature, constant information or linkage.
A hash table gives expected O(1) insertion/lookup with suitable hashing; a stack of scope tables supports lexical nesting.
Search the nearest scope first, insert declarations in the current scope, and remove visibility when leaving it.
Scanning may intern a spelling first; semantic analysis determines the declaration and type.
Implementations differ, so first interaction is conventional rather than universal.
Not every punctuation token needs a symbol-table entry; literals may use a separate literal table.
A hash table is an implementation, not the information’s semantic role.
COMP20 Names, types and advanced language features
Distinguish lexical recognition, grammatical structure and semantic constraints.
In obj.method(x), the scanner recognizes identifiers and punctuation; the parser recognizes a member call; semantic analysis resolves the receiver, accessible member and argument types.
Overload resolution chooses among signatures using static types; overriding can select an implementation at runtime.
Nested scopes require declaration identity rather than spelling alone: an inner int x can shadow an outer float x. Closures capture free variables from lexical environments; lifetime can outlive the creating stack frame.
Generic functions need parameter constraints or instantiation checks.
These features require symbol/type information beyond a CFG, even when their surface syntax is context-free.
Static checks occur before execution: type compatibility, duplicate declarations within a restricted scope, valid names, argument counts, return compatibility and control-flow placement.
A break is valid only in constructs allowed by the language; in C/C++ it can exit a loop or switch.
A compiler may annotate an AST or create typed IR; there is no mandatory uniquely named output tree.
Dynamic checks depend on runtime values, such as some bounds and null checks.
Static analysis can prove some accesses safe or faulty; “all memory errors cannot be statically checked” is too strong.
Unreachable code is not universally a semantic error: some languages reject it in specified cases, others merely warn or optimize it away.
A type checker verifies that operations are defined for their operands.
In a simple strict language, integer mod requires two integers; array indexing requires an array and integer index; an if condition requires Boolean; assignment requires equal or convertible types.
Function calls check parameter count and compatibility, and returns match result types.
Type inference derives types from constraints: if x is integer and + expects numeric operands, infer the expression type from numeric promotion rules.
It is a static technique even without explicit annotations.
Operator overloading supplies multiple operation meanings, not a substitute for type checking. int x="hello" is a type mismatch in ordinary C++/Java; division by zero and bounds violations are not automatically operand-type mismatches.
A syntax-directed translation scheme embeds executable actions in productions; the actions run while translating a source program, not while generating the compiler.
Attributes may compute types, values, AST pointers or generated code.
The scheme defines an input-to-output translation, not merely an input language.
Create an identifier leaf with mkleaf(id,entry), a number with mkleaf(num,value), and an operator node with mknode(op,left,right).
For a−4+c, construct +(−(a,4),c).
Postorder traversal prints postfix: a 4 − c +.
A stack evaluator pushes operands and pops right then left operands for an operator.
Infix-to-postfix is useful for stack machines but not mandatory for all compilers.
Common-subexpression elimination reuses an earlier value only if operand values and relevant memory remain unchanged.
A DAG can represent sharing.
Algebraic simplification removes identities when valid: integer x+0→x. Strength reduction replaces an operation with an equivalent cheaper form, such as unsigned x*8→x<<3 for a valid width and shift count.
Target costs determine whether it is actually cheaper.
Peephole optimization examines short instruction windows.
It can remove redundant loads/stores, replace machine idioms and shorten jump chains: jump L1 where L1 immediately jumps L2 can become jump L2. Local optimization is a wider category; peephole optimization is a concrete method within the relevant scope.
Code generation lowers checked IR to a target form.
Instruction selection chooses target operations; register allocation chooses where values reside; scheduling orders instructions while respecting dependencies; storage layout assigns offsets and follows ABI requirements.
Register assignment names actual physical registers after allocation decisions.
For t=a+b, a simple target could emit LOAD R1,a; LOAD R2,b; ADD R3,R1,R2; STORE t,R3.
Other targets may combine loads with arithmetic or keep t in a register.
Machine idioms, register availability and instruction order affect execution time.
Absolute machine code, relocatable object code, assembly and VM bytecode can be legitimate compiler targets; TAC is normally intermediate, but “cannot ever be target code” is an unjustified universal.
A register descriptor records which current values are held in a register.
An address descriptor for a name records all current locations containing its value, possibly memory and multiple registers.
A memory copy can become stale after a register-only assignment.
These are code-generator bookkeeping structures, not source-language types.
A simple code-generation algorithm calls getReg for a TAC instruction to select operand/result registers, emits necessary loads, emits the operation, then updates descriptors.
Prefer an already suitable register or a reusable dead operand; otherwise choose a spill victim and store any live value lacking another current copy.
At a block exit, preserve values needed by successors.
A value is live where it can be used before redefinition.
In the interference model, values that must coexist in distinct registers are connected by an edge; each register is a color.
Nonoverlapping live ranges may share a register.
If a valid assignment cannot fit the available registers, spilling places selected values in memory and inserts loads/stores.
The general graph k-colorability decision problem is NP-complete for fixed k≥3; optimal register assignment/spill minimization is a hard optimization problem in general, so practical allocators use heuristics.
Restricted interference graphs or SSA formulations can have different properties.
Do not describe every possible register-allocation algorithm as NP-complete merely because a general model is difficult.
For a=b+c*d;, the scanner recognizes names and operators, the parser forms an assignment with +(b,*(c,d)), and semantic analysis resolves declarations and operand/result types.
A declaration such as float a; int b,c,d; can require a conversion before storing the numeric result, according to language arithmetic rules.
COMP41 Distinguish tokens, lexemes and lexical analysis
The primary output of lexical analysis is a token stream, rather than a symbol table, AST or assembly; some are side structures. Distinguish a token category from the lexeme text that matches it.
Counting the loop header gives 14 tokens, even if no option matches.
Grouping characters into token classes is lexical analysis; grouping tokens into expressions and statements is syntax analysis.
Identify whether an analysis groups characters into tokens or tokens into syntactic constructs.
Symbol tables store identifiers and their attributes, not obligatorily every kind of token.
Trees store hierarchical constructs, while a symbol table stores declaration metadata.
COMP42 Compare parser methods and grammar conditions
Shift-reduce and LR are both bottom-up rather than top-down methods.
Recursive and nonrecursive predictive parsers can both be efficient.
Nested parentheses and parsing tables do not uniquely identify LR.
Ambiguity does not disappear merely by choosing LR, and leftmost derivation is not an ambiguity-resolution policy.
Overlapping FIRST sets, left recursion and ambiguity can each prevent a useful grammar from being LL(1); do not restrict the check to only the first two.
Check all applicable conditions and identify any conflicting table cell.
Precedence versus operator-precedence parsing needs a concrete conflict and policy, not a blanket claim that every shift-reduce conflict has one solution.
COMP43 Distinguish semantic analysis and translation
Type checking and symbol tables are both important to semantic analysis: one is an activity and one a data structure.
Semantic rules generally compute attributes, including but not limited to types, values and code; no listed specialized purpose is automatically exhaustive.
Both names and types belong in symbol records.
Distinguish division by zero, bounds violations, indentation mistakes and syntax errors from type errors; a type-error example should specify the language and incompatible operands.
Code generation is conventionally last in a simplified pipeline even if later target optimization exists.
A compiler may emit an annotated AST or typed IR, so distinguish representation, annotation and phase before forcing one tree name.
COMP-S01 Parser direction, expression parsing and coverage
The common two-way classification of parsing is by construction direction: top-down parsing expands from the start symbol, while bottom-up parsing reduces the input toward that symbol. This counts broad directions, not the number of parser algorithms or implementations.
Operator-precedence parsing is a restricted bottom-up expression-parsing method using a stack and precedence relations. With a suitable expression grammar, the stack retains unfinished surrounding expressions while nested parentheses are processed.
In the standard comparison by grammar coverage, canonical LR(1) is more general than the restricted operator-precedence method. Together with SLR(1)⊆LALR(1)⊆LR(1), this makes canonical LR(1) the broadest of those named deterministic parsing methods. Broader coverage does not mean faster execution or smaller tables.
COMP-S02 Grammar notation and general CFG parsing algorithms
Backus–Naur form, or BNF, is a notation for context-free grammar production rules. It describes how syntactic constructs are formed; it is different from an abstract syntax tree representing one particular program.
CYK and Earley are context-free grammar parsing algorithms. They determine grammatical structure or membership of an input sequence. They are different tasks from Thompson construction, which builds a token-recognizing NFA from a regular expression, and subset construction, which turns an NFA into a DFA.
COMP-S03 Equivalent specifications for ordinary token languages
Classical regular expressions, consistently right-linear regular grammars and finite automata describe the same regular-language family. Thus an ordinary token pattern specified by a regular expression also has a regular grammar and an equivalent finite-state recognizer.
This equivalence concerns expressive power, not spelling of the specification or implementation size. Context-free grammars can also describe regular languages, but their larger family is needed for syntax with unbounded nested structure rather than ordinary regular token patterns.
Instruction scheduling orders selected target instructions while preserving dependencies. A target-aware scheduler also considers instruction latencies and the processor resources needed by each operation. This is a backend optimization whose performance choices depend on the target machine, even when a reusable scheduling framework serves many targets.
By contrast, constant folding, dead-code elimination and safe loop-invariant motion can be expressed on a target-neutral IR using values, control flow and side-effect rules. Target costs can still influence whether a legal transformation is worthwhile. Machine independence therefore describes the abstraction of a pass, not freedom from all language semantics or implementation costs.