Data Structures & Algorithms Essentials using C++

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.

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 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 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.

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.

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.

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[].

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.

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.

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.

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 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.

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.