Instructor: Partha Sarathi Mandal[TEL: 2624, E-mail: psm] Department of Mathematics, Indian Institute of Technology Guwahati Course title: Data Structures and Algorithms [MA252] [3-0-0-6] and

Data Structures Lab with OOP [MA253] [0-1-2-4]Level: B.Tech.(M&C) Prerequisites: MA 221 or equivalent Semester: Dec'11 - Apr'12 Lecture Time: Monday: 09:00-09:55, Tuesday: 10-10:55, Wednesday: 11-11:55, ~~Friday: 08-08:55~~Lab Time for MA253: Tuesday: 2:00-4:55 PM (AL-2) (Tutorial:2:00-3:00PM) Class Room: 1102 (for MA252) and Dept. Lab (for MA253) TA: Mr. Barun Garain Links: Unix Command Dictionary Contents: Click Here Exams & Marking: MA252: Quizzes [20%] + Midsem [30%] + Endsem [50%]

MA253: [Quizzes + Assignments + Attendance] [40%] + Midsem [30%] + Endsem [30%]

Texts:

- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, 2001.
References:

- S. Sahni, Data Structures, Algorithms and Applications in C++, 2nd Ed., Universities Press, 2005.
- M. T. Goodrich and R. Tamassia, Data Structures and Algorithms in Java, Wiley, 2006.
- A. V. Aho and J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley, 1983.
Announcement:

- MA252: Endsem exam is on Apr 24, 2012 (The exam covers full syllabus of MA252)
- MA253: Endsem Lab exam is on Apr 10, 2012 (Tuesday), from 2:00PM to 4:30PM

(The syllabus for the exam. includes up to the last lecture of MA252- Quiz II is on April 02, 2012 (Monday), from 8:00AM.
- Assignment submission deadline is on 04/03/2012 (Sunday) before 11:59PM. The submission to be done by uploading the files to the folder name "usernameMA252A1" in the your math server account. The folder will be created by Mr. Majumdar. Note that after the deadline read and write permission will be over for the folder.
- MA253: Midsem Lab exam is on Feb 14, 2012 (Tuesday), from 2:00PM to 4:30PM

(The syllabus for the exam. includes up to the last lecture of MA252 and the tutorial of MA253)- Quiz I is on January 17, 2012 (Tuesday), from 10:00AM to 10:50AM
Lecture Notes: __________________________________________________________________________________ Dec 27 Lecture Notes 1 [Tests and marks distribution, Introduction, RAM Model, Estimating running time] Dec 28 Lecture Notes 2 [The problem of sorting, Insertion sort, Big-Oh notation, Computing prefix averages] Jan 02 Lecture Notes 3 [Asymptotic Notations, Merge sort, Recurrence equation] Jan 03 Lecture Notes 4 [Solving recurrences, Binary search, Powering a number] Jan 04 Lecture Notes 5 [Computing Fibonacci numbers, Matrix multiplication, Strassen's algorithm] Jan 09 Lecture Notes 6 [Quicksort, Complexity analysis of the quicksort] Jan 10 Lecture Notes 7 [kth Element Problem, Order Statistics, Randomized selection algorithm] Jan 11 Lecture Notes 8 [Analysis of expected time for randomized selection, Worst-case linear-time order statistics] Jan 16 Lecture Notes 9 [Complexity analysis of the Randomized quicksort, Decision-tree model, Lower bound for comparison sorting] Jan 17 Quiz I Jan 18 Lecture Notes 10 [Heap Sort] Jan 23 Lecture Notes 11 [Complexity analysis of Heap Sort] Jan 24 Lecture Notes 12 [Inserting elements in Heap, Priority queues, Sorting in linear time: Counting sort] Jan 25 Lecture Notes 13 [Radix sort, Complexity analysis of radix sort] Jan 30 Lecture Notes 14 [Bucket sort, Complexity analysis of Bucket sort] Jan 31 Lecture Notes 15 [Binary Search Trees (BST): Operation: Search, Minimum, Maximum, Predecessor, Successor, Insert/Create] Feb 01 Lecture Notes 16 [Deletion in BST, Binary Tree Traversal Methods] Feb 06 Lecture Notes 17 [Expression Tree and construction of expression tree from given travel orders] Feb 07 Lecture Notes 18 [Hashing] Feb 08, 13 Lecture Notes 19 [Review of Stack, Queue and Linked List] Feb 21 Midsem Feb 27 Lecture Notes 20 [Balanced Search Trees: AVL Tree] Feb 28 Lecture Notes 21 [Insertion & deletion in AVL Tree] Feb 29 Lecture Notes 22 [2-3 Tree] Mar 05 Lecture Notes 23 [Red-black Tree] Mar 12 Lecture Notes 24 [Graph Algorithms: Graph Search Methods, Breadth-first search (BFS)] Mar 13 Lecture Notes 25 [Spanning Tree, Depth-First Search (DFS), Topological Sorting] Mar 14 Lecture Notes 26 [Strongly connected components, Bi-connected components] Mar 19 Lecture Notes 27 [Disjoint Sets] Mar 20 Lecture Notes 28 [MST: Kruskal's Algorithm] Mar 21 Lecture Notes 29 [MST: Prim's Algorithm] Mar 26 Lecture Notes 30 [SSSP: Dijkstra's Algorithm] Mar 27 Lecture Notes 31 [SSSP: Bellman-Ford Algorithm] Mar 28 Lecture Notes 32 [Dynamic Programming] Apr 02 Quiz II Apr 03 Lecture Notes 33 [Longest common subsequence problem and dynamic programming solution] Apr 04 Lecture Notes 34 [Dynamic programming solution of 0-1 Knapsack problem] Apr 10 Lecture Notes 35 [Dynamic programming solution of Matrix Chain Order Problem] Apr 16 Lecture Notes 36 [All-Pairs Shortest Paths Problem, Dynamic programming solution based on matrix multiplication, Floyd-Warshall Algorithm] Apr 17 Lecture Notes 37[Complexity Class and NP-Completeness (for interested students)] Apr 24 Endsem