Recursion, Algorithms and Data Structures Bootcamp in C++

Explore memory management for recursion by contrasting stack memory, which stores local variables and calls, with the heap for dynamic data, noting stack overflow and heap fragmentation.

Show how each function call creates a stack frame and stores local variables and parameters on the stack, while objects reside on the heap. C++ requires manual memory management.

Explore recursion by reducing problems to smaller instances, define a base case to avoid infinite loops, and compare tail and head recursion with iterative solutions.

Compare head recursion and tail recursion by base case and execution order: head recursion performs operations after the recursive call, tail recursion before the call, yielding different output orders.

See how recursion uses the system stack to push stack frames, handle base cases, and compute sums and factorials, highlighting stack memory limits and tail versus head recursion.

Explore factorial computation using head recursion and tail recursion with an accumulator, comparing base case handling, recursion order, and how to optimize to iteration.

Explore how the factorial function uses recursion and stack frames to reach a base case and return the final result, illustrated by the 5! = 120 computation.

Compute the nth fibonacci number using head recursion with base cases 0 and 1, calling fib(n-1) and fib(n-2), summing results, and note the slow overhead from overlapping subproblems.

Explore how recursion computes Fibonacci numbers and visualizes stack memory, base cases, and stack frames, showing backtracking and return behavior as the function calls unfold.

Explore the towers of Hanoi, a three-peg disk puzzle that demonstrates recursion. Move n minus 1 disks to an auxiliary peg, relocate the largest disk to the destination, and finish.

Develop a recursive Towers of Hanoi solution that uses an integer disk representation and rods (A, B, C) to move all disks from source to destination, using the middle rod.

Visualize the Towers of Hanoi by tracing stack frames as the recursive algorithm moves disks from source to destination via the middle peg, highlighting base cases.

Compare recursion and iteration by highlighting independent stack frames, why recursion cannot alter outer variables, and why backtracking and dynamic programming commonly rely on recursion.

Explore how linear search finds a target in an unsorted list by checking items sequentially, yielding linear time. Compare with binary search and hash-based lookups for faster performance.

Implement a linear search on an unsorted one-dimensional array by scanning from 0 to n-1, reporting the found index and illustrating linear time; note binary search applies to sorted arrays.

Binary search on a sorted data structure finds an item in logarithmic time. It checks the middle item and discards half each iteration, requiring log n comparisons.

Explore binary search in a sorted array, using low, high, and middle indices with tail recursion; avoid overflow, handle misses, and locate items in logarithmic time.

Learn how backtracking uses recursion to solve constraint satisfaction problems by pruning invalid branches within a depth-first search on a search tree, with examples like n-queens and Sudoku.

Compare brute force search and backtracking using a search tree. Backtracking prunes bad states via depth-first search, delivering faster solutions; factorial and exponential running times appear, with the upcoming N-queens.

Explore the N-queens problem by placing one queen per column on an n by n board, using backtracking to avoid attacks along rows, columns, and diagonals.

Explore the tree representation of the three-queens problem, starting from an empty root and branching by queen placements, and learn how pruning speeds up backtracking versus brute force.

Develop a C++ N-queens solution using a two-dimensional board and a backtracking solver, with functions to set and print queens and to validate positions via rows and diagonals.

Explore how recursion, backtracking, and stack memory solve the N-queens problem, using recursive calls across columns, validating positions, backtracking on failures, and confirming a full solution.

Color graphs by assigning colors so adjacent vertices differ using backtracking, and explore the chromatic number and the NP-complete nature of the problem, with applications from scheduling to map coloring.

Explore the graph coloring problem with a six-vertex example, choosing colors while avoiding adjacent vertices sharing the same color, using backtracking and pruning to find a valid coloring.

Implement a backtracking graph coloring solution in C++ using an adjacency matrix and integer color indices, ensuring no adjacent nodes share a color and demonstrating feasibility with three colors.

