L: Lecturer Hours Per Week T: Tutorial Hours Per Week

Scheme of Syllabus for 5th Semester B.E. Computer Science & Engineering
(2014-15Batch)

Sl.
No / Subject Code / Subjects / Hrs/Week / C / CIE / *SEE / Total
L / T / P
1 / UCS521C / Analysis and Design of Algorithms / 3 / 0 / 2# / 4 / 50 / 50 / 100
2 / UCS512C / System Software / 3 / 0 / 0 / 3 / 50 / 50 / 100
3 / UCS523C / Data Communications / 4 / 0 / 0 / 4 / 50 / 50 / 100
4 / UCS524C / Software Engineering / 4 / 0 / 0 / 4 / 50 / 50 / 100
5 / - / Elective – 1 / 3 / 0 / 0 / 3 / 50 / 50 / 100
6 / - / Elective - 2 / 3 / 0 / 0 / 3 / 50 / 50 / 100
7 / UCS525L / System Software Lab / 0 / 1 / 3 / 2 / 50 / 50 / 100
8 / UCS526L / Operating Systems Lab / 0 / 2 / 2 / 2 / 50 / 50 / 100
Total / 20 / 3 / 7 / 25 / 400 / 400 / 800

L: Lecturer Hours per Week T: Tutorial hours per week

P: Practical Hours per Week C: Credit points

*CIE: Continuous Internal Evaluation *SEE: Semester End Examination

# Lab is to be evaluated for 20 marks in CIE only, theory is to be evaluated for 30 marks in CIE and 50

marks in SEE and the same scheme is applicable to elective courses on programming languages.

ANALYSIS AND DESIGN OF ALGORITHMS
Sub Code / : / UCS521C / Credits / : / 04
Hours/Week / : / Theory: 03, Practical: 2 / CIE MARKS / : / 50 (30 theory, 20 lab)
Total Hours / : / 40 / SEE Marks / : / 50

Course Objectives

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

Analyze and compare the asymptotic performance of algorithms.
Write the correctness proofs for algorithms.
Demonstrate a acquaintance with major algorithms and data structures.
Apply important algorithmic design paradigms and methods of analysis.
Synthesize efficient algorithms in to address common engineering challenges.

Course Outcomes

Students who complete the course will have demonstrated the ability to do the following:

Analyze worst-case, best case and average case running times of algorithms using asymptotic analysis.
Describe the various algorithmic paradigms like Brute Force, Divide and Conquer, Transform and Conquer,Dynamic Programming, Greedy technique.
Explain the major graph algorithms and their analyses.
Use the above techniques to synthesize solutions to new emerging engineering problems.

UNIT I (10 Hours)

Introduction: Notion of Algorithm, Fundamentals of Algorithmic Problem Solving, Important Problem Types, Fundamental Data Structures.

Fundamentals of the Analysis of Algorithm Efficiency: Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non-recursive and Recursive Algorithms, Example – Fibonacci Numbers.

Brute Force: Selection Sort and Bubble Sort, Sequential Search and Brute-Force String Matching, Exhaustive Search.

UNIT II (10 Hours)

Divide and Conquer:Mergesort, Quicksort, Binary Search, Binary tree traversals and related properties, Multiplication of large integers and Stressen’s Matrix Multiplication.

Decrease and Conquer: Insertion Sort, Depth First Search, Breadth First Search, Topological Sorting, Algorithms for Generating Combinatorial Objects.

UNIT III (10 Hours)

Transform and Conquer: Presorting, Balanced Search Trees, Heaps and Heapsort, Problem Reduction Space and Time Tradeoffs: Sorting by Counting, Input Enhancement in String Matching , Hashing, B-Trees Dynamic Programming: Computing a Binomial Coefficient, Warshall’s and Floyd’s Algorithms, Optimal Binary Search Trees. The Knapsack Problem and Memory Functions.

UNIT IV (10 Hours)

Greedy Technique: Prim’s Algorithm,Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees

Limitations of Algorithm Power: Lower-Bound Arguments, Decision Trees ,Problems

Coping with the Limitations of Algorithm Power: Backtracking, Branch-and-Bound,

Text Books:

AnanyLevitin, 2007,’Introduction to The Design & Analysis of Algorithms’, 2nd Edition, Pearson Education.

Reference Books

Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 2006,’Introduction to Algorithms’, 2nd Edition, PHI.
Horowitz E., Sahni S., RajasekaranS.,Galgotia Publications, 2001, ’Computer Algorithms’.

Note: It also includes laboratory (3 Hours Theory and 2 Hours Practical/Week)

SYSTEMS SOFTWARE
Sub Code / : / UCS512C / Credits / : / 03
Hours/Week / : / 03 / CIE MARKS / : / 50
Total Hours / : / 40 / SEE Marks / : / 50

Course Description

i)Course Learning objectives (CLO):

