National Institute of Technology Calicut

CSU 356 MOBILE COMPUTING

Pre-requisite: CSU 304 Computer Networks

 

L	T	P	C
3	0	0	3

Module I (10 hours)

Introduction to mobile computing, mobile development frameworks and tools, introduction to XML and UML.

Module II (10 hours)

Device independent and multichannel user interface development using UML, developing mobile GUIs, VUIs and mobile applications, multichannel and multimodal user interfaces.

Module III (11 hours)

Mobile agents and peer-to-peer architectures for mobile applications, wireless connectivity, synchronization and replication of mobile data, mobility and location based services, active transactions.

Module IV (11 hours)

Mobile Security, the mobile development process, architecture design and technology selection, mobile application development hurdles, testing mobile applications.

References:

1. 
   Reza B’Far, Mobile Computing Principles, Cambridge University Press, 2005.
   
2. 
   U. Hansmann, L. Merk, M. S. Nicklous and T. Stober, Principles of Mobile Computing, 2/e, Springer, 2003.
   
3. 
   Harold Davis, Anywhere Computing with Laptops: Making Mobile Easier, O’Reilly, 2005
   
4. 
   I. Stojmenovic, Handbook of wireless and Mobile computing, Wiley, 2002.
   
5. 
   Schiller J., Mobile Communications, 2/e, Pearson Education, 2003.
   

CSU 361 IMAGE PROCESSING

Pre-requisite: CSU 201 Discrete Computational Structures / MEG 501 Discrete Mathematics

L	T	P	C
3	0	0	3

Module I

Introduction - digital image representation - fundamental steps in image processing - elements of digital image processing systems - digital image fundamentals - elements of visual perception - a simple image model - sampling and quantization - basic relationship between pixels - image geometry - image transforms - introduction to Fourier transform - discrete Fourier transform - some properties of 2-fourier transform (DFT) - the FFT - other separable image transforms - hotelling transform

 

Module II

Image enhancement - point processing - spatial filtering - frequency domain - color image processing - image restoration - degradation model - diagonalization of circulant and block circulant matrices - inverse filtering - least mean square filter

 

Module III

Image compression - image compression models - elements of information theory - error-free compression - lossy compression - image compression standards

 

Module IV

Image reconstruction from projections - basics of projection - parallel beam and fan beam projection - method of generating projections - Fourier slice theorem - filtered back projection algorithms - testing back projection algorithms

 

References

1. Rafael C., Gonzalez & Richard E. Woods, Digital Image Processing, Addison Wesley, New Delhi

2. Rosenfeld A. & Kak A.C., Digital Picture Processing, Academic Press

3. Jain A.K, Fundamentals of Digital Image Processing, Prentice Hall, Englewood Cliffs, N.J.

4.   Schalkoff R. J., Digital Image Processing and Computer Vision, John Wiley and Sons, New York

5.   Pratt W.K., Digital Image Processing, 2^nd edition, John Wiley and Sons, New York

 

CSU 362 PATTERN RECOGNITION

Pre-requisite: CSU 203 Data Structures and Algorithms

L	T	P	C
3	0	0	3

 

Module I

Introduction - introduction to statistical - syntactic and descriptive approaches - features and feature extraction - learning - Bayes Decision theory - introduction - continuous case - 2-category classification - minimum error rate classification - classifiers - discriminant functions - and decision surfaces - error probabilities and integrals - normal density - discriminant functions for normal density

 

Module II

Parameter estimation and supervised learning - maximum likelihood estimation - the Bayes classifier - learning the mean of a normal density - general bayesian learning - nonparametric technic - density estimation - parzen windows - k-nearest neighbour estimation - estimation of posterior probabilities - nearest - neighbour rule - k-nearest neighbour rule

 

Module III

Linear discriminant functions - linear discriminant functions and decision surfaces - generalised linear discriminant functions - 2-category linearly separable case - non-separable behaviour - linear programming procedures - clustering - data description and clustering - similarity measures - criterion functions for clustering

 

Module IV

Syntactic approach to PR - introduction to pattern grammars and languages - higher dimensional grammars - tree, graph, web, plex, and shape grammars - stochastic grammars - attribute grammars - parsing techniques - grammatical inference

 

References

1. 
   Duda & Hart P.E, Pattern Classification And Scene Analysis, John Wiley and Sons, NY
   
2. 
   Gonzalez R.C. & Thomson M.G., Syntactic Pattern Recognition - An Introduction, Addison Wesley
   
3. 
   Fu K.S., Syntactic Pattern Recognition And Applications, Prentice Hall, Englewood cliffs, N.J.
   

CSU 364 NATURAL LANGUAGE PROCESSING
Pre-requisite: CSU 203 Data Structures and Algorithms

L	T	P	C
3	0	0	3

