2017 REGULATION

ANNA UNIVERSITY, CHENNAI

AFFILIATED INSTITUTIONS

B.E. COMPUTER SCIENCE AND ENGINEERING

REGULATIONS – 2017

CHOICE BASED CREDIT SYSTEM

III SEMESTER CURRICULUM AND SYLLABI

SEMESTER III

1

To extend student’s logical and mathematical maturity and ability to deal with abstraction.

To introduce most of the basic terminologies used in computer science courses and application of ideas to solve practical problems.

To understand the basic concepts of combinatorics and graph theory.

To familiarize the applications of algebraic structures.

To understand the concepts and significance of lattices and boolean algebra which are widely used in computer science and engineering.

UNIT I LOGIC AND PROOFS 12

Propositional logic – Propositional equivalences - Predicates and quantifiers – Nested quantifiers – Rules of inference - Introduction to proofs – Proof methods and strategy.

UNIT II COMBINATORICS 12

Mathematical induction – Strong induction and well ordering – The basics of counting – The pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear recurrence relations – Generating functions – Inclusion and exclusion principle and its applications

UNIT III GRAPHS 12

Graphs and graph models – Graph terminology and special types of graphs – Matrix representation of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths.

Algebraic systems – Semi groups and monoids - Groups – Subgroups – Homomorphism’s – Normal subgroup and cosets – Lagrange’s theorem – Definitions and examples of Rings and Fields.

Partial ordering – Posets – Lattices as posets – Properties of lattices - Lattices as algebraic systems – Sub lattices – Direct product and homomorphism – Some special lattices – Boolean algebra.

TOTAL: 60 PERIODS

OUTCOMES:

At the end of the course, students would:

Have knowledge of the concepts needed to test the logic of a program.

Have an understanding in identifying structures on many levels.

Be aware of a class of functions which transform a finite set into another finite set which relates to input and output functions in computer science.

Be aware of the counting principles.

Be exposed to concepts and properties of algebraic structures such as groups, rings and fields.

TEXTBOOKS:

1. Rosen, K.H., "Discrete Mathematics and its Applications", 7th Edition, Tata McGraw Hill Pub. Co. Ltd., New Delhi, Special Indian Edition, 2011.

2.Tremblay, J.P. and Manohar.R, " Discrete Mathematical Structures with Applications to Computer Science", Tata McGraw Hill Pub. Co. Ltd, New Delhi, 30th Reprint, 2011.

2

OUTCOMES:

On Completion of the course, the students should be able to:

 Simplify Boolean functions using KMap

 Design and Analyze Combinational and Sequential Circuits  Implement designs using Programmable Logic Devices

 Write HDL code for combinational and Sequential Circuits

3

REFERENCES:

1.Grimaldi, R.P. "Discrete and Combinatorial Mathematics: An Applied Introduction", 4th Edition, Pearson Education Asia, Delhi, 2007.

2.Lipschutz, S. and Mark Lipson., "Discrete Mathematics", Schaum’s Outlines, Tata McGraw Hill

Pub. Co. Ltd., New Delhi, 3rd Edition, 2010.

3.Koshy, T. "Discrete Mathematics with Applications", Elsevier Publications, 2006.

OBJECTIVES:

To design digital circuits using simplified Boolean functions

To analyze and design combinational circuits

To analyze and design synchronous and asynchronous sequential circuits

To understand Programmable Logic Devices

To write HDL code for combinational and sequential circuits

Standard Forms - Simplification of Boolean Functions using Karnaugh Map - Logic Gates – NAND and NOR Implementations.

Sequential Circuits - Storage Elements: Latches , Flip-Flops - Analysis of Clocked Sequential Circuits - State Reduction and Assignment - Design Procedure - Registers and Counters - HDL Models of Sequential Circuits.

TEXT BOOK:

1.M. Morris R. Mano, Michael D. Ciletti, “Digital Design: With an Introduction to the

Verilog HDL, VHDL, and SystemVerilog”, 6th Edition, Pearson Education, 2017.

REFERENCES:

