Spring 2023

Fall-2021,2022

Spring 2022

RCS 002: Algorithms


Fall 2020

Fall 2019, 2018, 2017

Spring 2020, 2019, 2018

Spring 2017

Feb 2016

Fall 2015, 2014, 2013

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
Lecture 1 - Introduction
Lecture 2 - Graph Isomorphism
Lecture 3 - Walks and Trails
Lecture 4 - Vertex Degrees-n-Counting
Lecture 5 - Directed Graphs
Lecture 6 - Trees

Spring 2016, 2015, 2014

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


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

Introduction
Lecture 1 - Mathematical Induction: Review Growth Functions
Lecture 2 - Solving Recurrences The Master Theorem
Lecture 3 - Proving Correctness of Algorithms
Lecture 4 - Comparison Sorting
Lecture 5 - Lower Bounds Linear-Time Sorting Algorithms
Lecture 6 - Selection Adversary
Lecture 7 - Analysis Red-Black Trees
Lecture 8 - NP - Completeness
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
(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

Undergraduate Level

  • 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

Postgraduate Level

  • 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
Useful Links
Karps's 21 NP-Complete Problems CS722
Karps's 21 NP-Complete Problems CS172
Some Lecture Notes of Previous Years
Introduction
Lecture 1 - Mathematical Induction: Review Growth Functions
Lecture 2 - Solving Recurrences The Master Theorem
Lecture 3 - Proving Correctness of Algorithms
Lecture 4 - Comparison Sorting
Lecture 5 - Lower Bounds Linear-Time Sorting Algorithms
Lecture 6 - Selection Adversary
Lecture 7 - Analysis Red-Black Trees
Lecture 8 - NP-Completeness
Previous Years Minors
Minor I'10 Minor II'10 Minor I'09 Minor II'09 Minor I'07 Minor II'07 Minor I'06 Minor II'06 Minor I'05 Minor II'05
MCA 204: Data Communication and Computer Networks


Contents

  • Data Communication: Theoretical basis of data communication; analog and digital signals; asynchronous and synchronous transmission; data encoding and modulation, techniques, broadband and baseband transmission; pulse code modulation, bandwidth, channel, baud rate of transmission; multiplexing; transmission medium; transmission errors - error handling mechanisms.
  • Network Classification and Data Communication Services: Local Area Networks, Wide Area Network, wireless network, internetworking.
  • Network Reference Models:Layered architectures, protocol hierarchies, interface and services: ISO-OSI reference model, TCP/IP reference model; internet protocol stacks.
  • Datalink Layer Functions and Protocols:Framing, error-control, flow -control; sliding window protocol; HDLC; Data link layer of internet.
  • Medium Access Sublayer: CSMA/CD protocol, switched and fast Ethernet, IEEE standards for LAN.
  • Network functions and protocols:Switching mechanism: Circuit switching, message switching, packet switching, routing and congestion control, TCP/IP protocol architecture.
  • Network Applications:File transfer protocol, electronic mail, World Wide Web.

References

  • A.S. Tanenbaum, Computer Networks (4th ed.), Prentice-Hall of India, 2003.
  • Behrouz Forouzan and S.C. Fegan, Data Communications and Networking, McGraw Hill, 2006.
  • W. Tomasi, Introduction to Data Communications and Networking, Pearson Education, 2007.
  • S. Haykin, Digital Communications, John Wiley & Sons, Inc., 2005.
  • P.C. Gupta, Data Communications and Computer Networks, Prentice-Hall of India, 2006.
  • L. L. Peterson and B. S. Davie, Computer Networks: A Systems Approach (3rd ed.), Morgan Kaufmann, 2003.
  • William Stallings, Data and Computer Communications (8th ed.), Pearson Education, 2007.

Some Lecture Notes of Previous Years

Lecture 1 - Introduction
Lecture 2 - Theoretical Basis for Data Communication
Lecture 3 - Physical Layer
Lecture 4 - PSTN
Lecture 5 - Data Link Layer
Lecture 6 - Data Link Layer Protocols
Lecture 7 - Medium Access Control
Lecture 8 - Network Layer
Lecture 9 - Transport Layer
Lecture 10 - Application Layer
The figures included in the presentation are from the soft study material provided with the following books:

  • A.S. Tanenbaum, Computer Networks (4th ed.), Prentice-Hall of India, 2003.
  • Behrouz Forouzan and S.C. Fegan, Data Communications and Networking, McGraw Hill, 2006.
(It is declared that it is being used purely for the teaching purposes.)