1) Discrete Mathematics in Computer Science
Sets. Finite and infinite sets. Countable sets. The diagonalizatiom method. The inclusion-exclusion principle. Mathematical induction. Combinations and permutations. Introduction to format languages and finite automata. Grammars. Groups, rings and fields. Isomorphisms, automorphisms and homeomorphisms. Permutation groups. Relations. The job scheduling problem. Binary relations, lattices, partially ordered sets. Equivalence relations and partitions. Introduction to Boolean algebra.
Computational models for sequential algorithms. Turing machine. Random access
machine (RAM). The class of polynomial problems. Algorithms on graphs. Shortest
path. Minimum spanning tree. Biconnectivity-Strongly connected components. Maximum
flow. The class of non-deterministically polynomial (NP) problems. Polynomial
reductions. NP-complete problems. Parallel algorithms. Computational models
for parallel algorithms. Interconnection networks. The parallel random access
machine (PRAM). The class NC. log-space reductions. P-compete problems. Efficient
and optimal parallel algorithms.
The uncertainly function as a measure of information. Properties of the uncertainty
function. Source coding-Huffman codes. Optimum codes. Shannon's first theorem.
Channel capacity. Shannon,s second theorem. Error correcting codes. Lower and
upper bounds. The sphere-packing bound. Hamming codes. Linear codes. Cyclic
codes, BCH codes. Error correcting capability of BCH codes. Shift registers
for encoding and decoding cyclic codes. Continous channel with Gaussian noise.
Average error probability.