Data Structures and Algorithms :Deep Dive into DSA using C++

Explore what recursion is by tracing function calls, activation records, and the stack, and learn how the base condition stops infinite recursion and enables recurrence relations.

Learn to add two numbers with recursion by reducing the second number until one is zero, returning the other, and explaining the base case, activation records, and recurrence relation.

Explains the power function a^b, shows a naive recursive approach with base case b=0 and linear time, then derives exponentiation by squaring for logarithmic time.

Explore a simple recursive power function in C++ that computes a^b with base case zero and result one, then contrast its optimized divide-by-two approach using even-odd checks.

Explore implementing the fibonacci series in C++ using recursion, with base cases for 0 and 1, and the recurrence fib(n) = fib(n-1) + fib(n-2), demonstrated from main with user input.

Explore how recursion computes the greatest common divisor of two numbers using the difference method, with examples like 8 and 12, and compare it with the modulo approach.

explores coding the gcd (hcf) of two integers using recursion, first by the subtraction method and then by a modulo-based euclidean algorithm for efficiency.

Calculate the factorial of a number using recursion, with base cases at one and zero, by multiplying n with factorial of n-1 and tracing activation records on the stack.

Explore how static and dynamic memory relate to the main memory layout in C/C++, including the code segment, initialized data, stack, heap, and dynamic allocation via the new operator.

Explore two-dimensional arrays as matrices with rows and columns, learn indexing like [row][column], and review a 3x5 example to illustrate element storage.

Learn how 2d arrays map to memory using row-major and column-major orders, with base address calculations and index bases from zero, one, or lower bounds.

Explore memory representation of n-dimensional arrays and derive the address from indices i1 through in using the base address alpha and the dimension sizes, via a summation of products formula.

Explore the array adt by describing its specifications, data members, and member functions—create, insert, delete, find, search, isEmpty, isFull, length, and display—while contrasting capacity with size and rotations.

Explore building an array abstract data type by implementing create and dynamic memory allocation with new, and a generic template array that supports insert, delete, and size and capacity tracking.

This lecture shows how to add an element to an array by validating the position, converting it to an index, shifting elements, and inserting at the correct index.

Implement a template-based insert function for a dynamic array in C++, validate positions, shift elements right, and update size, with exception handling and a display routine.

Implement the find function for arrays by validating the position and copying the element into the reference parameter. Return true for a position; discuss exception versus false for invalid position.

Code a template-based linear search for arrays, returning the found position or minus one if not found. Integrate the search with the class's constructor and other member functions in C++.

Implement and validate isEmpty() and isFull() for a templated array ADT, tracking size against capacity to determine emptiness and fullness while supporting insert, delete, and search.

Explore how length() tracks the current number of elements in an array and how display() prints elements from first to last or in reverse using a for loop.

Learn how to shift or rotate array elements left and right, by one or multiple positions, using loops to move each element and manage vacant spots.

Rotate array elements by one position left or right using a temporary variable and a shifting loop, then repeat for multiple rotations via a function call.

Learn to reverse an array using two methods: an auxiliary array for copy-back, and in-place swapping with two indices, comparing O(n) time and space costs.

Learn two methods to reverse array data in c++: use an auxiliary array with a temporary buffer, then perform an in-place swap with a temp variable.

Explain how linear search scans an array from the first element, comparing each item to a key until a match or end, and discuss time complexity and move-to-front optimization.

Demonstrate implementing a linear search in C++ using a template class with a dynamically allocated array, detailing the search loop, found or not found logic, and a move-to-front optimization.

Explain how binary search works on sorted arrays by using low, high, and mid to halve the search space, with iterative and recursive implementations and divide-and-conquer insights on time complexity.

Explore iterative binary search using a loop in C++, detailing parameters, mid calculation, and updates of low and high; determine success or failure and analyze complexities.

Demonstrates an iterative binary search in C++ using a template class with dynamic memory and ascending-ordered data, detailing low and high indices and searching for the key.

Discover binary search through divide and conquer, comparing iterative and recursive approaches, and learn how small problems split into subproblems, solve them, and combine results to find the key element.

