This course is a basic course offered to UG/PG students of Engineering/Science background. It consists of four main topics : 1.Discrete Mathematics: Symbolic representation of statements, Duality, Tutologies and contradictions, Quantifiers, languages and Grammers, Finite state machines, Lattices as partially ordered sets, Lattices as Algebraic systems, Sublattices, Boolean algebra and Boolean functions, Representations of Boolean functions, Application of Boolean functions to synthesis of circuits, Circuit minimizations, Karnaugh Map. 2.Graph theory: Various types of Graphs, Subgraphs, Walks, Trails, Paths, Cycles, Eularian and Hamiltonian graphs, Travelling salesman problem, Vertex and edge connectivity, Matrix representation of graphs, Incidence and adjacency matrices of graphs, Planar graphs, Kuratowski’s graphs, detection of planarity, Euler’s formula, duals of a Planar graph, Colouring of graphs, Four color theorem. 3.Linear programming problems: Graphical method, simplex method, Big-M method, two phase method, Dual Simplex method and applications. 4.Queuing theory: Basic charecteristics of Queuing modles, Distribution of arrivals and service times, M/M/1:∞/FIFO model, M/M/S:∞/FIFO model, M/M/1:N/FIFO model, M/M/S:N/FIFO model and their applications. INTENDED AUDIENCE: UG and PG students of technical institutions/ universities/collegesPREREQUISITES: Nil
Week 1: Symbolic representation of statements-I, Symbolic representation of statements-II, Tautologies and Contradictions, Predicates and Quantifiers-I, Predicates and Quantifiers-II. Week 2: Validity of Arguments, Languages and Grammers-I, Languages and Grammers-II, Languages and Grammers-III, Finite- state machines. Week 3: Partially ordered sets-I, Partially ordered sets-II, Partially ordered sets-III, Lattices-I, Lattices-II. Week 4: Lattices-III, Lattices-IV, Lattices-V, Boolean Algebra-I, Boolean Algebra-II. Week 5: Boolean Algebra-III, Boolean Algebra-IV, Logic Gates, Karnaugh map-I, Karnaugh map-II. Week 6: Various types of Graphs-I, Various types of Graphs-II, Path and Connectivity, Subgraphs and Traversable Multigraphs, Undiected and Directed Graphs. Week 7: Eulerian and Hamiltonian Graphs, Planer Graphs, Representation of Graphs, Isomorphic and Homeomorphic Graphs, Kuratowski’s Theorem. Week 8: Dual of Graph, Coloring of Graphs-I, Coloring of Graphs-II, Trees-I, Trees-II. Week 9: Graphical Method-I, Graphical Method-II, General Linear Programming Problem, Simplex Method-I, Simplex Method-II. Week 10: Big-M Method-I, Big-M Method-II, Two Phase Method-I, Two Phase Method-II, Duality-I. Week 11: Duality-II, Dual Simplex Method, Transportation Problem-I, Transportation Problem-II, Assignment Problem-I. Week 12: Assignment Problem-II.