Data Structures & Algorithms Essentials using C++

Learn to implement a simple c++ array for input and output with cin and cout, including reading marks for n students, updating values, and initialization considerations to avoid garbage.

Explore pass by reference for arrays in C++, showing how functions receive the array address, not a copy, and how to use n to track elements.

Implement linear search to locate a key in an array, returning its index or -1 if absent. Recognize it as a brute force technique with O(n) time.

learn to reverse an array in place by swapping symmetric elements from the ends toward the middle, achieving order of n time and order of one space.

Print subarrays by i, j, and k loops to output elements from i to j. Subarrays are consecutive, about n^2, with O(n^3) time; homework: print sums and largest sum.

The lecture uses a brute force approach to find the largest subarray sum by checking all subarrays with three loops, updating the current and largest sums, and revealing O(n^3) time.

Use prefix sums to optimize the largest subarray sum problem, building a prefix sum array and computing subarray sums in constant time to reduce time from O(n^3) to O(n^2).

Learn Kadane's algorithm to solve the maximum subarray sum problem by maintaining a running current sum and a maximum sum, discarding negative sums.

Explore vectors as dynamic, continuous memory 1D/2D arrays from the standard template library that grow automatically by doubling, with copies on reallocation, and learn passing by value or by reference.

Explore the solution for finding the largest element in a vector and compare it to arrays, highlighting vectors as a practical learning point in C++.

Using a sorted array, move two pointers from the ends to find the pair whose sum is closest to x, updating the best pair as you go.

Explore solving k rotate clockwise by using k mod n, then build a new vector with the last k elements followed by the first n−k elements, noting a second approach.

Rotate an array in place by three reversals: reverse the first n-k elements, reverse the last k elements, and reverse the entire array, achieving in-place k-rotation without extra space.

Explore how sorting algorithms organize everyday items, from fruits to books, and begin with bubble, selection, and insertion sort, while previewing counting, merge, quick, and heap sort.

bubble sort moves the largest element to the end by repeatedly swapping adjacent elements in an unsorted array, using two nested loops that compare a[j] and a[j+1].

Explore insertion sort, a simple sorting algorithm inspired by card games, and learn how to insert each element into its proper position by shifting larger items.

Implement insertion sort in C++, inserting the current element into its correct position in the array by shifting larger elements, iterating from index one to n minus one.

Explore C++'s inbuilt sort algorithm from the algorithm header, its N log N performance, and how to use comparators or built-in options like reverse and greater to control order.

Learn counting sort, a linear-time sorting technique using a frequency count array to sort data within a known range, illustrated with exam marks 0 to 100 and frequency-based placement.

Explore how cin.get reads input character by character, including spaces and newlines, fills a character array, and uses a stop condition such as a hash or newline to determine length.

Count alphabets, digits, and spaces in an input sentence with C++ by reading one character at a time using cin.get until newline and updating counters.

Discover how cin.getline reads an entire line into a sentence array, replaces the newline with a terminator, and compares with cin.get for large inputs or paragraphs.

Parse a directional string on a 2-D grid to compute the final displacement in x and y, then convert it to the shortest route using north, south, east, and west.

Explore c style strings in c++, learn to measure length with strlen (null terminated), copy with the string copy function, compare with the string compare function, and concatenate with strcat.

The lecture shows how to find the largest string by scanning N inputs with two variables: the current string and the largest so far, comparing by length and updating accordingly.

Implement run length encoding to compress a string by counting consecutive characters and emitting character plus count; select the shorter between encoded and original, in linear time using C++ strings.

Explore how multidimensional arrays extend 1-D arrays to 2-D, 3-D and beyond, with real-life examples like student marks, image pixels, and video data used in machine learning.

Learn how to define and initialize a 2-D character array in C++, store each row as a string, and print specific rows or iterate through all rows using cout.

Implement staircase search to locate a key in a matrix, returning a pair of row and column indices or -1,-1 when not found, starting from the top-right.

Analyze a 2d matrix sorted by rows and columns to search for a target element. Follow staircase search that achieves linear time by moving left or down from a corner.

Discover how the address of operator yields a variable's memory address, and how dereference and reference variables relate to pointers in c++, with hexadecimal printing via cout.

Learn how a pointer stores the address of another variable and how to use the address-of operator to assign it. Explore int pointers, pointer to a pointer, and dereference concepts.

