National Institute of Technology Calicut

CSU 401 COMPUTER ARCHITECTURE

Prerequisite: CSU 215 Computer Organization

L	T	P	Cr
3	0	2	4

Module I (11 + 5 Hours)
Fundamentals – Technology trend -performance measurement –Comparing and summarizing performance- quantitative principles of computer design –Amdahl’s law-Case studies. instruction set architectures – memory addressing- –type and size operand - encoding an instruction set - role of compilers - case study – MIPS 64 architecture – pipelining - pipeline hazards - data and control hazards - implementation issues – MIPS floating point pipeline-exception handling-Case study MIPSR 4000 pipeline.
Module II (11 + 7 Hours)

Instruction level parallelism - dynamic scheduling – Tomasulo’s algorithm- Score boarding-dynamic hardware prediction - multiple issue processor – multiple issue with dynamic scheduling-hardware based speculation- limitation of ILP-Case study P6 micro-architecture Introduction to multicore processors
Module III (10 + 10 Hours)
Static scheduling- loop unrolling-static branch prediction VLIW architecture- software pipelining-hardware support for exploring more parallelism at compile time-Case study IA 64 architecture.

Memory hierarchy design - reducing cache misses and miss penalty, reducing hit time - main memory organization - virtual memory and its protection - case study – Alpha 21264 memory hierarchy . Memory issues in multicore processor based systems

 

Module IV (10 + 6 Hours)
Multiprocessor and thread level parallelism- classification of parallel architecture-models of communication and memory architecture-Symmetric shared memory architecture-cache coherence protocols-distributed shared memory architecture-directory based cache coherence protocol- Memory consistency-relaxed consistency models multi threading- exploiting thread level parallelism multicore architecture

Simple networks - practical issues 

References

1. 
   Hennesy J. L. & Pattersen D. A., Computer Architecture: A Quantitative approach, 3/e, Harcourt Asia Pte Ltd. (Morgan Kaufman), Singapore
   
2. 
   Pattersen D. A. & Hennesy J. L., Computer Organisation and Design: The Hardware/ Software Interface, 3/e, Harcourt Asia Pte Ltd (Morgan Kaufman), Singapore
   

CSU 491 SEMINAR

Pre-requisite:NIL

L	T	P	Cr
0	0	3	1

Each student is expected to present a seminar on a topic of current relevance in computer science and engineering – they have to refer papers from standard journals like ACM, IEEE, JPDC, IEE etc. – at least three cross references must be used – the seminar report must not be the reproduction of the original paper.

CSU 498 PROJECT

Pre-requisite: CSU 321 Software Engineering

L	T	P	Cr
0	0	5	3

The project is for a duration of two semesters. Each student group (not more than 5 members in a group) is expected to develop a complete product. The design and development may include hardware and /or software. First part of the project is mainly for the design of the product. An interim report is to be submitted at the end of the semester. The assessment may be made individually and in groups.

CSU 363 COMPUTATIONAL INTELLIGENCE

Pre-requisite: CSU 203 Data Structures & Algorithms

L	T	P	Cr
3	0	0	3

 

Module I (12 Hours)

Artificial Intelligence: History and Applications, Production Systems,Structures and Strategies for state space search- Data driven and goal drivensearch, Depth First and Breadth First Search, DFS with Iterative Deepening,Heuristic Search- Best First Search, A* Algorithm, AO* Algorithm, ConstraintSatisfaction, Using heuristics in games- Minimax Search, Alpha BetaProcedure.

 

Module II (11 Hours)

 Knowledge representation - Propositional calculus, Predicate Calculus, Theorem proving by Resolution, Answer Extraction, AI Representational Schemes- Semantic Nets, Conceptual Dependency, Scripts, Frames, Introduction to Agent based problem solving.

Module III (11 Hours)

 Machine Learning- Symbol based and Connectionist, Social and Emergentmodels of learning, The Genetic Algorithm- Genetic Programming, Overview of Expert System Technology- Rule based Expert Systems, Introduction to Natural Language Processing.

Module IV (8 Hours)

 Languages and Programming Techniques for AI- Introduction to PROLOG and LISP, Search strategies and Logic Programming in LISP, Production System examples in PROLOG.

References

1. George F Luger, Artificial Intelligence- Structures and Strategies for Complex Problem Solving, 4/e, 2002, Pearson Education.

2. E. Rich, K.Knight, Artificial Intelligence, 2/e, Tata McGraw Hill

3. S Russel, P Norvig, Artificial Intelligence- A Modern Approach, 2/e, Pearson Education, 2002

3. Winston. P. H, LISP, Addison Wesley

