Data Structures

Topics we are covering

Algorithms

  • Understanding algorithms
  • How to write algorithms
  • Optimizing algorithms
  • Finding time complexity of an Algorithm

Introduction to Data Structure

  • Understanding Data types
  • What is Data Structure
  • Need of Data Structure
  • The Mathematical model

Lists

  • What is List and what is it’s need
  • Squentails lists (Arrays)
    • Advantages, Limitations
    • Implementing sequential lists
  • Linked Lists
    • The LinkedList structure
    • Advantages, Limitations
    • Singly Linked List
    • Doubly Linked List
    • Circular Linked List
  • Time complexity of Linked List and Sequential lists

Stacks

  • Understanding stacks
  • Stack usage
  • Implementing Stack
    • Sequential implementation
    • Linked implementation
  • Double stack and it’s implementation

Tree

  • Introduction to Tree data structure
  • Tree usage
  • Types of Trees
    • General Tree
    • Binary Tree
    • Binary Search Tree
  • Binary Search Tree (BST)
    • Understanding Binary Search Tree
    • BST usage
    • Insertion and deletion
    • Understanding BST algorithms
      • Inorder, Preorder, Postorder
      • BFS and DFS
    • Time complexity of BST algorithms
    • Implementing BST using arrays
    • Constructing BST back using the tree traversals
  • Threaded BST
    • Why Threaded BST
    • Understanding threaded BST
    • Threaded BST Algorithms
      • Insertion and deletion
      • Inorder, Preorder, Postorder
    • Time Complexity of Threaded BST
  • Height Balanced Trees (AVL Trees)
    • What is AVL Tree
    • Balance factor, right heavy and left heavy tree
    • Height balancing algorithm
    • Insertion and deletion algorithms
  • Few other types of trees
    • Strictly binary tree
    • Symmetric tree
    • Red Black Tree
  • B Tree and B+ Tree

Queues

  • What is Queue?
  • Understanding Queue usage
  • Implementing Queues
    • Sequential implementation
    • Linked implementation
  • Circular Queue
    • Usage and implementation
  • Types of Queue
    • Priority queue
    • Double ended queue

Graphs

  • Introduction to Graphs
  • Types of Graph
    • Directed Graph
    • Undirected Graph
  • Implementing Graphs
    • Sequential implementation
    • Linked implementation
  • Graph Algorithms
    • BFS
    • DFS
    • Shortest Path Algorithm
  • Minimal Spanning Tree
    • Creating minimal spanning tree from a graph using
      • Kruskal’s algorithms
      • Prim’s algorithm

Hash Tables

  • The hashing technique
  • Understanding Hash tables
  • Time complexity of operations on Hash Table
  • Collision resolution algorithms
  • Rehashing
  • Improving performance using Hash Tables

Infix, Prefix and Postfix Expression

  • Infix to prefix conversion and it’s evaluation
  • Infix to postfix conversion and it’s evaluation

Searching Algorithms

  • Linear Search
  • Binary Search
  • Indexed sequential search
  • Fibonacci Search

Sorting Algorithm

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Radix Sort
  • Merge Sort
  • Quick Sort
  • Heap Sort

Finding Time and Space Complexity of Algorithms

  • Omega notation
  • Big O notation