31251 - Summary

1. Intro to C++

1.1 Lecture

Introduction to C++

Output and Input I/O

Output (std::cout): Stands for "character output" and uses the insertion operator (<<) to flow data from the program to the console.
Input (std::cin): Stands for "character input" and uses the extraction operator (>>) to flow data from the console into a variable.
Type Sensitivity: The behavior of std::cin is dependent on the data type of the variable receiving the input , such as int , float , or std::string.

Different between std::cin and std::getline (std::cin, userInput)

std::cin is used for reading a single word (up to the first whitespace) into a variable.
std::getline reads an entire line of text, including spaces, into a variable.

std::string userInput;
std::cin >> userInput; // Reads a single word
std::getline(std::cin, userInput); // Reads the entire line

Ways to define int

int x; - Declares an integer variable named x without initialization.
int x = 5; - Declares and initializes x with the value 5.
int x(5); - Declares and initializes x with the value 5 using direct initialization.
int x{5}; - Declares and initializes x with the value 5 using uniform initialization (C++11).

int myNumber{3.5} //this will give an error
int myNumber(3.5) //no error will change to 3
int myNumber{} //value is 0
int myNumber() //value is random

Function

void myFunction() {
    // Function body
}

int main() {
    myFunction();
    return 0;
}

Classes

class Car {
    public:
        std::string brand;
        int model;
        void start() {
            std::cout << "Car started!" << std::endl;
        }
    private:
        int speed;
};

Memory Management: Variables, References, and Pointers

Understanding how C++ handles data in RAM is fundamental to Data Structures and Algorithms.

Variables

Variables act like a box stored in memory.
Each variable box has a unique hexadecimal address.
Declaration: A free memory box is selected and assigned a name.
Initialization: Assigning a name and putting a specific value into the box.

References

A reference acts as an alias or "nickname" for an existing variable.
It is declared using the & symbol, such as char &ref = test;.
Modifying a reference directly changes the value of the original variable because they share the same memory address.

Pointers

A pointer is a variable that stores the memory address of another variable.
Address Operator (&): Used to retrieve the memory address of a variable.

Pointer Declaration (*): Tells the compiler the variable is a pointer, such as char *ptr;. This Declaration also apply to the function parameters

//variable declaration
char test = 'A';
char *ptr = &test;

//function with pointer parameter
void myFunction(char *ptr) {
    // Function body
    *ptr = 'B'; // *ptr, dereferencing the pointer to change the value
}
myFunction(&test); //pass the address of test to the function

Dereferencing (*): Using the * symbol to access or change the value stored at the memory address the pointer is pointing to.

Passing Variables to Functions

There are three distinct methods for passing arguments to functions in C++:

Method	Description	Effect on Original Variable
Pass by Value	A copy of the value is created and passed to the function.	None; changes within the function do not affect the original.
Pass by Reference	The function receives a reference to the original variable.	Direct; changes to the parameter affect the original value.
Pass by Pointer	The function receives the memory address (pointer) of the variable.	Direct; changes via dereferencing affect the original value.
Pass by Const Reference	Receives a reference (alias) but treats it as read-only.	None; Efficient for large data (no copy).

Pass by Value

The function creates a completely new "box" in memory and copies the value into it. Changes to the parameter x do not affect the original num.

void doubleValue(int x) {
    x = x * 2; // Changes ONLY the copy
}

int main() {
    int num = 5;
    doubleValue(num);
    // num is still 5
}

Pass by Reference

The function receives an alias (nickname) for the original variable. No copy is made, so modifying x directly modifies num.

void doubleValue(int &x) {
    x = x * 2; // Changes the original num
}

int main() {
    int num = 5;
    doubleValue(num);
    // num is now 10
}

Pass by Pointer

The function receives the memory address of the original variable. Using the dereference operator (*), it can directly access and modify the value in the original variable's memory location.

void doubleValue(int *x) {
    *x = (*x) * 2; // Reaches into the address to change value
}

int main() {
    int num = 5;
    doubleValue(&num); // Pass the address of num
    // num is now 10
}

Pass by Const Reference

The function uses the direct memory block (address) but cannot alter the value. This combines the safety of Pass by Value with the efficiency of Pass by Reference by avoiding expensive copies (e.g., when passing large text or 1 million rows of data).

void processBigData(const std::string &data) {
    // data += " modification"; // Error: Cannot modify const reference
    std::cout << "Read-only access to " << data.length() << " chars." << std::endl;
}

int main() {
    std::string hugeText(1000000, 'A'); // Simulate large data
    processBigData(hugeText); // Fast: Passes by address, no copy is made
}

Class in C++

Class Template and Implementation

#ifndef MY_INTEGER_HPP_
#define MY_INTEGER_HPP_

class myInteger {
 private:
  int value {};

 public:
  // default constructor
  myInteger();

  // constructor taking an integer
  // explicit means we don't allow myInteger x = 3
  // the constructor has to be explicitly called
  explicit myInteger(int);

  // copy constructor
  // create a copy constructor with the same value as another myInteger
  myInteger(const myInteger&);

  // assignment operator
  // this enables myInteger x {3}; myInteger y {5}; x = y;
  myInteger& operator=(const myInteger&);
  // allow user to assignment object: a = b = c
  // Without & in the myInteger, it will create copy, causing a redundance work

  // destructor, delete the memory
  ~myInteger();

  // determine if two myIntegers are equal
  friend bool operator==(const myInteger&, const myInteger&);

  // determine if one myInteger is less than another
  friend bool operator<(const myInteger&, const myInteger&);
};

#endif  // MY_INTEGER_HPP_

Class Structure and Encapsulation