1.G. K. Kharate, Digital Electronics, Oxford University Press, 2010

2.John F. Wakerly, Digital Design Principles and Practices, Fifth Edition, Pearson Education, 2017.

3.Charles H. Roth Jr, Larry L. Kinney, Fundamentals of Logic Design, Sixth Edition, CENGAGE Learning, 2013

4.Donald D. Givone, Digital Principles and Design‖, Tata Mc Graw Hill, 2003.

To understand the concepts of ADTs

To Learn linear data structures – lists, stacks, and queues

To understand sorting, searching and hashing algorithms

To apply Tree and Graph structures

Abstract Data Types (ADTs) – List ADT – array-based implementation – linked list implementation ––singly linked lists- circularly linked lists- doubly-linked lists – applications of lists –Polynomial Manipulation – All operations (Insertion, Deletion, Merge, Traversal).

UNIT II LINEAR DATA STRUCTURES – STACKS, QUEUES 9

Stack ADT – Operations - Applications - Evaluating arithmetic expressions- Conversion of Infix to postfix expression - Queue ADT – Operations - Circular Queue – Priority Queue - deQueue – applications of queues.

UNIT III NON LINEAR DATA STRUCTURES – TREES 9

Tree ADT – tree traversals - Binary Tree ADT – expression trees – applications of trees – binary search tree ADT –Threaded Binary Trees- AVL Trees – B-Tree - B+ Tree - Heap – Applications of heap.

UNIT IV NON LINEAR DATA STRUCTURES - GRAPHS 9

Definition – Representation of Graph – Types of graph - Breadth-first traversal - Depth-first traversal – Topological Sort – Bi-connectivity – Cut vertex – Euler circuits – Applications of graphs.

UNIT V SEARCHING, SORTING AND HASHING TECHNIQUES 9

Searching- Linear Search - Binary Search. Sorting - Bubble sort - Selection sort - Insertion sort - Shell sort – Radix sort. Hashing- Hash Functions – Separate Chaining – Open Addressing – Rehashing – Extendible Hashing.

TOTAL: 45 PERIODS

OUTCOMES:

At the end of the course, the student should be able to:

Implement abstract data types for linear data structures.

Apply the different linear and non-linear data structures to problem solutions.

Critically analyze the various sorting algorithms.

4

TEXT BOOKS:

1.Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, 2nd Edition, Pearson

Education,1997.

2.Reema Thareja, “Data Structures Using C”, Second Edition , Oxford University Press, 2011

REFERENCES:

1.Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest, Clifford Stein, “Introduction to

Algorithms", Second Edition, Mcgraw Hill, 2002.

2.Aho, Hopcroft and Ullman, “Data Structures and Algorithms”, Pearson Education,1983.

3.Stephen G. Kochan, “Programming in C”, 3rd edition, Pearson Education.

4.Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed, “Fundamentals of Data Structures in C”, Second Edition, University Press, 2008

To understand Object Oriented Programming concepts and basic characteristics of Java

To know the principles of packages, inheritance and interfaces

To define exceptions and use I/O streams

To develop a java application with threads and generics classes

To design and build simple Graphical User Interfaces

UNIT I INTRODUCTION TO OOP AND JAVA FUNDAMENTALS 10

Object Oriented Programming - Abstraction – objects and classes - Encapsulation- Inheritance - Polymorphism- OOP in Java – Characteristics of Java – The Java Environment - Java Source File -Structure – Compilation. Fundamental Programming Structures in Java – Defining classes in Java – constructors, methods -access specifiers - static members -Comments, Data Types, Variables, Operators, Control Flow, Arrays , Packages - JavaDoc comments.

UNIT II INHERITANCE AND INTERFACES 9

Inheritance – Super classes- sub classes –Protected members – constructors in sub classes- the Object class – abstract classes and methods- final methods and classes – Interfaces – defining an interface, implementing interface, differences between classes and interfaces and extending interfaces - Object cloning -inner classes, Array Lists - Strings

UNIT III EXCEPTION HANDLING AND I/O 9

