The course will be based on the programming language Haskell.
Recommended Texts
Programming Language Concepts
Recommended Texts
Finite automata---regular languages---pumping lemma--- stack automata---context free languages---applications to compilers---Turing machines---universal Turing machines--- halting problem---non deterministic Turing machines--- complexity classes---P v/s NP.
Recommended Texts
Big O notation — sorting and searching — algorithm analysis techniques, recurrences — graph algorithms: DFS, BFS, shortest paths, spanning trees — divide and conquer — greedy algorithms — dynamic programming — data structures: heaps, binary search trees, union-finde — advanced topics: LP, network flows
Recommended Texts
Propositional and Predicate Logic: syntax, semantics, axiomatic systems, completeness, compactness --- resolution, automated reasoning --- introduction to modal and temporal logics and their use in system specifications.
Recommended Texts
Recommended Texts
Communication models: handshake synchronization, message-passing, shared memory --- Semaphores, monitors, co-routines --- distributed algorithms: leader election, distributed consensus --- clock synchronization --- byzantine agreement --- models: Petri Nets, I/O-automata.
Recommended Texts
Specification and verification of concurrent and reactive programs --- Reactive systems: syntax and semantics, fairness requirements --- Specification language -- temporal logic; state, future, and past formulas; deductive systems Program properties: safety, guarantee, obligation, response, persistence, and reactivity --- Verification of programs: proof systems, algorithmic verification of finite-state programs.
Recommended Texts
Turing machines; determinism and non-determinism --- time and space hierarchy theorems; speed-up and tape compression; Blum axioms --- structure of complexity classes NP, P, NL, L, PSPACE; complete problems --- randomness and complexity classes RP, RL, BPP --- alternation, polynomial-time hierarchy --- circuit complexity --- parallel complexity, NC, RNC --- relativized computational complexity --- time-space trade-offs --- Introduction to Interactive Proofs --- Arthur-Merlin Games, IP = PSPACE.
Recommended Texts
Linear equations---Gaussian elimination---integral solutions ---Smith normal form---linear functionals--- duality---cones --- Simplex method---introduction to queueing theory--- Elementary Game theory.
Recommended Texts
Suggested Textbooks
Elementary number theory --- Pseudo-random bit generation --- elementary cryptosystems --- number theoretic algorithms (RSA) --- symmetric key cryptosystems - DESIDEA, AES, --- authentication --- digital signatures, electronic commerce (anonymous cash, micropayments), key management--- PGP --- zero-knowledge protocols --- fairness.
Recommended Texts
discrete probability --- simple random variables --- the law of large numbers---Binomial, Poisson and normal distributions--- central limit theorem---random variables --- expectations and moments --- Markov chains.
Recommended Texts