At the end of the course student will learn/understand/ think/experience/appreciate:

Basic concepts and types of system softwares.
Design and characteristics of various machine architectures such as SIC, SIC/XE, RISC and CISC.
Basic concepts, algorithms and implementation methods of assembler, loader, linker and compiler.
Lex and Yacc programming languages, their structures etc. to design lexical analyzer and syntactic analyzer for given applications.
Characteristics, algorithms and implementation methods of Macro-processor.

ii)Course outcomes:

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

List and define features/concepts of machine architectures and system softwares.
Explain characteristics/concepts/basic operations of machines architectures, system softwares and Lex and Yacc tools.
Write programs to implement simple assembler, loader, linker, macroprocessor, lexical analyzer and syntactic analyzer.
Compare and contrast types of softwares, machine architectures, system softwares and Lexical and syntactic analyzer.
Analyze, Design and implement system softwares for different architectures.

UNIT I (10 Hours)

Machine Architecture: Introduction, System Software and Machine Architecture, Simplified Instructional Computer (SIC) - SIC Machine Architecture, SIC/XE Machine Architecture, SIC Programming Examples, Traditional (CISC) Machines - VAX Architecture, RISC Machines - Ultra SP ARC Architecture. Assemblers: Basic Assembler Function - A Simple SIC Assembler, Assembler Algorithm and Data Structures, Machine Dependent Assembler Features - Instruction Formats & Addressing Modes, Program Relocation, Machine Independent Assembler Features - Literals, Symbol-Definition Statements, Expression, Program Blocks, Control Sections and Programming Linking.

UNIT II (10 Hours)

Loaders And Linkers: Basic Loader Functions - Design of an Absolute loader, A Simple Bootstrap Loader, Machine-Dependent Loader Features - Relocation, Program Linking, Algorithm and Data Structures for a Linking Loader, Machine-Independent Loader Features - Automatic Library Search, Loader Options, Loader Design Options - Linkage Editor, Dynamic Linkage, Bootstrap Loaders.

UNIT III (10 Hours)

Compilers: Basic Compiler Function - Grammars, Lexical Analysis, Syntactic Analysis, Code Generation, Machine Dependent Compiler Features Intermediate Form of the Program. Machine-Dependent Code Optimization, Machine Independent Compiler Features - Structured Variables, Machine Independent Code Optimization, Storage Allocation, Block Structured Languages.

UNIT IV (10 Hours)

Macro Processor: Basic Macro Processor Functions - Macro Definitions 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 Processor Design Options - Recursive Macro Expansion, General-Purpose Macro Processors, Macro Processing Within Language Translators. Lex And Yacc: Lex and Yacc - The Simplest Lex Program, Recognizing Words with LEX, Grammars, Parser-Lexer Communication, A Y ACC Parser, The Rules Section, Running LEX and Y ACC, LEX and Hand- Written Lexers, Using LEX - Regular Expression, Examples of Regular Expressions, A Word Counting Program, Using Y ACC - Grammars, Recursive Rules, Shift/Reduce Parsing, What Y ACC Cannot Parse, A Y ACC Parser - The Definition Section, The Rules Section, Symbol Values and Actions, The LEXER, Compiling and Running a Simple Parser, Arithmetic Expressions and Ambiguity, Variables and Typed Tokens.

TEXT BOOKS:

1)Leyland.L.Beck, 1997, System Software, 3rd Edition, Addison-Wesley.

2)John.R.Levine, 1999, Tony Mason and Doug Brown, Lex and Yacc, O’Reilly, SPD.

REFERENCE BOOK:

1)D.M.Dhamdhere, 1999,System Programming and Operating Systems, 2nd Edition, TMH.

DATA COMMUNICATIONS
Sub Code / : / UCS523C / Credits / : / 04
Hours/Week / : / 04 / CIE MARKS / : / 50
Total Hours / : / 48 / SEE Marks / : / 50

Course Objectives:

To understand the concept of data communication and modulation techniques.
To comprehend the use of different types of transmission media and network devices.
To understand the error detection and correction in transmission of data.
To understand the concept of flow control, error control and LAN protocols.
To understand the functions performed by Network Management System.

COURSE LEARNING OUTCOMES :(Knowledge based)

understand the basic principles of network design;
Understand the concept data communication within the network environment;
Understand the conflicting issues and resolution techniques in data transmission.
Understand the setting up of a network environment with all the necessary data. communication components, procedure and techniques that make it functional

UNIT – I (12Hours)

Introduction: Data Communications; Networks; the Internet; Protocols and Standards; Network Models: Layered tasks; The OSI Model, Layers in the OSI model; TCP / IP Protocol Suite, Addressing.

Data and Signals: Analog and digital signals; Periodic Analog Signals, Digital Signals, Transmission impairment; Data rate limits; Performance.

