M.Sc. Tech (Industrial Mathematics with Computer Applications)

M.Sc. Tech (Industrial Mathematics with Computer Applications)
Three -Years Self- Financed Post Graduate Degree Programme
(Started from Jun 2002)

COURSE STRUCTURE

Pre-requisite for the Course : Mathematics Courses of the B.A./B.Sc. first two years/Engineering Mathematics Course of B.E. as taught in Indian Universities.

Part – II    (Duration : One Year)
MIM 201     Any two of the followings with equal Weightage :
                    (a) Algebra – II

(b) Topology – II

(d) Discrete Mathematical Structures – II

MIM 202     Computer Graphics
MIM 203     Object Oriented Programming with C
MIM 204     Operating Systems
MIM 205     Design and Analysis of Algorithms
MIM 206     Practicals related to Papers MIM 202, 203, 204
                    - Shortly written as MIM

Additional Recommended References
Avner Friedman, Mathematics in Industrial Problems (All Volumes of the series), Springer-Verlag, New York Inc.

DETAILS OF SYLLABUS

Part – II (Duration: One Year)
MIM 201 Any two of the following :

(a) Algebra – II Field Theory
Unit-1 Extensions of field, the transcendence of e, roots of polynomials construction with straightedge and compass.

Unit-2 The fixed field of a group of automophisms, the theorem on symmetric polynomials, the Galois group of a polynomial, the fundamental theorem of Galois theory, solvability by radicals Galois group over the rationals, finite fields, Wedderburn’s theorem on finite division rings. Note: The topics from Algebra of units 1 and 2 are roughly covered by chapter 5 ( all articles ) and chapter 7 ( 7.1 and 7.2 only ) of the book entitled “ Topics in Algebra ” by I. N. Herstein 2nd Edition. Wiley Eastern Ltd., 1975.

(b) Topology – II Advance Topics
Unit-1 The quotient topology, the product and box topologies, the uniform topology, the metrezability and an infinite product of R, the product topology and Husdorff, regular, normal spaces, Tietz extension theorem, Uryshon’s metrization theorem, Stone-Cech compactification, topological dimension : Lebesgue’s covering dimension Rm and compact M- Manifold.

Unit-2 Homotopy of paths, the fundamental group, covering spaces the fundamental groups of the circle, the punctured plane, the n-sphere Sn and some surfaces, the fundamental theorem of algebra.

Note: The topics from Topology of units 1 and 2 are roughly covered by chapters 2 ( articles 2.8, 2.9, 2.10, 2.11 only ), some theorems of chapters 3 and 4, chapter 5 (5.1, 5.2, 5.3), Chapter 7 (7.9 only) and Chapter 8 (8.1 to 8.9 only) of James R. Munke’s: “ Topology, A first course ”, 2nd Prentice – Hall of India Pvt. Ltd., New Delhi. 2002.

(c)       Discrete Mathematical Structures - 1
    Formal Logic-Statements. Symbolic Representation and Tautologies. Quantifiers, Predicates and Validity. Propositional Logic.
    Semigroups & Monoids, Relations and Ordering, Transitive Closure of a relation, Functions. Definitions and Examples of Semigroups and Monoids (Including those pertaining to concatenation operation). Homomorphism of Semigroups and Monoides. Congruence relation. Quotient Semigroups. Subsemigroup and submonoids. Direct products. Basic homomorphism Theorem.
    Lattices-Lattices as partially ordered sets. Their properties. Lacttices as Algebraic systems. Sublattices, Direct products, and Hommorphisms. Some Special Lattices e.g., Complete Complemented and Distributive Lattices.
    Boolean Algebras-Boolean Algebras as Lattices. Various Boolean Identities. The Switching Algebra example. Subalgebras, Direct Products and Homomorphisms. Join-irreducible elements, Atoms and Minterms. Boolean Forms and Their Equivalence. Minterm Boolean Forms, Sum of Products Canonical Forms. Minimization of Boolean Functions. Applications of Boolean Algebra to Switching Theory (using AND, OR & NOT gates). The Karnaugh Map method.
    Graph Theory-Definition of (undirected) Graphs, Paths, Circuits, Cycles, & Subgraphs. Induced Subgraphs. Degree of a vertex. Connectivity. Planar Graphs and their properties. Trees. Euler’s Formula for connected Planar Graphs.
    Complete & Complete Bipartite Graphs. Kuratowski’s Theorem and its use. Spanning Trees, Cut-sets, Fundamental Cut-sets, and Cycles. Minimal Spanning Trees and Kruskal’s Alogrithm. Matrix Representations of Graphs. Euler’s
    Theorem on the Existence of Eulerian Paths and Circuits. Directed Graphs. Indegree and Outdegree of a Vertex.
    Weighted undirected Graphs. Dijkstra’s Algorithm. Strong Connectivity & Warshall’s Algorithm. Directed Trees. Search Trees. Tree Traversals.