class myInteger {
private:
    int value {};

The class stores one private variable: value.
Because it is private, outside code cannot access it directly.
All interaction must happen through constructors, operators, or friend functions.

This demonstrates encapsulation — hiding internal data.

Object Creation (Constructors)

Default Constructor

myInteger::myInteger() {}

Used when no value is provided:

myInteger a;

Because value was declared as int value {};, it is automatically initialized to 0.

Constructor with an Integer

myInteger::myInteger(int input) : value {input} {}

Used when creating an object with a value:

myInteger a(5);

The syntax : value {input} is called a member initializer list. It directly initializes value with input.

The constructor is marked explicit, which prevents:

myInteger a = 5;   // Not allowed

This avoids unintended automatic conversions.

Copying Objects (Copy Constructor)

myInteger::myInteger(const myInteger& x) : value {x.value} {}

Used when creating a new object from an existing one:

myInteger a(5);
myInteger b = a;   // Copy constructor

What happens:

A new object b is created.
b.value is set to a.value.

This teaches how objects are copied safely.

Assigning Objects (Assignment Operator)

myInteger& myInteger::operator=(const myInteger& x) {
    value = x.value;
    return *this;
}

Used when both objects already exist:

myInteger a(5);
myInteger b(3);

b = a;   // Assignment operator

What happens:

b.value is replaced with a.value.
The function returns *this (a reference to the current object).

Returning a reference allows chained assignment:

a = b = c;

If it returned by value instead of reference, extra copies would be created.

Object Destruction (Destructor)

myInteger::~myInteger() {}

Called automatically when an object goes out of scope.

In this class, it does nothing because no dynamic memory is used. However, it demonstrates how cleanup would work if resources were allocated.

Operator Overloading and Friend Functions Relationship

Operator Overloading

The class overloads comparison operators so that objects behave like integers.

Equality Operator

bool operator==(const myInteger& x, const myInteger& y) {
    return x.value == y.value;
}

Allows:

if (a == b)

It compares the private value of both objects.

Less-Than Operator

bool operator<(const myInteger& x, const myInteger& y) {
    return x.value < y.value;
}

Allows:

if (a < b)

Why Are These Operators friend?

In the class:

friend bool operator==(const myInteger&, const myInteger&);
friend bool operator<(const myInteger&, const myInteger&);

These operators are not member functions. They are normal functions defined outside the class.

However, they need access to the private value. The keyword friend gives them permission to access private members.

Without friend, this line would cause an error:

return x.value == y.value;

Summary: Object Lifecycle and Operator Overloading

This class demonstrates:

Encapsulation (private data)
Object initialization (constructors)
Copy construction
Assignment between objects
Object destruction
Operator overloading
Controlled access using friend

Although the class only wraps an int, it teaches how real C++ classes manage their lifecycle and behave like built-in types. This is foundational knowledge for writing safe and well-designed C++ classes.

2. Sequence Containers

2.1 Lecture Part 1: Abstract Data Types (ADTs)

ADT vs Data Structure

ADT Definition: A collection of values and a specification of operations that can be performed on them. It acts like a "user's manual," focusing on what can be done rather than how.
Data Structure Definition: A concrete implementation of an ADT.
Problem Solving Strategy: Design algorithms using ADTs by imagining "special powers" (operations) needed to solve the problem, then find a data structure that efficiently implements those powers

Example: Contains Duplicate

The lecture uses Leetcode 217 to illustrate these concepts.

The Problem: Given an array, determine if any value appears twice.
Brute Force: A double for loop checks every element against all previous elements.
ADT Approach: Define an ADT with two operations: contains(val) and insert(val).
Efficiency: While the double loop is one implementation, using more advanced data structures like Hash Tables or Balanced Binary Search Trees can significantly improve performance.

2.2 Lecture Part 2: Sequence Containers: Vectors, Deques, and Arrays

Fixed-Sized Arrays and the RAM Model

Fixed-Size Array ADT: Requires a maximum size at initialization. Operations include get(i) and set(i, x).
Random Access Memory (RAM) Model:
- Memory is viewed as a long tape of "words" with integer addresses.
- Rule 1: Constant time reading/writing to any address.
- Rule 2: Constant time memory allocation/freeing.
- Rule 3: Constant time arithmetic on addresses.
Implementation: Elements are stored in a contiguous block of memory. The address of any element is calculated using the formula:

\text{Address} = \underbrace{\&arr[0]}_{base\_address} + \underbrace{i \times \text{sizeof(type)}}_{index \times \text{number of bytes per element}}

Resizable Arrays

The Problem: Fixed-size arrays require knowing the size in advance, which isn't always possible.
Resizable Array ADT: Supports push_back(x), pop_back(), size(), get(i), and set(i, x).
Implementation Strategy:
1. Start with a fixed-size array.
2. Fill it from left to right as long as there is excess capacity (takes constant time).
3. When full, allocate a new, larger array, copy the old elements over, and free the old memory.

Growth Strategy: Why Doubling?

Why not just add 1? If we only add 1 element at a time, the cost of copying dominates. To insert N elements, it would take $1 + 2 + 3 + ... + N = O(N^2)$ time.
Why doubling? By doubling the size, we ensure that the expensive copy operation happens less frequently. This leads to an amortized time complexity of $O(1)$ for push_back.

Doubling Strategy: When the array becomes full:

Create a new array
Make its capacity double the old one
Copy old elements into it and Free the old array

Total Copying Cost
Each resize copies all current elements:
1 + 2 + 4 + ... + n/2

Why Not +1 Growth? If capacity increases by 1 each time:

1 + 2 + 3 + ... + (n−1) = n(n−1)/2

This is O(n²) (very slow).

2.3 Vector Functions and Syntax

std::vector Fundamentals

A vector is a dynamic data structure that stores elements in a contiguous block of memory and resizes automatically as needed .

Key Syntax and Operations:

Initialization:
- std::vector<int> nums {3, 1, 4}; — Creates a vector with initial values.
- std::vector<int> result(nums.size(), 1); — Creates a vector of a specific size filled with a default value (e.g., 1).
Accessing Elements:
- nums[i] — Access via indexing operator (fast, no bounds checking) .
- nums.at(i) — Access with bounds checking .
Capacity Management:
- nums.push_back(val) — Adds an element to the end.
- nums.size() — Returns the number of elements currently in the vector .
- nums.capacity() — Returns the total space allocated before a resize is required .
Looping Strategies:
- Standard for-loop: for (std::size_t i = 0; i < nums.size(); i++) — Use std::size_t because it is unsigned and can handle larger indices than int .
  - Alternative of std::size_t is auto, but we need to add u (unsigned), preventing warning
```
for (auto i = 0u; i < nums.size(); i++) {
    // ...
}
```
- Range-based for-loop: for (int n : nums) — Cleanest way to iterate over every element.
- Iterator-based for-loop: for (auto it = nums.begin(); it != nums.end(); it++) — Use iterators to iterate over every element.
```
for (auto it = vec.begin(); it < vec.end(); it++) {
    std::cout << *it << '\n';
}
```

How Vectors Work (Doubling Strategy)

Vectors use a doubling strategy to resize efficiently:

Initial Allocation: When created, a vector has a small initial capacity (e.g., 1 or 2).
Doubling: When full, it allocates a new array with twice the current capacity.
Copying: All existing elements are copied to the new array.
Cleanup: The old array is deleted.

Example:

Action	Size	Capacity	Memory Cost
Create	0	1	1
push_back(10)	1	1	1
push_back(20)	2	2	2 (copy 1 element)
push_back(30)	3	4	4 (copy 2 elements)
push_back(40)	4	4	0
push_back(50)	5	8	4 (copy 4 elements)

Why Doubling?

O(n) amortized time: Each element is copied only when the vector doubles, so the average cost per element is constant .
Avoids O(n²) copying: Unlike +1 growth, doubling keeps copying localized .

3. Templates and Iterators

3.1 Lecture

Code Architecture in C++

In professional C++ development, programs are divided into multiple files. This approach is called separate compilation. It improves organization, maintainability, and compilation efficiency.

Header Files (`.hpp`) – Interface

Header files contain declarations only. They describe:

Class definitions (structure)
Function signatures (name, parameters, return type)
Member variables

They do not contain implementation logic.

Example: student.hpp

#ifndef STUDENT_HPP
#define STUDENT_HPP

#include <string>

class Student {
private:
    std::string name;
    int age;

public:
    Student(std::string n, int a);
    void printInfo();
};

#endif

This file defines what a Student is, but not how its functions work.

Implementation Files (`.cpp`) – Definitions

Implementation files contain the actual logic of functions declared in the header.

Example: student.cpp

#include "student.hpp"
#include <iostream>

Student::Student(std::string n, int a) {
    name = n;
    age = a;
}

void Student::printInfo() {
    std::cout << name << " is " << age << " years old.\n";
}

The Student:: prefix connects the function definition to the class declared in the header.

Compilation and Linking

Compilation happens in two stages:

Compile source files into object files:
```
g++ -c student.cpp
g++ -c main.cpp
```
Link object files into an executable:
```
g++ student.o main.o -o program
```

If only main.cpp changes, student.cpp does not need to be recompiled. This improves efficiency in large projects.

Header Guards

Header guards prevent multiple inclusion of the same header file, which would otherwise cause redefinition errors.

#ifndef STUDENT_HPP
#define STUDENT_HPP

// declarations

#endif

The macro is defined the first time the file is included. Subsequent inclusions are ignored.

Templates (Generic Programming)

Templates allow writing code that works with multiple data types without duplication. They enable generic programming.

Without templates, separate versions of the same function would be required for each type.

Function Template Example

#include <iostream>

template<typename T>
T add(T a, T b) {
    return a + b;
}

int main() {
    std::cout << add(3, 4) << "\n";        // int
    std::cout << add(2.5, 1.5) << "\n";    // double
}

The compiler generates specific versions of the function when it sees how it is used. This is called template instantiation.

Class Template Example

template<typename T>
class Box {
private:
    T value;

public:
    Box(T v) : value(v) {}