UNIT – II (12 Hours)

Digital Transmission, Analog Transmission And Multiplexing: Digital-to-Digital conversion; Analog-to-Digital conversion: PCM; Transmission modes, Digital - to - Analog conversion; Analog - to - Analog conversion; Multiplexing.

Transmission Media: Guided media, unguided media: Wireless.

UNIT – III (12 Hours)

Error Detection and Correction:

Introduction to Error Detection and Correction; Block Coding; Linear Block Codes; Cyclic codes, Checksum.

Data Link Control: Framing; Flow and Error control; Protocols; Noiseless channels; Noisy channels; HDLC; Point-to-point Protocol.

Multiple Accesses: Random Access; Controlled Access; Channelization.

UNIT – IV (12 Hours)

Ethernet: EEE standards; Standard Ethernet and changes in the standard; Fast Ethernet; Gigabit Ethernet.

Wireless LANs and Connection of LANs: IEEE 802.11; Bluetooth. Connecting devices; Backbone Networks; Virtual LANs.

Other Technologies: Cellular telephony; SONET / SDH: Architecture, Layers, Frames; STS multiplexing.

TEXT BOOK:

1)Behrouz A. Forouzan, 4th Edition, Tata McGraw-Hill, 2006, Data Communications and Networking.

REFERENCE BOOKS:

1)Alberto Leon, Garcia and IndraWidjaja, 3rd Edition, Tata McGraw- Hill, 2004, Communication Networks: Fundamental Concepts and Key Architectures.

2)William Stallings, 8th Edition, Pearson Education, 2007, Data and Computer Communication.

SOFTWARE ENGINEERING
Sub Code / : / UCS524C / Credits / : / 04
Hours/Week / : / 04 / CIE MARKS / : / 50
Total Hours / : / 48 / SEE Marks / : / 50

Course Outcomes

1. Describing the software and software engineering, types of systems and their properties, concept of software process and models.

2. Demonstrating different requirements documents, designs, models, verifying and validating.

3. Analyzing different models, designs and methods of software development, and verification and validation and software architecture.

4. To judge the different software process activities, system process activities, management and software architecture.

5. Able to use all the approaches to develop different models, designs, requirements document and creating skeletal system

Course Objectives

Knowledge of basic software engineering methods and practices, and their appropriate application and understanding of some ethical and professional issues.

An understanding of software requirements, different software architectural styles and implementation issues.

An understanding of approaches to verification and validation, software evolution and related issues.

An understanding on quality control and how to ensure good quality software.

Development of significant teamwork and project based experience.

To gain a broad understanding of the discipline of software engineering and its application and management.

UNIT –I (12 Hours)

OVERVIEW: Introduction: FAQ's about software engineering, Professional and ethical responsibility. Socio-Technical systems: Emergent system properties; Systems engineering; Organizations, people and computer systems; Legacy systems.

CRITICAL SYSTEMS, SOFTWARE PROCESSES: Critical Systems: A simple safety-critical system; System dependability; Availability and reliability. Software Processes: Models, Process iteration, Process activities; The Rational Unified Process; Computer-Aided Software Engineering.

UNIT –II (12 Hours)

REQUIREMENTS: Software Requirements: Functional and Non-functional requirements; User requirements; System requirements; Interface specification; The software requirements document. Requirements Engineering Processes: Feasibility studies; Requirements elicitation and analysis; Requirements validation; Requirements management.

SYSTEM MODELS, PROJECT MANAGEMENT: System Models: Context models; Behavioral models; Data models; Object models; Structured methods. Project Management: Management activities; Project planning; Project scheduling; Risk management.

UNIT –III (12 Hours)

SOFTWARE DESIGN: Architectural Design: Architectural design decisions; System organization; Modular decomposition styles; Control styles. Object-Oriented design: Objects and Object Classes; An Object- Oriented design process; Design evolution.

DEVELOPMENT: Rapid Software Development: Agile methods; Extreme programming; Rapid application development. Software Evolution: Program evolution dynamics; Software maintenance; Evolution processes; Legacy system evolution.

UNIT –IV (12 Hours)

VERIFICATION AND VALIDATION: Verification and Validation: Planning; Software inspections; Automated static analysis; Verification and formal methods. Software testing: System testing; Component testing; Test case design; Test automation.

MANAGEMENT: Managing People: Selecting staff; Motivating people; Managing people; The People Capability Maturity Model. Software Cost Estimation: Productivity;

DESIGNING AND DOCUMENTING SOFTWARE ARCHITECTURE: Architecture in the life cycle; Designing the architecture; Forming the team structure; Creating a skeletal system.

TEXT BOOK:

1)Ian Somerville, 8th Edition, Pearson Education, 2007, Software Engineering.

2)Len Bass, Paul Clements, Rick Kazman, Pearson Education, 2003. Software Architecture in Practice , 2nd Edition,

