Data Structures and Algorithms

• Instructors : Chandan Saha, Sathish Govindarajan   Course number and Credits : UMC 201 and 3:1,   Lecture time : T,Th 10:00-11:20 am,   Venue : G-21 (old physics building).


• TAs: : Agrim Dewan, Sreesankar T M, Himanshu Gupta, Jaydip Mokariya, Shivansh Wattal, Surojit Panja


• Syllabus :
  • Order notations
  • Sorting algorithms: Insertion sort, Merge sort, Heapsort, Quicksort
  • Sorting lower bound; Sorting in linear time: Counting sort, Radix sort, Bucket sort
  • Medians and Order Statistics
  • Elementary data structures: Arrays, Matrices, Stacks, Queues, Linked lists, Trees
  • Hash tables: Universal hashing, Pairwise independent hash functions
  • Binary search trees; Red-Black trees
  • Dynamic Programming
  • Greedy Algorithms
  • Amortized analysis
  • Elementary graph algorithms: DFS, BFS, Topological sort
  • Minimum spanning trees
  • Finding shortest paths
  • NP-hardness (if time permits)


• References :
  1. Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein
  (We'll closely follow this book)
  2. Data Structures and Algorithms in C by Mark Allen Weiss
  3. Algorithm Design by Jon Kleinberg and Eva Tardos
  
  
• Prerequisites : UENG 101, and some mathematical maturity.


• Grading policy :
  • Two class test - 30% (each 15%)
  • Mid-term exam - 35%
  • End-term exam - 35%


• First class test : Sep 3 (Thursday), 10 -- 11:20 am in G-21


• Second class test : Nov 3 (Tuesday), 10 -- 11:20 am in G-21


• Lectures :
  • Lecture 1: Course info; Introduction; Insertion sort; Order notations
  • Lecture 2: Divide-and-conquer: Merge sort; Matrix multiplication; Recurrences
  • Lecture 3: Heaps; Heapsort; Priority Queues