    T getValue() {
        return value;
    }
};

Usage:

Box<int> intBox(10);
Box<std::string> strBox("Hello");

One template definition can produce multiple typed classes.

Importance of Templates

The Standard Template Library (STL) is built using templates. Examples include:

std::vector
std::list
std::sort
std::find

Templates allow algorithms to operate generically on containers using iterators.

Iterators

An iterator is an object that allows traversal of elements in a container. It acts similarly to a pointer. Iterators connect containers with algorithms.

Basic Iterator Example

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {10, 20, 30};

    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << "\n";
    }
}

vec.begin() returns an iterator to the first element.
vec.end() returns an iterator to one past the last element.
*it dereferences the iterator to access the value.

Iterators with Algorithms

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {5, 2, 8, 1};
    std::sort(vec.begin(), vec.end());
}

std::sort operates using iterators. It does not depend on the specific container type, only on the iterator capabilities.

Half-Open Interval

STL algorithms use a half-open interval:

[first, last)

This means:

Include first
Exclude last

Half-Open Interval Example

std::vector<int> vec = {10, 20, 30, 40, 50};
std::sort(vec.begin() + 1, vec.end() - 1);

This sorts the elements from index 1 up to but not including the last element.

Important: Dereferencing vec.end() results in undefined behavior.

Iterator Categories

Category	Capabilities	Example Container
Random Access	Jump forward/backward, compare, arithmetic	`std::vector`
Bidirectional	Move forward and backward	`std::list`
Forward	Move forward only	`std::forward_list`

Random Access Example

auto it = vec.begin();
it = it + 2;  // valid for vector

This is invalid for std::list because it does not support random access.

Bidirectional Example

#include <list>

std::list<int> myList = {10, 20, 30};
auto it = myList.begin();
++it; // Move forward to 20
--it; // Move backward to 10

Bidirectional iterators can be incremented (++) and decremented (--), but do not support arithmetic like it + 2.

Forward Example

#include <forward_list>

std::forward_list<int> fList = {10, 20, 30};
auto it = fList.begin();
++it; // Move forward to 20
// --it; // Error: Cannot move backward

Forward iterators can only be incremented sequentially using ++.

Stack vs Heap (Memory Model)

Feature	Stack	Heap
Usage	Local variables and function call frames	Dynamic memory (`new`, `new[]` / `delete`, `delete[]`)
Speed/Management	Fast, automatically managed	Slower, manually managed (unless using smart pointers)
Lifetime	Memory is freed when the variable goes out of scope	Controlled by the programmer; objects can outlive their creation scope
Size limits	Limited and fixed per thread (not suitable for very large allocations)	Used by containers (e.g., `std::vector` naturally stores its elements here)

Stack vs Heap Example

void foo() {
    Player p;                 // p on stack, destroyed at end of foo()
    Player* q = new Player(); // object on heap, pointer q on stack
    // ... use q ...
    delete q;                 // must delete to avoid memory leak
}

Constructors and Destructors

Default Constructor

Called when an object is created without arguments. Used to set sensible defaults.

class Player {
public:
    std::string name;
    int health;

    Player() : name("Unknown"), health(100) {}
};

Parameterized Constructor and Initialization Lists

Initializes an object with explicit values. Prefer initialization lists over assignment inside the constructor body—they are more efficient and required for const members and references.

Player(std::string n, int h) : name(n), health(h) {}

Destructor

Called when an object is destroyed. Used to free resources allocated by the object (e.g., heap memory, file handles, sockets).

~MyVector() {
    delete[] arrayPointer_;
}

Copy Initialization and Assignment

Copy Constructor

Purpose: Defines how to create a new object as a copy of an existing object.

MyVector v1;
MyVector v2 = v1; // copy constructor used

Shallow vs Deep Copy

Shallow Copy (Default): Member-wise copy where pointers are copied as values, meaning both objects point to the same heap memory. Dangerous for owned resources.
Deep Copy: Allocates new memory and copies the actual contents so each object owns its own resource.

The Shallow Copy Problem:

MyVector v1;
v1.arrayPointer_ = new int[5]{1,2,3,4,5};
MyVector v2 = v1; // default shallow copy
// v1 and v2 point to the same memory. When both are destroyed -> double delete -> crash.

Deep Copy Implementation:

MyVector::MyVector(const MyVector& other)
  : size_(other.size_), capacity_(other.capacity_) {
    if (other.arrayPointer_) {
        arrayPointer_ = new int[capacity_];
        for (int i = 0; i < size_; ++i)
            arrayPointer_[i] = other.arrayPointer_[i];
    } else {
        arrayPointer_ = nullptr;
    }
}

Result: v2 receives its own copy of the array and can be safely destroyed independently of v1.

Copy Assignment

Used to overwrite an existing object with data from another (v2 = v1; where both already exist).

Copy-and-Swap Idiom

Best Practice: Use the Copy-and-Swap idiom to ensure exception safety and avoid self-assignment issues.

MyVector& MyVector::operator=(MyVector other) {
    std::swap(arrayPointer_, other.arrayPointer_);
    std::swap(size_, other.size_);
    return *this;
}

The Rule of Three

The Rule of Three states that if a class requires a manual implementation of a raw pointer to heap memory, it likely requires all three:

Destructor: To free the memory (delete[]).
Copy Constructor: To perform a Deep Copy during initialization.
Copy Assignment Operator: To perform a Deep Copy during assignment.

If you omit any of these while using new, your program will likely suffer from memory leaks (forgetting the destructor) or double-free crashes (forgetting the copy logic).

3.2 Templated + MyVector functions

MyVector & Template Example

Set up

1. Overview: What is `MyVector`?

1. Overview: What is MyVector?

template <typename T>
class MyVector { ... };

A dynamic array container similar to std::vector.
Supports adding, removing, and accessing elements dynamically.
Stores size_, capacity_, and arrayPointer_ to manage memory efficiently.

2. Private Variables

T* arrayPointer_ = nullptr;
int size_ = 0;
int capacity_ = 0;

arrayPointer_ points to the first element of a dynamic array.
size_ tracks the number of elements currently in the vector.
capacity_ tracks allocated memory size, which may exceed size_.
Key invariant: size_ <= capacity_.

Functions + Templates

3. Default Constructor

template <typename T>
MyVector<T>::MyVector() {}

Creates an empty vector.
Initial values: arrayPointer_ = nullptr, size_ = 0, capacity_ = 0.

4. Constructor with Size