Apply a two-pointer strategy from both ends to merge the smaller side’s adjacent element, counting the minimum merge operations needed to transform a given array into a palindrome.

Learn to compute the minimum merge operations needed to convert an array into a palindrome by repeatedly merging adjacent elements into their sum, demonstrated with a two-pointer approach.

Print all subarrays with zero sum by starting at each index and maintaining a running sum, using a brute force approach and printing when the total is zero.

Tackle a coding challenge to find the smallest missing positive number from an unsorted array using quick sort to partition negatives and positives around a pirate element, achieving linear-time performance.

Compare arrays and linked lists, focusing on dynamic versus static memory allocation, insertion and deletion costs, traversal-based access, and the memory layouts of stack and heap.

Understand linked lists in C++, including dynamic memory allocation, node structures with data and next pointers, and using templates to build generic linked lists.

Explore the design of a generic class ADT for a singly linked list in C++, with a node class, template data type, and operations insert, delete, find, search, and display.

Learn how to delete an element from a singly linked list using a delete function, handling first, last, and middle positions with reference parameters and proper memory release.

Implement a template-based delete operation for singly linked lists, handling first, last, and middle positions. Update length and remove the node using two pointers and data copying.

Explore the find() operation for a singly linked list in C++, validating the position and using a reference parameter for the element, then returning true or false.

Implement the search function on a singly linked list using linear search to return the key’s position or minus one if not found.

Implement a linear search in a singly linked list by traversing from the head with a pointer, comparing nodes to a target, returning the position or -1 if not found.

Learn the isEmpty() implementation for a singly linked list, returning true when no nodes exist and false otherwise, with notes on dynamic memory and the lend function for length.

Implement all member functions of a singly linked list by creating an object, inserting nodes at various positions, displaying, deleting by position, and using find, search, and length checks.

Explain how to concatenate two linked lists in c++ by attaching the second list to the end of the first, using f and s pointers, and display the merged list.

Merge two sorted linked lists in C++ by either creating a new merged list or rearranging existing links. Explore memory allocation, node pointers, and linear time complexity O(m+n).

Demonstrates merging two sorted linked lists by rearranging pointers, not creating a new list, using two guiding pointers and data comparisons to splice nodes into a single list.

Copy the linked list data into an auxiliary array and reverse the sequence. Rebuild the linked list from the array's end to start, and analyze the resulting linear time complexity.

Implement insert in a circular linked list using two parameters: position and data, covering memory allocation, and first, last, and middle insertions with pointer updates.

Present a C++ implementation of inserting elements into a circular linked list, covering constructor initialization, dynamic node creation, and insertions at first, middle, or last positions with proper pointer updates.

Demonstrate displaying the data elements of a circular linked list from the first node, using pointers and loop termination when returning to the first node, illustrating three display approaches.

Learn how to implement a destructor for a circular linked list, safely deleting dynamically allocated nodes from first to last while updating pointers.

Explore the doubly linked list, with left and right pointers for previous and next nodes, enabling bidirectional traversal and flexible structure creation using struct or template class in C++.

Explore the template-based abstract data type for a doubly linked list, detailing its declared data members, public interface, and outside-class implementations of operations like insert, find, display, and length.

Insert elements into a doubly linked list in c++. Update three pointers for first and last insertions, and four pointers for middle insertions.

Implement insert for a doubly linked list by allocating a new node, initializing data and pointers, and inserting at first, last, or middle positions while updating length.

Learn polynomial addition by merging two polynomials using a linked list of terms. Compare exponents, sum coefficients on matches, and copy terms; implemented in C++ with coefficient, exponent, and next.

Detect a cycle in a linked list using Floyd's cycle detection with slow and fast pointers, comparing addresses as they traverse until they meet.

Detect a cycle in a linked list using Floyd's cycle detection with slow and fast pointers, then remove the cycle by setting the loop's tail node next to null.

Identify the intersection point of two linked lists by comparing node counts and aligning list lengths, then advance both pointers until they meet or reach null.

Demonstrate pairwise swapping of adjacent nodes in a linked list by rearranging pointers, not data, using a node class, insert, display, and a pointer-to-pointer head.

