Data Structures and Algorithms

This course introduces students to algorithm analysis techniques, fundamental data structures, and basic algorithms. The course emphasizes algorithm analysis and correctness proofs. Students should be familiar with at least one programming language beforehand. The algorithms are presented independently of any specific programming language.

• Algorithm Analysis (2 sessions)
  • Algorithms and their time complexity: Fibonacci sequence and maximum subarray problem
  • Function growth: O, Ω, and Θ notations
• Divide and Conquer Algorithms (2 sessions)
  • Merge sort, multiplication of n-bit numbers
  • Master theorem
• Randomized Algorithms (1 session)
  • Las Vegas and Monte Carlo algorithms: approximate median problem
  • Random permutation and applications: hiring problem
• Order Statistics and Sorting (3 sessions)
  • Selection of k-th element (randomized and deterministic)
  • Comparison-based sorting: quicksort (randomized analysis)
  • Lower bounds for comparison-based sorting, non-comparison sorts: counting sort, radix sort
• Data Structures (5 sessions)
  • Lists, queues, and stacks
  • Binary search trees
  • Priority queues (min/max heaps), heapsort
  • Hashing and hash functions
• Greedy Algorithms (1 session)
  • Coin change, scheduling problems
• Dynamic Programming (2 sessions)
  • Fibonacci numbers, weighted interval scheduling
  • Coin change, longest common subsequence
• Graph Algorithms (2 sessions)
  • Graph representation and traversal
  • Shortest path algorithms: Dijkstra's algorithm

• Practical Assignments: 3 points
• Theoretical Assignments: 3 points
• Final Exam: 14 points