## Spring 2023

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

MCAC 201: Design and Analysis of Algorithms
 S.No. Lectures Practice Questions / Programming Assignments Quiz Videos 1. Review Lecture 1.1: Introduction Algorithms Quiz Lecture 1.2: Linear Search Programming Assignment Quiz Lecture 1.3: Asymptotic Notations Practice Questions Quiz Lecture 1.4: Input Size Quiz 2. Sorting Lecture 2.1: Insertion SortInsertion Sort Demo Programming Assignment Quiz Lecture 2.2: Stable and In-Place Sorting Programming Assignment 3. Divide and Conquer Lecture 3.1: Binary Search Lecture 3.2: Merge Sort Lecture 3.3: Merge Sort Analysis Lecture 3.4: Quick Sort Lecture 3.5: Quick Sort Analysis 4. More on Sorting (Linear Sort) Lecture 4.1: Lower Bounds n Count Sort Lecture 4.2: Radix Sort 5. Greedy Lecture 5.1: Scheduling Problems Lecture 5.2: MST and Shortest Path PracticeQsAssignment Quiz1Quiz2_MST_SP 6. Dynamic Porgramming Lecture 6.1: Introduction to DP PracticeQs_DP Quiz Lecture 6.2: Weighted Interval Scheduling Lecture 6.3: Matrix Multiplication Lecture 6.4: Knapsack Problem Lecture 6.5: Sequence Alignment Problem 7. Randomised Algorithms Lecture 7.1: Probability Review Quiz 1 Video Lecture 7.2: Expectation of Random Variable Quiz 2 Video Lecture 7.3: Randomised Quicksort Quiz 3(QS and Find) Video Lecture 7.4: Randomised Find Quiz 3(QS and Find) Video Lecture 7.5: Randomised Built BST Video 8. String Matching Lecture 8.1 KMP

## Fall-2021,2022

• #### MCSC 101: Design and Analysis of Algorithms

MCSC 101: Design and Analysis of Algorithms
 S.No. Lectures Practice Questions / Programming Assignments Quiz Videos 1. Review Lecture 1.0: Four Representative Problems Video Lecture 1.1: Correctness of Basic Algorithms PracticeQsAssignment Quiz Video on Correctness of Linear Search Lecture 1.2: Correctness of Binary Search Correctness of Binary Search Lecture 1.3: Recursion PracticeQsAssignment Quiz Lecture 1.4: Greedy: Scheduling Problems Lecture 1.5: Greedy: MST and Shortest Path PracticeQsAssignment Quiz1Quiz2_MST_SP Lecture 1.6: Introduction to DP PracticeQs_DP Quiz Lecture 1.7: Weighted Interval Scheduling Lecture 1.8: Matrix Multiplication Lecture 1.9: Segmented Least Square Lecture 1.10: Knapsack Problem Lecture 1.11: Sequence Alignment Problem Lecture 1.12: Shortest Path(DP) 2. Randomised Algorithms Lecture 2.1: Probability Review Quiz 1 Video Lecture 2.2: Expectation of Random Variable Quiz 2 Video Lecture 2.3: Randomised Quicksort Quiz 3(QS and Find) Video Lecture 2.4: Randomised Find Quiz 3(QS and Find) Video Lecture 2.5: Randomised Built BST Video 3. Divide and Conquer Lecture 3.1: Divide and Conquer I PracticeQs_DnCAssignmentQs_DnC Quiz Lecture 3.2: Divide and Conquer II 4. Bipartite Matching Lecture 4.1 Bipartite Matching Quiz 5. Network Flow Lecture 5.1 Network Flow Quiz 6. NP-Hardness Lecture 6.1 Introduction to NP Quiz Lecture 6.2 Introduction to NP-Hardness Quiz Lecture 6.3 Approximation Algorithms 7. String Matching Lecture 7.1 KMP 8. Parallel Algorithms

## Spring 2022

• #### 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 Programming Assignment 1aProgramming Assignment 1bPractice Questions Asymptotic Notations Input Size 2. Lecture 2: Stacks Programming Assignment --- 3. Lecture 3: Queues and Linked Lists Programming Assignment --- 4. Lecture 4: Dictionaries --- --- 5. Lecture 5: Hashing Programming AssignmentPractice Questions --- 6. Lecture 6: Trees --- --- 7. Lecture 7: Tree Walks / Traversals Programming AssignmentPractice Questions --- 8. Lecture 8: Ordered Dictionaries Practice Questions --- 9. Lecture 9: Deletion --- --- 10. Lecture 10: Quick Sort --- --- 11. Lecture 11: AVL Trees Practice Questions --- 12. Lecture 12: AVL Trees Practice Questions --- 13. Lecture 13: Trees Practice Questions --- 14. Lecture 14: Red Black Trees --- --- 15. Lecture 15: Insertion in Red Black Trees --- --- 16. Lecture 16: Disk Based Data Structures Practice Questions --- 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

## Fall 2020

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

MCAC 301: Design and Analysis of Algorithms
 S.No. Lectures Practice Questions / Programming Assignments Quiz Videos 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 Video 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 Lecture 5.2: Merge Sort Analysis 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 Videos 1. Lecture 1.1: Correctness of Basic Algorithms Video on Correctness of Linear Search Lecture 1.2: Correctness of Binary Search Video on 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

## Fall 2015, 2014, 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

## Spring 2016, 2015, 2014

• #### MCA 202: Discrete Mathematics

MCA 202: Discrete Mathematics

Syllabus

Overview: Counting, pigeon-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

## Fall 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

## Courses 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 - 2011: 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