template <typename T>
MyVector<T>::MyVector(int n) :
  arrayPointer_ {n > 0 ? new T[n]{} : nullptr},
  size_ {n},
  capacity_ {n} {}

Allocates memory for n elements initialized to 0.
Both size_ and capacity_ are set to n.
Example: MyVector<int> v(5) → [0,0,0,0,0].

5. Copy Constructor

template <typename T>
MyVector<T>::MyVector(const MyVector<T>& other) 
  : arrayPointer_ {other.size_ > 0 ? new T[other.size_] : nullptr},
    size_ {other.size_},
    capacity_ {other.capacity_} {
    for (int i = 0; i < size_; ++i)
        arrayPointer_[i] = other.arrayPointer_[i];
}

Used when copying a vector: MyVector<int> b = a;.
Allocates new memory and copies elements.
Ensures a and b point to different memory.

6. Initializer List Constructor

template <typename T>
MyVector<T>::MyVector(std::initializer_list<T> vals) {
  size_ = capacity_ = vals.size();
  arrayPointer_ = new T[size_];
  int i = 0;
  for (T x : vals)
    arrayPointer_[i++] = x;
}

Allows vector initialization with {}: MyVector<int> v = {1,2,3};.
Sets size_ and capacity_ to list size.
Copies each element from the initializer list.

7. Destructor

template <typename T>
MyVector<T>::~MyVector() {
  delete[] arrayPointer_;
}

Frees dynamically allocated memory.
Prevents memory leaks from new T[].

8. Copy Assignment Operator

template <typename T>
MyVector<T>& MyVector<T>::operator=(MyVector<T> other) {
  std::swap(arrayPointer_, other.arrayPointer_);
  std::swap(size_, other.size_);
  std::swap(capacity_, other.capacity_);
  return *this;
}

Implements copy-swap idiom.
Swaps content of *this with other for safe assignment.
Handles self-assignment and memory management automatically.

9. push_back()

template <typename T>
void MyVector<T>::push_back(T val) { ... }

Adds an element at the end of the vector.
If size_ < capacity_, simply store the value.
If size_ == capacity_, double capacity_, allocate new memory, copy old elements, delete old memory, then add the new value.
Maintains size_ correctly after addition.

10. pop_back()

template <typename T>
void MyVector<T>::pop_back() {
  if (!empty()) --size_;
}

Removes the last element by decreasing size_.
Memory remains allocated; element is logically removed.

11. back()

template <typename T>
T& MyVector<T>::back() {
  return arrayPointer_[size_ - 1];
}

Returns a reference to the last element.
Can be used to read or modify the last element.
Requires size_ > 0 to be safe.

12. empty()

template <typename T>
bool MyVector<T>::empty() {
  return size_ == 0;
}

Returns true if the vector has no elements.
Simple check on size_.

13. size()

template <typename T>
int MyVector<T>::size() const {
  return size_;
}

Returns the number of elements stored.
Constant function, does not modify the vector.

14. capacity()

template <typename T>
int MyVector<T>::capacity() const {
  return capacity_;
}

Returns the allocated memory size (max elements without reallocation).

15. operator[]

template <typename T>
T& MyVector<T>::operator[](int i) { return arrayPointer_[i]; }

template <typename T>
const T& MyVector<T>::operator[](int i) const { return arrayPointer_[i]; }

Access elements by index: v[i].
Returns by reference so values can be modified.
Const version allows read-only access.
If returned by value, assignment like v[0] = 5 would not work.

C++ needs two versions to handle:

Non-const objects → can read and modify elements.

MyVector<int> v;
v[0] = 5;  // uses non-const version
// ---------------
MyVector<int> v = {1,2,3};
v[0] = 10;  // ✅ Can modify

Const objects → can only read elements.

const MyVector<int> cv;
int x = cv[0];  // uses const version
// ---------------
const MyVector<int> cv = {1,2,3};
int x = cv[0];  // ✅ Can read
cv[0] = 10;     // ❌ Error! Cannot modify, because it's const

16. Explicit Template Instantiation

template class MyVector<int>;
template class MyVector<float>;
template class MyVector<double>;

Tells the compiler to generate code for these types.
Ensures vector works for int, float, and double.

17. Example of Memory Layout

MyVector<int> v = {1,2,3};

arrayPointer_ → [1][2][3][ ][ ][ ]
size_ = 3
capacity_ = 6

Shows size_ vs capacity_.
Unused memory is allocated but ignored until needed.

18. Core Concepts Learned

Dynamic memory allocation: new[] / delete[].
Pointers to manage dynamic arrays.
Copy constructor ensures separate memory for copies.
Push-back resizing doubles capacity.
Access via reference allows modification.
Efficient memory management with copy-swap idiom.

4. Linked Lists

4.1 Lecture

Linked List: Singly Linked List

Each node contains a value and a pointer to the next node.
Last node points to nullptr.
Insertion and deletion are efficient.
Random access is not supported.
Memory allocation is dynamic, not contiguous.

4.2 Singly Linked List + forward_list Example

forward_list Example

Set up

1. Overview: What is `ForwardList`?

1. Overview: What is ForwardList?

class ForwardList { ... };

Implements a singly linked list storing integers.
Each node stores data and a pointer to the next node.
Supports operations: push/pop at the front, access front element, display, check empty, and get size.

2. Node Structure

struct Node {
    int data {};
    Node* next = nullptr;
    Node(){}
    Node(int input_data, Node* next_node = nullptr) : data{input_data}, next{next_node} {}
};

data stores the value of the node.
next points to the next node in the list.
Constructors allow default creation or setting data and next node pointer.

3. Private Variables

int size_ = 0;
Node* head_ = nullptr;

size_ tracks the number of nodes.
head_ points to the first node of the list.
If head_ == nullptr, the list is empty.

Functions

4. Default Constructor

ForwardList::ForwardList() {}

Creates an empty list.
head_ is initialized to nullptr, size_ = 0.

5. Destructor

ForwardList::~ForwardList() {
  for (Node* cur = head_; cur != nullptr;) {
    Node* tmp = cur;
    cur = cur->next;
    delete tmp;
    --size_;
  }
}

Frees all nodes to prevent memory leaks.
Traverses from head_ to the end, deleting each node.
Updates size_ as nodes are deleted.

6. Constructor from Initializer List

ForwardList::ForwardList(std::initializer_list<int> input) {
  for (auto it = std::rbegin(input); it != std::rend(input); it++) {
    push_front(*it);
  }
}

Allows initialization: ForwardList fl = {1,2,3};
Iterates backwards through the initializer list.
Calls push_front to maintain order.

7. push_front()

void ForwardList::push_front(int data) {
  head_ = new Node{data, head_};
  size_++;
}

Adds a node at the beginning.
Creates a new node pointing to the old head_.
Updates head_ to the new node.
Increases size_.

8. pop_front()

void ForwardList::pop_front() {
  Node* temp = head_;
  head_ = head_->next;  // (*head_).next
  delete temp;
  size_--;
}

Removes the first node.
head_ = head_->next moves the head pointer to the second node.
Deletes the old head node.
Decreases size_.

Why `head_->next` and not `head_.next`?

head_ is a pointer to Node, not a Node object.
head_.next would be valid only if head_ were an object, because . accesses members of an object.
-> is shorthand for (*head_).next:
```
head_->next == (*head_).next
```
Always use -> when accessing members through a pointer.