(d)        Discrete Mathematical Structures - 2
    Introductory Computability Theory-Finite State Machines and their transition Table Diagrams. Equivalence of Finite State Machines. Reduced Machines. Homomorphism. Finite Automata. Acceptors. Non-deterministic Finite Automata and equivalence of its power to that of Deterministic Finite Automata. Moore and Mealy Machines.
    Turing Machine and Partial Recursive Functions.
    Grammars and Languages-Structure Grammars. Rewriting Rulers. Derivations. Sentential Forms. Language generated by a Grammar. Regular, Context-Free, and Context Sensitive Grammars and Languages. Regular sets, Regular Expressions and the Pumping Lemma. Kleene’s Theorem.
Notions of Syntax Analysis. Polish Notations. Conversion of Infix Expressions to Polish Notation.

References

J.P.Tremblay & R.Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw-Hill Book Co.,1999.
J.L. Gersting, Mathematical Structures for Computer Science, (3rd edition), Computer Science Press, New York. Seymour Lepschutz, Finite Mathematics (International edition 1983), McGraw-Hill Book Company, New York.
S. Witala, Discrete Mathematics – A Unified Approach, McGraw-Hill Book Co. J.E.Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages & Computation, Narosa Publishing House.
C. L. Liu, Elements of Discrete Mathematics, McGraw-Hill Book Co.
N. Deo, Graph Theory with Applications to Engineering and Computer Sciences, Prentice Hall of India.

MIM 202 Computer Graphics

    Input/Output devices-Light Pens. Joystick. Digitizers. Refreshing display devices. Random and raster scan display devices.
    Line Generation and Area Filling algorithms-Bresenham line generation algorithm. Scan line, Flood-fill and boundary-fill algorithms for polygonal domains.
    Line Clipping Algorithms-Cohen-Suthurland algorithm. Cyrus-Beck algorithm. Liang - Bar sky algorithm.
    Transformations in 2D-Translation, rotation, Scaling and shearing transformations. Reflection about any arbitrary line, Homogeneous Coordinates.
    Projections-Parallel projection. Isometric projection. Cabinet and Cavalier oblique projections, perspective projection. Vanishing points. 1-point and 2-point perspective projection.
    Representing Curves and Surfaces-Polygon Meshes. Hermite and Bezier Cubic Curves. B-spline Curves. Uniform.
    Non-uniform, open and non-open B-splines. Bicubic surface, patches. Conditions for smooth-joining of curves and surface patches.
    Hidden line/surface elimination algorithms-Z-buffer algorithms, depth-sort
    Algorithm, area-subdivision method, floating horizon algorithm.
    Effect of Lights-Ambient and diffuse reflection models. Phong’s specular reflection model. Gourand and Phong shading models.
    Fractals-Self-similar fractals, self affined fractals, self-squaring fractals. Mandelbrot sets.
    Constructive solid geometry.

References
    1.    Hearn and Baker-Computer Graphics, Prentice-Hall of India.
    2.    Foley and Vandam, Feiner, Hughes-Computer Graphics, Addison Wesley.
    3.    Rogers, Procedural Elements of Computer Graphics, McGraw-Hill.

MIM 203 Object Oriented Programming with C++

    Introduction to Object-oriented programming paradigm and design.
    Object, Class-Superclass. Subclass. Metaclass. Hierarchy. Instance. Polymorphism (Operator Overloading).
    Inheritance-Hierarchical. Multiple. Selective.
    Object-oriented Methods-Objected-oriented analysis. Construction and Testing. Object Modeling Techniques. Case Studies.
    Programming-Introduction to OOP languages-Class concept in SIMULA. Pure object-oriented language like Smalltalk 80. Hybrid Object-oriented language like C++ , etc. Details of C++ .
    Data Types-Primitive and User defined. Operators. Classes-Friend. Derived. Structures and Expressions. Pointers and reference parameters. Virtual Functions. Templates. Storage Representation. Subprograms and Storage Management. Functions. Function prototyping. Class definition. Class extension. Nesting of Classes. Constructor and Destructor. Memory Allocation for Objects. Type Definitions. Operator Overloading. Type conversions and Casting. Data Abstraction. Input and output. File Handling Programme-defined exceptions. Conditional Compilation.

Application-Use of OOP concepts in different areas :

