Data Structures & Algorithms Blueprint - Part 1 (of 2)

Explore asymptotic notations such as big-O notation, big Omega notation, and small omega notation to compare running time and space efficiency of algorithms by examining two functions with standard operators.

Explore the formal definition of big O notation with a simple example. Determine when f(n) is O(g(n)) by a positive constant c and large input sizes.

Explore how to measure algorithm running time and time complexity, comparing iterative and recursive approaches, and using constant-time operations and Big O, Theta, and Omega notations.

explain how doubling or halving a variable affects running time, showing the loop runs in theta(log n) with base two, and discuss log base changes, big o and big omega.

Analyze the time complexity of nested loops where the inner loop depends on the outer index, deriving a total running time of n^2 log n.

This lecture explains how to compare function growth rates using asymptotic analysis, ignoring constants, and determine dominance with examples like log n, log log n, and power functions.

Examine how to compute factorials with iterative loops or recursive function calls. Understand base conditions, memory allocation for local variables, and how time complexity differs between iteration and recursion.

Explore how function calls create activation records on the stack, and how recursion levels determine memory usage, minimum activation records, and space complexity during execution.

The lecture expands the recurrence T(n)=2T(n-1)+C to reveal a geometric progression and proves T(n)=O(2^n), also noting dynamic programming can reduce this exponential time.

Explore time complexity for recursive functions by formulating a recurrence, distinguishing decreasing and dividing models, using the base case and back substitution, and noting master theorem and divide-and-conquer ideas.

Discover deriving time complexity from a recurrence using back substitution, showing how the dominant term becomes n log n (base two).

Apply the master theorem to recurrences, identify case three by comparing a, b^k, and p, and illustrate a non-applicable case where parameters are not constants.

Learn how to assess space complexity for iterative algorithms by examining memory use. A simple loop typically uses constant space, while two-dimensional arrays allocate n^2 space.

Explore the space complexity of recursive functions by tracing recursion trees and activation records. Learn how memory usage scales as activation records grow with n, with constant record size.

Explore how to compute space complexity of a recursive function by counting activation records on the stack, using a recursion tree, and noting no extra data structures.

Explore arrays, one of the two basic data structures, and how contiguous memory with zero-based indexing enables random access and easy comparison with linked lists.

Compare zero-based and one-based array indexing to understand how element positions affect address calculations. Apply formulas for one- and two-dimensional arrays using starting addresses and element sizes to locate elements.

Solve a row-major order address calculation for a 10 by 15 array with one-based indices, first element at 100, 1-byte integers; derive a[i][j] as 15i + j + 84.

Understand how associativity resolves evaluation order when operators share precedence, with left-to-right rules for most operators and right-to-left rules for unary operations.

Explore parameter passing by value and by reference, showing how copying values differs from updating memory through addresses and pointers, including a swap demonstration.

Demonstrate how pointers and arrays share access patterns, using address-of and dereference amid precedence rules; compare arrays, which are not variables, with pointer variables and valid assignments between them.

Explore valid pointer operations, including assigning same-type pointers, subtracting and adding integers for pointer arithmetic, and comparing pointers within an array, while noting null pointers and limits on invalid actions.

Explore pointer arithmetic and the difference between the address of the first element and the address of the entire array, using arrays of five integers and pointer types.

Explore passing 1d and 2d arrays to functions by reference, using pointers and array names as addresses, and contrast call by value with call by reference.

Explore a program that uses a pointer to an integer array, prints values, and demonstrates post and pre increment, as well as pointer arithmetic and final address.