Swap adjacent nodes in a linked list by updating links, not data. Use two pointers to traverse and pair nodes for swap, handling head and end cases.

Explore the stack data structure, its last-in, first-out behavior, top-oriented push and pop operations, the stack adt, and representations with arrays and linked lists, including infix/postfix conversion and evaluation.

Explore the stack abstract data type, its top and size members, and operations such as push, pop, peek, search, and display, with array or LINDA representations.

Learn the array representation of a stack in memory using a generic template array, with top, length, and dynamic memory management. Implement push, pop, search, isEmpty, isFull, and display operations.

Demonstrates implementing a stack using an array representation, with push and pop operations, top index, and handling overflow and underflow, including dynamic memory allocation in the constructor.

Implement stack operations in c++ by coding push and pop with overflow and underflow checks, using templates and scope resolution; provide find and search functionalities.

Learn to implement an array-based stack in c++ with a template class, including push, pop, display, search, find, and is empty/full operations, plus constructor and destructor memory management.

Implement two stacks in a single array with two top indices and separate push, pop, and display operations. Use a constructor with a size to allocate memory and initialize tops.

the lecture demonstrates implementing a linked stack adt in c++ using templates, defining a node, a top pointer, and length, and implementing push, pop, find, search, empty, and display.

Implement a stack using a linked list in C++ through a template-based node and stack classes, supporting push, pop, display, search, and destructor for element management.

Explore the diverse uses of stacks in data structures and algorithms, from postfix conversion and evaluation to recursion, function calls, maze solving, backtracking, browser history, and redo operations.

Learn how infix expressions are converted to postfix using operator precedence and parentheses, with stack-based evaluation and concrete examples like a+b*c and e+b*c to produce postfix forms.

Learn to convert an infix expression to postfix using a stack, with operator precedence handling for +, -, *, /, and a sentinel hash, culminating in the postfix output.

Convert infix expressions to postfix using a character stack and operator precedence. Demonstrates pushing and popping to produce postfix without parentheses, shows input and resulting postfix output.

Convert an infix expression with parentheses to postfix using a stack, applying incoming and in-stack priorities to correctly output the postfix sequence.

Implement infix to postfix conversion with parentheses using a stack in c++. Apply incoming and in-stack priority rules to manage operators and generate the postfix output.

Evaluate postfix expressions using a stack by pushing operands, applying operators, and pushing results back. Trace a left-to-right scan on the example 3 2 5 * + to produce 13.

Learn postfix evaluation with a stack. Read a postfix expression, convert digit chars using ASCII values, push digits, and apply operators by popping two operands and pushing results.

Explore postfix evaluation through a stack-based c++ implementation, using push and pop, handling digits and operators, and retrieving the final result from the stack top.

Explore how a stack checks if a parentheses expression is fully matched by pushing left parentheses and popping on right parentheses.

Demonstrate reversing a string using a stack by pushing each character, popping into a reverse array via a reverse function, and printing the result, with push, pop, and isEmpty methods.

Implement a stack that returns the minimum element in constant time using two stacks, including push, pop, and get min operations with an auxiliary stack to track the minimum.

Build a single-stack solution that returns the minimum element in constant time without an extra stack. Use encoded values during push and pop to maintain the current minimum.

Explore the queue data structure with real-time examples, define insertion at the end and deletion from the front, and contrast its first-in, first-out behavior with a stack.

Explore queue adt as a template class in C++ using an array representation with front and rear indices and insert, delete, find, search, is empty, is full, length, and display.

Implement remaining queue member functions in C++, including find and search for element retrieval and index or -1 return, plus is_empty, is_full, lend, and display from first to last.

Learn to implement enQueue in a circular queue by managing front and rear, checking for full conditions, and wrapping indices, with an optimized next index approach.

Explore deleting from a circular queue by advancing the front pointer, handling the empty case when front equals rear, and displaying remaining elements from front+1 to rear.

Explore a template-based circular queue ADT in C++. Implement constructor, destructor, enqueue and dequeue operations, and methods to check empty or full, display elements, and access front and rear elements.

The lecture explains the linked representation of a queue using a linked list in c++, detailing front and rear pointers, node structure, and enqueue and dequeue operations.

