Data Structures
Introduction, array and vector, pointers and iterators, index, List, map, tree, graph, Data Structure & Algorithm, ADT (Abstract Data Type), Operation name, pre-condition, post-condition, time24 ADT, Class API, time24 class, dividing the source code between cpp and header files, Example: Parking garage costs, API, STL string container class.
Definition, push & pop operations, LIFO, Overflow & Underflow, class Stack definition, handling exceptions in stack, defining your own exception class, Difference between inheriting from std::exception & std::runtime_error, creating generic type independent stack using templates, Application of stack, Balancing parenthesis, tokenizer class, get_token(), Reverse polish notation (postfix notation), applications of RPN, Evaluating postfix expressions, Shunting yard algorithm - to convert infix to postfix, Recursion & Stack, factorial using recursion, Nth Fibonacci number using recursion, recursion tree, searching for a number in an unordered array using recursion, Finding binary equivalent of a decimal number using recursion, binary recursive function to search for a number in an unordered array of numbers, STL stack container adapter class.
Definition, enqueu, dequeu, FIFO, linear data structure, bounded & unbounded queues Queue using arrays, Queue_Int class, Queue using doubly linked lists, Deque (Double Ended Queue) STL Queue adaptor container class
Self-referential structure, arrays & lists, node class, List_Int class, head, tail push_back, push_front, pop_back, pop_front, print, size, begin, end, clear, insert, swap, erase Iterator_Node class, operator*, operate ->, how to overload the operator ->, operator ==, operator !=, operator ++ (prefix & postfix), 'main' driver function, Creating stack using List_Int, Arrays vs. Lists, types of lists, singly linked lists, circular singly linked list, doubly linked lists, circular doubly linked lists, sentinel or dummy nodes and its benefits, List_double_ptr_Int class for doubly linked list Creating a template class for doubly linked lists
Definition, internal node, leaf node, root, parent, child, siblings, connected-acyclic-graph subtree, empty tree, branching factor, outdegree, internal and external nodes, height of a node depth of a node, tree representation using pointers and dynamic memory allocation, Tree traversal Traversal using stack and traversal using queue, Depth-first and Breadth-first traversal Pre-order, In-order, Post-order, Level-order (queue), preorder (recursive & iterative) Inorder (recursive and iterative), Postorder (recursive & iterative), Breadth first traveral using queue Common operations on trees, common uses of tree structure, BST (Binary Search Trees), Searching in a BST Divide-conquer technique, iterative search algorithm, recursive search algorithm, inserting a node into a tree insertion using recursion and iteration, Creating a tree, how tree structure changes based on the order of insertion Drawbacks of trees, insertion complexity - worst, best and average, self-balancing trees Node deletion, inorder successor, inorder predecessor, Sorting using BST, sorting complexity Types of binary trees, full binary tree, proper binary tree, complete binary tree, perfect binary tree balanced binary tree, height-balanced binary tree, degenerate tree, tree representation using arrays Representing trees using parenthesized expressions, maintaining a pointer to the parent in each node Program to create a binary search tree, Tree_Int class (32 pages), why not 'tree' container class in STL How many different binary trees using n nodes, how many different BSTs using n nodes,
Definition of binary heap, shape & heap property, maxheap, minheap, priority-queues, Heap implementation, complete binary tree, array implementation, Left -> 2*i, Right -> left + 1, Parent -> int(i/2) Placing root at index 1 instead of at index 0 -> can be done using left shift and integer division, height of heap from number of nodes Inserting a node to a heap, up-heap operation, deletion root from heap, down-heap, max_heapify procedure Creating a heap using Floyd's algorithm, build_max_heap() procedure, complexity - O(n) - derivation Increasing/Decreasing the key value of a node, heap_increase_key() and heap_decrease_key() procedures Heap sort algorithm, complexity -> n*log(n), example, Creating heap using STL, 'algorithm' header file STL heap procedures -> make_heap, push_heap, pop_heap, sort_heap, is_heap, is_heap_until Program to create a max_heap class (15 pages)
Self-balancing search trees, complexity comparisons for average and worst cases, comparison with red-black trees Tree rotations, left and right rotations, implementing rotations with pointer update operations, balance factor of anode 4 cases for tree re-balancing: left-left, left-right, right-right, right-left cases, examples Code to create AVL tree, updating binary_tree code to AVL by addition of few functions.
Introduction, definition, Rudolf Bayer, complexity of operations, Properties 1, 2, 3, 4 & 5 for Red Black Trees, Example, Uncle node, Parent node and Grandparent node, Insertion operation -> Cases 1, 2, 3, 4(a), 4(b), 5(a), 5(b), Deletion operation -> Case 1, 2, 3, 4, 5, 6.
Definition for multiway search trees, example, searching in multiway search trees, deletion in multiway search trees, B-tree, definition, insertion into B-tree, example with m = 3, example with m = 5, deletion from B-tree (a little tricky), example with m = 3, example with m = 5, 'Etymology of B-trees unknown' - Rudolf Bayer & Ed McCreight, 2-3 trees, its properties and example, 2-3 tree creation/insertion/deletion, 2-4 tree definition, properties, creation/insertion/deletion.
Definition of a graph, hedges (nodes) & vertices, directed & undirected graphs, empty graph, trivial graph, operations on graph, cycles & loops, number of edges possible in directed graph with n nodes (with & without loops), number of edges possible in undirected graph with n nodes (with & without loops), graph representations, Adjacency matrix, Adjacency list, Incidence Matrix, Incidence list, Comparison of the various schemes, sparse graph, Neighbourhood, Degree of a vertex, indegree and outdegree, Adjacent vertex, isolated vertex, non-adjacent vertex & end vertex, Density of a graph, Paths, Walks, Cycles, Length, Distance, Diameter, Connected vertices, Connected graphs, Connected components (bunch of buttons lying on the floor), Cliques, Maximal clique, Clique number (NP-complete), Strongly connected graph, strongly connected components, weakly connected graph, Robert Endre Tarjan, Complete graph (Kn), Simple graph, Null/Empty/Edgeless graph, Planar graphs, Euler's formula for planar graphs, planarity testing, Regular graph, Cycle graph, Bipartite graph, Complete Bipartite graph (Kn,n), How to check whether a graph is bipartite or not?, Star graphs, Seven Bridges of Konigsberg problem, Eulerian path & Eulerial walk, Euler tour, Hamiltonial path, Hyper graph, Breadth First Search/Traversal (BFS) algorithm, Depth First Search/Traversal (DFS), Dot graph representation, Program to represent graph using adjacency list (22 pages),Spanning tree, Fundamental Cycle, number of vertices/edges in a spanning tree, spanning forest, number of spanning trees in a tree graph, number of spanning trees in a cycle graph, number of spanning trees in a complete graph (Cayley's graph), number of spanning trees in a Bipartite graph, Kirchoff's matrix tree theorem, degree matrix, adjacency matrix, Laplacian matrix, Minimum spanning tree (MST), Boruvka's algorithm, Prim's algorithm, Kruskal's algorithm, reverse-delete algorithm, Kruskal's algorithm, Example, Complexity: O(E log E) or O(E log V), Prim's algorithm, Example, Applications of MST
Introduction, hash function, hash table, phone book example, linear probing example, separate chaining example, Properties of hashing function - deterministic, uniformity, continuity, easy to compute, Avalanche effect in hashing function, hashing function used in cryptography and in data structures, Perfect hashing function, trivial hashing function, example: mapping country codes to country names, Hashing uniformly distributed data, h = z mod n, h = z * n / N, Middle square method, modulo division, Folding technique - fold shift and fold boundary, digit extraction technique, polynomial hash codes, A hash used in Java, key statistics in hashing techniques, load factor, comparison of time and space complexity for hashing, Clustering, primary clustering (for linear probing) and secondary clustering (quadratic probing), Collision resolution techniques, Hashing with separate chaining, also called open hashing or closed addressing, searching/inserting/deleting in a hash table with chaining, Open addressing - linear probing, quadratic probing and double hashing techniques, comparing the caching performances, Overflow area technique for collision resolution, comparison of techniques
Introduction, MAKE_SET(), UNION(), FIND_SET(), An application - Connected Components, Linked list representation of disjoint sets, complexity analysis for linked list implementation, Weighted-Union heuristic for linked list representation, Disjoint-set forest, MAKE_SET(), UNION() and FIND_SET() operations on tree representations, union by rank and path compression, pseudo-code, example, complexity, inverse Ackermann's function.
Introduction, examples of range queries, naive solutions, RMQ using Segment tree, segment tree construction (recursive procedure), sum of elements withing a given range using Segment trees, updating a value in the segment tree, time complexity, RMQ and LCA problems and how they are related, cartesian tree, finding LCA in a binary tree using RMQ, Euler tour of the tree, first occurrence array, sample code, complexity, generalization for higher dimensions.
Introduction, motivation, prefix sums, SUM() operation, ADD() operation, initializing the tree, Leetcode problem on Range query (problem number 307), sample implemenation from Wikipedia.
Last Updated: May 2019