Explore how reference variables in C++ create aliases for the same object, enabling pass-by-reference and showing that x and y share memory and must be initialized.

Learn how to implement pass by reference in c++ using pointers and the dereference and address-of operators to increment a video’s view count in place, with a void return.

Master dynamic memory allocation in C++. Distinguish stack and heap memory, allocate at runtime with new, and free with delete while preventing memory leaks.

Vectors grow by doubling capacity when full, copying elements to a new memory block and freeing the old one; pushback has amortized constant time with occasional linear reallocations.

The lecture shows how a 2d vector, a vector of vectors, replaces a 2d array. It uses index-based and for-each loops to print elements and update a specific element.

Implement a vector class in c++ with pushback, popback, and front/back access, backed by a dynamic array that doubles capacity when full, plus size, capacity, and operator[].

Explore how vector push back adapts. Full vectors reallocate with doubled capacity, copy elements, and delete old array; non-full inserts at the next index and updates current size.

Convert your data structure into a reusable header file, import it in multiple programs, and keep the code generic by using templates to support any data type.

Use the inbuilt find function from the algorithm header to search arrays or vectors, returning an iterator; derive index by subtracting begin and compare to end to detect not found.

Sort a complex student data structure—name paired with a vector of marks—using a custom comparator to rank by total marks with the C++ sort function.

Explore bitwise operators in C++ to manipulate data at the binary level, including and, or, xor, not, and left/right shifts. Understand how two's complement enables negation and representation.

Explore binary left shift and right shift in C++. Left shift multiplies by two to the power, while right shift divides by two to the power, with simple examples.

learn how to get the ith bit of a number using bitwise operations in c++, by creating a mask with 1 left shifted by i and AND-ing with the number.

Shows clearing ith bit with a mask that has zero at that position and ones elsewhere, then and-ing the number to preserve bits, as 13 becomes 9 when clearing bit.

Update the ith bit of a number by clearing it, building a mask for the desired value, and applying bitwise operations to set it to 0 or 1.

Learn to clear bits in a range i to j by constructing a mask with ones outside the range and zeros inside, then apply it to the number.

Learn to replace bits in a 32-bit number by clearing the bit range from J to I, creating a mask from M, and OR-ing the shifted M into N.

Determine whether a number is a power of two by using a bitwise and of n and n minus one, which yields zero when n is a power of two.

Demonstrates a hack to count set bits by using n and n minus one, removing the last set bit each iteration, so total iterations equal the number of set bits.

Convert a decimal number to binary using bitwise operators by extracting the last bit, updating the answer with powers of ten, and right-shifting the input.

Explore recursion through the fibonacci series by implementing a two-call recursive function for F(n-1) and F(n-2), examining base cases, call stack, and exponential time with linear space.

Implement a recursive function to find the first occurrence of a key in an array using a linear search, returning the correct index or minus one if not found.

Learn to find the first occurrence of a key with a recursive approach that reduces the problem size, checks the zeroth index, and returns the index or minus one.

Learn to find the last occurrence of a key in an array using a recursive approach that checks the subproblem first and returns the index or -1.

Demonstrate a recursive last occurrence solution in an array, with a base case returning -1 when absent, and a subindex that computes the final index, comparing to the first occurrence.

Explore how to compute a raise to the power n using a recursive approach with base case n equals zero returning one, and note its linear time and space complexity.

Explore exponentiation by squaring to optimize the power function, reducing time and space complexity to logarithmic by solving a recurrence that halves n and handles odd and even powers.

Explore converting bubble sort from iterative loops to recursive implementations in C++. Learn outer- and inner-loop recursion with base cases and practical notes.

present a recursive method that prints the word for each digit of a number, using n mod 10 and n/10 with a base case when the number reaches zero.

Explore solving a board filling problem with 4-unit tiles by deriving a recurrence, comparing vertical and horizontal placements, identifying base cases, and recognizing overlapping subproblems for dynamic programming.

determine the number of binary strings of length n with no consecutive ones using f(n)=f(n-1)+f(n-2), with recursion, dp, and matrix exponentiation techniques.

Explore the friends pairing problem with recursion, deriving f(n)=f(n-1)+(n-1)f(n-2) and base cases, then apply memoization to reach linear time via dynamic programming.