Object-oriented Software Engineering-Architecture of OOSE method. Reusability and OOP. Testing in OOSE. Case study in OOSE.
Object-oriented OS-Objects and operations. Cooperating objects. Capabilities. Process Management. Memory Manager. Device Management. Object-based communication. Architecture of an object-based OS.
Object-oriented DBMS-Introduction. Object Identifier. Object Structure. Type Constructor and Destructor. Encapsulation. Object-oriented Data Model. Object-oriented Data Definition Language. Type Hierarchies and Inheritance. Example OODBMS.
Object-oriented graphics-Requirements of Graphics System. Advantages of Object-oriented approach. Object-oriented Interface Architecture. Generation and Display of Graphics Object. GKS and Object-oriented system design. Part Hierarchies and Computer Graphics. Phigs and Part Hierarchies. Object-oriented standards in Graphics.

References

Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley.
Peter Muler, Introduction to Object-Oriented Programming using C++ , Globe wide Network Academy.
Namir C. Shammas, Foundations of C++ and Object Oriented Programming, Comdex Computer Publishing Co.
Richard Johnsonbaurgh and Martin Kalin, Object-Oriented Programming in C++ , Prentice Hall.
Timothy Budd, An Introduction to Object-Oriented Programming, Addison-Wesley.
Grady Booch, Object-Oriented Analysis and Design, Addison-Wesley.

MIM 204 Operating Systems

    Evolution of Operating System. Basic concepts-User job. Resources. Batch Processing. Multiprogramming.Time sharing. Process. Process Control Block.
    Memory management-Address Protection. Segmentation. Virtual Memory. Paging. Page replacement algorithms.
    Support for concurrent process-Mutual Exclusion. Shared Data. Critical Sections. Busy form of waiting, lock and unlock primitives, synchronization, blocking and wake up.
    Process Scheduling-Process states. Virtual processors. Interrupt mechanism. Scheduling algorithms. Implementation of concurrency primitive.
    System Deadlock-Prevention. Detection and Avoidance.
    Multiprogramming system-Queue management. I/O Supervisors. Memory Management. File system, disk scheduling. Shell Programming. UNIX-C interface. System calls. Device Driver. Interrupt Handler. UNIX and DOS as example systems. Introduction to Network and Distributed Operating System. Overview of Netware.

References :
    1.    P.B. Hansen, Operating System Principles, PHI.
    2.    Peterson and Silberschatz, Operating System Concepts, Addison-Wesley.
    3.    A.N. Haberman, Introcduction to Operating System Design, Galgotia.
    4.    K. Christian, The UNIX Operating System, John Wiley.
    5.    Manuals of DOS, UNIX and Netware.

MIM 205 Design and Analysis of Algorithms

    Mathematical Foundations - Growth functions. Summations, and recurrences - substitution, iteration, and master methods, counting, and probability, amortized analysis.
    Sorting-Heap sort, quick sort, merge sort, sorting in linear time, median, and order statistics.
    Advanced Data Structures - B-trees, red-black trees, hashing, dynamic order statistics, binomial and fibonacci heap, disjoint sets.
    Dynamic Programming-matrix chain multiplication, longest common subsequence, optimal polygon triangulation.
    Greedy Algorithms-Huffman coding and task scheduling problems.
    Graphs-Traversal, topological sort, minimum spanning trees, single source shortest paths-Dijkstra’s and Bellman Ford Algorithms, all-pairs shortest path, maximum flow problems.
    Sorting Networks-Comparison networks, bitonic sort and merge-sort networks.
    Arithmetic circuits-Combinational circuits, addition, multiplication, and clocked circuits.
    Parallel Algorithms-CRCW, EREW algorithms, efficiency, sorting linear systems problems.
    Matrix Operations-Strassen’s algorithms, matrix inversion. FFT-Polynomial representation, DFT, FFT.
    Number-Theoretic Algorithms-Modular arithmetic. Chinese remainder theorem, RSA Codes.
    String Matching-Rabin-Karp, KMP, Boyer-Moore algorithms.
    Geometric Algorithms-Algorithms for finding convex hull. Closest pair of points. Linear Programming Problems.
    NP-completeness-P and NP classes, NP-completeness and reducibility, NP-Completeness proofs.
    Approximation algorithms-Vertex cover, traveling salesman, set-coveing, and subset-sum problems.

References :
    1.    T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, Prentice Hall of India.
    2.    S. Basse, A.V. Gelder, Computer Algorithms, Introduction to Design & Analysis, Addison Wesley.
    3.    S. Sedge wick, Algorithms, Addison Wesley.
    4.    M.J. Quinn, Designing Efficient Algorithms for Parallel Computers.

M.Sc. Tech (Industrial Mathematics with Computer Applications) Three -Years Self- Financed Post Graduate Degree Programme (Started from Jun 2002)