Data Structures 

Lecture Notes:

  • Introduction to Data Structures(Pages: 90)

    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.


  • Stack Data Structure (Pages: 138)

    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.


  • Queue Data Structure

    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


  • Linked List

    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


  • Tree Data Structure

    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,


  • Heap Data Structure

    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)


  • AVL Tree Data Structure

    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.


  • Red Black Trees

    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.


  • Multiway Search Trees & B-Trees

    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.


  • Graph Data Structure

    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


  • Hashing

    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


  • Disjoint Set Data Structure

    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.


  • Segment Trees (Pages 85)

    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.



Lab Sheets:


Data Structure C++ programs:

  • AVL tree
  • Stack template
  • Matching parentheses using stack
  • Queue using arrays
  • Infix to posfix expression conversion & postfix expression evaluation
  • Singly linked list of integers with iterator
  • Doubly linked list with iterator
  • Doubly linked list template class with iterator
  • Queue using doubly linked list
  • Tree of integers
    • insert(): to insert a new node into the tree
    • inorder(), preorder(), postorder(), leverlorder(): to traverse the tree inorder, preorder, postorder & levelorder
    • search(): to search for a key in the tree
    • get_inorder_successor(): to get the inorder successor of a given node
    • get_inorder_predecessor(): to get the inorder predecessor of a given node
    • get_parent(): to get the parent of a node
    • is_left_child(), is_right_child(), is_root(), is_leaf()
    • has_two_siblings(), has_only_one_sibling()
    • delete_node(): to delete a given node from the tree
    • clear(): to clear the tree or a subtree of the tree
  • Heap of integers
  • Red Black Trees
  • Heap using STL
  • Graph data structure representation using adjacency list
    • Can create weighted or un-weighted graph
    • Can create directed or undirected graph
    • insert_edge(): to insert an edge to the graph
    • set_weight(): to set the weight of the graph
    • get_weight(): to get the weight of the graph
    • print(): to print the graph
    • print_weights(): to print the edges and the corresponding weights
    • print_to_file(): to print the graph into a file using the 'dot' graph representation language
    • edge_count(): to get the number of edges
    • find_vertex(), find_edge(): to find the vertex and the edge
    • delete_vertex(), delete_edge(): to delete the vertex and the edge
    • BFS_visit(): to do the breadth first search traversal on the graph
    • print_bfs_tree(): to print the BFS tree to a file using the 'dot' graph description language
    • print_tree_with_edges_colored(): to print a given graph with certain edges with a specific color
    • DFS_visit(): to do depth first search traversal on the graph
    • print_dfs_tree(): to print the DFS tree to a file in 'dot' graph description language
    • is_connected(): checks whether a given graph is connected
    • find_MST_using_Kruskal(): to find the minimum spanning tree using the kruskal's algorithm
  • Binary tree re-construction:
    • When inorder and preorder are given: C++ code
    • When inorder and postorder are given: C++ code

Misc:

link="#000000" vlink="#000000" alink="#000000"