# Teaching                                                                                       Time Table Calendar

## Courses Taught During Jan 2021 - May 2021

• #### MCAC 201: Data Structures

MCAC 201: Data Structures
 S.No. Lecture Practice Questions / Programming Assignments Quiz 1. Lecture 1: Introduction to Data Structures and Algorithms --- --- 2. Lecture 2: Stacks --- --- 3. Lecture 3: Queues and Linked Lists --- --- 4. Lecture 4: Dictionaries --- --- 5. Lecture 5: Hashing --- --- 6. Lecture 6: Trees --- --- 7. Lecture 7: Tree Walks / Traversals --- --- 8. Lecture 8: Ordered Dictionaries --- --- 9. Lecture 9: Deletion --- --- 10. Lecture 10: Quick Sort --- --- 11. Lecture 11: AVL Trees Practice QuestionsUnder Preparation --- 12. Lecture 12: AVL Trees --- --- 13. Lecture 13: Trees Practice QuestionsUnder Preparation --- 14. Lecture 14: Red Black Trees --- --- 15. Lecture 15: Insertion in Red Black Trees --- --- 16. Lecture 16: Disk Based Data Structures --- --- 17. Lecture 17: Case Study - Searching for Patterns --- --- 18. Lecture 18: Tries --- --- 19. Lecture 19: Data Compression --- --- 20. Lecture 20: Priority Queues --- --- 21. Lecture 21: Binary Heaps --- --- 22. Lecture 22: Why Sorting? --- --- 23. Lecture 23: More Sorting --- --- 24. Lecture 24: Graphs --- --- 25. Lecture 25: Data Structures for Graphs --- --- 26. Lecture 26: Two Applications of Breadth First Search --- ---
• #### RCS 002: Algorithms

 RCS 002: Algorithms

## Courses Taught During July 2020 - November 2020

• #### MCAC 301: Design and Analysis of Algorithms

MCAC 301: Design and Analysis of Algorithms
 S.No. Lectures Practice Questions / Programming Assignments Quiz 1. Lecture 1.1: Introduction Algorithms Quiz 1.1 - Introduction to Algorithm Lecture 1.2: Linear Search Programming Assignment 1 - Linear Search Quiz 1.2 - Linear Search 2. Lecture 2.1: Asymptotic Notations Practice Questions- Asymptotic Notations Quiz 2.1 - Asymptotic Notations Lecture 2.2: Input Size Quiz 2.2 - Input Size 3. Lecture 3.1: Correctness: Linear Search Quiz 3.1 - Loop Invariance Lecture 3.2: Insertion SortInsertion Sort Demo Programming Assignment 2 - Insertion Sort Quiz 3.2 - Sorting 4. Lecture 4.1: Stable and In-Place Sorting Programming Assignment 4 - Insertion Sort Analysis Lecture 4.2: Divide n Conquer Binary Search 5. Lecture 5.1: Merge Sort (Under Preparation) Lecture 5.2: Merge Sort Analysis (Under Preparation) 6. Lecture 6.1: Quick Sort Lecture 6.2: Quick Sort Analysis 7. Lecture 7.1: Lower Bounds n Count Sort Lecture 7.2: Radix Sort
• #### MCSC 101: Design and Analysis of Algorithms

MCSC 101: Design and Analysis of Algorithms
 S.No. Lectures Practice Questions / Programming Assignments Quiz 1. Lecture 1.1: Correctness of Basic Algorithms Lecture 1.2: Correctness of Binary Search 2. Lecture 2.1: Four Representative Problems Lecture 2.2: Divide n Conquer II 3. Lecture 3.1: Greedy-I (Correctness IntSch) Lecture 3.2: Greedy-II (SP MST) 4. Lecture 4.1: Weighted Interval Scheduling Lecture 4.2: Matrix Chain Multiplication Lecture 4.3: Segmented Least Square Lecture 4.4: Knapsack Problem Lecture 4.5: Sequence Alignment Lecture 4.6: Shortest Path

## Courses Taught During July 2019 - November 2019

• #### MCA 301: Design and Analysis of Algorithms

 MCA 301: Design and Analysis of Algorithms Input Size and Asymptotic Notations

## Courses Taught During July 2013 - November 2013

