Pigeon Hole Principle and its applications. Discrete Probability. Concept of Conditional and Joint Probability. Birthday Paradox problem.
Module II (8 Hours)
Generating Functions, Partitions of Integers. The Exponential Generating Functions.
Recurrence Relations .The First-Order Linear Recurrence Relation. The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients. The Non homogeneous Recurrence Relation.
Module III(12 Hours)
Graphs: Introduction to Graphs, Terminology and Representation. Connectivity. Euler and Hamilton Paths
Shortest Path Problems, Modeling problems like Knight's tour and TSP. Graph Coloring and Chromatic Polynomials. Planarity.
Module IV(10 Hours)
Network Flows, Transport Networks. Labeling Algorithm and the Max-Flow Min-Cut Theorem. Combinatorial Implications of the Max-Flow Min-Cut Theorem. Matching Theory. Stable Marriage problem.
1. Grimaldi R. P. Discrete and Combinatorial Mathematics, 5/e, Addison Wesley, 2002.
2. Thomas Koshy. Discrete Mathematics with Applications, Academic Press, Elsevier, 2004.
3. Kenneth H Rosen. Discrete Mathematics and its Applications. McGraw Hill, 2000.
4. Ravindra K. K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
Number Systems and codes, Boolean algebra: postulates and theorems, constants, variables and functions, switching algebra, Boolean functions and logical operations, Karnaugh map: prime cubes, minimum sum of products and product of sums, Quine-McClusky algorithm, Combinational Logic: analysis and design of combinational logic circuits, parallel adders and look-ahead adders, comparators, decoders and encoders, code conversion, multiplexers and demultiplexers, parity generators and checkers, ROMs,
Module II(10 + 5 Hours)
PLAs, .PLA minimization, PLA folding, design for testability, Counters and shift registers: excitation tables, ripple counters, synchronous counters, up-down counters, design of sequential circuits, shift registers and their applications. Clock mode sequential machines.
Module III (11 + 10 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 IV (11 + 8 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, Interrupts- Interrupt controller, DMA Controller.
N. N. Biswas, Logic Design Theory, Prentice Hall of India, New Delhi, 1993.
T. L. Floyd, Digital Fundamentals, 3/e, Universal Book Stall, New Delhi, 1986.
3.B. B. Brey, The Intel Microprocessors 8086 to Pentium: Architecture, Programming and Interface, 6/e,
5. H. P. Messmer, The Indispensable PC Hardware Book, 3/e, Addison Wesley, 1997.
6. A. K. Ray, and K. M. Bhurchandi, Advanced Microprocessors and Peripherals, Tata McGraw Hill, 2000.
7. D. V. Hall, Microprocessors and Interfacing: Programming and Hardware, 2/e, Tata McGraw Hill, New Delhi, 1992.
CSU 230 PROGRAM DESIGN Pre-requisites: CSU 101 Computer Programming, Knowledge of Graphs and Trees
Module1: (10 + 5 Hours)
Review of Programming Constructs- Conditional and Iterative constructs, Data types, Control Structures, Functions, Parameter passing- calling conventions, Recursion, Asymptotic notation for complexity analysis.
Module2: (11 + 12 Hours )
Pointers and dynamic memory allocation, Abstract Data Types, Lists, Stacks, Queues, Trees, Search Trees and traversal algorithms, Heaps and Priority queues.
Module3: .(11 + 7 Hours )
Searching - Linear and Binary, Sorting- Insertion and Selection sorting, Divide an conquer, Quick sort, Merge Sort, Heap Sort, External Sorting.
Module4: (10 + 4 Hours )
Memory Management, Garbage collection algorithms, , Storage allocation for objects with mixed sizes, Buddy systems, Storage compaction.
Aho A.V., Hopcroft J.E., and Ullman J.D., Data Structures and Algorithms, Pearson Education, New Delhi, 1983.
Cormen T.H., Leiserson C.E, Rivest R.L. and Stein C, Introduction to Algorithms, Prentice Hall India, New Delhi, 2004
Sahni S., Data Structures, Algorithms, and Applications in C++, Mc Graw Hill, Singapore, 1998.
Wirth N., Algorithms +Data Structures = Programs, Prentice Hall India, New Delhi, 1976.