9. front() by Value

int ForwardList::front() const {
  return head_->data;
}

Returns the value of the first node.
Const version, cannot modify the node.

10. front() by Reference

int& ForwardList::front() {
  return head_->data;
}

Returns a reference to the first node’s data.
Allows modifying the value:
```
fl.front() = 10;
```

11. display()

void ForwardList::display() const {
  for (Node* it = head_; it != nullptr; it = it->next)
    std::cout << it->data << (it->next ? " " : "");
}

Traverses the list from head_ to nullptr.
Prints values in sequence, separated by spaces.

12. empty()

bool ForwardList::empty() const {
  return size_ == 0;
}

Returns true if the list has no nodes.

13. size()

int ForwardList::size() const {
  return size_;
}

Returns the number of nodes in the list.

14. Key Concepts

Singly linked list: each node points only to the next.
head_ pointer: always points to the first node.
Dynamic memory: new/delete for node allocation.
Push/Pop front: O(1) operations.
Accessing node members:
- Use -> for pointers (head_->next).
- Use . for objects (node.data).
Const vs reference access:
- front() const → read only.
- front() non-const → read/write.

5. Hash Tables, Stacks, Queues

5.1 Lecture

Hashmap Functions

Details

Hashmap in cpp - std::unordered_map

Most common std::unordered_map functions

Accessing Elements

Use [] for easy access or at() if you want to ensure the key exists.

std::unordered_map<std::string, int> scores = {{"Alice", 10}};
// operator[]: Creates the key if it doesn't exist (e.g., Bob becomes 0)
scores["Bob"] = 20; 
// at(): Throws an error if the key is missing
int a = scores.at("Alice"); 

Checking Existence

Before C++20, find was the standard; now contains is preferred for readability.

// Modern (C++20 and later)
if (scores.contains("Alice")) { /* Found it */ }
// Traditional (Works in all versions)
if (scores.find("Alice") != scores.end()) { /* Found it */ }

Inserting Elements

insert and emplace add new items, but they won't overwrite existing ones.

// Standard insertion
scores.insert({"Charlie", 30});
// Efficient "in-place" construction
scores.emplace("Daisy", 40);
// C++17: Insert OR Update if it already exists
scores.insert_or_assign("Alice", 50); 

Removing Elements

You can remove by key or clear everything at once.

// Remove by key (returns 1 if found/removed, 0 otherwise)
scores.erase("Alice");
// Remove by iterator
auto it = scores.find("Bob");
if (it != scores.end()) scores.erase(it);
// Wipe the entire map
scores.clear();

Iterating

You can loop through the map using a range-based loop. Remember that first is the key and second is the value.

for (const auto& [key, val] : scores) { // C++17 Structured Binding
    std::cout << key << " has score " << val << std::endl;
}
// Check size or if empty
if (!scores.empty()) {
    std::cout << "Size is: " << scores.size();
}

Hashmap Functions Constant time logic + Sample Scatch Coding

Hash table concept: A hash table stores keys in an array of buckets, where a hash function converts a key into an array index.
Core idea: Instead of searching through elements, the structure computes the location of the key directly using a hash function.
Operations: Insert, search, and delete all compute the bucket first, then operate only on that bucket.
Handling collisions: If multiple keys map to the same bucket, they are stored together (e.g., using a linked list, called separate chaining).
Why O(1): Because the hash function directly jumps to the correct bucket, avoiding scanning the entire structure, making operations constant time on average.

Details

Sample: Hashmap Functions

Example structure:

bucket[0] -> 10 -> 20
bucket[1] -> 5
bucket[2] -> 17 -> 22
bucket[3]
bucket[4] -> 9

Sample code:

#ifndef HASH_HPP_
#define HASH_HPP_

#include <list>
#include <algorithm>


template <std::size_t N>
class Hash {
 
  std::list<int> buckets[N] {}; // Array of N buckets, each bucket is a linked list of integers
  std::size_t numElements {}; // Tracks how many elements are stored in the hash table

 public:
  void insert(int key) {
    std::size_t bucket = key % N; // Compute bucket index using the hash function (key % N)
    
    if (!contains(key)) { // Check if the key is NOT already in the hash table
      buckets[bucket].push_back(key); // Insert the key into the linked list stored in that bucket
      ++numElements;
    }
  }

  void erase(int key) {
    std::size_t bucket = key % N;
    
    if (contains(key)) { // Only remove if the key exists in the table
      buckets[bucket].remove(key); // Remove the key from the linked list in that bucket
      --numElements;
    }
  }

  bool contains(int key) {
    std::size_t bucket = key % N; // Compute the bucket index for this key

    auto it = std::find(buckets[bucket].begin(), buckets[bucket].end(), key); // Search the linked list in that bucket for the key

    return it != buckets[bucket].end();
  }

  std::size_t size() {
    return numElements;
  }
};

#endif      // HASH_HPP_

Stack Functions

Stack Functions in C++ - std::stack

std::stack is a container adapter that follows the LIFO (Last-In, First-Out) principle.

Core Functions and Usage

Here is how those specific functions look and behave in C++:

Function	C++ Syntax	Description
Constructor	`std::stack<int> A;`	Creates an empty stack (in this case, for integers).
Push	`A.push(x);`	Adds element `x` to the very top.
Top	`A.top();`	Returns a reference to the top element without removing it.
Pop	`A.pop();`	Removes the top element. Note: In C++, `pop()` returns `void`.
Size	`A.size();`	Returns the number of elements currently in the stack.

A Quick Code Example

To use a stack, you need to include the <stack> header. Here is how your logic translates into a functional snippet:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> A; // Creates an empty stack

    A.push(10);        // Stack: [10]
    A.push(20);        // Stack: [10, 20] (20 is at the top)

    std::cout << "Top element: " << A.top() << std::endl; // Returns 20
    std::cout << "Size: " << A.size() << std::endl;        // Returns 2

    A.pop();           // Removes 20. Stack: [10]
    
    return 0;
}

Important Tip

Always check if the stack is empty using A.empty() before calling A.top() or A.pop(). Attempting to access the top of an empty stack will cause your program to crash (undefined behavior).

Stack Functions from Scratch with Vector

myStack.hpp

#ifndef STACK_HPP_
#define STACK_HPP_

#include <vector>

template <typename T>
class MyStack {
 private:
  std::vector<T> data {};

 public:
  // default constructor
  MyStack();

  // add an element to the top of stack
  void push(T val);

  // remove an element from the top of stack
  void pop();

  // get the element at the top of stack
  T& top();

  // return number of elements in the stack
  int size();

  // check if stack is empty
  bool empty();
};

#endif      // STACK_HPP_

myStack.cpp

#include <vector>
#include <string>
#include "myStack.hpp"

// default constructor (nothing to do here)
template <typename T>
MyStack<T>::MyStack() {}

// add an element to the top of stack
template <typename T>
void MyStack<T>::push(T val) {
  data.push_back(val);
}

// remove an element from the top of stack
template <typename T>
void MyStack<T>::pop() {
  data.pop_back();
}

// get the element at the top of stack
template <typename T>
T& MyStack<T>::top() {
  return data.back();
}

// return number of elements in the stack
template <typename T>
int MyStack<T>::size() {
  return data.size();
}

// check if stack is empty
template <typename T>
bool MyStack<T>::empty() {
  return data.empty();
}