Exceptions - exception hierarchy - throwing and catching exceptions – built-in exceptions, creating own exceptions, Stack Trace Elements. Input / Output Basics – Streams – Byte streams and Character streams – Reading and Writing Console – Reading and Writing Files

UNIT IV MULTITHREADING AND GENERIC PROGRAMMING 8

Differences between multi-threading and multitasking, thread life cycle, creating threads, synchronizing threads, Inter-thread communication, daemon threads, thread groups. Generic Programming – Generic classes – generic methods – Bounded Types – Restrictions and Limitations.

5

Graphics programming - Frame – Components - working with 2D shapes - Using color, fonts, and images - Basics of event handling - event handlers - adapter classes - actions - mouse events - AWT event hierarchy - Introduction to Swing – layout management - Swing Components – Text Fields , Text Areas – Buttons- Check Boxes – Radio Buttons – Lists- choices- Scrollbars – Windows –Menus – Dialog Boxes.

TOTAL: 45 PERIODS

OUTCOMES:

Upon completion of the course, students will be able to:

Develop Java programs using OOP principles

 Develop Java programs with the concepts inheritance and interfaces

Build Java applications using exceptions and I/O streams

Develop Java applications with threads and generics classes

Develop interactive Java programs using swings

TEXT BOOKS:

1.Herbert Schildt, “Java The complete reference”, 8th Edition, McGraw Hill Education, 2011.

2.Cay S. Horstmann, Gary cornell, “Core Java Volume –I Fundamentals”, 9th Edition, Prentice Hall, 2013.

REFERENCES:

1.Paul Deitel, Harvey Deitel, “Java SE 8 for programmers”, 3rd Edition, Pearson, 2015.

2.Steven Holzner, “Java 2 Black book”, Dreamtech press, 2011.

3.Timothy Budd, “Understanding Object-oriented programming with Java”, Updated Edition,

Pearson Education, 2000.

To introduce the relevance of this course to the existing technology through demonstrations, case studies, simulations, contributions of scientist, national/international policies with a futuristic vision along with socio-economic impact and issues

To study the various analog and digital modulation techniques

To study the principles behind information theory and coding

To study the various digital communication techniques

Amplitude Modulation – AM, DSBSC, SSBSC, VSB – PSD, modulators and demodulators – Angle modulation – PM and FM – PSD, modulators and demodulators – Superheterodyne receivers

UNITII PULSE MODULATION 9

Low pass sampling theorem – Quantization – PAM – Line coding – PCM, DPCM, DM, and ADPCM And ADM, Channel Vocoder - Time Division Multiplexing, Frequency Division Multiplexing

UNIT III DIGITAL MODULATION AND TRANSMISSION 9

Phase shift keying – BPSK, DPSK, QPSK – Principles of M-ary signaling M-ary PSK & QAM – Comparison, ISI – Pulse shaping – Duo binary encoding – Cosine filters – Eye pattern, equalizers

6

UNIT IV INFORMATION THEORY AND CODING 9

Measure of information – Entropy – Source coding theorem – Shannon–Fano coding, Huffman Coding, LZ Coding – Channel capacity – Shannon-Hartley law – Shannon's limit – Error control codes – Cyclic codes, Syndrome calculation – Convolution Coding, Sequential and Viterbi decoding

UNIT V SPREAD SPECTRUM AND MULTIPLE ACCESS 9

PN sequences – properties – m-sequence – DSSS – Processing gain, Jamming – FHSS – Synchronisation and tracking – Multiple Access – FDMA, TDMA, CDMA,

TOTAL: 45 PERIODS

OUTCOMES:

At the end of the course, the student should be able to:

Ability to comprehend and appreciate the significance and role of this course in the present contemporary world

Apply analog and digital communication techniques.

Use data and pulse communication techniques.

Analyze Source and Error control coding.

TEXT BOOKS:

1.H Taub, D L Schilling, G Saha, “Principles of Communication Systems” 3/e, TMH 2007

2.S. Haykin “Digital Communications” John Wiley 2005

REFERENCES:

1.B.P.Lathi, “Modern Digital and Analog Communication Systems”, 3rd edition, Oxford University Press, 2007