• #### MCA 520: Graph Theory

 MCA 520: Graph Theory Syllabus Fundamental Concepts: What is a graph (vertices, edges, neighbors, complement, coloring, connected components; Matrix representation (Isomorphism, subgraphs, bipartite, simple; complete and planer graphs); Paths, cycles, and trails; Bipartite graphs, Konig's theorem; Vertex Degrees and counting (Degree sequences); Directed graphs (outdegree, indegree, orientation, tournaments). Trees: Properties of trees, Spanning trees and enumeration; Minimum spanning trees and shortest paths. Matching and covers: Maximum matchings (augmenting paths, Hall's theorem, perfect matching), Konig's theorem, Independent set, vertex cover and relation to matchings; Algorithms for maximum bipartite matching and weighted bipartite matching. Connectivity and Paths: k-connected graphs, vertex cuts and edge cuts, Harary theorem, Whitney theorem, Menger's theorem; Network flow problems (Max flow, max-flow min-cut theorem). Coloring of Graphs: vertex coloring, k-coloring, chromatic number, clique number, coloring algorithms; coloring in interval graphs, Brook's theorem, chordal graphs, perfect graphs, Berge's theorem; Approximation algorithms for coloring. Planar Graphs: Dual graphs, faces, Euler's Formula; coloring of planar graphs. Introduction to Random Graphs Reading Material: D.B. West, "Introduction to Graph Theory", PHI, 2003. Jonathan L. Gross and Jay Yellen, "Graph Theory and Its Applications", Second Edition Chapman Hall (CRC), 2005. Gary Chartrand, "Introductory Graph Theory", Dover Publications, 1984. The course will also be a taught through various research papers. Lecture Notes Under Construction
• #### MCS 101: Design and Analysis of Algorithms

 MCS 101: Design and Analysis of Algorithms Lecture Notes Under Construction

## Course Taught During January 2013 - May 2013

• #### MCA 202: Discrete Mathematics

MCA 202: Discrete Mathematics

Syllabus

Overview: Counting, pegion-hole principle, generating functions, recurrence relations, linear recurrence relations with constant coefficients, homogenous solutions, particular solutions, total solutions, solution by the method of generating functions.

Growth of Functions: Asymptotic notations, monotonicity, comparison of standard functions - floors and ceilings, polynomials, exponentials, logarithms and factorials, summations: summation formulas and properties, bounding summations, approximation by integrals.

Graph Theory: Basic terminology, multigraphs and weighted graphs, paths and circuits, searching techniques: BFS, DFS and their applications, shortest paths in weighted graphs, Eulerian paths and circuits, Hamiltonian paths and circuits, Traveling Salesperson problem, planar graphs, trees and rooted trees, prefix codes, minimal spanning trees, cut sets, directed graphs.

Mathematical Logic: Propositions, connectives, conditionals and biconditionals, well formed formulas, tautologies, equivalence of formulas, duality law, normal forms, inference theory for propositional calculus; predicate calculus: predicates, free and bound variables, inference theory of predicate calculus.

Introduction to algebraic structures groups, lattices and boolean algebra.

References

• C.L. Liu, Elements of Discrete Mathematics, McGraw-Hill Pub. Co., 1977.
• D.E. Knuth, The Art of Computer Programming(3rd ed.), Vol. 1, Addison Wesley, 1997.
• R.L. Graham, D.E. Knuth, O. Patashnik, Concrete Mathematics(2nd ed.), Addison- Wesley, 1994.

Lecture Notes of 2012

 Lecture 1 - Asymptotic Notations Lecture 2 - Asymptotic Monotonicity and Standard Functions Lecture 3 - Summations Lecture 4 - Recurrence Lecture 5 - Graphs Lecture 6 - BFS and DFS Lecture 7 - Minimum Spanning Tree Lecture 8 - EC and HC

## Courses Taught During July 2012 - November 2012

• #### MCA 301: Design and Analysis of Algorithms

MCA 301: Design and Analysis of Algorithms

Syllabus

• Introduction: RAM model, O(log n) bit model.
• Review of data structures: Balanced trees, Mergeable sets.
• Algorithm Design Techniques: Iterative techniques, Divide and conquer, dynamic programming, greedy algorithms.
• Searching and Sorting Techniques: Review of elementary sorting techniques-selection sort, bubble sort, insertion sort; more sorting techniques-quick sort, heap sort, merge sort, shell sort; external sorting.
• Lower bounding techniques: Decision Trees, Adversaries.
• String Processing: KMP, Boyre-Moore, Robin Karp algorithms.
• Introduction to randomized algorithms: Random numbers, randomized Qsort, randomly Built BST.
• Number Theoretic Algorithms: GCD, Addition and Multiplication of two large numbers, polynomial arithmetic, Fast-Fourier Transforms.
• Graphs: Analysis of Graph algorithms Depth-First Search and its applications, minimum Spanning Trees and Shortest Paths.
• Introduction to Complexity Theory: Class P, NP, NP-Hard, NP Completeness.
• Introduction to Approximation Algorithms.

References

• T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Indtroduction to Algoritms, Prentice-Hall of India, 2006.
• J. Kleinberg and E.Tardos, Algorithms Design, Pearson Education, 2006.
• S.Baase, Computer algorithms: Introduction to Design and Analysis, Addison Wesley, 1999.
• A.V. Levitin, Introduction to the Design and Analysis of algorithms, Pearson Education, 2006.