Explore the knight's tour on an n by n board, visiting every cell exactly once, with eight moves and backtracking, and its link to hamiltonian paths and cycles.

Implement a knight's tour on an eight-by-eight board using a two-dimensional solution matrix to store step counters, initialize the board, and backtrack with valid moves.

Analyze why brute force is slow, how backtracking trims factorial complexity to exponential, and how metaheuristics like simulated annealing and genetic algorithms offer approximate solutions for NP-complete problems.

Dynamic programming uses recursion with memorization or tabulation to solve problems with overlapping subproblems and optimal substructure, trading memory for faster running time.

Explore Fibonacci numbers, compare recursive and dynamic programming approaches, and learn memorization with an associative array to store subproblem results, achieving linear time with extra memory.

Master dynamic programming to compute Fibonacci numbers efficiently in C++. Compare recursive and iterative approaches, using a memoized one-dimensional table to avoid recomputation.

Explore the knapsack problem, a dynamic programming driven optimization that maximizes value under a weight capacity, covering zero-one and divisible variants, DP tables, and complexity.

Apply dynamic programming to the knapsack problem, building a two dimensional table to maximize profit for given item weights and capacities, and reconstruct the chosen items from the table.

Implement the knapsack problem with a two-dimensional table to maximize value by considering item weights and values, and reconstruct the selected items for the final solution.

Explore why data structures matter for handling large data sets, showing how proper storage with trees, associative arrays, and priority queues can dramatically boost algorithm speed and manage memory tradeoffs.

Differentiate abstract data types from data structures by showing how abstract data types define behavior as blueprints, while data structures offer concrete implementations for fast operations using stacks and queues.

Explore array data structures, highlighting zero-based indexing, contiguous memory, fast random access, and one- and two-dimensional arrays, plus dynamic resizing.

Learn array operations, including appending in constant time, resizing by doubling, and shifting items; understand memory and time tradeoffs and how arbitrary insertions or removals affect complexity.

Learn arrays in C++, define size and name, index from zero, and perform fast access and updates in constant time. Compare linear search with binary search trees and removal costs.

Explore the linked list, where each node stores data and a next pointer. Understand head access, null termination, and why lists need memory beyond arrays to avoid shifting.

Explore linked list operations, including inserting at the head, appending to the end, and removing first, last, or arbitrary items, and compare constant time versus linear time complexity.

Explore the pros and cons of linked lists, highlighting dynamic memory growth and variable item sizes as advantages, and memory overhead, no random access, and unidirectional traversal as drawbacks.

Implement a generic singly linked list in C++ using header files and templates, with unique_ptr nodes, a head reference, and operations for insert at head, remove, traverse, and track size.

Compare arrays and linked lists, outlining static versus dynamic behavior, random access advantages, head and tail operations, memory usage, and why searches remain linear for both.

Explore real-world uses of linked lists, from memory management with malloc and free on the heap to doubly linked blocks, tab navigation, photo viewers, and cryptographically linked blockchains.

Explore the stack abstract data type, its last-in, first-out structure, and operations like push, pop, and peek. See how stacks support memory, recursion, and algorithms like depth-first search and Minimax.

Explore how stack memory stores local variables and method calls via stack frames during recursion, and how the heap handles dynamic allocation, objects, and fragmentation with garbage collection.

Visualize stack memory as it handles function calls by stacking frames and local variables, while heap memory stores objects reachable via stack references and garbage collection frees unused objects.

Learn to implement a generic stack in C++ using arrays, with push and pop, track size and capacity, and resize by doubling or halving to manage memory.

Learn to implement a stack using a linked list in C++, with a head pointer and unique_ptr nodes, achieving constant-time push and pop, and tracking size with a counter.

Explore the queue abstract data type, its fifo behavior, and operations like enqueue, dequeue, and peek, and see how it powers os scheduling and breadth first search.

Implement a queue using a linked list with head and tail references, supporting enqueue and dequeue in constant time, and tracking size with a counter, remaining generic via templates.