Neelima Gupta

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

• 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.

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.

• 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.

• 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.

• 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.

• 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.

• 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.

• 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.

• 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 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

• 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.

• 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.

• 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.