template class MyStack<int>;
template class MyStack<char>;
template class MyStack<std::string>;

6. Big Oh, Analysis of Algorithms

6.1 Lecture

1. Recursion Fundamentals

Recursion Fundamentals

Recursion is a technique where a function calls itself to solve a problem by breaking it down into simpler, identical subproblems.

The Three Pillars of Recursive Logic

Divide: Break the problem into smaller, similar subproblems.
Conquer: Solve subproblems recursively until they are simple enough to solve directly.
Combine: Merge subproblem solutions to solve the original problem.

The Base Case (Critical)

The Base Case is the "exit condition" for the smallest possible input. Without it, the function enters an endless loop, eventually causing a stack overflow.

2. Factorial Logic (

n!

)

Factorial Recursive Logic

The factorial of $n$ is the product of all positive integers from $1$ to $n$ .

Recursive Pattern: $n! = n \times (n-1)!$ .
Base Case: $0! = 1$ .

int factorial(int n) {
    if (n == 0) return 1;       // Base Case: stops recursion
    return n * factorial(n-1);  // Recursive Step: n * (n-1)!
}

3. Fibonacci Sequence Logic

Fibonacci Sequence Recursive and iterative Logic

In this sequence, each number is the sum of the two preceding numbers.

Recursive Formula: $fib(n) = fib(n-1) + fib(n-2)$ .
Base Cases: $fib(0) = 0$ and $fib(1) = 1$ .

Comparison: Recursive vs. Iterative

Feature	Recursive Fibonacci	Iterative Fibonacci
Logic	Follows math formula directly.	Uses a `for` loop to build up.
Base Cases	`if (n <= 1) return n;`.	`if (n <= 1) return n;`.
Efficiency	Slower; calculates the same values many times.	Faster; calculates each value exactly once.
Memory	Uses Stack space for every call.	Uses minimal fixed memory (3 variables).

// Recursive Logic
int64_t recursiveFibonacci(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;

	return recursiveFibonacci(n-1)+recursiveFibonacci(n-2);
}

// Iterative Logic (Building from the bottom up)
int64_t iterativeFibonacci(int n) {
    if (n <= 1) return n;
    int64_t prev1 = 0, prev2 = 1;
    for (int i = 2; i <= n; ++i) {
        int64_t ans = prev1 + prev2; // Combine previous two
        prev1 = prev2;               // Shift window forward
        prev2 = ans;
    }
    return prev2;
}

7. Sorting, Divide and Conquer

7.1 Lecture

Sorting 0s and 1s

Key Points:

The array is guaranteed to only contain 0s and 1s (or false/true)
Faster than generic sorting because we exploit this constraint
Uses a two-pointer approach — one pointer scans right, one tracks the "boundary"
Core idea: track the position of the first 1 in the array
- Whenever a 0 is found to the right of that position → swap it with the first 1
- Then advance the "first 1" pointer one step right
Only requires a single pass through the array → O(n) time
No extra memory needed — sorting is done in-place

Code Sample and Explanation

#ifndef SORT_BOOLEAN_HPP_
#define SORT_BOOLEAN_HPP_
#include <iterator>
#include <utility>

// Iter = iterator to a container of pairs: { first: 0 or 1, second: string }
template <typename Iter>
void sortBoolean(Iter begin, Iter end) {

  Iter leftEnd = begin;
  // STEP 1: Scan forward to find the FIRST "1" in the array.
  // leftEnd will stop at the first element where first == 1.
  // If the whole array is 0s, leftEnd will reach end and we return early.
  while (leftEnd != end and leftEnd->first == 0) {
    ++leftEnd;
  }

  // STEP 2: If no 1 was found, the array is already sorted — nothing to do.
  if (leftEnd == end) {
    return;
  }

  // INVARIANT: leftEnd always points to the leftmost "1" in the unsorted region.
  // We now scan j from the element AFTER leftEnd to the end of the array.
  for (Iter j = std::next(leftEnd); j != end; ++j) {

    // STEP 3: If we find a 0 to the right of the first 1...
    if (j->first == 0) {
      // ...swap the 0 (at j) with the first 1 (at leftEnd).
      // The 0 moves left into the sorted region, the 1 moves right.
      std::swap(*leftEnd, *j);

      // Advance leftEnd so it still points to the leftmost 1.
      // (The element we just swapped in is now the new first 1.)
      ++leftEnd;
    }
    // If j->first == 1, we skip it — it's already on the correct (right) side.
  }
}
#endif  // SORT_BOOLEAN_HPP_

Walkthrough example: [0, 1, 0, 1, 0]

leftEnd scans → stops at index 1 (first 1)
j starts at index 2, finds 0 → swap indices 1 & 2 → [0, 0, 1, 1, 0], leftEnd = index 2
j moves to index 3, finds 1 → skip
j moves to index 4, finds 0 → swap indices 2 & 4 → [0, 0, 0, 1, 1], leftEnd = index 3
Done ✓

The Partition Problem

Key points:

Generalises the 0s-and-1s sort to any type with any condition
Takes a predicate function p — a function that returns true or false for any element
Goal: rearrange the array so that all elements where p(x) == false come before all elements where p(x) == true
The insight: applying p to every element maps the array to 0s and 1s — so the exact same algorithm applies
Returns an iterator pointing to the first element that satisfies p (the boundary between the two groups)
Time complexity: O(n) — one pass through the array
In-place, no extra memory needed
Used as the building block inside Quicksort

Code Sample and Explanation

#ifndef PARTITION_HPP_
#define PARTITION_HPP_
#include <iterator>
#include <utility>

// Iter      = any iterator (works on vectors, arrays, etc.)
// Predicate = any callable that takes an element and returns bool
//             e.g. [](int x){ return x > 3; }
template <typename Iter, typename Predicate>
Iter myPartition(Iter begin, Iter end, Predicate p) {

  Iter leftEnd = begin;

  // STEP 1: Scan forward to find the FIRST element that satisfies p(x).
  // This is equivalent to finding the first "1" in the 0s-and-1s problem.
  // Elements that do NOT satisfy p(x) are already on the correct (left) side.
  while (leftEnd != end and not p(*leftEnd)) {
    ++leftEnd;
  }

  // STEP 2: If no element satisfies p(x), no rearrangement needed.
  // Return end to signal the boundary is at the very end (all elements are "false").
  if (leftEnd == end) {
    return leftEnd;
  }

  // INVARIANT: leftEnd always points to the leftmost element satisfying p(x).
  // (Same logic as sortBoolean — leftEnd is the "first 1" pointer.)
  for (Iter j = std::next(leftEnd); j != end; ++j) {

    // STEP 3: If j points to a "false" element (does NOT satisfy p)...
    if (not p(*j)) {
      // ...swap it with the first "true" element (at leftEnd).
      // This pushes the false element left and the true element right.
      std::swap(*leftEnd, *j);

      // Advance leftEnd to maintain the invariant.
      ++leftEnd;
    }
    // If p(*j) is true, element is already on the right side — skip it.
  }

  // Return the boundary iterator:
  // everything before leftEnd is "false", everything from leftEnd onward is "true".
  return leftEnd;
}
#endif  // PARTITION_HPP_

Walkthrough example: array [3, 1, 4, 1, 5, 9, 2], predicate p(x) = x > 3

