index

BASICS MUST DO

• Merge sort, Quick sort - linked list and array
• Binary search (array)
• sliding window
• slow and fast pointer (linked list)
• Binary tree (inorder, preordder, post order, level order)
• Max and min heap creation from array
• Graph (BFS, DFS)
• Trie (create)
• Dynamic programming (0/1 knapsacck)
• backtracking (knights tour)

List Of DS

• Array

  • Binary search
  • 2 pointers
  • sliding window
  • Moores voting algorithm
  • Modified merge sort
  • Quick sort initial parttition
  • valley peak approach

• LinkedList

  • slow and fast pointers
  • detect cycle and where it begins
  • insertion, deletion and reversal

• Binary tree and BST

  • Inorder, preorder and post order (DFS)
  • level order (BFS)
  • left/right view and bottom/top view
  • Find height and max width
  • Is a complete Binary tree or not?
  • Longest path in a tree

• Stack and Queue

  • array and linkedlist implementation
  • FIFO and LIFO
  • stack : DFS graph, balanced or valid paranthesis, next greater element, infix to postfix conversion
  • queue : level order for BT, BFS graph, task scheduler

• Heap (Binary Heap)

  • Top K elements
  • Max and min heap
  • Priority Queue

• Graph (Dijkstra, Bellman ford, Floyd warshall, prim, kruskal, topological sort)

  • matrix and adjacency list representation
  • weighted and unweighted
  • DFS and BFS
  • directed acyclic graph and shortest path
  • keeping a visisted array
  • topological sort

• Matrix

• Advanced Data Structure

  • Segment Tree
  • Trie
  • AVL Tree
  • Splay Tree
  • Red-Black Tree
  • K Dimensional Tree
  • Self-Balancing BSTs
  • Binary indexed tree / Fenwick tree

link : https://www.geeksforgeeks.org/data-structures/#Misc

---

List of Algorithms

• Analysis of algorithms

• Searching and Sorting

  • Binary search
  • linear search
  • quick sort (TC : worst case - n2, avg case : nlogn; SC is O(1) )
  • merge sort (TC : all case - nlogn; SC for array: O(n) and for linked list : O(logn))
  • insertion, selection and bubble sort

• Dynamic Programming

  • Memoization and Bottom up approach
  • Overlapping subproblems
  • keeping a cache for already computed result
  • Using recursion and then optimizing
  • 0/1 knapsack problem

• Backtracking

  • The Knight’s tour problem
  • Recursion and actually it is a brute force
  • Keep a visited array
  • Permutations of given String

• Greedy Algorithms

  • Kruskal’s Minimum Spanning Tree (MST)
  • Prim’s Minimum Spanning Tree
  • Dijkstra’s Shortest Path
  • Huffman Coding

• Divide and Conquer

• Bit Algorithms

  • Taking xor
  • Binary indexed tree

link : https://www.geeksforgeeks.org/fundamentals-of-algorithms/

==============================================================================

SYLLABUS

List Of DS

• Array -
• LinkedList
• Binary tree
• Binary Search tree
• Stack
• Queue
• Heap (Binary Heap)
• Graph (Dijkstra, Bellman ford, Floyd warshall, prim, kruskal, topological sort)
• Matrix
• Advanced Data Structure(Segment Tree, Trie, AVL Tree, Splay Tree, Red-Black Tree, K Dimensional Tree, Self-Balancing BSTs)

link : https://www.geeksforgeeks.org/data-structures/#Misc

---

List of Algorithms

• Analysis of algorithms
• Searching and Sorting
• Dynamic Programming
• Backtracking (The Knight’s tour problem, Rat in a Maze, Sudoku, Hamiltonian cycle, Print all permutations of a given string)
• Greedy Algorithms ( Kruskal’s Minimum Spanning Tree (MST), Prim’s Minimum Spanning Tree, Dijkstra’s Shortest Path, Huffman Coding )
• Divide and Conquer
• Bit Algorithms
• Graph Algorithms

link : https://www.geeksforgeeks.org/fundamentals-of-algorithms/