Course Syllabus
Malaviya National Institute of Technology, Jaipur
Dept. of ECE Session: I (Odd) Semester 2014 (July)
Course: ECT-205 Graph Theory Course-teacher: Dr. Vineet Sahula, Professor
Weightage assignment: MTE: ETE: Assignments/Quizzes - 40:40:20
Quizzes are not open books/notes. Examinations are normally open notes/books.
Course site: https://piazza.com/mnit.ac.in/fall2016/ect205
|
Lecture plan: |
|
|
Electrical network Analysis |
02 |
|
Graph introduction, terminology, trees, circuits, cut-set/vertices, planarity/duality |
08 |
|
Vector-spaces & matrix for a graph, coloring, covering, partitioning |
06 |
|
Directed graphs, enumeration of graphs |
02 |
|
Graph applications- switching, networks, operations research, & others |
05 |
|
Graph applications- operations research, & others |
05 |
|
Total |
28 |
Learning outcomes:
- Be able to appreciates the basics & definition of a combinatorial GRAPH
- Be able to grasp features, properties of special graphs
- Learns graph algorithms and its applications into Circuits, computer problem solving etc.
- In long perspective, is able to appreciate the significance of GRAPH as a versatile modeling entitiy which can be used for analysis as well as synthesis- especially for chip design, wireless communication protocols & system design, computer problem solving, data structures etc.
Syllabus as on records: 2(2L)/week
Graph Theory- basics, Planarization, triangulation, graph algorithms for shortest/longest paths, spanning tree, search etc.
Algorithms & complexity- shortest path, max-flow, Dijkshtra’s algorithm, min-cost flow, algorithm for graph search and matching; spanning trees and matroids; Integer Linear programming, Greedy algorithm, approximation algorithms; branch-and-bound; dynamic programming.
- Narsingh Deo, Graph theory, Prentice Hall India, 2008.
- H. Cormen, C. E. Leiserson and R. L. Rivest, “Introduction to Algorithms,” McGraw-Hill, 2007
- Baase, Computer algorithms, Pearson India 2008.
Course Summary:
| Date | Details | Due |
|---|---|---|