About Mathematics for Computer and Information Science 4 (GAMAT401)
Mathematics for Computer and Information Science 4 (GAMAT401) is a fourth-semester course in the KTU B.Tech 2024 scheme (Group A). It carries 3 credits (L:T:P:R = 3:0:0:0) and has no prerequisites. The course gives a comprehensive understanding of the fundamentals of graph theory, including paths, cycles, trees, graph algorithms, graph colouring and matrix representations, with applications across various disciplines.
Syllabus
- Module 1: Introduction to graphs, applications of graphs, finite and infinite graphs, incidence and degree, isolated and pendant vertices, null graph, isomorphism, subgraphs, walks, paths and circuits, connected and disconnected graphs, and components.
- Module 2: Euler graphs, operations on graphs, Hamiltonian paths and circuits, Travelling Salesman Problem, connectivity, edge connectivity, vertex connectivity, directed graphs, and types of directed graphs.
- Module 3: Trees and their properties, pendant vertices, distance and centres in a tree, rooted and binary trees, counting trees, spanning trees, Prim's and Kruskal's algorithms, Dijkstra's shortest path algorithm, and the Floyd-Warshall shortest path algorithm.
- Module 4: Matrix representation of graphs (adjacency matrix, incidence matrix, circuit matrix, path matrix), colouring, chromatic number, chromatic polynomial, and the greedy colouring algorithm.
Exam pattern
The end-semester exam is for 60 marks and lasts 2 hours 30 minutes. Part A has 8 compulsory questions of 3 marks each (2 from each module, 24 marks). Part B has 2 questions from each module, of which you answer one, each carrying 9 marks (4 x 9 = 36 marks). Continuous internal evaluation (CIE) carries 40 marks: attendance (5), assignment or microproject (15) and two internal exams (10 + 10).
Study tips
Start with the basic definitions in Module 1, because every later module builds on them. Practise drawing graphs and checking properties such as isomorphism, Euler and Hamiltonian circuits and connectivity. In Module 3, work through Prim's, Kruskal's, Dijkstra's and Floyd-Warshall step by step on different graphs, as these are the most common numerical questions. In Module 4, practise writing matrices from graphs and finding the chromatic polynomial. The syllabus excludes the proofs of some theorems, so check the official list before you spend time on them. Solve previous year question papers to see how questions are framed.
Notes and resources
Find module-wise notes, solved problems, previous year question papers and the syllabus for GAMAT401 below. Use them together with your class notes for best results.