Explore implementing a queue with a linked representation, including traversing to a given position, validating input, retrieving elements, performing a linear search, and managing front, rear, display, and destructor operations.

Implement a queue using a singly linked list in C++, with front and rear pointers. Enqueue, dequeue, and display update size and show elements from front to rear.

Delete front and delete rear operations in a dequeue, with empty checks, pointer updates, single-element handling, and size adjustment.

Learn to implement a queue using two stacks, pushing elements into the first stack, transferring to the second stack, and popping to realize first-in, first-out order.

Implement a queue with a single stack using recursion to dequeue elements. Enforce first in, first out by pushing data and popping from the stack.

Understand the basic tree terminology, including root, nodes and edges, leaf and internal nodes, parent, child, ancestor, descendant, siblings, degree, level, height, depth, and forest.

Explore array representation of binary trees, sizing memory by height and storing nodes level by level, from left to right, for use in heaps and heap sort.

Learn the linked representation of binary trees in C++ using a template node with left and right pointers, compare with structures, and note memory efficiency and traversal applications.

Explore various binary tree types, including left-skewed and right-skewed trees, full and complete binary trees, proper (strict) trees, and balanced trees, with their defining properties.

Compare full, complete, and almost complete binary trees: a full tree has zero or two children at each node. How complete and almost complete trees differ in density and storage.

Discover how to find the height of a binary tree with a recursive algorithm, compare left and right subtrees, and clarify the relationship between height and depth.

Discover how to count nodes in a binary tree using recursive functions, combining left and right counts with one for the current node, and learn an alternative direct-call approach.

Construct an expression tree from an infix expression by converting to postfix and using a stack to connect operands as leaves and operators as internal nodes in a binary tree.

Explore the distinction between internal and external nodes in regular and proper binary trees, and learn that external nodes equal internal nodes plus one, or internal equals external minus one.

Explore in-order traversal of a binary tree, printing nodes in left-root-right order via recursion and an iterative stack-based approach, with step-by-step examples.

Master pre-order traversal on binary trees by visiting the root, then the left subtree, then the right subtree, using both recursive and iterative (stack-based) approaches.

Demonstrates iterative pre-order traversal of a binary tree using a stack to store node addresses, visiting root, then left, then right, with push and pop operations.

Explore constructing a binary tree from traversal sequences; a single traversal cannot yield a unique tree, but combining in-order with pre-order or post-order yields a unique binary tree.

Explore a template based binary tree in c++ with a node class and binary tree adt, implementing recursive and iterative traversals (in-order, pre-order, post-order) and height function.

Explore the binary tree's children-sum property by verifying each node's value equals the sum of its left and right children, with missing children treated as zero.

Shows a C++ solution that builds a binary tree and recursively verifies the children sum property, ensuring each node equals the sum of its left and right children.

This lecture presents a class-based C++ solution for evaluating a binary expression tree by constructing nodes, identifying leaves, and recursively applying +, -, *, / to left and right operands.

Explore the dictionary data structure, an abstract type with insert, delete, and search, illustrated by a library database, and compare binary search trees with hashing for efficient lookups.

Learn search operations in a binary search tree, using key comparisons to navigate left or right subtrees and return the matching node.

Insert a key into a binary search tree by performing a search first to avoid duplicates, then allocate memory and attach the new node to the left or right.

Illustrates how to perform an ll rotation on an AVL tree after inserting nodes, using balance factors to rotate three nodes and restore balance to a binary search tree.

Demonstrate implementing an avl tree rotation in c++, computing node height and balance factor, performing insertions, and applying an ll rotation to restore balance.

Explore the rr rotation on an AVL tree, performing a single right-right rotation after a right-right insertion to restore balance, using three nodes and balance factors.

Explore the implementation of the RR rotation in an AVL-like structure, updating pointers, heights, and balance factors while validating with in-order traversal and root updates.

The lecture demonstrates constructing an AVL tree by inserting elements and adjusting with single and double rotations (ll, lr, rl, rr) to keep balance factors within -1 to 1.

Evaluate a boolean function that determines whether a binary tree is skewed BST from its pre-order traversal, using a running minimum and maximum range across the sequence.