Step	Array state	leftEnd value
Start	`[3, 1, 4, 1, 5, 9, 2]`	points to 4 (index 2, first true)
Swap 4↔1 (index 2↔3)	`[3, 1, 1, 4, 5, 9, 2]`	advances to 4 (index 3)
Swap 4↔2 (index 3↔6)	`[3, 1, 1, 2, 5, 9, 4]`	advances to 5 (index 4)
End of array	`[3, 1, 1, 2, 5, 9, 4]`	returns index 4

Result: [3,1,1,2] all ≤3 (false) on the left, [5,9,4] all >3 (true) on the right ✓

Quicksort

Key Points:

A recursive sorting algorithm that uses myPartition as its core building block
Strategy: divide and conquer
- Pick a pivot (last element of the current subarray)
- Partition: everything less than the pivot goes left, everything greater goes right
- The pivot lands in its exact final sorted position — it never moves again
- Recursively apply the same process to the left and right halves
Base case: a subarray of size 0 or 1 is already sorted → return immediately
Average time complexity: O(n log n)
- Each partition call does O(n) work
- On average, we have O(log n) levels of recursion (each pivot halves the problem)
Worst case: O(n²) — happens when the pivot is always the smallest or largest element (e.g. already-sorted array with last-element pivot)
In-place — no extra array needed, just swaps
After partitioning, the pivot is swapped into the boundary position so it sits between the two halves

Code Sample and Explanation

#ifndef QUICKSORT_HPP_
#define QUICKSORT_HPP_
#include <algorithm>
#include <iterator>

// --- myPartition (same as Partition section above) ---
// Included here because quicksort depends on it.
template <typename Iter, typename Predicate>
Iter myPartition(Iter begin, Iter end, Predicate p) {
  Iter leftEnd = begin;
  while (leftEnd != end and not p(*leftEnd)) { ++leftEnd; }
  if (leftEnd == end) { return leftEnd; }
  for (Iter j = std::next(leftEnd); j != end; ++j) {
    if (not p(*j)) { std::swap(*leftEnd, *j); ++leftEnd; }
  }
  return leftEnd;
}

// --- Quicksort (using homemade partition) ---
template <typename Iter>
void quicksort(Iter begin, Iter end) {

  // BASE CASE: If the subarray has fewer than 2 elements, it's already sorted.
  // std::distance counts elements between begin and end.
  if (std::distance(begin, end) < 2) {
    return;
  }

  // STEP 1: Choose the PIVOT — the last element in the current subarray.
  // std::prev(end) gives an iterator to the last element.
  // We copy the value (not a reference) so swaps don't affect it.
  auto pivot = *std::prev(end);

  // STEP 2: Partition all elements EXCEPT the pivot (begin to std::prev(end)).
  // The predicate is: "is element a GREATER THAN the pivot?"
  //   - false (≤ pivot) → goes to the LEFT side
  //   - true  (> pivot) → goes to the RIGHT side
  // leftEnd now points to the first element greater than pivot — the boundary.
  Iter leftEnd = myPartition(
    begin,
    std::prev(end),                              // exclude the pivot itself
    [&pivot](const auto& a) { return a > pivot; } // predicate: a > pivot
  );

  // STEP 3: Place the pivot in its FINAL position.
  // Swap the pivot (currently at the last position) with the first element
  // that is greater than it (leftEnd). The pivot now sits exactly at the boundary.
  // Everything to its left is ≤ pivot; everything to its right is > pivot.
  std::iter_swap(leftEnd, std::prev(end));

  // STEP 4: Recursively sort the LEFT half (elements < pivot).
  // This subarray runs from begin up to (but NOT including) leftEnd.
  quicksort(begin, leftEnd);

  // STEP 5: Recursively sort the RIGHT half (elements > pivot).
  // This subarray starts ONE PAST leftEnd (skipping over the now-placed pivot).
  quicksort(std::next(leftEnd), end);
}

// --- Alternative: Quicksort using std::partition ---
// std::partition uses the OPPOSITE predicate convention:
//   - true  → goes LEFT  (elements we want on the left: a <= pivot)
//   - false → goes RIGHT (elements we want on the right: a > pivot)
// Otherwise identical logic to the version above.
template <typename Iter>
void quicksort_std(Iter begin, Iter end) {
  if (std::distance(begin, end) < 2) {
    return;
  }
  auto pivot = *std::prev(end);

  // std::partition: elements satisfying predicate go LEFT.
  // Predicate is a <= pivot, so elements ≤ pivot go left — same result as above.
  Iter leftEnd = std::partition(
    begin,
    std::prev(end),
    [&pivot](const auto& a) { return a <= pivot; } // NOTE: flipped from homemade version
  );

  std::iter_swap(leftEnd, std::prev(end));
  quicksort_std(begin, leftEnd);
  quicksort_std(std::next(leftEnd), end);
}
#endif  // QUICKSORT_HPP_

Walkthrough example: [7, -2, 10, 8, 3, 1, 5]

quicksort([7,-2,10,8,3,1,5])
  pivot = 5
  partition → [-2, 3, 1, | 5 | 7, 10, 8]   (5 is now in final position)
  quicksort([-2, 3, 1])
    pivot = 1
    partition → [-2 | 1 | 3]               (1 is now in final position)
    quicksort([-2])  → base case, return
    quicksort([3])   → base case, return
  quicksort([7, 10, 8])
    pivot = 8
    partition → [7 | 8 | 10]               (8 is now in final position)
    quicksort([7])   → base case, return
    quicksort([10])  → base case, return
Final result: [-2, 1, 3, 5, 7, 8, 10] ✓

8. STUVAC (Study Vacation)

8.1 Revision

Review Weeks 1-7

8.2 Tasks

Due: Ex 6 (12 Apr, 23:59)

9. Priority Queues and BSTs

9.1 Lecture

1. Queue vs Priority Queue

Queue vs Priority Queue

Queue (FIFO)

First In, First Out
Elements are removed in the order they arrive

Priority Queue

Elements are removed based on priority, not order
Highest priority element is always removed first

2. Priority Queue in C++

Priority Queue in C++

Default behavior:

std::priority_queue is a max heap
Largest element is always at the top

Operations

Operation	Description	Time Complexity
`push(x)`	Insert element	O(log n)
`pop()`	Remove top element	O(log n)
`top()`	Access top element	O(1)

3. Min Priority Queue

Min Priority Queue

To make the smallest element come first:

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

4. Finding the k-th Largest Element

Finding the k-th Largest Element

Idea

Keep only the k largest elements
Use a min heap
If size exceeds k, remove the smallest element

Result

The top element is the k-th largest

5. C++ Example

C++ Example

#include <iostream>
#include <queue>
#include <vector>

int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    for (int num : nums) {
        pq.push(num);

        if (pq.size() > k) {
            pq.pop();
        }
    }

    return pq.top();
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;

    std::cout << findKthLargest(nums, k) << std::endl;
    return 0;
}

6. Heap (Underlying Structure)

Heap (Underlying Structure)

Binary tree structure
Heap property:
- Min heap: parent ≤ children
- Max heap: parent ≥ children

Array Representation

For index i:

Left child: 2 * i
Right child: 2 * i + 1
Parent: i / 2

10. Graphs

10.1 Lecture

1. What is a Graph?

What is a Graph?

A graph is made of:

Nodes (vertices): the points
Edges: the connections between points

Key ideas

A graph can have cycles (loops)
It does not have to start from one root like a tree

Types of graphs

