teaching

I teach Data Structures, Design and Analysis of Algorithms, and Machine Learning to BTech undergraduate students.

Course: Design and Analysis of Algorithms

This course covers fundamental techniques for designing efficient algorithms and analyzing their complexity. Topics include:

  • Asymptotic Analysis and Big-O Notation
    • Growth of functions: polynomial, exponential, logarithmic, linear, and constant time complexities
    • Formal definitions of Big-O, Big-Theta, and Big-Omega notations
    • Best-case, average-case, and worst-case analysis - Priori and posteriori analysis of algorithms - Common complexity classes: P, NP, NP-Complete, NP-Hard - Comparing algorithms using asymptotic notation - Practical implications of asymptotic analysis
  • Brute Force Approach
    • Introduction to brute force algorithms
    • Time and space complexity considerations
    • Applications and limitations
    • Examples:
      • Linear search
      • String pattern matching (Naive algorithm)
      • 0/1 Knapsack Problem ($O(2^n)$ time complexity)
      • Travelling Salesman Problem ($O(n!)$ time complexity)
      • Assignment Problem ($O(n!)$ time complexity)
  • String Pattern Matching Algorithms
    • Naive pattern matching
    • Knuth-Morris-Pratt (KMP) algorithm
    • Rabin-Karp algorithm
    • Applications in text processing and bioinformatics
  • Divide and Conquer Strategies
    • Recurrence relations
      • Substitution method
      • Recursive tree method
      • Master Theorem
    • Classic algorithms: Merge Sort, Quick Sort, Binary Search, Strassen’s Algorithm
  • Graph Algorithms
    • Graph representations (adjacency list/matrix)
    • Breadth-First Search (BFS) and Depth-First Search (DFS)
    • Shortest paths (Dijkstra’s and Bellman-Ford algorithms)
    • Minimum Spanning Trees (Prim’s and Kruskal’s algorithms)
    • Topological sorting
  • Greedy Algorithms
    • Greedy-choice property and optimal substructure
    • Examples: Activity Selection, Huffman Coding, Minimum Spanning Trees (Kruskal’s and Prim’s algorithms)
  • Dynamic Programming
    • Overlapping subproblems and optimal substructure
    • Memoization and tabulation
    • Examples: Longest Common Subsequence, Matrix Chain Multiplication, Knapsack Problem
  • Backtracking
    • Systematic search and pruning
    • State space tree
    • Examples: N-Queens Problem, Subset Sum, Graph Coloring
  • Branch and Bound
    • Bounding functions and pruning
    • Difference from backtracking
    • Examples: Traveling Salesman Problem, 0/1 Knapsack Problem
  • NP-Completeness
    • P, NP, NP-Complete, and NP-Hard classes
    • Polynomial-time reductions
    • Examples: SAT, Vertex Cover, Clique, Subset Sum
  • Additional Topics (as time permits)
    • Network flows (Ford-Fulkerson algorithm)
    • Approximation algorithms
    • Randomized algorithms

Target Audience: BTech undergraduate students
Prerequisites: Data Structures

Materials and resources will be provided during lectures and on the course portal.

Course: Data Structures

This course introduces fundamental data structures and their applications in computer science. Topics include:

  • Introduction to Data Structures
    • Abstract Data Types (ADTs)
    • Classification: Linear vs Non-linear, Static vs Dynamic
  • Arrays and Strings
    • Representation and operations
    • Multidimensional arrays
    • String manipulation and pattern matching basics
  • Linked Lists
    • Singly, doubly, and circular linked lists
    • Operations: insertion, deletion, traversal, searching
    • Applications
  • Stacks and Queues
    • Stack operations and applications (expression evaluation, recursion)
    • Queue types: simple, circular, priority, and double-ended queues (deque)
    • Applications in scheduling and buffering
  • Trees
    • Binary trees, binary search trees (BST)
    • Tree traversals: inorder, preorder, postorder
    • AVL trees, B-trees
    • Applications: expression trees, Huffman coding
  • Heaps
    • Definition and properties of heaps
    • Types: min-heap and max-heap
    • Heap operations: insertion, deletion, heapify
    • Applications: priority queues, heap sort
  • Graphs
    • Representation: adjacency matrix and list
    • Traversal: BFS and DFS
    • Applications: shortest path, connectivity
  • Hashing
    • Hash functions and collision resolution techniques
    • Applications: dictionaries, symbol tables
  • Sorting and Searching Algorithms
    • Linear and binary search
    • Sorting: bubble, selection, insertion, merge, quick, and heap sort
    • Time and space complexity analysis

Target Audience: BTech undergraduate students
Prerequisites: Basic programming knowledge (C/C++/Java)

Course materials, assignments, and additional resources will be shared during lectures and via the course portal.