2.H P Hsu, Schaum Outline Series – “Analog and Digital Communications” TMH 2006

3.B.Sklar, Digital Communications Fundamentals and Applications” 2/e Pearson

Education 2007.

To implement linear and non-linear data structures

To understand the different operations of search trees

To implement graph traversal algorithms

To get familiarized to sorting and searching algorithms

1.Array implementation of Stack and Queue ADTs

2.Array implementation of List ADT

3.Linked list implementation of List, Stack and Queue ADTs

4.Applications of List, Stack and Queue ADTs

5.Implementation of Binary Trees and operations of Binary Trees

6.Implementation of Binary Search Trees

7.Implementation of AVL Trees

8.Implementation of Heaps using Priority Queues.

9.Graph representation and Traversal algorithms

10.Applications of Graphs

11.Implementation of searching and sorting algorithms

12.Hashing – any two collision techniques

TOTAL: 60 PERIODS

7

OUTCOMES:

At the end of the course, the students will be able to:

Write functions to implement linear and non-linear data structure operations

Suggest appropriate linear / non-linear data structure operations for solving a given problem

Appropriately use the linear / non-linear data structure operations for a given problem

Apply appropriate hash functions that result in a collision free scenario for data storage and retrieval

To build software development skills using java programming for real-world applications.

To understand and apply the concepts of classes, packages, interfaces, arraylist, exception handling and file processing.

To develop applications using generic programming and event handling.

LIST OF EXPERIMENTS

1.Develop a Java application to generate Electricity bill. Create a class with the following members: Consumer no., consumer name, previous month reading, current month reading,

type of EB connection (i.e domestic or commercial). Compute the bill amount using the following tariff.

If the type of the EB connection is domestic, calculate the amount to be paid as follows:

201 -500 units - Rs. 4 per unit

 > 501 units - Rs. 6 per unit

If the type of the EB connection is commercial, calculate the amount to be paid as follows:

201 -500 units - Rs. 6 per unit

 > 501 units - Rs. 7 per unit

2.Develop a java application to implement currency converter (Dollar to INR, EURO to INR, Yen to INR and vice versa), distance converter (meter to KM, miles to KM and vice versa) , time converter (hours to minutes, seconds and vice versa) using packages.

3.Develop a java application with Employee class with Emp_name, Emp_id, Address, Mail_id, Mobile_no as members. Inherit the classes, Programmer, Assistant Professor, Associate Professor and Professor from employee class. Add Basic Pay (BP) as the member of all the inherited classes with 97% of BP as DA, 10 % of BP as HRA, 12% of BP as PF, 0.1% of BP for staff club fund. Generate pay slips for the employees with their gross and net salary.

4.Design a Java interface for ADT Stack. Implement this interface using array. Provide necessary exception handling in both the implementations.

5.Write a program to perform string operations using ArrayList. Write functions for the following

a.Append - add at end

b.Insert – add at particular index

c.Search

d.List all string starts with given letter

8

6.Write a Java Program to create an abstract class named Shape that contains two integers and an empty method named print Area(). Provide three classes named Rectangle, Triangle and Circle such that each one of the classes extends the class Shape. Each one of the classes contains only the method print Area () that prints the area of the given shape.

7.Write a Java program to implement user defined exception handling.

8.Write a Java program that reads a file name from the user, displays information about whether the file exists, whether the file is readable, or writable, the type of file and the length of the file in bytes.

9.Write a java program that implements a multi-threaded application that has three threads. First thread generates a random integer every 1 second and if the value is even, second thread computes the square of the number and prints. If the value is odd, the third thread will print the value of cube of the number.

10.Write a java program to find the maximum value from the given type of elements using a generic function.

11.Design a calculator using event-driven programming paradigm of Java with the following options.

a)Decimal manipulations

b)Scientific manipulations

12.Develop a mini project for any application using Java concepts.

TOTAL : 60 PERIODS

OUTCOMES

Upon completion of the course, the students will be able to

Develop and implement Java programs for simple applications that make use of classes, packages and interfaces.

