Data Structures and Algorithms

Define data types and classify them into primitive and non-primitive forms, then present abstract data types as the logical specification of data and operations, separate from their implementation.

Explore abstract data type classification by linear versus nonlinear, homogeneous versus non-homogeneous, and static versus dynamic; learn core linear examples: arrays, linked lists, stacks, and queues.

Explore arrays as a fundamental, homogeneous data structure with sequential memory layout, index-based access, and fixed length, comparing ADT versus data structure and covering single and two-dimensional storage.

Explore array operations: traversal, searching (sequential and binary), and insertion/deletion, along with static versus dynamic arrays, their advantages and drawbacks, and applications in stacks, queues, sorting, and CPU scheduling.

Compute element addresses in two-dimensional arrays by applying row major or column major orders, using base address, element size, and array dimensions.

Explore linked lists, where each node stores data and a pointer to the next node, with a head and null pointer, enabling sequential access and operations: search, insertion, deletion, traversal.

Explore searching and traversal in linked lists, using next and previous pointers to locate elements, track positions, and support insertion and deletion in sorted lists.

Learn insertion in a linked list across four cases—empty list, beginning, end, and middle—using a search to locate positions, then delete nodes by updating links.

Explore linked list variations such as singly, doubly, and circular lists. Compare their insertion, deletion, and traversal with arrays, and examine the complexity of these operations and common applications.

Explore the stack ADT and its push and pop operations, learn how overflow and underflow are handled, and compare array and linked-list implementations in a last-in, first-out structure.

Explore how stacks store return addresses in function calls, reverse strings, backtrack, and support expression evaluation through infix, postfix, and prefix notations with precedence and associativity.

Explore the queue data structure, its FIFO behavior, and enqueue and dequeue operations. Compare linear and circular implementations, and discuss array versus linked list approaches and OS scheduling.

Explore stacks and queues, including linear, circular, and double-ended varieties, with front and rear operations and memory-efficient behavior, plus practice examples on scheduling and undo/redo.

Learn the fundamentals of algorithms: define problems with inputs and outputs, set memory and time constraints, and design well-defined, finite procedures that transform inputs into outputs.

Analyze algorithms by predicting running time and memory from input size, count primitive operations, and describe growth rates such as constant, linear, quadratic, logarithmic, and exponential.

Explore how sorting algorithms analyze input and produce ascending or descending output using insertion, bubble, and selection sort. Compare comparison and non-comparison methods, and learn about in-place and stable sorts.

Learn how insertion sort, a simple in-place and stable sorting algorithm, inserts each element into its proper position within the sorted left side, with pseudocode and an example.

Explore selection sort and bubble sort as in-place, comparison-based techniques. Learn how selection sort is not stable and how bubble sort swaps elements to move the largest to the end.

Analyze best, worst, and average-case performance of insertion sort, selection sort, and bubble sort, comparing running times and stability across sorted and reverse-sorted inputs.

The lecture demonstrates insertion sort through passes, showing the first five elements become sorted after the fourth pass, while remaining elements stay put, and discusses best, worst, and average cases.

Explore divide-and-conquer with merge sort, detailing dividing into subproblems, recursively solving and merging to produce a sorted, stable, non in-place array with O(n log n) time.

learn how quicksort uses divide and conquer, partitions with a pivot, and sorts in place by recursively handling left and right subarrays, without a merge step.

analyze sorting outputs to decide whether they arise from insertion, selection, or merge (mozart), compare to quicksort, and explain when merge (mozart) or insertion/selection is preferred.

Explore divide-and-conquer, greedy, and dynamic programming techniques in data structures and algorithms. Assess backtracking and branch-and-bound approaches, highlighting overlapping subproblems, stored results, and the tractability of exponential algorithms.