computer science syllabus
university: anna university
regulation: 2004
B.E Cse Third Sem Syllabus:
SEMESTER III
(Applicable to the students admitted from the Academic year 2006 – 2007 onwards)
| Code No. | Course Title | L | T | P | M |
THEORY | |||||
| MA1201 | Mathematics III | 3 | 1 | 0 | 100 |
| CS1151 | Data Structures | 3 | 1 | 0 | 100 |
| CS1202 | Digital Principles and Systems Design | 3 | 1 | 0 | 100 |
| CS1203 | System Software | 3 | 0 | 0 | 100 |
| CS1204 | Object Oriented Programming | 3 | 0 | 0 | 100 |
| CY1201 | 3 | 0 | 0 | 100 | |
PRACTICAL | |||||
| CS1205 | Object Oriented Programming Lab | 0 | 0 | 3 | 100 |
| CS1206 | Digital Lab | 0 | 0 | 3 | 100 |
| CS1152 | Data Structures Lab | 0 | 0 | 3 | 100 |
MA1201 Mathematics III 3 1 0 100
Aim
The course aims to develop the skills of the students in the areas of boundary value problems and transform techniques. This will be necessary for their effective studies in a large number of engineering subjects like heat conduction, communication systems, electro-optics and electromagnetic theory. The course will also serve as a prerequisite for post graduate and specialized studies and research.
Objectives
At the end of the course the students would
· Be capable of mathematically formulating certain practical problems in terms of partial differential equations, solve them and physically interpret the results.
· Have gained a well founded knowledge of Fourier series, their different possible forms and the frequently needed practical harmonic analysis that an engineer may have to make from discrete data.
· Have obtained capacity to formulate and identify certain boundary value problems encountered in engineering practices, decide on applicability of the Fourier series method of solution, solve them and interpret the results.
· Have grasped the concept of expression of a function, under certain conditions, as a double integral leading to identification of transform pair, and specialization on Fourier transform pair, their properties, the possible special cases with attention to their applications.
· Have learnt the basics of Z – transform in its applicability to discretely varying functions, gained the skill to formulate certain problems in terms of difference equations and solve them using the Z – transform technique bringing out the elegance of the procedure involved.
UNIT I PARTIAL DIFFERENTIAL EQUATIONS 9 + 3
Formation of partial differential equations by elimination of arbitrary constants and arbitrary functions – Solution of standard types of first order partial differential equations – Lagrange’s linear equation – Linear partial differential equations of second and higher order with constant coefficients.
UNIT II Fourier Series 9 + 3
Dirichlet’s conditions – General Fourier series – Odd and even functions – Half range sine series – Half range cosine series – Complex form of Fourier Series – Parseval’s identify – Harmonic Analysis.
UNIT III Boundary value problems 9 + 3
Classification of second order quasi linear partial differential equations – Solutions of one dimensional wave equation – One dimensional heat equation – Steady state solution of two-dimensional heat equation (Insulated edges excluded) – Fourier series solutions in Cartesian coordinates.
UNIT IV Fourier Transform 9 + 3
Fourier integral theorem (without proof) – Fourier transform pair – Sine and
Cosine transforms – Properties – Transforms of simple functions – Convolution theorem – Parseval’s identity.
Cosine transforms – Properties – Transforms of simple functions – Convolution theorem – Parseval’s identity.
UNIT V Z -TRANSFORM AND DIFFERENCE Equations 9 + 3
Z-transform - Elementary properties – Inverse Z – transform – Convolution theorem -Formation of difference equations – Solution of difference equations using Z - transform.
TUTORIAL 15
TOTAL : 60
Text Books
1. Grewal, B.S., “Higher Engineering Mathematics”, Thirty Sixth Edition, Khanna Publishers, Delhi
2. Kandasamy, P., Thilagavathy, K., and Gunavathy, K., “Engineering Mathematics Volume III”, S. Chand & Company ltd., New Delhi
3. Wylie C. Ray and Barrett Louis, C., “Advanced Engineering Mathematics”, Sixth Edition, McGraw-Hill, Inc., New York
ReferenceS
1. Andrews, L.A. , and Shivamoggi B.K., “Integral Transforms for Engineers and Applied Mathematicians”, Macmillen , New York
2. Narayanan, S., Manicavachagom Pillay, T.K. and Ramaniah, G., “Advanced Mathematics for Engineering Students”, Volumes II and III, S. Viswanathan (Printers and Publishers) Pvt. Ltd. Chennai, 2002.
3. Churchill, R.V. and Brown, J.W., “Fourier Series and Boundary Value Problems”, Fourth Edition, McGraw-Hill Book Co., Singapore
CS1151 DATA STRUCTURES 3 1 0 100
AIM
To provide an in-depth knowledge in problem solving techniques and data structures.
OBJECTIVES
· To learn the systematic way of solving problems
· To understand the different methods of organizing large amounts of data
· To learn to program in C
· To efficiently implement the different data structures
· To efficiently implement solutions for specific problems
UNIT I PROBLEM SOLVING 9
Problem solving – Top-down Design – Implementation – Verification – Efficiency – Analysis – Sample algorithms.
UNIT II LISTS, STACKS AND QUEUES 8
Abstract Data Type (ADT) – The List ADT – The Stack ADT – The Queue ADT
UNIT III TREES 10
Preliminaries – Binary Trees – The Search Tree ADT – Binary Search Trees – AVL Trees – Tree Traversals – Hashing – General Idea – Hash Function – Separate Chaining – Open Addressing – Linear Probing – Priority Queues (Heaps) – Model – Simple implementations – Binary Heap
UNIT IV SORTING 9
Preliminaries – Insertion Sort – Shellsort – Heapsort – Mergesort – Quicksort – External Sorting
UNIT V GRAPHS 9
Definitions – Topological Sort – Shortest-Path Algorithms – Unweighted Shortest Paths – Dijkstra’s Algorithm – Minimum Spanning Tree – Prim’s Algorithm – Applications of Depth-First Search – Undirected Graphs – Biconnectivity – Introduction to NP-Completeness
TUTORIAL 15
TOTAL : 60
TEXT BOOKS
1. R. G. Dromey, “How to Solve it by Computer” (Chaps 1-2), Prentice-Hall of India
2. M. A. Weiss, “Data Structures and Algorithm Analysis in C”, 2nd ed, Pearson Education Asia, 2002. (chaps 3, 4.1-4.4 (except 4.3.6), 4.6, 5.1-5.4.1, 6.1-6.3.3, 7.1-7.7 (except 7.2.2, 7.4.1, 7.5.1, 7.6.1, 7.7.5, 7.7.6), 7.11, 9.1-9.3.2, 9.5-9.5.1, 9.6-9.6.2, 9.7)
REFERENCES
1. Y. Langsam, M. J. Augenstein and A. M. Tenenbaum, “Data Structures using C”, Pearson Education Asia, 2004
2. Richard F. Gilberg, Behrouz A. Forouzan, “Data Structures – A Pseudocode Approach with C”, Thomson Brooks
3. Aho, J. E. Hopcroft and J. D. Ullman, “Data Structures and Algorithms”, Pearson education Asia , 1983.
CS1202 DIGITAL PRINCIPLES AND SYSTEM DESIGN 3 1 0 100
AIM
To provide an in-depth knowledge of the design of digital circuits and the use of Hardware Description Language in digital system design.
OBJECTIVES
· To understand different methods used for the simplification of Boolean functions
· To design and implement combinational circuits
· To design and implement synchronous sequential circuits
· To design and implement asynchronous sequential circuits
· To study the fundamentals of VHDL / Verilog HDL
UNIT I BOOLEAN ALGEBRA AND LOGIC GATES 8
Review of binary number systems - Binary arithmetic – Binary codes – Boolean algebra and theorems - Boolean functions – Simplifications of Boolean functions using Karnaugh map and tabulation methods – Logic gates
UNIT II COMBINATIONAL LOGIC 9
Combinational circuits – Analysis and design procedures - Circuits for arithmetic operations - Code conversion – Introduction to Hardware Description Language (HDL)
UNIT III DESIGN WITH MSI DEVICES 8
Decoders and encoders - Multiplexers and demultiplexers - Memory and programmable logic - HDL for combinational circuits
UNIT IV SYNCHRONOUS SEQUENTIAL LOGIC 10
Sequential circuits – Flip flops – Analysis and design procedures - State reduction and state assignment - Shift registers – Counters - HDL for sequential logic circuits, Shift registers and counters.
UNIT V ASYNCHRONOUS SEQUENTIAL LOGIC 10
Analysis and design of asynchronous sequential circuits - Reduction of state and flow tables – Race-free state assignment – Hazards.
TUTORIAL 15
TOTAL : 60
TEXT BOOKS
1. M.Morris Mano, “Digital Design”, 3rd edition, Pearson Education, 2002.
REFERENCES
1. Charles H.Roth, Jr. “Fundamentals of Logic Design”, 4th Edition, Jaico Publishing House, 2000.
1. Donald D.Givone, “Digital Principles and Design”, Tata McGraw-Hill, 2003.
CS1203 SYSTEM SOFTWARE 3 0 0 100
AIM
To have an understanding of foundations of design of assemblers, loaders, linkers, and macro processors.
OBJECTIVES
· To understand the relationship between system software and machine architecture.
· To know the design and implementation of assemblers
· To know the design and implementation of linkers and loaders.
· To have an understanding of macroprocessors.
· To have an understanding of system software tools.
UNIT I Introduction 8
System software and machine architecture – The Simplified Instructional Computer (SIC) - Machine architecture - Data and instruction formats - addressing modes - instruction sets - I/O and programming.
UNIT II Assemblers 10
Basic assembler functions - A simple SIC assembler – Assembler algorithm and data structures - Machine dependent assembler features - Instruction formats and addressing modes – Program relocation - Machine independent assembler features - Literals – Symbol-defining statements – Expressions - One pass assemblers and Multi pass assemblers - Implementation example - MASM assembler.
UNIT III Loaders and Linkers 9
Basic loader functions - Design of an Absolute Loader – A Simple Bootstrap Loader - Machine dependent loader features - Relocation – Program Linking – Algorithm and Data Structures for Linking Loader - Machine-independent loader features - Automatic Library Search – Loader Options - Loader design options - Linkage Editors – Dynamic Linking – Bootstrap Loaders - Implementation example - MSDOS linker.
UNIT IV Macro Processors 9
Basic macro processor functions - Macro Definition and Expansion – Macro Processor Algorithm and data structures - Machine-independent macro processor features - Concatenation of Macro Parameters – Generation of Unique Labels – Conditional Macro Expansion – Keyword Macro Parameters-Macro within Macro-Implementation example - MASM Macro Processor – ANSI C Macro language.
UNIT V SYSTEM SOFTWARE TOOLS 9
Text editors - Overview of the Editing Process - User Interface – Editor Structure. - Interactive debugging systems - Debugging functions and capabilities – Relationship with other parts of the system – User-Interface Criteria.
TOTAL : 45
TEXT BOOK
1. Leland L. Beck, “System Software – An Introduction to Systems Programming”, 3rd Edition, Pearson Education Asia , 2000.
REFERENCES
1. D. M. Dhamdhere, “Systems Programming and Operating Systems”, Second Revised Edition, Tata McGraw-Hill, 1999.
2. John J. Donovan “Systems Programming”, Tata McGraw-Hill Edition, 1972.
AIM
To present the concept of object oriented programming and discuss the important elements of C++ and Java.
OBJECTIVES
Since C++ and Java play a predominant role in software development it is felt that the following objectives can be achieved after studying this subject.
i) Understand the concepts of Object oriented Programming.
ii) Write simple applications using C++ and Java.
iii) Compare and contrast features of C++ and Java.
UNIT I INTRODUCTION 8
Object-oriented paradigm, elements of object oriented programming – Merits and demerits of OO methodology – C++ fundamentals – data types, operators and expressions, control flow, arrays, strings, pointers and functions.
UNIT II PROGRAMMING IN C++ 10
Classes and objects – constructors and destructors, operator overloading – inheritance, virtual functions and polymorphism
UNIT III FILE HANDLING 9
C++ streams – console streams – console stream classes-formatted and unformatted console I/O operations, manipulators - File streams - classes file modes file pointers and manipulations file I/O – Exception handling
UNIT IV JAVA INTRODUCTION 9
An overview of Java, data types, variables and arrays, operators, control statements, classes, objects, methods – Inheritance.
UNIT V JAVA PROGRAMMING 9
Packages and Interfaces, Exception handling, Multithreaded programming, Strings, Input /Output.
TOTAL : 45
TEXT BOOKS
1. K.R.Venugopal, Rajkumar Buyya, T.Ravishankar, "Mastering C++", TMH, 2003 (Unit I, Unit II, Unit III)
2. Herbert Schildt, "the Java 2 : Complete Reference", Fourth edition, TMH, 2002 (Unit IV, Unit-V)(Chapters 1-11,13,17)
REFERENCES
1. Ira Pohl, “Object oriented programming using C++”, Pearson Education Asia, 2003
2. Bjarne Stroustrup, “The C++ programming language”, Addison Wesley, 2000
3. John R.Hubbard, “Progranning with C++”, Schaums outline series, TMH, 2003
4. H.M.Deitel, P.J.Deitel, “Java : how to program”, Fifth edition, Prentice Hall of India private limited.
5. E.Balagurusamy “ Object Oriented Programming with C++”, TMH 2/e
AIM
The aim of this course is to create awareness in every engineering graduate about the importance of environment, the effect of technology on the environment and ecological balance and make him/her sensitive to the environment problems in every professional endeavour that he/she participates.
OBJECTIVE
At the end of this course the student is expected to understand what constitutes the environment, what are precious resources in the environment, how to conserve these resources, what is the role of a human being in maintaining a clean environment and useful environment for the future generations and how to maintain ecological balance and preserve bio-diversity.
1. INTRODUCTION TO ENVIRONMENTAL STUDIES AND NATURAL
RESOURCES 10
Definition, scope and importance – Need for public awareness – Forest resources: Use and over-exploitation, deforestation, case studies. Timber extraction, mining, dams and their effects on forests and tribal people – Water resources: Use and over-utilization of surface and ground water, floods, drought, conflicts over water, dams-benefits and problems – Mineral resources: Use and exploitation, environmental effects of extracting and using mineral resources, case studies – Food resources: World food problems, changes caused by agriculture and overgrazing, effects of modern agriculture, fertilizer-pesticide problems, water logging, salinity, case studies – Energy resources: Growing energy needs, renewable and non renewable energy sources, use of alternate energy sources. case studies – Land resources: Land as a resource, land degradation, man induced landslides, soil erosion and desertification – Role of an individual in conservation of natural resources – Equitable use of resources for sustainable lifestyles.
Field study of local area to document environmental assets – river / forest / grassland / hill / mountain.
2. ECOSYSTEMS AND BIODIVERSITY 14
Concept of an ecosystem – Structure and function of an ecosystem – Producers, consumers and decomposers – Energy flow in the ecosystem – Ecological succession – Food chains, food webs and ecological pyramids – Introduction, types, characteristic features, structure and function of the (a) Forest ecosystem (b) Grassland ecosystem (c) Desert ecosystem (d) Aquatic ecosystems (ponds, streams, lakes, rivers, oceans, estuaries) – Introduction to biodiversity – Definition: genetic, species and ecosystem diversity – Biogeographical classification of India – Value of biodiversity: consumptive use, productive use, social, ethical, aesthetic and option values – Biodiversity at global, National and local levels – India as a mega-diversity nation – Hot-spots of biodiversity – Threats to biodiversity: habitat loss, poaching of wildlife, man-wildlife conflicts – Endangered and endemic species of India – Conservation of biodiversity: In-situ and Ex-situ conservation of biodiversity.
Field study of common plants, insects, birds
Field study of simple ecosystems – pond, river, hill slopes, etc.
3. ENVIRONMENTAL POLLUTION 8
Definition – Causes, effects and control measures of: (a) Air pollution (b) Water pollution (c) Soil pollution (d) Marine pollution (e) Noise pollution (f) Thermal pollution (g) Nuclear hazards – Soil waste management: Causes, effects and control measures of urban and industrial wastes – Role of an individual in prevention of pollution – Pollution case studies – Disaster management: floods, earthquake, cyclone and landslides.
Field study of local polluted site – Urban / Rural / Industrial / Agricultural.
4. SOCIAL ISSUES AND THE ENVIRONMENT 7
From unsustainable to sustainable development – Urban problems related to energy – Water conservation, rain water harvesting, watershed management – Resettlement and rehabilitation of people; its problems and concerns, case studies – Environmental ethics: Issues and possible solutions – Climate change, global warming, acid rain, ozone layer depletion, nuclear accidents and holocaust, case studies. – Wasteland reclamation – Consumerism and waste products – Environment production act – Air (Prevention and Control of Pollution) act – Water (Prevention and control of Pollution) act – Wildlife protection act – Forest conservation act – Issues involved in enforcement of environmental legislation – Public awareness.
5. HUMAN POPULATION AND THE ENVIRONMENT 6
Population growth, variation among nations – Population explosion – Family welfare programme – Environment and human health – Human rights – Value education – HIV / AIDS – Women and child welfare – Role of information technology in environment and human health – Case studies.
L = 45 Total = 45
TEXT BOOKS
1. Gilbert M.Masters, ‘Introduction to Environmental Engineering and Science’, 2nd edition,
Pearson Education, 2004.
2. T.G. Jr. Miller, ‘Environmental Science’, Wadsworth Publishing Co.
3. C. Townsend, J. Harper and Michael Begon, ‘Essentials of Ecology’, Blackwell Science.
4. R.K. Trivedi and P.K. Goel, ‘Introduction to Air Pollution’, Techno-Science Publications.
REFERENCE BOOKS
1. Bharucha Erach, ‘The Biodiversity of India’, Mapin Publishing Pvt. Ltd., Ahmedabad India
2. R.K. Trivedi, ‘Handbook of Environmental Laws, Rules, Guidelines, Compliances and Standards’, Vol. I and II, Enviro Media.
3. Cunningham, W.P. Cooper, T.H. Gorhani, ‘Environmental Encyclopedia’, Jaico Publ., House, Mumbai, 2001.
4. K.D. Wager, ‘Environmental Management’, W.B. Saunders Co., Philadelphia , USA
CS1205 OBJECT ORIENTED PROGRAMMING LAB EXPERIMENTS 0 0 3 100
C++
1. Programs Using Functions
- Functions with default arguments
- Implementation of Call by Value, Call by Address and Call by Reference
2. Simple Classes for understanding objects, member functions and Constructors
- Classes with primitive data members
- Classes with arrays as data members
- Classes with pointers as data members – String Class
- Classes with constant data members
- Classes with static member functions
3. Compile time Polymorphism
- Operator Overloading including Unary and Binary Operators.
- Function Overloading
4. Runtime Polymorphism
- Inheritance
- Virtual functions
- Virtual Base Classes
- Templates
5. File Handling
- Sequential access
- Random access
JAVA
6. Simple Java applications
- for understanding reference to an instance of a class (object), methods
- Handling Strings in Java
7. Simple Package creation.
- Developing user defined packages in Java
8. Interfaces
- Developing user-defined interfaces and implementation
- Use of predefined interfaces
9. Threading
- Creation of thread in Java applications
- Multithreading
10. Exception Handling Mechanism in Java
- Handling pre-defined exceptions
- Handling user-defined exceptions
CS1206 DIGITAL LABORATORY 0 0 3 100
LIST OF EXPERIMENTS
1. Verification of Boolean theorems using digital logic gates
2. Design and implementation of combinational circuits using basic gates for arbitrary functions, code converters, etc.
3. Design and implementation of 4-bit binary adder / subtractor using basic gates and MSI devices
4. Design and implementation of parity generator / checker using basic gates and MSI devices
5. Design and implementation of magnitude comparator
6. Design and implementation of application using multiplexers
7. Design and implementation of Shift registers
8. Design and implementation of Synchronous and Asynchronous counters
9. Coding combinational circuits using Hardware Description Language (HDL software required)
10. Coding sequential circuits using HDL (HDL software required)
CS1152 DATA STRUCTURES LAB 0 0 3 100
AIM
To teach the principles of good programming practice and to give a practical training in writing efficient programs in C
OBJECTIVES
· To teach the students to write programs in C
· To implement the various data structures as Abstract Data Types
· To write programs to solve problems using the ADTs
Implement the following exercises using C:
1. Array implementation of List Abstract Data Type (ADT)
2. Linked list implementation of List ADT
3. Cursor implementation of List ADT
4. Array implementations of Stack ADT
5. Linked list implementations of Stack ADT
The following three exercises are to be done by implementing the following source files
(a) Program for ‘Balanced Paranthesis’
(b) Array implementation of Stack ADT
(c) Linked list implementation of Stack ADT
(d) Program for ‘Evaluating Postfix Expressions’
An appropriate header file for the Stack ADT should be #included in (a) and (d)
6. Implement the application for checking ‘Balanced Paranthesis’ using array implementation of Stack ADT (by implementing files (a) and (b) given above)
7. Implement the application for checking ‘Balanced Paranthesis’ using linked list implementation of Stack ADT (by using file (a) from experiment 6 and implementing file (c))
8. Implement the application for ‘Evaluating Postfix Expressions’ using array and linked list implementations of Stack ADT (by implementing file (d) and using file (b), and then by using files (d) and (c))
9. Queue ADT
10. Search Tree ADT - Binary Search Tree
11. Heap Sort
12. Quick Sort