Module I (8 hours)

Introduction to Natural Language Processing, Different Levels of language analysis, Representation and understanding, Linguistic background.

Module II (12 hours)

Grammars and parsing, Top down and Bottom up parsers, Transition Network Grammars, Feature systems and augmented grammars, Morphological analysis and the lexicon, Parsing with features, Augmented Transition Networks.

Module III (12 hours)

Grammars for natural language, Movement phenomenon in language, Handling questions in context free grammars, Hold mechanisms

in ATNs, Gap threading, Human preferences in parsing, Shift reduce parsers, Deterministic parsers, Statistical methods for

Ambiguity resolution

Module IV (10 hours)

Semantic Interpretation, word senses and ambiguity, Basic logical form language, Encoding ambiguity in logical from, Thematic roles, Linking syntax and semantics, Recent trends in NLP.

References:

1. James Allen, Natural Language Understanding, Second Edition, 2003, Pearson Education.

2. D Juraffsky, J H Martin, Speech and Language Processing, Pearson Education

CSU 373 COMPUTATIONAL COMPLEXITY
Pre-requisite: CSU 305 Theory of Computation

L	T	P	C
3	0	0	3

Module I (10 hours)

Review of Complexity Classes, NP and NP Completeness, Space Complexity, Hierarchies, Circuit satisfiability, Karp Lipton Theorem.

Module II (10 hours)

Randomized Computation, PTMs, Examples, Important BPP Results, Randomized Reductions, Counting Complexity, Permanent’s and Valiant’s Theorem

Module III (10 hours)

Review of Interactive Proofs, Lowerbounds: Randomized Decision Trees, Yao’s minimax lemma, Communication Complexity, Multiparty Communication Complexity

Module IV (12 hours)

Advanced Topics: Selected topics from Average case Complexity, Levin’s theory, Polynomial time samplability, random walks, expander graphs, derandomization, Error Correcting Codes, PCP and Hardness of Approximation, Quantum Computation

 

References:

1. Papadimtriou C. H.., Computational Complexity, Addison Wesley, First Edition, 1993.

