I MCA I Semester Syllabus

Mathematical Foundations

Unit I
Mathematical logic – normal forms – theory of inference – predicate calculus – equivalence relation – recursion.
Unit II
Semi groups – monoids - groups – costs & legrange’s theorem – normal sub groups – homomorphism - Rings – fields – partially ordered sets – lattices – Boolean algebra.
Unit III
Finite state automata – non deterministic finite state automata – equivalence of FA & NFA – pumping lemma – properties of regular sets
Unit IV
Phrase structure grammar – context free languages and PDA – derivation trees – Chomsky and greibach normal forms – equivalence of PDAs and CFLs
Unit V
Turing machines – basic model – techniques for TM construction – Enhancements of TM characteristics – Recursive sets & undesirability - rice theorem.
Text Book
Discrete Mathematics, M.K.Venkatraman , N.Sridharan, Chandrasekaran, the national publishing company 2000
Reference:
1. Discrete Mathematical structures with applications to computer science, Trembley and manohar, McGraw Hill 1997.
2.Introdunction to automata theory , languages and computation , J.E Hopcroft and J.D.Ullman, Narosa publishing house, 1989.
3.Modern applied algebra, brikth off bartee , CBS publisher 1987

Digital Logic and computer Design
Unit I
Binary systems: Digital computers and digital system – binary number base conversion – octal and hexadecimal numbers – complements – binary codes – binary storage and registers – binary logic –integrated circuits Boolean algebra and logic gates: Basic definitions – axiomatic definition of Boolean algebra – basic theorems and properties of Boolean algebra – Boolean functions – canonical and standard forms – other logic operations – digital logic gates – IC digital logic families.

Unit II
Simplification of Boolean functions : map method – Two and three variable maps – four variables maps – five and six variable maps –product of sum simplifications – NAND and NOR implementations – other two level implementations – don’t care conditions – conditional logic : Introduction – design procedure – adders – sub tractors – code conversion – analysis procedure – multilevel NAND circuits – multilevel NOR circuits – XOR and equivalence functions

Unit III
Combinational logic with MSI and LSI : Introduction – binary parallel adder – decimal adder – magnitude comparator – decoders – multiplexer – read only memory – programmable logic array – concluding remarks sequential circuits – register counters and memory unit : Introduction – registers – shift registers – ripple counters – synchronous counters – timing sequences – memory unit

Unit IV:
Processor logic design : Introduction – processor organization – arithmetic logic unit – design of arithmetic circuit – design of logic circuit – design of arithmetic logic unit – status registers – design of shifters – processors unit – design of accumulator – control logic design : Introduction – organizational – hard –wired control – PLA control – micro program control – control of processor unit – Hard – wired control – PLA control – micro program sequences

Unit V
Computer design: Introduction –system of configuration – computer instructions – timing and control – execution of instructions – design of computer registers – design of control – computer console – microcomputer system design : Introduction – micro computer organization – micro processor organization
Text Book:
Digital Logic and computer design, M.Morris mano , prentice hall of India 2006
Reference
1. Digital principles & applications, Donald p Leach, albert paul malvino TMI
2. Computer organizations & architecture, wiliam stallings PHI 2008
3. Digital logic and computer organizations, V.Raja raman T. Rajaraman, T.Radha Krishnan PHI 2006


Programming in C
Unit I
Overview of C : History of C – importance of C – Basic structure of C – programming style – constants , variables and data types – declaration of variables, storage class – defining symbolic constants – declaring a variable as constant , volatile – overflow and underflow of data. Operators and expressions : arithmetic , relational, logical , assignment operators – increment and decrement operators, conditional operators, bitwise operators – special operators – arithmetic expressions – evaluation of expressions – precedence of arithmetic operators – type conversion in expressions – operator precedence and associatively – mathematical functions – managing i/o operations: reading and writing a character – formatted input , output. Decision making and branching: if statement, if…else statement – nesting of if … else statement – else if ladder – switch statement – the?: operator – go to statement

