Department of Mathematics
MATH237 - Mathematics
IIC
Unit Syllabus
Basic Material:
- Sentences, tautologies and logical equivalence,
sentential functions and sets, set functions, quantifier logic,
negation.
- Relations, equivalence relations, equivalence
classes, functions.
- The natural numbers, induction.
- Division and factorization, greatest
common divisor, an elementary property of primes.
Computational Aspects:
- Languages, regular languages.
- Finite state machines, pattern recognition
machines, delay machines, equivalence of states, the minimization
process.
- Deterministic finite state automata,
equivalence of states and minimization, non-deterministic finite
state automata, regular languages, conversion to deterministic
finite state automata.
- Turing machines, the busy beaver problem,
the halting problem.
- Coding theory, the Hamming metric, group
codes, matrix codes, Hamming codes, polynomial codes.
- Public key cryptography.
Mathematical Aspects:
- Principle of inclusion-exclusion.
- Generating functions, the extended binomial
theorem.
- Number of solutions of a linear equation,
use of inclusion-exclusion, the generating function method.
- Linear recurrence relations, method
of undetermined coefficients, lifting the trial functions, the
generating function method.
- Graphs, valency, walks, paths, cycles,
Hamiltonian cycles, Eulerian walks, trees, spanning tree of a
connected graph.
- Weighted graphs, minimal spanning tree.
- Search algorithms, depth-first search,
breadth-first search, the shortest path problem.
- Digraphs, networks and flows, maximum
flow and minimum cut.