Develop and implement Java programs with arraylist, exception handling and multithreading .

Design applications using file processing, generic programming and event handling.

To understand the various basic logic gates

To design and implement the various combinational circuits

To design and implement combinational circuits using MSI devices.

To design and implement sequential circuits

To understand and code with HDL programming

LIST OF EXPERIMENTS

1.Verification of Boolean Theorems using basic gates.

2.Design and implementation of combinational circuits using basic gates for arbitrary functions, code converters.

3.Design and implement Half/Full Adder and Subtractor.

4.Design and implement combinational circuits using MSI devices:

4 – bit binary adder / subtractor

Parity generator / checker

Magnitude Comparator

Application using multiplexers

9

5.Design and implement shift-registers.

6.Design and implement synchronous counters.

7.Design and implement asynchronous counters.

8.Coding combinational circuits using HDL.

9.Coding sequential circuits using HDL.

10.Design and implementation of a simple digital system (Mini Project).

TOTAL: 60 PERIODS

OUTCOMES:

Upon Completion of the course, the students will be able to:

Implement simplified combinational circuits using basic logic gates

Implement combinational circuits using MSI devices

Implement sequential circuits like registers and counters

Simulate combinational and sequential circuits using HDL

LIST OF EQUIPMENT FOR A BATCH OF 30 STUDENTS:

LABORATORY REQUIREMENT FOR BATCH OF 30 STUDENTS HARDWARE:

1.Digital trainer kits - 30

2.Digital ICs required for the experiments in sufficient numbers

SOFTWARE:

1. HDL simulator.

OBJECTIVES:

The Course will enable learners to:

Equip students with the English language skills required for the successful undertaking of academic studies with primary emphasis on academic speaking and listening skills.

Provide guidance and practice in basic general and classroom conversation and to engage in specific academic speaking activities.

improve general and academic listening skills

Make effective presentations.

UNIT I

Listening as a key skill- its importance- speaking - give personal information - ask for personal information - express ability - enquire about ability - ask for clarification Improving pronunciation - pronunciation basics taking lecture notes - preparing to listen to a lecture - articulate a complete idea as opposed to producing fragmented utterances.

UNIT II

Listen to a process information- give information, as part of a simple explanation - conversation starters: small talk - stressing syllables and speaking clearly - intonation patterns - compare and contrast information and ideas from multiple sources- converse with reasonable accuracy over a wide range of everyday topics.

UNIT III

Lexical chunking for accuracy and fluency- factors influence fluency, deliver a five-minute informal talk - greet - respond to greetings - describe health and symptoms - invite and offer - accept - decline - take leave - listen for and follow the gist- listen for detail

10

UNIT IV

Being an active listener: giving verbal and non-verbal feedback - participating in a group discussion - summarizing academic readings and lectures conversational speech listening to and participating in conversations - persuade.

UNIT V

Formal and informal talk - listen to follow and respond to explanations, directions and instructions in academic and business contexts - strategies for presentations and interactive communication - group/pair presentations - negotiate disagreement in group work.

TOTAL :30PERIODS

OUTCOMES:

At the end of the course Learners will be able to:

Listen and respond appropriately.

Participate in group discussions

Make effective presentations

Participate confidently and appropriately in conversations both formal and informal

TEXT BOOKS:

1.Brooks,Margret. Skills for Success. Listening and Speaking. Level 4 Oxford University Press, Oxford: 2011.

2.Richards,C. Jack. & David Bholke. Speak Now Level 3. Oxford University Press, Oxford: 2010

REFERENCES:

1.Bhatnagar, Nitin and MamtaBhatnagar. Communicative English for Engineers and Professionals. Pearson: New Delhi, 2010.

2.Hughes, Glyn and Josephine Moate. Practical English Classroom. Oxford University Press: Oxford, 2014.

3.Vargo, Mari. Speak Now Level 4. Oxford University Press: Oxford, 2013.

4.Richards C. Jack. Person to Person (Starter). Oxford University Press: Oxford, 2006.

5.Ladousse, Gillian Porter. Role Play. Oxford University Press: Oxford, 2014

11