Unit II
The while statement – do statement – the for statement – jumps in loops
Unit III
Arrays : one dimensional array – declaration, initialization – two dimensional array – multidimensional array – dynamic arrays – initializations, strings : declaration, initialization and string variables – reading and writing string – arithmetic operations on strings – putting string together – comparison – string handling function – table of strings – features of string
Unit IV
User defined functions: need – multi function program – elements of user defined function – definition – return values and their types – function calls, declaration , category – all types of arguments and return values – nesting of functions – recursion – passing arrays – string to functions – scope visibility and life time of variables – multi file programs – Structures and unions : defining a structure – declaring structure variables – accessing structure members – initialization – copying and comparing – operations on individual members – arrays of structures – arrays within structures – structures within structures – structures and function – unions – size of structures – bit fields

Unit V
Pointers: accessing the address of a variable – declaring, initialization of pointer variables – accessing a variable through its pointer – chain of pointers – pointer expressions – pointer increment – and scale factors – pointer and arrays – pointers and character strings – array of pointers – pointer as function arguments – function returning pointers – pointers to functions – pointers and structures. Files defining, opening, closing a file. I/O operation on files – error handling during I/O operations – random access to file - command line arguments.
Text Book:
Programming in ANSI C. E.Balagurusamy, Tata Mcgraw Hill Publishing company 2008
Reference:
Programming with C (Schaum’s outline series) Gottfried, Tata McGraw Hill 2007
Data Structures
Unit I
Introduction and overview
Definitions – concept of data structures – overview of data structures – implementation of data structures
Arrays:
Definitions – Terminology – one dimensional array – multidimensional array – pointer arrays

Linked Lists
Definition – single linked lists – circular linked list – double linked list – circular double linked list – application of linked list – memory representation – boundary tag system – reallocation strategy – buddy system – compaction

Unit II

Stacks:
Introduction – definition – representation of stack – operation on stacks – applications of stack

Queues:
Introduction – definition – representation of queues – various queue structures – applications of queues

Unit III

Trees:
Basic terminologies – definition and concepts – representation of binary tree – operation of binary tree – types of binary trees

Unit IV

Graphs:
Introduction – graph terminologies – representation of Graphs – operation on Graphs – application on graph structures – BDD and its applications

Unit V
Tables: Rectangular tables – jagged tables – inverted tables – hash tables

Sets
Definition and terminologies – representation of sets – operation of sets – application of sets
Text Book
Classic data structures – D.samantha PHI 2008
Reference :

Lab 1 Programming with C
Write a C program
To find sum of digits of a number, to reverse a given number and check if it is a palindrome
To evaluate sine series and cosine series
To sort an array using bubble sort and insertion sort
To count the occurrences of a number in a sort
To solve quadratic equation using switch case
To do string operations
To find factorial value, Fibonacci, GCD value using recursion
To add, subtract and multiply two matrices
To find row wise sum of a matrix of order m x n
To perform binary search and linear search using function
To find NCR and NPR values using Function
To calculate mean, variance and standard deviation using function
To prepare pay bill – structure
To prepare mark sheet – structure
To perform inventory calculations – structure
Develop an application to manage records of your friends. the record contains friends ID, name, email address , telephone number
The application provides menu consists of
i. Listing of all friend information
ii. Insert new friends info (and save to the file)
iii. Search for a record of your friend ( by name)

To demonstrate the use of bitwise operators
to prepare mark sheet – File
To prepare EB bill – File
Interaction with keyboard – turn on the caps lock key
Interaction with video memory – fill the video memory with different colored ‘a’
draw a house using graphical functions
animate a picture
create a linked list and manipulate

Lab 2 Visual Programming Lab

Calculator (simple and scientific)
Tic tock game
paint brush (line, circle , fill color , free drawing with different color pane & different size)
Note Pad (File Open, close, save, font, font-style, font-size, find and replace)
Excel work sheet (using flex grid)
Use flex grid to represent calendar using two combo for month and year. Consider leap year
student information system ( add, delete , save, undo)
Inventory control system ( purchase , sales & stock report ) with bill printing facility
online exam ( user id, fixed level exam, multi level exam, multiple choice questions, result should be stored user wise)
Chatting application using Winsock