REFERENCE BOOKS:

1)Roger S. Pressman, 7th Edition, McGraw-Hill, 2007, Software Engineering: A Practitioners Approach.

2)Shari Lawrence Pfleeger, Joanne M. Atlee, 3rd Edition, Pearson Education, 2006, Software Engineering Theory and Practice.

3)Waman S Jawadekar, Tata McGraw Hill, 2004, Software Engineering Principles and Practice.

SYSTEMS SOFTWARE LABORATORY
Sub Code / : / UCS525L / Credits / : / 02
Hours/Week / : / 04 / CIE MARKS / : / 50
Exam Hours / : / 03 / SEE Marks / : / 50

Course learning Objectives:

At the end of the course student will learn/practice/ think/experience/appreciate:

Design and implement of system softwares using C or C++.
Design and implement of scanners using Lex tool.
Design and implement of parser using Yacc tool.

Course outcomes:

At the end of the semester student should be able to:

Implement the system softwares such as assembler, loader and linker etc using C or C++.
Design and write Lex program to implement lexical analyzer for given problem statement.
Design and write Yacc program to implement parser for the given structure recognition.
Modify the existing design of the algorithm of system softwares to enhance the efficiency.

Part I

Write a C program to implement pass one of two pass assembler.
Write a C program to implement absolute loader.
Write a C program to implement pass one of two pass macroprocessor.
Write a C program to implement pass two of two pass macroprocessor
Write a C program to generate a lexical analyzer to identify the C keywords
Design recursive descent parser for parsingpascal read & write statements.

Part II

Design lexical analysers using Lex tool to accomplish the following.

Design Lexical analyzer to count the no of occurrences of the words from a given text file.The program should accept the text file and list of words as input.
Design Lexical analyzer to count no of positive numbers and negative numbers from the input given.
Design Lexical analyzer to count number of printf and scanf statements and replace them by sprintf and sscanf respectively.
Design Lexical analyzer to count number of integers , float, double,char variable from C declaration statements
Design Lexical analyzer to count number of blank spaces lines, characters, words from a given text file.
Design Lexical analyzer to check whether a given simple arithmetic operation is valid or not. If valid print number of positive, negative, multiplication and division operators separately

Part III

Design parsers using Yacc tool to accomplish the following.

Design parser using Yacc tool to test the validity of a simple expression involving operators ‘+’,’-‘,’/’,’*’.
Design parser using Yacc tool to evaluate the given arithmetic expression involving operators ‘+’,’-‘,’/’,’*’.
Design parser using Yacc tool to recognize a valid variable which starts with a letter followed by any number of letters and digits.The length of the identifier should not exceed 15.
Design parser using Yacc tool to recognize the grammar an b where n>=10.
Design parser using Yacc tool to recognize the validity of nested if statements and also display the number of levels of nesting

Note:

Continuous Internal Evaluation (50 marks) :

Marks are based on execution of assignments and lab internal test. The marks are distributed as below;

30 marks for lab assignment execution.
20 marks for lab internal test.

Semester End Examination (50 marks):

In semester end examination two questions will be given. One from Part-I and one from Part-II and Part-III respectively.

OPERATING SYSTEM LABORATORY
Sub Code / : / UCS526L / Credits / : / 02
Hours/Week / : / 04 / CIE MARKS / : / 50
Exam Hours / : / 03 / SEE Marks / : / 50

OBJECTIVE:

1. to gain practical experience with designing and implementing concepts of operating systems.

2. to study system calls.

3. to implement commands using system calls.

4. to study and use different interprocess communication methods in concurrent application.

OUTCOMES: Upon the completion of Operating Systems practical course, the student will be able to:

1. implement and analyze basic services and functionalities of the operating system using system calls.

2. implement multithreaded applications .

3. develop applications using concurrent processes considering synchronization problems.

4.compare benefits of thread over process.

5.Simulate and analyze CPU Scheduling Algorithms like FCFS, Round Robin, SJF, and Priority.

6. Implement memory management schemes and page replacement schemes

PART A

Write a C program to sort the given set of numbers. Let the parent process sort the first half of the list and child process sort the second half of the list. Finally let the parent process merge the two sorted sublists and display the result.
Write a C program to sort the given set of numbers. Let the parent sort the first half of the list and child thread sort the second half of the list. Finally let the parent thread merge the two sorted sublists and display the result.
Write a C program to implement Shortest Request Next Scheduling Policy(Non-Preemptive).
Write a C program to implement the following memory allocation schemes by considering the problem of external fragmentation.

a.Best Fit

b.Worst Fit

Write a C program to implement FIFO page replacement technique,also check Beladays anomaly.
Write a C program to implement LRU page replacement technique.
Write a C program to implement Producer-Consumer problem using Dekkers algorithm
Write a C program to implement Bankers Algorithm.

PART B