Skip to content

Latest commit

 

History

History
229 lines (216 loc) · 7.45 KB

README.md

File metadata and controls

229 lines (216 loc) · 7.45 KB

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.