YouTube Channel

Link to the Channel: http://youtube.com/c/kushashwaraviShrimali/

Syllabus for DSA Series:

(Please see Notes section towards the end for references)

1. Why study Algorithms? Role of Algorithms in the industry and research.
2. Getting Started:
   • Insertion Sort
   • Analyzing Algorithms
   • Designing Algorithms
3. Asymptotic Analysis
4. Introduction to Basic Data Structures: (to be discussed in detail later)
   • Arrays
   • Strings
   • Stacks
   • Queues
   • Linked Lists
5. Recursion:
   • About Recursion
   • Comparison with and without recursion (performance)
   • Example: Binary Search and File Systems
   • Analysis
   • Maximum Recursive Depth (Python/C++)
   • Linear Recursion, Binary Recursion, Multiple Recursion
   • Eliminating Tail Recursion
   • C++ inlining of recursion?
   • Problems (LeetCode)
6. Divide and Conquer Technique:
   • Maximum subarray problem
   • Strassen's algorithm for matrix multiplication
   • Substitution method for solving recurrences
   • Recursion Tree method for solving recurrences
   • Proof of the master theorem
   • LeetCode questions using D and C
7. Sorting
   • Basic sorting techniques:
     • Bubble Sort
     • Insertion Sort
     • Merge Sort
   • Heap Sort
     • Heaps
     • Building a heap
     • Algorithm
     • Priority Queues
     • Usage, and questions on LeetCode
   • Quick Sort
     • About Quick Sort
     • Performance of Quick Sort
     • A randomized version of Quick Sort
     • Analysis
   • Linear Time Sorting
     • Lower bounds for sorting
     • Counting Sort
     • Radix Sort
     • Bucket Sort
   • Which sorting to use, and when?
     • Medians and other statistics
       • Minimum and maximum
       • Selection in expected linear time
       • Selection in worst-case linear time
8. Data Structures: Arrays
   • Low-Level Arrays (Referential Arrays and Compact Arrays, Python)
   • Dynamic Arrays and Amortization
     • Implementing Dynamic Array
     • Amortized Analysis of Dynamic Arrays
     • Python: List Class
     • Arrays vs STL Vectors (C++), Memory Allocation and Resizing
   • Source Code walk through:
     • Implementation of STL's vector class
   • Efficiency of Python's List, and Tuple Classes
   • Examples of using Arrays in Problem Solving
   • Use of vectors/arrays in open source libraries
9. Stacks:
   • About Stack
   • Implementations:
     • Array-based
   • Reversing Data using Stack
   • Usage in matching patterns
   • Usage in open source libraries:
     • Usage in Chromium
     • Usage in GTK Stack Switcher (GTK Library)
10. Queues:
    • About Queues
    • Implementation:
      • Array-based
    • Double-Ended Queues
      • About
      • Implementing using a ciruclar array
      • Dequeue in STL and Python
    • Questions
    • Usage in Open Source libraries
11. Common questions for stacks and queues in problem solving (dedicated time)
12. Linked Lists:
    • Singly Linked Lists
      • Implement Stack using Singly Linked List
      • Implement Queue using Singly Linked List
    • Circularly Linked Lists
      • Round Robin Schedulers
      • Implementing Queue using Circularly Linked List
    • Doubly Linked Lists
      • Basic Implementing
      • Implementing Dequeue using Doubly Linked Lists
    • Positional List Abstract Data Type (Python)
      • About
      • Doubly Linked List Implementation
    • Sorting a Positional List
    • Maintaining Access Frequencies
      • Using sorted list
    • Link-based vs Array-based sequeunces
    • Questions
    • Usage in Open Source Libraries:
      • Chromium/Any other browser
13. Implementing Pointers and Objects
14. Representing Rooted Trees
15. Hash Tables:
    • Direct-address tables
    • Hash Tables
    • Hash Functions
    • Open addressing
    • Perfect hashing
    • Questions
16. Trees
    • General Trees
      • About
      • Computing Depth and Height
    • Binary Trees
    • Implementing Trees:
      • Array-based
      • Linked Structure for Binary and General Trees
    • Tree Traversal Algorithms
      • Preorder
      • Postorder
      • Inorder
      • Breadth-First Tree Traversal
      • Implementing Tree Traversals (C++ and Python)
      • Applications Euler Tours and Template Method Pattern
    • Questions
    • Usage in Open Source Libraries:
      • Tiling Window Manager
17. Search Trees:
    • Binary Search Trees
      • About
      • Querying a BST
      • Insertion and Deletion
      • Randomly built BST
    • Balanced Search Trees
    • AVL Trees
    • Splay Trees
    • (2, 4) Trees
    • Red-Black Trees
      • Properties
      • Rotation, Insertion, Deletion
    • Questions
    • Usage in Open Source Libraries (TBD)
18. Selection
    • Prune and Search
    • Randomized Quick Select
    • Analyzing Randomized Quick Select
    • Questions
    • Usage

Syllabus for following topics will be decided soon as we start:

• Dynamic Programming
• Greedy Algorithms
• Amoritzed Analysis
• Advanced Data Structures:
  • B-Trees
  • Fibonacci Heaps
  • van Emde Boas Trees
  • Data Structures for Disjoint Sets
• Graph Algorithms
  • BFS, DFS, Topological Sort, Strongly Connected Components
  • Minimum Spanning Trees, Kruskal and Prim algorithms
  • Single Source Shortest Paths:
    • Bellman-Ford Algo
    • Single-Source Shortest Paths in Directed Acyclic Graphs
    • Dijkstra's Algorithm
    • Difference constraints and shortest paths
    • Proofs
  • All-Pairs Shortest Paths
    • Shortest Paths and Matrix Multiplication
    • The Floyd-Warshall Algorithm
    • Johnson's Algorithm for sparse graphs
  • Maximum Flow
    • Flow networks
    • The Ford-Fulkerson Method
    • Maximum bipartie matching
    • Push-Relabel Algorithms
    • Relabel to Front Algorithm

Once this is done, we'll cover:

• Multi-threaded Algorithms
  • Dynamic Multi-threading
  • Multi-Threaded Matrix Multiplication
  • Multi-Threaded Merge Sort
• Matrix Operations
• Linear Programming (more on this later)
• Sparse Matrices
• Polynomials and FFT
• Number Theoretic Algorithms (cryptos and more)
• String Matching
• Computational Geometry (Convex Hull)
• Np-Completeness
• Approximation Algorithms
• Usage of Graphs in Compilers

Notes

• The syllabus is highly motivated from one of the best resources around:
  • Introductiont o Algorithms (Third Edition) - Thomas H. Cormen et al
  • Data Structures and Algorithms in Python (Wiley publications) - Goodrich et al
• Lots of questions will be discussed as we move along, the target is to be good in problem solving.
• Every time we go, we'll discuss use of a data structure or an algorithm in an open-source project.

Do you want to collaborate?

This is going to be a huge series, and I'll appreciate if someone wants to collaborate in this. If you are curious, here is how you can collaborate:

1. Join the discord channel: https://discord.gg/AMByfmS4NC.
2. Follow the latest updates, and join us on the live streams.
3. If you have a better solution to a problem we discussed before, let us know!
4. If you want to come on the stream and talk about a topic, please share your profile with the admin team on discord, and I'll be more than happy to consider you for a guest session.
5. If you want me to show-case your project on how you used a particular data structure or algorithm, you are most welcome to reach out to us.