Undirected: connection goes both ways
Directed: connection goes one way
Weighted: edges have values like distance or cost

2. Graph Representation

Graph Representation

Adjacency List

This is the most common way to store a graph.

Each node stores a list of its neighbors.

vector<vector<int>> adj(n);

// undirected edge
adj[u].push_back(v);
adj[v].push_back(u);

Weighted Graph

If edges have weights, store a pair:

vector<vector<pair<int, int>>> adj(n);

// edge u -> v with weight w
adj[u].push_back({v, w});

Adjacency Matrix

A 2D table is used.

matrix[u][v] = 1 means there is an edge.

vector<vector<int>> matrix(n, vector<int>(n, 0));

matrix[u][v] = 1;
matrix[v][u] = 1;

Quick comparison

Method	Space	Edge Check
Matrix	O(V²)	Fast
List	O(V + E)	Slower

3. Traversal Algorithms

Traversal Algorithms

Traversal means visiting all the nodes in a graph.

Breadth-First Search (BFS)

Idea

Visits nodes level by level
Uses a queue

Use

Good for shortest path in an unweighted graph

BFS code

#include <queue>

void bfs(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

Depth-First Search (DFS)

Idea

Goes as deep as possible first
Uses recursion or a stack

Use

Cycle detection
Path finding
Topological sort

DFS code

void dfs(int u, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[u] = true;

    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v, adj, visited);
        }
    }
}

4. Example Graph

Example Graph

Let’s use this graph:

0 connected to 1 and 2
1 connected to 3 and 4
2 connected to 5

Adjacency list

vector<vector<int>> adj = {
    {1, 2},    // 0
    {0, 3, 4}, // 1
    {0, 5},    // 2
    {1},       // 3
    {1},       // 4
    {2}        // 5
};

Picture in words

5. BFS Step-by-Step

BFS Step-by-Step

Start from node 0.

Step 1

Visit 0
Queue: [0]

Step 2

Remove 0
Add its neighbors 1, 2
Queue: [1, 2]

Step 3

Remove 1
Add new neighbors 3, 4
Queue: [2, 3, 4]

Step 4

Remove 2
Add new neighbor 5
Queue: [3, 4, 5]

Step 5

Remove 3
No new nodes
Queue: [4, 5]

Step 6

Remove 4
No new nodes
Queue: [5]

Step 7

Remove 5
No new nodes
Queue: []

BFS order: 0, 1, 2, 3, 4, 5

6. DFS Step-by-Step

DFS Step-by-Step

Start from node 0.

Step 1

Visit 0
Go to 1

Step 2

Visit 1
Go to 3

Step 3

Visit 3
No new unvisited nodes
Backtrack to 1

Step 4

From 1, go to 4

Step 5

Visit 4
No new unvisited nodes
Backtrack to 1
Backtrack to 0

Step 6

From 0, go to 2

Step 7

Visit 2
Go to 5

Step 8

Visit 5
No new unvisited nodes

DFS order: 0, 1, 3, 4, 2, 5

7. Main Difference

Main Difference

BFS	DFS
Uses a queue	Uses recursion or a stack
Visits level by level	Goes deep first
Good for shortest path	Good for exploring paths

1. Intro to C++

1.1 Lecture​

Introduction to C++​

Memory Management: Variables, References, and Pointers​

Variables​

References​

Pointers​

Passing Variables to Functions​

Class in C++​

Class Template and Implementation​

2. Sequence Containers

2.1 Lecture Part 1: Abstract Data Types (ADTs)​

ADT vs Data Structure​

Example: Contains Duplicate​

2.2 Lecture Part 2: Sequence Containers: Vectors, Deques, and Arrays​

Fixed-Sized Arrays and the RAM Model​

Resizable Arrays​

2.3 Vector Functions and Syntax​

3. Templates and Iterators

3.1 Lecture​

Code Architecture in C++​

Header Files (.hpp) – Interface​

Implementation Files (.cpp) – Definitions​

Compilation and Linking​

Header Guards​

Templates (Generic Programming)​

Importance of Templates​

Iterators​

Half-Open Interval​

Iterator Categories​

Stack vs Heap (Memory Model)​

Constructors and Destructors​

Default Constructor​

Parameterized Constructor and Initialization Lists​

Destructor​

Copy Initialization and Assignment​

Copy Constructor​

Copy Assignment​

The Rule of Three​

3.2 Templated + MyVector functions​

MyVector & Template Example​

Set up​

1. Overview: What is MyVector?​

2. Private Variables​

Functions + Templates​

3. Default Constructor​

4. Constructor with Size​

5. Copy Constructor​

6. Initializer List Constructor​

7. Destructor​

8. Copy Assignment Operator​

9. push_back()​

10. pop_back()​

11. back()​

12. empty()​

13. size()​

14. capacity()​

15. operator[]​

16. Explicit Template Instantiation​

17. Example of Memory Layout​

18. Core Concepts Learned​

4. Linked Lists

4.1 Lecture​

Linked List: Singly Linked List​

4.2 Singly Linked List + forward_list Example​

Set up​

1. Overview: What is ForwardList?​

2. Node Structure​

3. Private Variables​

Functions​

4. Default Constructor​

5. Destructor​

6. Constructor from Initializer List​

7. push_front()​

8. pop_front()​

Why head_->next and not head_.next?​

9. front() by Value​

10. front() by Reference​

11. display()​

12. empty()​

1.1 Lecture

Introduction to C++

Memory Management: Variables, References, and Pointers

Variables

References

Pointers

Passing Variables to Functions

Class in C++

Class Template and Implementation

2.1 Lecture Part 1: Abstract Data Types (ADTs)

ADT vs Data Structure

Example: Contains Duplicate

2.2 Lecture Part 2: Sequence Containers: Vectors, Deques, and Arrays

Fixed-Sized Arrays and the RAM Model

Resizable Arrays

2.3 Vector Functions and Syntax

3.1 Lecture

Code Architecture in C++

Header Files (`.hpp`) – Interface

Implementation Files (`.cpp`) – Definitions

Compilation and Linking

Header Guards

Templates (Generic Programming)

Importance of Templates

Iterators

Half-Open Interval

Iterator Categories

Stack vs Heap (Memory Model)

Constructors and Destructors

Default Constructor

Parameterized Constructor and Initialization Lists

Destructor

Copy Initialization and Assignment

Copy Constructor

Copy Assignment

The Rule of Three

3.2 Templated + MyVector functions

MyVector & Template Example

Set up

1. Overview: What is `MyVector`?

2. Private Variables

Functions + Templates

3. Default Constructor

4. Constructor with Size

5. Copy Constructor

6. Initializer List Constructor

7. Destructor

8. Copy Assignment Operator

9. push_back()

10. pop_back()

11. back()

12. empty()

13. size()

14. capacity()

15. operator[]

16. Explicit Template Instantiation

17. Example of Memory Layout

18. Core Concepts Learned

4.1 Lecture

Linked List: Singly Linked List

4.2 Singly Linked List + forward_list Example

Set up

1. Overview: What is `ForwardList`?

2. Node Structure

3. Private Variables

Functions

4. Default Constructor

5. Destructor

6. Constructor from Initializer List

7. push_front()

8. pop_front()

Why `head_->next` and not `head_.next`?

9. front() by Value

10. front() by Reference

11. display()

12. empty()

13. size()

14. Key Concepts

5.1 Lecture

Hashmap Functions