2.` Motwani R, Randomized Algorithms, Cambridge University Press, 1995.

3. Vazirani V., Approximation Algorithms, Springer, First Edition, 2004.

4. 
   Mitzenmacher M and Upfal E., Probability and Computing, Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
   
5. 
   Arora S and Boaz B, Computational Complexity, (Web Draft) http://www.princeton.edu/theory/complexity
   

CSU 471 ADVANCED TOPICS IN ALGORITHMS
Pre-requisite: CSU 301 Design and Analysis of Algorithms

L	T	P	C
3	0	0	3

Module I (10 hours)

Discrete Probability: Probability, Expectations, Tail Bounds, Chernoff Bound, Markov Chains. Random Walks. Review of Generating functions, Exponential Generating Functions. Review of Recurrence Relations – both homogeneous and non-homogeneous of first and second degrees. Review of Analysis of recursive and non recursive algorithms.

Module II (12 hours)

Randomized Algorithms, Moments and Deviations. Tail Inequalities. Randomized selection.

Las Vegas Algorithms. Monte Carlo Algorithms. Parallel and Distributed Algorithms. Concept of De-Randomization and techniques.

Module III (10 hours)

Complexity: Probabilistic Complexity Classes, Proof Theory. Interactive Proof Systems.

Examples of probabilistic algorithms. Proving that an algorithm is correct 'Almost sure'.
Complexity analysis of probabilistic algorithms . The complexity classes PP and BPP

Module IV (10 hours)

Kolmogorv Complexity – basic concepts. Models of Computation. Applications to analysis of algorithms. Lower bounds. Relation to Entropy. Kolmogorov complexity and universal probability.

Godel's Incompleteness Theorem. Different Interpretations. Chatin’s Proof for Godel’s Theorem.
References:

1. R. Motwani and P. Raghavan, Randomized Algorithms, Cambrdige University Press, 1995

2. C. H. Papadimitriou, Computational Complexity, Addison Wesley, 1994

3. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer verlag N.Y, 1992

CSU 472 QUANTUM COMPUTATION
Pre-requisites: CSU 203 Data Structures and Algorithms, CSU 301 Design and Analysis of Algorithms

L	T	P	C
3	0	0	3

Module I (12 hours)

Review of Linear Algebra. The postulates of quantum mechanics. Review of Theory of Finite Dimensional Hilbert Spaces and Tensor Products.

Module II (8 hours)

Models of computation – Turing machines. Quantifying resources. Computational complexity and the various complexity classes. Models for Quantum Computation. Qubits. Single and multiple qubit gates. Quantum circuits. Bell states. Single qubit operations. Controlled operations and measurement. Universal quantum gates.

Module III (12 hours)

Quantum Algorithms – Quantum search algorithm - geometric visualization and performance. Quantum

search as a quantum simulation. Speeding up the solution of NP Complete problems. Quantum search as an

unstructured database. Grover’s and Shor’s Algorithms.

Module IV (10 hours)

Introduction to Quantum Coding Theory. Quantum error correction. The Shor code. Discretization of errors, Independent error models, Degenerate Codes. The quantum Hamming bound. Constructing quantum codes – Classical linear codes, Shannon entropy and Von Neuman Entropy.

References:

1. Nielsen M.A. and I.L. Chauang, Quantum Computation and Quantum Information,

Cambridge University Press, 2002.

2. Gruska, J. Quantum Computing, McGraw Hill, 1999.

3. Halmos, P. R. Finite Dimensional Vector Spaces, Van Nostrand, 1958.

CSU 305 THEORY OF COMPUTATION
Pre-requisite: CSU 211 Formal Languages and Automata

L	T	P	C
3	0	0	3

Module I (8 hours)

Undecidability: Recursive and Recursively enumerable sets, Undecidability, Rice theorems.

Module II (16 hours)

Complexity: P, NP, PSPACE and Log space. Reductions and Completeness. Hierarchy theorems, Probabilistic classes, BPP, EXP time and space complexity classes.

Module III (8 hours)

Logic: Propositional logic, compactness, decidability, Resolution.

Module IV (10 hours)

Undecidability in first order predicate calculus, Resolution. Gödel’s incompleteness theorem

Text Books:
1. M. Sipser, Introduction to the Theory of Computation, Thomson, 2001.

2. C. H. Papadimitriou., Computational Complexity, Addison Wesley, 1994.

References:

1. 
   C. H. Papadimitriou, H. Lewis., Elements of Theory of Computation, Prentice Hall, 1981.
   
2. 
   J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation, Narosa, 1989.
   
3. 
   J. C. Martin, Introduction to Languages and the Theory of Computation, Mc Graw Hill, 2002.
   
4. 
   M. R. Garey and D. S. Johnson. Computers & Intractability, W. H. Freeman & Co., San Farnisco, 1979.
   

CSU 315 COMPUTER HARDWARE

Prerequisite: CSU 202 Logic Design

L	T	P	C
3	0	0	3

Module I (8 Hours)

PC hardware: motherboard, memory SDRAM, RDRAM Adapters – graphic adapter, network adapter. Controllers, floppy and hard disk controllers, streamers and other drives, Interfaces - parallel and serial interfaces, keyboard, mice and other rodents, the power supply, operating system, BIOS, and memory organization. 8086/8088 Hardware specification: clock generator, bus buffering and latching, bus timing, ready and wait states, minimum and maximum mode operations. Features of Pentium IV processor



Module II (12 Hours)

Microprocessor architecture: real mode and protected mode memory addressing, memory paging. Addressing modes: data addressing, program memory addressing, stack memory addressing. Data movement instructions, Arithmetic and logic instructions, Program control instructions, Programming the microprocessor: modular programming, using keyboard and display, data conversions, disk files, interrupt hooks, using assembly language with C/C++.

 

Module III (13 Hours)

Memory interface: memory devices, address decoding, 16 bit (8086), 32 bit (80486) and 64 bit (Pentium) ,Hardware architecture for embedded systems-processor-memory-latches and buffers-display unit-16 and 32 bit processors. Memory interfaces, dynamic RAM. I/O interface: port address decoding, PPI, 8279 interface, 8254 timer interface, 16550 UART interface, ADC/DAC interfaces.

 

Module IV (9 Hours)

Interrupts: interrupt processing, hardware interrupts, expanding the interrupt, 8259A programmable interrupt controller. DMA: DMA operation, 8237 DMA controller, shared bus operation, disk memory systems, video displays.

Bus interface: ISA bus, EISA and VESA buses, PCI bus.

 

References:

1. B. B. Brey, The Intel Microprocessors 8086 to Pentium: Architecture, Programming and Interface, 6/e,

Prentice Hall of India, New Delhi, 2003.

2. Programming for embedded systems Dream Software team , Willey 2002

3. H. P. Messmer, The Indispensable PC Hardware Book, 3/e, Addison Wesley, 1997.

4. A. K. Ray, and K. M. Bhurchandi, Advanced Microprocessors and Peripherals, Tata McGraw Hill, 2000.

5. D. V. Hall, Microprocessors and Interfacing: Programming and Hardware, 2/e, Tata McGraw Hill, New Delhi, 1992.

6. K. Miller, An Assembly Language Introduction to Computer Architecture using the Intel Pentium, Oxford University

Press, 1999.

7. S. J. Bigelow, Troubleshooting, Maintaining, and Repairing PCs, 2/e, Tata McGraw Hill, New Delhi, 1999.