Lecture Notes of 2012

 Introduction Lecture 1 - Mathematical Induction: Review Growth Functions
Some Lecture Notes of Previous Years

Previous Years Minors

 Minor I'07 Minor II'07 Minor I'06 Minor II'06 Minor I'05 Minor II'05
• #### MCS 312: Special Topics in Theoretical Computer Science

MCS 312: Special Topics in Theoretical Computer Science
(NP Completeness and Approximation Algorithms)

Syllabus

• Introduction to NP Completeness and Approximation.
• Problems from first principle: Satisfiability SAT, 3SAT.
• Graphs: Clique, Covering, Graph Partitioning, Subgraph problem, Graph Isomorphism, Graph Coloring, Hamiltonian Cycle Problem, TSP.
• Network Design Problems: Steiner tree, Spanning Trees, Cuts and Connectivity, Routing and Flow Problems.
• Sets and Partitions: Set partition and Covering, Subset sum.
• NP-hard problems: Clustering Problems like k-means clustering, co-clustering, connected kmeans clustering. More new problems as they are added to the class of NPC or NPH.
• Approximation algorithms for the above problems.

References

• M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences), 1979.
• Teofilo F. Gonzalez, Handbook of NP-Completeness: Theory and Applications, 2009.
• Vijay V. Vazirani, Springer-Verlag, Approximation Algorithms, France, 2006.
• Teofilo F. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics (Chapman & Hall/Crc Computer and Information Science Series), 2007.
• Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali, Linear Programming and Network Flows by 2004.
• Part of the course will be covered by research papers.

Lecture Notes of 2012

 Introduction to NP Lecture 2 - Satisfiablity Lecture 3 - Hamiltonian Cycle Lecture 4 - The Knapsack Problem & Bin Packing Lecture 5 - Set Cover & Traveling Salesman Problem Lecture 6 - 3D Matching Problem Lecture 7 - Exact 3-Cover Problem Lecture 8 - Graph Coloring

## Subjects Taught Previously

• 1989 - 2002: Systems Analysis and Design, Computer System Architecture, Programming languages from COBOL, Pascal to C, Discrete Structures, Data Structures, Algorithms, Theory of Computation/ Automata Theory, Statistical Techniques

• 2002 - till date: Systems Programming, Data Communication and Computer Networks, Design and Analysis of Algorithms, Algorithms in Bioinformatics, NP Completeness and Approximation Algorithms.
• #### MCS 101: Design and Analysis of Algorithms

MCS 101: Design and Analysis of Algorithms

Syllabus

• Review of algorithm design techniques like Iterative Techniques and Divide & Conquer through Sorting, Searching and Selection problems.
• Review of Lower Bounding techniques: decision trees, adversary.
• String Processing: KMP, Boyre-Moore, Rabin Karp algorithms.
• Introduction to randomized algorithms: random numbers, randomized quick sort, randomly built binary search tree.
• Number Theoretic Algorithms: GCD, addition and multiplication of two large numbers, polynomial arithmetic, Fast-Fourier transforms.
• Advanced Techniques to analyze algorithms: Use and study advanced data structures unionfind ( Disjoint Set Structure), Fibonacci heaps.
• Graph algorithms: Matching and Flows.
• Parallel algorithms: Basic techniques for sorting, searching and merging in parallel.
• Geometric algorithms: Point location, Convex hulls and Voronoi diagrams.
• Complexity Theory: Classes P, NP, NP-Hard, NP Complete.
• Approximation Algorithms: Introduction through examples.

References

• T.H. Cormen, C.E.Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, McGraw-Hill, 2002.
• Sara Baase, Computer Algorithms: Introduction to Design and Analysis, Addison Wesley, 1999.
• R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
• Teofilo F.Gonzalez, Handbook of NP-Completeness: Theory and Applications Chapman & Hall, 2009.
• Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, France, 2006.
• S. Rajasekharan and John Reif, Handbook of Parallel Computing: Models, algorithms and applications, Chapman and Hall/CRC, 2007.
• Gareth A. Jones and Josephine M. Jones, Elementary Number Theory, Springer, 1998.
• F P Preparata and M I Shamos, Computational Geometry: An Introduction Springer, 1993.

Lecture Notes of 2011

 Lecture 1 - Introduction Lecture 2 - Review Lecture 3 - Review Lecture 4 - Adversary Lecture 5 - Correctness of Algorithms Lecture 6 - Expected Running Times and Randomized Algorithms Lecture 7 - String Matching Lecture 8 - Number Theoretic Problems Lecture 9 - Parallel Algorithms Lecture 10 - Network Flows Lecture 11 - NP-Completeness Lecture 12 - Approximation Algorithms Lecture 13 - Dynamic Programming Lecture 14 - Analysis of Graph Algorithms Grades 