A dark, readable revision page for the Programming 622 study guide, focused on C++ software design, STL containers, data structures, searching, sorting, trees and graphs.
A question-by-question map from the Programming 622 assignment brief to the most relevant content in this study hub. Start with the topics listed for each question, then use the links to open the fuller explanations, examples, and complexity notes in the general module content.
Use the assignment brief as the requirement source. The cards below identify study-guide content to revise; they do not replace the brief's implementation, testing, README, file-submission, or academic-integrity requirements. The subsection marks printed in the brief add to 105, although Question One is labelled 100 marks, so confirm the weighting with your lecturer if needed.
Question 1.115 marks
AI Agent Authentication & Access Control
Build the Engineer class, protect its state through a clear interface, store engineers in a vector, and search for valid credentials.
Study-guide content to apply
Classes and ADTs for encapsulated engineer data, accessors, and operations.
Big-O analysis to justify the chosen search strategy and its assumptions, such as sorted data for binary search.
Implementation focus: Do not store or display a plain-text password. Explain the password representation and make the clearance level explicit, for example with an enum or validated value.
Question 2.1-2.220 marks
City Data Management: Dynamic Containers
Use a vector for daily sensor readings and a linked list for historical logs, then implement insertion, removal, traversal, display, and a complexity comparison.
Big-O analysis for access, insertion, removal, and traversal; distinguish finding a position from changing links once a node is known.
Comparison to explain: A vector provides fast indexed access but may move elements during insertion or reallocation. A linked list grows node by node and supports link changes, but traversal and locating an item are sequential.
Question 3.1-3.225 marks
Event Processing: FIFO Queue and LIFO Override Stack
Model normal city events with a queue and emergency overrides with a stack, then show how each processing order fits the real-world requirement.
Study-guide content to apply
Queue operations for arrival order, enqueue, dequeue, front, and empty checks.
Priority queues as useful context when the system later needs severity-based ordering rather than pure FIFO.
STL components and iterators for filtering or prioritising event records with standard-library algorithms.
Design distinction: A queue answers “which event arrived first?”; a stack answers “which override was added most recently?” Keep the two policies separate even if both are processed in the same simulation.
Question 4.115 marks
Object-Oriented City Architecture
Translate the supplied CityComponent hierarchy and its PowerSystem, TransportSystem, HealthSystem, and SecuritySystem classes into a maintainable C++ design. Demonstrate encapsulation, inheritance, polymorphism, constructors, and destructors through processEvent().
Study-guide content to apply
Classes for private state, public behaviour, constructors, and object lifetime.
Function contracts for documenting preconditions and postconditions around processEvent().
Implementation focus: Give the base class a virtual interface and use base-class references or pointers to call the derived overrides. Ensure cleanup is safe when objects are handled polymorphically.
Question 5.1-5.215 marks
STL Algorithms and Performance Optimisation
Apply the required algorithms to sensor data and events, then justify each choice with a time-complexity explanation.
Big-O analysis for sort, find, min_element, max_element, and count_if; state whether the operation makes one pass, sorts the range, or depends on an ordered input.
Be precise: The assignment names standard algorithms that are not all demonstrated individually in the general content. Use the STL and iterator material for the pattern, then document the complexity of the exact algorithm call you use.
Question 6.15 marks
System Reports and Analytics
Turn the stored events and response measurements into readable reports: totals, most-common emergency type, averages, and a load summary.
Study-guide content to apply
Iterators for scanning containers without coupling the report code to one concrete container.
Function contracts for documenting file-open failures, malformed records, missing files, and post-load invariants.
Scope note: File streams are an assignment extension rather than a standalone chapter in this study-guide-derived page. Keep the persistence layer separate from the data structures, validate every open/read operation, and explain the chosen text or binary format in the README.
Test Focus Areas
A future home for confirmed test coverage and targeted revision guidance.
Coming soon
Test Focus Areas are coming soon
This section will be updated when the relevant guidance is available.
Exam Focus Areas
Confirmed exam focus areas will be added here once the assessment coverage is available.
Coming soon
Exam focus areas are coming soon
The current exam-focus content has been cleared and will be updated when the confirmed focus areas are provided.
General Module Content
Use the chapter links below for the full study-guide-derived explanations and examples referenced by the Assignment Helper.
1. Software Engineering Principles And C++ Classes
The guide starts by connecting software engineering practice to C++ program design: understand the problem, design algorithms and objects, implement with documented functions and classes, then test before the program enters long-term maintenance.
Software life cycleAnalysis and designBig-OClassesADTPreconditions
1.1 Software Life Cycle
A program has a life cycle from the moment it is first conceived until it is retired. The guide names three fundamental stages: development, use and maintenance.
Development: the new program is created to solve a customer's problem.
Use: the completed program is released and users begin applying it to real work.
Maintenance: problems, corrections and improvement ideas are sent back to the developer.
Exam angle: Maintenance is not an afterthought. A well-developed program is easier and less expensive to maintain.
1.2 Development Phase
Software engineers break development into four main phases: analysis, design, implementation, and testing/debugging. Each phase answers a different question.
Analysis
Design
Implementation
Testing and debugging
Analysis: understand the problem, required user interaction, data, output format and any complex subproblems.
Design: create algorithms for the full problem and for each subproblem.
Implementation: write and compile the C++ code for the classes and functions discovered in design.
Testing and debugging: run test cases, compare actual output to expected output, then find and fix faults.
1.3 Algorithm Analysis: Big-O
After designing an algorithm, the guide says it should also be analysed. The focus is normally the number of basic operations as a function of input size n, not the raw time on one computer.
Big-O describes the dominant growth term when n becomes large. Constants and smaller terms become less important. For example, n2 + n is treated as O(n2) because the quadratic term dominates.
Growth
Meaning
Typical Guide Connection
O(1)
Fixed amount of work, independent of input size.
Simple statements and direct vector access.
O(n)
Work grows in direct proportion to the number of items.
Sequential search and traversal.
O(log n)
The problem is repeatedly divided into smaller parts.
Binary search.
O(n2)
Repeated work over the same growing data set.
Nested loops and simple comparison sorting patterns.
How to analyse: identify the dominant operation first. In searching, count comparisons; in matrix multiplication, multiplication may be the expensive operation.
1.4 Classes
A C++ class is the mechanism used to combine data and operations in one unit. It defines a type; memory is allocated only when objects of that type are declared.
Class components are called members.
Members can be data members or member functions.
Member functions can directly access other members of the same class.
Members are usually grouped under private, protected or public access specifiers.
The semicolon after the closing brace is part of the class syntax.
The guide uses preconditions and postconditions to document how a function should be called and what will be true after it finishes.
Precondition: what must be true before the call, such as "the value must be nonnegative".
Postcondition: what the function guarantees after the call, such as "returns centimetres" or "returns -1.0 for invalid input".
assert can enforce a condition, but a failed assertion terminates the program.
Design decision: Returning an error value lets the caller recover; using assert is stricter and is better when continuing would make the program invalid.
1.6 Data Abstraction, Classes And ADTs
Abstraction separates logical properties from implementation details. The guide's car example makes the idea simple: the driver needs to know how to start and drive the car, not how the engine is built.
Data abstraction applies the same idea to data types. An abstract data type has a type name, a domain of possible values, and a set of operations. A C++ class is a convenient way to implement an ADT because it can expose operations while hiding storage details.
The guide gives a practical OOD technique: start with the problem description, list nouns and verbs, then choose candidate classes and operations.
Nouns often suggest possible classes or data values.
Verbs often suggest operations.
After choosing a class, identify operations objects can perform, operations performed on the object, and information the object must maintain.
Guide example: In a cylinder problem, cylinderType is a natural class; radius and height are data; volume, surface area, input and print are operations.
Topic 1 Extended Code Example: ADT-Style Class With Contracts
This example combines the guide's software-design ideas: analyse the problem, model the correct object, protect its data, document preconditions/postconditions, and expose clear operations.
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
using namespace std;
class cylinderType {
private:
double radius;
double height;
public:
// Default constructor.
// Postcondition: the object exists with safe starting dimensions.
cylinderType() {
radius = 1.0;
height = 1.0;
}
// Constructor with parameters.
// Precondition: r and h must be positive measurements.
// Postcondition: radius = r and height = h.
cylinderType(double r, double h) {
setDimensions(r, h);
}
// Member function used to change the object's data safely.
// Encapsulation means outside code cannot assign radius/height directly.
void setDimensions(double r, double h) {
assert(r > 0 && h > 0);
radius = r;
height = h;
}
// Logical operation of the ADT.
// The caller needs the result, not the internal formula details.
double volume() const {
const double pi = 3.141592653589793;
return pi * radius * radius * height;
}
// Another logical operation of the ADT.
double surfaceArea() const {
const double pi = 3.141592653589793;
return 2 * pi * radius * (radius + height);
}
void print() const {
cout << fixed << setprecision(2);
cout << "Radius: " << radius << endl;
cout << "Height: " << height << endl;
cout << "Volume: " << volume() << endl;
cout << "Surface area: " << surfaceArea() << endl;
}
};
int main() {
// Analysis: the problem needs radius and height as input data.
// Design: cylinderType stores dimensions and provides operations.
cylinderType waterTank(3.5, 8.0);
// Implementation: use the public interface instead of touching private data.
waterTank.print();
return 0;
}
Topic 1 Extended Code Example: Reading Code For Big-O
This small program shows how to connect code structure to operation growth, which is exactly what the Big-O section expects you to practise.
#include <iostream>
#include <vector>
using namespace std;
bool sequentialSearch(const vector<int>& values, int target) {
// In the worst case, the loop checks every element once.
// If values has n elements, the dominant operation is n comparisons.
// Worst-case complexity: O(n).
for (int item : values) {
if (item == target) {
return true;
}
}
return false;
}
void printPairs(const vector<int>& values) {
// This nested loop compares every element with every other element.
// For n elements, the inner statement can run n * n times.
// Dominant term: n2, so complexity is O(n2).
for (int i = 0; i < static_cast<int>(values.size()); i++) {
for (int j = 0; j < static_cast<int>(values.size()); j++) {
cout << values[i] << "," << values[j] << " ";
}
cout << endl;
}
}
int main() {
vector<int> marks = {72, 85, 91, 60};
cout << boolalpha;
cout << "Found 91? " << sequentialSearch(marks, 91) << endl;
printPairs(marks);
return 0;
}
Topic 1 Glossary: Key Words And Code Terms
analysis
The phase where the problem, inputs, outputs, user needs and constraints are understood before coding begins.
design
The phase where algorithms, classes and operations are planned.
implementation
The phase where the planned solution is translated into C++ code.
testing
Running test cases to compare expected output with actual output.
debugging
Finding and correcting faults discovered during testing.
O(n)
Linear growth; the work grows in proportion to the number of items.
O(log n)
Logarithmic growth; the problem is repeatedly divided into smaller parts.
O(n2)
Quadratic growth; commonly caused by nested loops over the same data set.
class
A programmer-defined C++ type that groups data members and member functions.
object
A variable or instance created from a class type.
private
An access specifier that hides members from outside code.
public
An access specifier for the interface clients are allowed to call.
const
Used on member functions to promise that the object will not be changed by that function.
assert
A debugging check that terminates the program if a required condition is false.
precondition
What must be true before a function is called.
postcondition
What a function guarantees after it completes.
ADT
Abstract data type; a logical type described by values and operations, separate from implementation details.
constructor
A member function that initializes an object when it is created.
The STL provides professionally written class templates and generic algorithms for storing, accessing and manipulating data. This topic introduces containers, iterators and algorithms, then uses vector and deque to show the common patterns.
The guide frames the STL around the central goal of a program: store data, access data and manipulate data to produce results.
Component
Role
Typical Examples
Containers
Class templates that manage objects of a given type.
vector, deque, list, stacks and queues.
Iterators
Pointer-like objects used to step through container elements.
begin(), end(), ++it, *it.
Algorithms
Reusable functions that manipulate ranges of data.
copy, searching, sorting and transformation-style operations.
2.2 Sequence Containers
STL containers are classified into sequence containers, associative containers and container adapters. In a sequence container, every object has a specific position.
vector: dynamic array, random access, fast insertion at the end.
deque: double-ended queue, can expand at the front and back.
list: linked sequence container, covered later in the linked-list topic.
Container adapters are revisited with stacks and queues.
2.3 Sequence Container: vector
A vector stores and manages its objects in a dynamic array. Because arrays are random-access structures, vector elements can be accessed with indexes just like array elements.
Use #include <vector>.
Declare the component type, for example vector<int> intList;.
vector<int> intList(10); creates ten integer elements initialized to zero.
push_back adds a new element at the end when you do not already know the final size.
Do not write past the current vector size with the subscript operator.
Every container provides begin() and end(). The guide uses them to initialise iterator loops and to mark the range processed by algorithms.
begin() returns an iterator positioned at the first element.
end() returns the stopping position just past the final element.
insert and erase often need an iterator to specify the exact position.
Inserting in the middle of a vector is expensive because later elements must shift.
vector<int>::iterator it = marks.begin();
++it; // Move to the second element.
marks.insert(it, 90); // Insert 90 before that position.
2.5 The copy Algorithm
The STL copy algorithm copies a range of elements from a source to a destination. The source range is written as first...last - 1, which means last is the stopping position, not the final copied element.
Include <algorithm> for copy.
The first two parameters describe the source range.
The third parameter describes the destination start.
The destination must have enough space unless an insert/output iterator is used.
Shortcut: You can create the output iterator directly inside the copy call: copy(vecList.begin(), vecList.end(), ostream_iterator<int>(cout, ", "));
2.7 Iterators
Iterators work like pointers into containers. The two core operations are incrementing the iterator with ++ and dereferencing it with * to access the current value.
Iterator Type
Capability
Where It Matters
Input
Read values while moving forward.
Reading from streams.
Output
Write values while moving forward.
Writing to streams.
Forward
Read/write while moving forward and revisiting elements.
General one-way traversal.
Bidirectional
Move forward and backward.
list, set, map.
Random access
Jump directly using arithmetic and indexing-like movement.
vector, deque, arrays and strings.
Exam trap: Do not assume every container behaves like an array. Some containers are better traversed through iterators than direct indexes.
Topic 2 Extended Code Example: vector, Iterators, insert And copy
This example follows the guide's vector sequence: declare a vector, add elements, process by index, process by iterator, insert at an iterator position, and output with copy.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {
vector<int> marks;
// push_back is used when the vector starts empty or the final size is unknown.
marks.push_back(13);
marks.push_back(75);
marks.push_back(28);
marks.push_back(35);
cout << "Original values: ";
for (int i = 0; i < static_cast<int>(marks.size()); i++) {
// vector supports random access, so index-based processing is valid.
cout << marks[i] << " ";
}
cout << endl;
for (int i = 0; i < static_cast<int>(marks.size()); i++) {
marks[i] *= 2; // Same position, updated value.
}
cout << "Doubled values: ";
vector<int>::iterator it;
for (it = marks.begin(); it != marks.end(); ++it) {
// *it dereferences the iterator and returns the element it points to.
cout << *it << " ";
}
cout << endl;
it = marks.begin();
++it;
++it; // Move to the third element.
marks.insert(it, 88); // Insert before the current iterator position.
cout << "After inserting 88: ";
copy(marks.begin(), marks.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
Topic 2 Extended Code Example: deque And Double-Ended Access
The guide introduces deque after vector. Use it when insertions/removals at both the front and the back are part of the problem.
#include <algorithm>
#include <deque>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
deque<int> queueLikeData;
ostream_iterator<int> screen(cout, " ");
// push_back adds at the rear, similar to the vector examples.
queueLikeData.push_back(13);
queueLikeData.push_back(75);
queueLikeData.push_back(28);
queueLikeData.push_back(35);
cout << "Initial deque: ";
copy(queueLikeData.begin(), queueLikeData.end(), screen);
cout << endl;
// deque can grow efficiently at both ends.
queueLikeData.push_front(0);
queueLikeData.push_back(100);
cout << "After front and back insertion: ";
copy(queueLikeData.begin(), queueLikeData.end(), screen);
cout << endl;
// Remove from both ends.
queueLikeData.pop_front();
queueLikeData.pop_back();
// Insert in the middle using an iterator position.
deque<int>::iterator middle = queueLikeData.begin();
++middle;
queueLikeData.insert(middle, 444);
cout << "After removals and middle insert: ";
copy(queueLikeData.begin(), queueLikeData.end(), screen);
cout << endl;
return 0;
}
Topic 2 Glossary: Key Words And Code Terms
STL
The Standard Template Library; reusable C++ containers, iterators and algorithms.
container
An object that stores and manages a collection of values.
sequence container
A container where elements are kept in a specific linear order.
vector
A dynamic array with fast indexed access and efficient insertion at the end.
deque
A double-ended sequence container that supports insertion and removal at both ends.
iterator
A pointer-like object used to move through a container.
begin()
Returns an iterator positioned at the first element.
end()
Returns the stopping iterator just past the final element.
push_back()
Adds a new element to the end of a vector, deque or list.
push_front()
Adds a new element to the front of a deque or list.
insert()
Adds an element at a position identified by an iterator.
erase()
Removes an element or range from a container.
copy()
An STL algorithm that copies a range from one place to another.
ostream_iterator
An output iterator that writes each copied value to a stream such as cout.
*it
Dereferences an iterator to access the element it currently points to.
Linked lists use dynamically allocated nodes connected by pointer links. They solve some array limitations because nodes do not need contiguous memory and insert/delete operations can often be done by changing links instead of shifting data.
A linked list is a collection of nodes. Each node stores the data and the address of the next node. The order of the list is therefore determined by links, not by neighbouring memory positions.
The first node is reached through a separate pointer such as head or first.
The last node's link is NULL or nullptr.
Nodes can be anywhere in memory; they do not need to sit next to one another.
Because links move in one direction, losing the first pointer means losing access to the list.
struct nodeType {
int info; // Data stored in the node.
nodeType *link; // Address of the next node.
};
nodeType *head = nullptr;
3.1.2 Traversal Discipline
To traverse a linked list, the guide stresses that you should not move head. Instead, copy head into another pointer such as current and advance that pointer.
Common failure: If you write head = head->link; just to move through the list, the original first node becomes unreachable unless you saved it somewhere else.
nodeType *current = head;
while (current != nullptr) {
cout << current->info << " ";
current = current->link;
}
3.2 Item Insertion And Deletion
Insertion and deletion are link-management operations. The guide's key rule is to preserve the rest of the list before rerouting pointers.
To insert after p, first make the new node point to p->link.
Only after that should p->link point to the new node.
To delete a node after p, save it in q, bypass it, then delete q.
Bypassing without deleting leaves inaccessible memory behind.
Pointer order matters:newNode->link = p->link; must happen before p->link = newNode; when only one pointer marks the insertion position.
3.3 Linked List As An ADT
The guide moves from individual pointer statements to a reusable linked-list ADT. The user of the ADT should ask for operations, not manually manipulate every node.
ADT Operation
Purpose
initializeList
Set up an empty list.
isEmptyList
Check whether the list has no nodes.
print / length
Traverse nodes without exposing pointer details.
front / back
Retrieve first or last information.
search, insert, deleteNode
Core list manipulation operations.
destroyList / copy
Manage dynamic memory safely.
3.5-3.6 Unordered And Ordered Lists
The guide separates linked lists into unordered lists and ordered lists because search, insert and delete behave differently.
Unordered list: elements have no particular order; insertion can happen at the front or end.
Ordered list: elements are kept according to a comparison rule, usually ascending order.
After inserting or deleting from an ordered list, the resulting list must still be ordered.
For efficiency, the generic list keeps both first and last pointers plus a node count.
3.7-3.9 List Variations
A doubly linked list stores links in both directions. This supports backward movement, but every insert or delete must maintain both the forward and backward links.
list is the STL sequence container version of a linked list.
Header and trailer nodes can simplify edge cases at the beginning and end of a list.
Circular linked lists connect the final node back into the list rather than ending with NULL.
Topic 3 Extended Code Example: Build, Traverse, Insert And Delete A Linked List
This example demonstrates the guide's essential linked-list pointer rules: keep head stable during traversal, connect the new node before changing the previous node, and delete removed nodes.
#include <iostream>
using namespace std;
struct nodeType {
int info;
nodeType *link;
};
void printList(nodeType *head) {
// Use current for traversal so head still points to the first node.
nodeType *current = head;
while (current != nullptr) {
cout << current->info << " ";
current = current->link;
}
cout << endl;
}
void insertAfter(nodeType *p, int value) {
if (p == nullptr) return;
nodeType *newNode = new nodeType;
newNode->info = value;
// Correct order: first preserve the rest of the list.
newNode->link = p->link;
p->link = newNode;
}
void deleteAfter(nodeType *p) {
if (p == nullptr || p->link == nullptr) return;
// q saves the node being removed so its memory can be released.
nodeType *q = p->link;
p->link = q->link;
delete q;
}
int main() {
nodeType *head = new nodeType{10, nullptr};
head->link = new nodeType{20, nullptr};
head->link->link = new nodeType{40, nullptr};
printList(head); // 10 20 40
insertAfter(head->link, 30);
printList(head); // 10 20 30 40
deleteAfter(head); // Delete node 20.
printList(head); // 10 30 40
while (head != nullptr) {
nodeType *old = head;
head = head->link;
delete old;
}
return 0;
}
Topic 3 Glossary: Key Words And Code Terms
linked list
A collection of nodes connected by pointer links instead of contiguous array positions.
node
A record that stores one data item and one or more links to other nodes.
info
The data field inside a node in the guide's linked-list examples.
link
The pointer field that stores the address of the next node.
head
The pointer that gives access to the first node in the list.
current
A traversal pointer used to move through the list without losing the first node.
nullptr
The modern C++ null pointer value used when a pointer does not address a node.
->
The pointer member access operator; used for fields such as current->info.
new
Allocates dynamic memory for a node or object.
delete
Releases dynamic memory that was allocated with new.
insert
An ADT operation that adds a new item by adjusting links.
deleteNode
An ADT operation that removes a node and releases its memory.
ordered list
A list where items are stored according to key order.
unordered list
A list where insertion does not maintain sorted order.
doubly linked list
A linked list where each node stores links to both the next and previous nodes.
Recursion solves a problem by reducing it to smaller versions of itself. The guide uses factorial, largest-in-array, reverse linked-list printing, Fibonacci-style thinking and backtracking to show when recursive thinking is natural.
Base caseGeneral caseRecursive functionCall stackBacktrackingIteration tradeoffs
4.1 Recursive Definitions
A recursive definition contains a direct answer for the simplest case and a rule that expresses a larger case in terms of a smaller case.
The base case gives the answer directly and stops recursion.
The general case reduces the problem toward the base case.
A recursive function is a function that calls itself.
Direct recursion happens when a function calls itself; indirect recursion happens when functions call one another in a cycle.
Exam trap: A recursive solution without a reachable base case is not a solution; it keeps calling until the program fails.
4.2 Problem Solving Using Recursion
The guide's pattern is to identify how the problem shrinks. For factorial, n! becomes n * (n - 1)!. For largest-in-array, the largest of a list is the maximum of the first item and the largest item in the rest of the list.
Problem
Base Case
General Case
Factorial
0! = 1
n * fact(n - 1)
Largest in array
Sublist length is 1.
Compare first value with largest of the rest.
Reverse print list
Pointer is NULL.
Print tail first, then current node.
4.3 Recursion Or Iteration?
Iteration repeats with loops; recursion repeats through function calls. The guide notes that recursion uses extra memory and execution time because every recursive call has its own parameters and local variables.
Choose iteration when it is at least as obvious and easier to construct.
Choose recursion when the recursive solution maps more naturally to the problem.
Any recursive program can be written iteratively, but the iterative version may be much harder to design.
When execution time or memory is critical, compare the recursive and iterative costs carefully.
4.3 Backtracking
Backtracking constructs partial solutions and abandons a path when it cannot lead to a valid solution. The guide uses the n-queens puzzle: place queens row by row, and back up when a row has no legal column.
Build a partial solution.
Reject it as soon as it violates a rule.
Try the next choice at the most recent decision point.
Continue until a complete valid solution is found or all choices fail.
Topic 4 Extended Code Example: Recursive Largest And Reverse Print
This example shows two guide patterns: a recursive array problem that reduces the index range, and a linked-list problem where the action happens after the recursive call.
#include <iostream>
using namespace std;
struct nodeType {
int info;
nodeType *link;
};
int largest(const int list[], int lowerIndex, int upperIndex) {
// Base case: one element remains, so it is the largest in this sublist.
if (lowerIndex == upperIndex) {
return list[lowerIndex];
}
// General case: find the largest in the smaller sublist first.
int maxOfRest = largest(list, lowerIndex + 1, upperIndex);
if (list[lowerIndex] >= maxOfRest) {
return list[lowerIndex];
}
return maxOfRest;
}
void reversePrint(nodeType *current) {
// Hidden base case: if current is nullptr, the if body does not run.
if (current != nullptr) {
// First print the tail of the list.
reversePrint(current->link);
// Then print the current node while the recursive calls unwind.
cout << current->info << " ";
}
}
int main() {
int values[] = {23, 43, 35, 38, 67, 12, 76, 10};
cout << "Largest: " << largest(values, 0, 7) << endl;
nodeType *head = new nodeType{5, new nodeType{10, new nodeType{15, nullptr}}};
cout << "Reverse list: ";
reversePrint(head); // Prints 15 10 5
cout << endl;
while (head != nullptr) {
nodeType *old = head;
head = head->link;
delete old;
}
return 0;
}
Note: The recursive call must move toward the base case. In largest, lowerIndex increases; in reversePrint, current moves along the link chain.
Topic 4 Glossary: Key Words And Code Terms
recursion
A technique where a function solves a problem by calling itself on a smaller version of the problem.
recursive function
A function that directly or indirectly calls itself.
base case
The stopping case that gives an answer without another recursive call.
general case
The part of the definition that reduces the problem toward the base case.
call stack
The runtime structure that stores active function calls and their local data.
direct recursion
A function calls itself inside its own body.
indirect recursion
Two or more functions call one another in a cycle.
iteration
Repetition using loops such as for, while or do...while.
backtracking
A recursive search method that tries a choice, backs up if it fails, and tries another choice.
factorial
The product n * (n - 1) * ... * 1, often used to introduce recursive definitions.
return
Ends a function call and sends a value back to the caller.
largest()
A common guide example that finds the largest array value by comparing one value with the largest of the rest.
reversePrint()
A linked-list recursion example that prints the tail before the current node.
A stack is a Last In First Out structure. The guide connects stacks to function calls, recursive calls, array and linked implementations, postfix expression evaluation, and replacing some recursive algorithms with nonrecursive stack-based algorithms.
LIFOpushtoppopArray stackLinked stackPostfix
5.1 Stack ADT
A stack adds and removes elements only at the top. The last element pushed is the first one popped, which is why a stack is a LIFO data structure.
top: C
B
bottom: A
push(D) places D above C. top() reads the current top. pop() removes the current top item only.
5.1 Array Implementation
In an array stack, elements are stored in an array and stackTop tracks how many elements are in the stack. The top item is at stackTop - 1.
initializeStack sets the stack to empty.
isEmptyStack checks whether there are no elements.
isFullStack checks whether the fixed array has space.
push stores at the top and advances stackTop.
pop decreases stackTop after checking the stack is not empty.
5.2 Linked Implementation Of Stacks
A linked stack avoids the fixed-size limit of an array stack by allocating nodes dynamically. In the linked representation, stackTop stores the address of the top node, not an array index.
The stack is empty when stackTop == NULL.
A linked stack is full only if the program runs out of memory.
push creates a new node and links it before the old top.
pop saves the top node, moves stackTop down, and deletes the old top.
5.4 Application: Postfix Expressions
In postfix notation, operators appear after operands, so the operators appear in the order required for computation. Stacks fit this perfectly.
Scan the expression left to right.
Push each operand.
When an operator appears, pop the needed operands.
Apply the operator and push the result.
At =, exactly one value should remain: the answer.
Error cases: Too few operands, illegal operators and too many final operands all indicate invalid postfix expressions.
5.6 Removing Recursion And STL stack
The guide uses stacks to replace some recursive processes because a stack can remember items that still need to be processed. C++ also provides the STL stack class adapter for stack-style work.
Recursive calls are naturally managed by the computer's call stack.
A manual stack can store nodes, states or pending operations.
Use this when you need a nonrecursive version of a naturally recursive algorithm.
Topic 5 Extended Code Example: Postfix Calculator With stack
This program implements the guide's postfix rule: operands are pushed, operators pop two operands, and the final stack must contain exactly one answer.
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
bool applyOperator(stack<double>& values, char op) {
if (values.size() < 2) {
return false; // Not enough operands for a binary operator.
}
double right = values.top();
values.pop();
double left = values.top();
values.pop();
switch (op) {
case '+': values.push(left + right); break;
case '-': values.push(left - right); break;
case '*': values.push(left * right); break;
case '/': values.push(left / right); break;
default: return false; // Illegal operator.
}
return true;
}
bool evaluatePostfix(const string& expression, double& answer) {
stack<double> values;
istringstream input(expression);
string token;
while (input >> token) {
if (token == "=") {
break; // End of expression, as in the guide examples.
}
if (token == "+" || token == "-" || token == "*" || token == "/") {
if (!applyOperator(values, token[0])) {
return false;
}
} else {
values.push(stod(token)); // Token is an operand.
}
}
if (values.size() != 1) {
return false; // Too many operands remain, or no answer exists.
}
answer = values.top();
return true;
}
int main() {
double result = 0;
if (evaluatePostfix("6 3 + 2 * =", result)) {
cout << result << endl; // (6 + 3) * 2 = 18
} else {
cout << "Invalid postfix expression" << endl;
}
return 0;
}
Topic 5 Glossary: Key Words And Code Terms
stack
A data structure where insertion and deletion happen at one end called the top.
LIFO
Last In First Out; the most recently pushed item is removed first.
top
The end of the stack where all stack operations occur.
push()
Adds a new item to the top of the stack.
pop()
Removes the top item from the stack.
top()
Returns the current top item without removing it.
isEmptyStack()
Checks whether the stack contains no elements.
isFullStack()
Checks whether a fixed array stack has reached capacity.
stackTop
The variable that tracks the current top position or top node.
postfix
An expression format where operators appear after operands, such as 6 3 +.
operand
A value used by an operator.
operator
A symbol such as +, -, * or / that performs an operation.
std::stack
The STL container adapter that provides stack operations.
empty()
An STL stack function that returns true when the stack has no elements.
A queue is a First In First Out structure. Items are added at the rear and deleted from the front, making queues useful for real systems where arrival order matters, such as bank lines, printers and simulations.
A queue adds at the rear and deletes from the front. Like stacks, queues need guard operations so you do not delete from an empty queue or add to a full queue.
front: A
B
C
rear: D
initializeQueue resets the queue.
front returns the first element; back returns the last element.
addQueue adds at the rear.
deleteQueue removes at the front.
6.2 Implementation Of Queues As Arrays
An array queue needs queueFront, queueRear, storage for the elements and a maximum size. A simple one-way movement wastes freed array space, so the guide uses a circular array.
Advance an index with (index + 1) % maxQueueSize.
A circular array wraps from the last slot back to slot 0.
A count variable can distinguish a full queue from an empty queue.
queueFront changes after deletion; queueRear changes after insertion.
6.3 Linked Implementation Of Queues
A linked queue stores items in nodes and keeps pointers to the first and last nodes. This supports clean deletion from the front and insertion at the rear without shifting array elements.
queueFront points to the node that will be removed next.
queueRear points to the node where the next item will be linked.
When the final node is deleted, both pointers must represent an empty queue.
6.4 Priority Queues
A priority queue relaxes pure FIFO order. Higher-priority customers or jobs move ahead of lower-priority ones, such as emergency patients or urgent print jobs.
A linked list can keep items ordered by priority.
A tree-like structure is often more efficient.
The STL priority_queue uses a priority rule, often based on <.
Priority queues connect directly to heapsort and heap-based priority queues later in the guide.
6.5 Queue Applications: Simulation
The guide uses queues to model systems such as banks, theatres, grocery stores and printers. A server provides service, customers wait in a queue, and the simulation measures behaviour such as average waiting time.
A time-driven simulation uses a clock counter.
Customer objects store arrival time, waiting time and transaction time.
Server objects track whether they are free and how much service time remains.
Queues are the natural structure for customers waiting to be served in arrival order.
This example uses the guide's circular-array idea: the front and rear wrap around with modulo arithmetic, and count tells whether the queue is empty or full.
#include <iostream>
#include <stdexcept>
using namespace std;
class intQueue {
private:
static const int maxQueueSize = 5;
int list[maxQueueSize];
int queueFront;
int queueRear;
int count;
public:
intQueue() {
queueFront = 0;
queueRear = maxQueueSize - 1;
count = 0;
}
bool isEmptyQueue() const {
return count == 0;
}
bool isFullQueue() const {
return count == maxQueueSize;
}
void addQueue(int item) {
if (isFullQueue()) {
throw runtime_error("Queue is full");
}
queueRear = (queueRear + 1) % maxQueueSize;
list[queueRear] = item;
count++;
}
int front() const {
if (isEmptyQueue()) {
throw runtime_error("Queue is empty");
}
return list[queueFront];
}
void deleteQueue() {
if (isEmptyQueue()) {
throw runtime_error("Queue is empty");
}
queueFront = (queueFront + 1) % maxQueueSize;
count--;
}
};
int main() {
intQueue tickets;
tickets.addQueue(101);
tickets.addQueue(102);
tickets.addQueue(103);
cout << "Serving customer " << tickets.front() << endl;
tickets.deleteQueue();
tickets.addQueue(104);
cout << "Next customer " << tickets.front() << endl;
return 0;
}
Topic 6 Glossary: Key Words And Code Terms
queue
A data structure where items are added at the rear and removed from the front.
FIFO
First In First Out; the earliest item inserted is removed first.
front
The end of the queue where deletion occurs.
rear
The end of the queue where insertion occurs.
addQueue()
Adds a new item at the rear of the queue.
deleteQueue()
Removes the item at the front of the queue.
front()
Returns the first item, the next item that would be deleted.
back()
Returns the last item, the most recently added item.
queueFront
The index or pointer that identifies the front item.
queueRear
The index or pointer that identifies the rear item or next rear position.
circular array
An array representation where indexes wrap around using modulo arithmetic.
%
The modulo operator used to wrap queue indexes back to the beginning.
priority_queue
An STL adapter where deletion is based on priority rather than pure arrival order.
simulation
A model of a real system, often using queues to represent waiting customers or jobs.
Searching determines whether an item exists, where it is located, or where it should be inserted or deleted. The guide compares comparison-based searching with hashing, where an address is computed rather than found by repeated key comparison.
A key is the part of a record that uniquely identifies the item, such as a student ID in a student record. Searching, sorting, insertion and deletion often compare or use these keys.
A search can simply answer whether an item exists.
It can return the item's position.
In ordered data, it can also help find where a new item should be inserted.
Algorithm analysis counts key comparisons for comparison-based searches.
7.2 Sequential Search
Sequential search starts at the first element and continues until the item is found or the entire list has been searched. It does not require the list to be ordered, so it is flexible but slow for large lists.
Best case: the item is first.
Average case: about half the list is searched.
Worst case: the item is last or absent, so every item is checked.
for (int i = 0; i < length; i++) {
if (list[i] == item)
return i;
}
return -1;
7.4 Binary Search
Binary search uses divide and conquer on an ordered array-based list. Each iteration compares the search item with the middle element, then discards the half where the item cannot be.
The list must be ordered before binary search is valid.
The search range shrinks by about half each iteration.
Guide comparison: For 1024 sorted items, binary search needs at most about 11 loop iterations, while sequential search averages about 512 comparisons.
7.6 Hashing
Hashing uses a hash function to compute the likely address of an item in a hash table. This is not comparison based, which is why hashing can average order 1 search when the table is well designed.
The hash table is usually stored in an array.
The hash function maps a key to an index: 0 <= h(key) < tableSize.
Good hash functions are easy to compute and reduce collisions.
The division method uses key % tableSize.
Exam trap: Hashing is not comparison based. You must explain the role of the hash function and how collisions are handled.
7.7-7.8 Collision Resolution
A collision occurs when different keys hash to the same location. Because collisions are unavoidable in realistic tables, the guide covers open addressing and chaining.
Technique
Idea
Tradeoff
Linear probing
Search the next slots circularly until a free one appears.
No pointers, but clustering can occur.
Rehashing
Use a different probe function after collision.
Can spread probes better.
Chaining
Each table slot points to a linked list of colliding keys.
Handles many collisions, but uses linked-list overhead.
Topic 7 Extended Code Example: Binary Search And Hashing
This example contrasts comparison-based binary search with hash-table addressing and linear probing for collisions.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& list, int item) {
int first = 0;
int last = static_cast<int>(list.size()) - 1;
while (first <= last) {
int mid = (first + last) / 2;
if (list[mid] == item) {
return mid;
} else if (list[mid] > item) {
last = mid - 1;
} else {
first = mid + 1;
}
}
return -1;
}
int hashFunction(int key, int tableSize) {
// Division method from the guide.
return key % tableSize;
}
bool insertLinearProbe(vector<int>& table, int key, int emptyKey) {
int tableSize = static_cast<int>(table.size());
int index = hashFunction(key, tableSize);
int probes = 0;
while (table[index] != emptyKey && probes < tableSize) {
if (table[index] == key) {
return true; // Key is already present.
}
index = (index + 1) % tableSize; // Circular probe sequence.
probes++;
}
if (probes == tableSize) {
return false; // No empty slot.
}
table[index] = key;
return true;
}
int main() {
vector<int> ordered = {12, 18, 22, 34, 39, 58, 75, 89};
cout << "75 found at index " << binarySearch(ordered, 75) << endl;
const int emptyKey = -1;
vector<int> hashTable(9, emptyKey);
for (int key : {5, 28, 19, 15, 20, 33, 12, 17, 10}) {
insertLinearProbe(hashTable, key, emptyKey);
}
cout << "Hash table: ";
for (int value : hashTable) {
cout << value << " ";
}
cout << endl;
return 0;
}
Topic 7 Glossary: Key Words And Code Terms
search key
The value used to identify and compare records during searching.
sequential search
A search that checks items one by one from the start of the list.
binary search
A search that repeatedly halves an ordered array-based list.
ordered list
A list where items are arranged by key order.
first
The lower boundary of the current binary search range.
last
The upper boundary of the current binary search range.
mid
The middle index tested during binary search.
binarySearch()
A function that returns the target position or -1 when the target is absent.
hashing
Computing a storage address from a key instead of searching through comparisons.
hash function
The rule that maps a key to a hash table index.
hash table
The array-like structure that stores items at computed positions.
collision
Occurs when two keys map to the same hash table index.
linear probing
A collision strategy that checks the next table slot until an empty one is found.
chaining
A collision strategy that stores multiple keys at one hash location using a linked list.
Sorting places data in order so later operations, especially binary search, can be more efficient. The guide compares selection sort, insertion sort, Shellsort, quicksort, mergesort, heapsort and priority queues.
The guide studies sorting algorithms as public operations of list classes. This gives the sorting functions direct access to the stored elements and lets the class decide the most appropriate algorithm for its representation.
Array-based lists support direct indexing.
Linked-list sorts must work through links.
Comparison-based sorts are limited by a lower bound of about O(n log2 n) in the worst case.
Selection and insertion sort are simpler but usually O(n2).
8.1 Selection Sort
Selection sort repeatedly finds the smallest element in the unsorted portion and swaps it into the first unsorted position.
Initially, the entire list is unsorted.
Find the smallest element in list[index]...list[length - 1].
Swap it with list[index].
Move index forward and repeat.
Performance idea: Selection sort makes many comparisons but relatively few item movements because each pass mainly swaps once.
8.2 Insertion Sort
Insertion sort divides the array into a sorted upper portion and an unsorted lower portion. The first unsorted element is moved into its correct place in the sorted portion.
firstOutOfOrder points to the first item in the unsorted part.
If it is already greater than the previous item, it stays where it is.
If it is smaller, it is saved in temp while larger sorted items shift down.
Finally, temp is inserted into the gap.
8.3 Shellsort
Shellsort is a modified insertion sort that reduces item movement by first sorting elements far apart, then reducing the gap until the final gap is 1.
Also called diminishing-increment sort.
Moves far-away elements closer to their final positions earlier.
The guide uses Knuth-style increments such as 1, 4, 13, 40 and so on.
Avoid weak increment patterns that delay comparing important positions until the final pass.
8.4-8.5 Quicksort, Mergesort And Heapsort
The later sorting sections focus on algorithms that improve on the usual quadratic behaviour of simple sorts.
Algorithm
Core Idea
Guide Emphasis
Quicksort
Partition around a pivot, then recursively sort sublists.
Average O(n log2 n), worst case O(n2).
Mergesort
Divide and merge sorted parts.
Useful with linked list-based lists.
Heapsort
Build a heap, repeatedly move the largest item into place.
Worst-case O(n log2 n).
8.6 Priority Queues Revisited
Heaps connect sorting to priority queues. A heap keeps the highest-priority item available at the root, making it a natural structure for repeated priority removal.
Topic 8 Extended Code Example: Selection Sort And Insertion Sort
This example shows the two early array-based sorts from the guide: selection sort chooses the smallest remaining item, while insertion sort shifts a value into the sorted part.
#include <iostream>
#include <vector>
using namespace std;
void selectionSort(vector<int>& list) {
for (int index = 0; index < static_cast<int>(list.size()) - 1; index++) {
int smallestIndex = index;
// Find the smallest item in the unsorted portion.
for (int loc = index + 1; loc < static_cast<int>(list.size()); loc++) {
if (list[loc] < list[smallestIndex]) {
smallestIndex = loc;
}
}
// Move the smallest item to the start of the unsorted portion.
int temp = list[index];
list[index] = list[smallestIndex];
list[smallestIndex] = temp;
}
}
void insertionSort(vector<int>& list) {
for (int firstOutOfOrder = 1;
firstOutOfOrder < static_cast<int>(list.size());
firstOutOfOrder++) {
if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) {
int temp = list[firstOutOfOrder];
int location = firstOutOfOrder;
// Shift larger sorted items one position down.
do {
list[location] = list[location - 1];
location--;
} while (location > 0 && list[location - 1] > temp);
// Insert the saved value into its correct location.
list[location] = temp;
}
}
}
void print(const vector<int>& list) {
for (int value : list) {
cout << value << " ";
}
cout << endl;
}
int main() {
vector<int> a = {16, 30, 24, 7, 62, 45, 5, 55};
vector<int> b = a;
selectionSort(a);
insertionSort(b);
print(a);
print(b);
return 0;
}
Topic 8 Glossary: Key Words And Code Terms
sorting
Arranging data into a chosen order, usually ascending or descending by key.
selection sort
Repeatedly selects the smallest item from the unsorted part and swaps it into position.
insertion sort
Builds a sorted section by inserting each new item into its correct place.
Shellsort
A diminishing-increment version of insertion sort that compares items far apart first.
quicksort
A divide-and-conquer sort that partitions values around a pivot.
mergesort
A divide-and-conquer sort that divides data and merges sorted parts.
heapsort
A sort that uses a heap structure to repeatedly place the largest item.
pivot
The reference value used to partition data during quicksort.
swap
Exchanges two values, often after finding the smallest or largest item.
firstOutOfOrder
The guide's insertion-sort index for the first item not yet in the sorted portion.
temp
A temporary variable used to hold a value while other items shift or swap.
location
The insertion-sort index that moves backward to find the correct insertion point.
gap
The distance between compared items in Shellsort.
O(n log2 n)
A common efficient comparison-sort growth rate.
O(n2)
Quadratic growth seen in simple sorts such as selection and insertion sort.
Trees organize data dynamically so insertion, deletion and lookup can be more efficient than plain sequential structures. This chapter moves from general binary trees to binary search trees, AVL balancing and B-trees.
Binary treeTraversalBSTHeightAVLRotationsB-tree
9.1 Binary Trees
A binary tree is either empty or has a root node plus two binary subtrees called the left subtree and right subtree. Every node has at most two children.
The root pointer is stored outside the tree.
Each node stores data, a left link and a right link.
A leaf has no left or right child.
Empty subtrees are part of the definition and matter in algorithms.
Root
Left subtree
Right subtree
9.2 Binary Tree Traversal
Traversal visits every node. Since child links do not point back to the parent, recursive traversal is natural: after a subtree call completes, control returns to the parent.
Traversal
Order
Root Visit
Preorder
Root, left, right.
Before subtrees.
Inorder
Left, root, right.
Between left and right.
Postorder
Left, right, root.
After subtrees.
9.3 Binary Search Trees
A binary search tree gives search direction. At every node, smaller keys are in the left subtree and larger keys are in the right subtree.
Search starts at the root.
If the item equals the node, the search succeeds.
If the item is smaller, follow the left link.
If the item is larger, follow the right link.
If the search reaches an empty subtree, the item is absent.
9.4-9.6 BST Analysis And Nonrecursive Traversal
The performance of a BST depends on its shape. A nicely built tree behaves like repeated halving; a tree built from sorted data can become linear and behave like a linked list.
Search is faster when tree height is small.
Nonrecursive traversal uses an explicit stack to remember parent nodes.
Traversal functions can accept function parameters so the user controls what happens when a node is visited.
9.7-9.8 AVL Trees And Rotations
AVL trees are height-balanced binary search trees. For each node, the heights of the left and right subtrees differ by at most 1.
The balance factor is based on right height minus left height.
Valid AVL balance factors are -1, 0 and 1.
Insertion and deletion may require rotations.
Rotations reconstruct a small part of the tree so the BST order remains valid and height balance is restored.
9.9 B-Trees
B-trees generalize search trees so a node can hold multiple keys and multiple children. They are useful when minimizing tree height matters, especially for storage systems where each node access is expensive.
Topic 9 Extended Code Example: Binary Search Tree Insert, Search And Traversal
This example uses the guide's BST rule: compare at the current node, then move left for smaller values and right for larger values. Inorder traversal prints values in sorted order.
#include <iostream>
using namespace std;
struct treeNode {
int info;
treeNode *llink;
treeNode *rlink;
};
void insert(treeNode *&root, int item) {
if (root == nullptr) {
root = new treeNode{item, nullptr, nullptr};
return;
}
if (item < root->info) {
insert(root->llink, item);
} else if (item > root->info) {
insert(root->rlink, item);
}
// Duplicate values are ignored in this simple example.
}
bool search(treeNode *root, int item) {
treeNode *current = root;
while (current != nullptr) {
if (current->info == item) {
return true;
} else if (item < current->info) {
current = current->llink;
} else {
current = current->rlink;
}
}
return false;
}
void inorder(treeNode *root) {
if (root != nullptr) {
inorder(root->llink);
cout << root->info << " ";
inorder(root->rlink);
}
}
void destroy(treeNode *&root) {
if (root != nullptr) {
destroy(root->llink);
destroy(root->rlink);
delete root;
root = nullptr;
}
}
int main() {
treeNode *root = nullptr;
for (int value : {60, 50, 70, 58, 80, 65}) {
insert(root, value);
}
cout << "Inorder sequence: ";
inorder(root);
cout << endl;
cout << boolalpha << "Search 58: " << search(root, 58) << endl;
destroy(root);
return 0;
}
Topic 9 Glossary: Key Words And Code Terms
binary tree
A tree where each node has at most two children.
root
The top node of a tree, or the pointer that gives access to the whole tree.
leaf
A node with no children.
subtree
A smaller tree rooted at a child node.
llink
The guide's left-child pointer in a binary tree node.
rlink
The guide's right-child pointer in a binary tree node.
preorder
Traversal order: root, left subtree, right subtree.
inorder
Traversal order: left subtree, root, right subtree.
postorder
Traversal order: left subtree, right subtree, root.
BST
Binary search tree; left values are smaller and right values are larger at each node.
insert()
Adds a new node while preserving binary search tree order.
search()
Follows left or right links until an item is found or an empty subtree is reached.
destroy()
Deletes tree nodes, usually with postorder-style recursion.
AVL tree
A height-balanced binary search tree.
rotation
A restructuring step used to restore AVL balance.
B-tree
A multiway search tree designed for efficient disk/file-system style access.
Graphs model relationships using vertices and edges. The guide introduces graph terminology, memory representation, graph ADTs, depth-first and breadth-first traversal, shortest paths, minimum spanning trees and topological ordering.
VerticesEdgesAdjacency listDFSBFSDijkstraPrim
10.2 Graph Definitions And Notations
A graph G = (V, E) has a finite nonempty set of vertices and a set of edges. If the edges are ordered pairs, the graph is directed; otherwise, it is undirected.
Adjacent vertices are connected by an edge.
A loop is an edge incident on a single vertex.
A simple graph has no loops and no parallel edges.
A path is a sequence of vertices connected by edges.
A connected graph has a path from any vertex to any other vertex.
A
B
C
A-B, B-C, A-C
10.1 Graph Representation
Programs must store graphs in memory before processing them. The guide focuses on two common representations.
Representation
How It Works
Useful Reminder
Adjacency matrix
An n x n matrix stores 1 or 0 depending on whether an edge exists.
Undirected graphs produce symmetric matrices.
Adjacency list
An array stores one linked list per vertex, listing adjacent vertices.
Good when many possible edges are absent.
10.4 Graphs As ADTs
A graph ADT hides the representation and exposes graph operations. In the guide, graphType stores an array of linked lists, plus maxSize and gSize.
isEmpty checks whether the graph has no vertices.
createGraph builds the adjacency-list representation.
clearGraph deallocates graph storage.
printGraph, DFS and BFS expose useful graph operations.
10.5 Graph Traversals
Graph traversal is more complex than tree traversal because graphs may contain cycles and may not be connected. The guide uses a visited array to prevent repeated visits and restarts traversal at unvisited vertices.
Traversal
Structure Used
Behaviour
Depth-first traversal
Recursion or stack
Go as deep as possible before backing up.
Breadth-first traversal
Queue
Visit neighbours first, then their neighbours.
10.7 Shortest Path
For weighted graphs, the guide introduces Dijkstra's shortest path algorithm. Starting from a source vertex, it repeatedly chooses the closest unsettled vertex and updates distances through that vertex.
Initialize the smallest known weights from the source.
Mark the source weight as 0.
Choose the unprocessed vertex with the smallest known weight.
Relax outgoing edges by checking whether going through that vertex improves a path.
Repeat until shortest distances are found.
Exam trap: Shortest path uses edge weights; ordinary graph traversal order alone does not prove a weighted shortest path.
10.8-10.10 Minimum Spanning Trees And Topological Order
A spanning tree connects all vertices of a connected graph without cycles. A minimum spanning tree has the smallest total edge weight. The guide covers Prim's algorithm, then topological order for directed acyclic dependency-style graphs.
Prim's algorithm starts with a source vertex and repeatedly adds the cheapest edge that connects a new vertex.
A graph has a spanning tree only if it is connected.
Topological ordering places vertices before the vertices that depend on them.
Breadth-first topological ordering uses indegrees and a queue.
Topic 10 Extended Code Example: Adjacency List With DFS And BFS
This example stores a graph as adjacency lists, then traverses it with depth-first recursion and breadth-first queue processing.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class graphType {
private:
vector<vector<int>> graph;
void dft(int vertex, vector<bool>& visited) const {
visited[vertex] = true;
cout << vertex << " ";
// Visit each adjacent vertex that has not already been reached.
for (int adjacent : graph[vertex]) {
if (!visited[adjacent]) {
dft(adjacent, visited);
}
}
}
public:
graphType(int vertices) : graph(vertices) {}
void addEdge(int from, int to) {
graph[from].push_back(to);
}
void depthFirstTraversal() const {
vector<bool> visited(graph.size(), false);
for (int v = 0; v < static_cast<int>(graph.size()); v++) {
if (!visited[v]) {
dft(v, visited);
}
}
cout << endl;
}
void breadthFirstTraversal() const {
vector<bool> visited(graph.size(), false);
queue<int> q;
for (int start = 0; start < static_cast<int>(graph.size()); start++) {
if (visited[start]) continue;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int current = q.front();
q.pop();
cout << current << " ";
for (int adjacent : graph[current]) {
if (!visited[adjacent]) {
visited[adjacent] = true;
q.push(adjacent);
}
}
}
}
cout << endl;
}
};
int main() {
graphType g(6);
g.addEdge(0, 1);
g.addEdge(0, 5);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(5, 4);
cout << "DFS: ";
g.depthFirstTraversal();
cout << "BFS: ";
g.breadthFirstTraversal();
return 0;
}
Topic 10 Glossary: Key Words And Code Terms
graph
A structure made of vertices and edges, written as G = (V, E).
vertex
A node or point in a graph.
edge
A connection between vertices.
directed graph
A graph where edges have direction.
undirected graph
A graph where edges do not have direction.
adjacent
Describes two vertices connected by an edge.
path
A sequence of vertices connected by edges.
connected graph
A graph where a path exists between every pair of vertices.
adjacency matrix
A two-dimensional representation marking whether each edge exists.
adjacency list
A representation where each vertex stores a list of its neighbours.
visited
A Boolean tracking structure used to avoid revisiting vertices.
DFS
Depth-first search; explores deeply before backing up.
BFS
Breadth-first search; visits neighbours before moving to the next level.
dft()
The recursive helper used in the example for depth-first traversal.
breadthFirstTraversal()
A queue-based traversal that processes vertices in breadth-first order.
Dijkstra
A shortest-path algorithm for weighted graphs with nonnegative edge weights.
Prim
An algorithm for finding a minimum spanning tree in a connected weighted graph.