4. Ivan Bratko, Prolog Programming for Artificial Intelligence, 3/e, Addison Wesley, 2000

CSU 499 PROJECT

Pre-requisite: CSU 321 Software Engineering

L	T	P	Cr
0	0	10	5

This is the second part of the project. This part is for the development, testing, and installation of the product. The product should have user manuals. A detailed report is to be submitted at the end of the semester. The assessment may be made individually and in groups.

PART II : ELECTIVE COURSES


CSU 339 ADVANCED DATA STRUCTURES
Pre-requisite: CSU 203 Data Structures and Algorithms

L	T	P	Cr
3	0	0	3

Module I (10 Hours)
Review of elementary data structures. Advanced Trees – Red Black Trees, AVL Trees, Optimal Binary Search Trees, Splay Trees.

 

Module II (10 Hours)

B Trees, Tries, Binary Heaps, Priority Queues, Binomial Heaps, Fibonacci Heaps.
Module III (10 Hours)

Disjoint set representation – Path compression algorithm – Graph algorithms, Connected components, topological sort, Minimum spanning tree, Algorithms of Kruskal and Prim,

Module IV (12 Hours)
Single-source shortest paths – Dijkstra's algorithm, Bellman-Ford Algorithm. All-Pairs shortest paths – Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs. Maximum Flow - Flow networks, Ford-Fulkerson Method.

 

References:

1. Cormen T.H., Leiserson C.E, and Rivest R.L., Introduction to Algorithms, Prentice Hall India, New Delhi, 1990.

2. Wirth N., Algorithms + Data Structures = Programs, Prentice Hall India, New Delhi, 1976.

3. Sartaj Sahni, Data Structures, Algorithms and Applications in C++, Universities Press, 2005.

CSU 358 COMMUNICATION AND INFORMATION THEORY
Pre-requisites: CSU 201 Discrete Computational Structures / MAG 501 Discrete Mathematics,

Knowledge of Probability Theory

L	T	P	Cr
3	0	0	3

Module I (10 Hours)

Entropy – Joint entropy and conditional entropy. Source Coding theorem – Shannon-Fano, Huffman Coding.

Mathematical properties of entropy function. Chain rules for entropy, relative entropy and mutual information. Efficiency of Shannon-Fano coding. Optimality of Huffman coding.
Module II (12 Hours)

Channel Models – Symmetric channels. Binary Symmetric Channel – Information – Channel Coding theorem – Review of associated mathematical background . Channel relationships. Uniform Channel. Converse of Shannon's theorem.

Module III (10 Hours)

Zero error cordes. Error Correcting Codes . Ideal observer decoding. Minimum distance decoding.

Maximum Likelihood decoding. Single Error Correction and Double Error Correction. Syndrome Decoding.
Module IV (10 Hours)

Linear Codes . Study of Repetition codes. Parity codes. Cyclic codes. Hamming code. Introduction to Golay code and Reed-Solomon codes. Establishing the bounds on a couple of these codes and the process of decoding them.

Reference:

5. 
   1. R. W. Hamming, Coding and Information Theory, Prentice Hall, 1986.
   
6. 
   2. T. Cover and J. Thomas, Elements of Information Theory, Wiley, 1991.
   
7. 
   3. P. Garret, The mathematics of coding theory, Pierson Education, 2005.
   

CSU 371 LOGIC FOR COMPUTER SCIENCE
Pre-requisite: CSU 305 Theory of Computation

L	T	P	Cr
3	0	0	3

Module I (11 Hours)

Propositional logic, syntax of propositional logic, main connective, semantics of propositional logic, truth tables and tautologies, tableaus, soundness theorem ,finished sets, completeness theorem,.
Module II (12Hours)

Predicate logic, syntax of predicate logic, free and bound variables, semantics of predicate logic,, graphs, tableaus, soundness theorem, finished sets, completeness theorem, equivalence relations, order relations, set theory.

Module III (14 Hours)

Linear time Temporal Logic(LTL), syntax of LTL, semantics of LTL, Buchi Automata, Buchi recognizable languages and their properties, Automata theoretic methods, Vardi-Wolper Construction, Satisfiability problem of LTLl, Model checking problem of LTL.

Module IV ( 6Hours)

Software Veification: Tools used for software verification.SPIN and SMV. Introduction to both tools. Method of verification by the tools.

References:

8. 
   1. Jerome Keisler H. Joel Robbin, Mathematical Logic and Computability, McGraw-Hill International Editions, 1996.
   
9. 
   2. Papadimitriou, C. H., Computational Complexity, Addison Wesley, 1994
   
10. 
    3. Gallier, J. H., Logic for Computer Science: Foundations of Automatic Theorem Proving,, Harper and Row, 1986.