←Computer Science & Engineering

3L + 1T + 0P Unit-1.0 6 hrs. Sets, Relation and Function: Operations and Laws of Sets, Cartesian Products, Binary Relation, Partial Ordering Relation, Equivalence Relation, Image of a Set, Sum and Product of Functions, Bijective functions, Inverse and Composite Function, Size of a Set, Finite and infinite Sets, Countable and uncountable Sets, Cantor's diagonal argument and The Power Set theorem, Schroeder-Bernstein theorem. Unit-2.0 8 hrs. Principles of Mathematical Induction: The Well-Ordering Principle, Recursive definition, The Division algorithm: Prime Numbers, The Greatest Common Divisor: Euclidean Algorithm, The Fundamental Theorem of Arithmetic. Basic counting techniques-inclusion and exclusion, pigeon-hole principle, permutation and combination. Unit-3.0 6 hrs. Propositional Logic: Syntax, Semantics, Validity and Satisfiability, Basic Connectives and Truth Tables, Logical Equivalence: The Laws of Logic, Logical Implication, Rules of Inference, The use of Quantifiers. Unit-4.0 4 hrs. Proof Techniques: Some Terminology, Proof Methods and Strategies, Forward Proof, Proof by Contradiction, Proof by Contraposition, Proof of Necessity and Sufficiency. Unit-5.0 8 hrs. Algebraic Structures and Morphism: Algebraic Structures with one Binary Operation, Semi Groups, Monoids, Groups, Congruence Relation and Quotient Structures, Free and Cyclic Monoids and Groups, Permutation Groups, Substructures, Normal Subgroups, Algebraic Structures with two Binary Operation, Rings, Integral Domain and Fields. Boolean Algebraand Boolean Ring, Identities of Boolean Algebra, Duality, Representation of Boolean Function, Disjunctive and Conjunctive Normal Form Unit-6.0 10 hrs. Graphs and Trees: Graphs and their properties, Degree, Connectivity, Path, Cycle, Sub Graph, Isomorphism, Eulerian and Hamiltonian Walks, Graph Coloring, Coloring maps and Planar Graphs, Coloring Vertices, Coloring Edges, List Coloring, Perfect Graph, definition properties and Example, rooted trees, trees and sorting, weighted trees and prefix codes, Bi-connected component and Articulation Points, Shortest distances. Computer Oriented Approach, 3rd Edition by, Tata McGraw –Hill.

3L + 0T + 0P Unit-1.0 7 hrs. Functional blocks of a computer: CPU, memory, input-output subsystems, control unit. Instruction set architecture of a CPU–registers, instruction execution cycle, RTL interpretation of instructions, addressing modes, instruction set. Case study – instruction sets of some common CPUs. Unit-2.0 7 hrs. Data representation: signed number representation, fixed and floating point representations, character representation. Computer arithmetic – integer addition and subtraction, ripple carry adder, carry look-ahead adder, etc. multiplication – shift-and- add, Booth multiplier, carry save multiplier, etc. Division restoring and non-restoring techniques, floating point arithmetic. Unit-3.0 7 hrs. Introduction to x86 architecture. CPU control unit design: hardwired and micro- programmed design approaches, Case study – design of a simple hypothetical CPU. Memory system design: semiconductor memory technologies, memory organization. Unit-4.0 7 hrs. Peripheral devices and their characteristics: Input-output subsystems, I/O device interface, I/O transfers–program controlled, interrupt driven and DMA, privileged and non- privileged instructions, software interrupts and exceptions. Programs and processes– role of interrupts in process state transitions, I/O device interfaces – SCII, USB. Unit-5.0 7 hrs. Pipelining: Basic concepts of pipelining, throughput and speedup, pipeline hazards. Parallel Processors: Introduction to parallel processors, Concurrent access to memory and cache coherency. Unit-6.0 7 hrs. Memory organization: Memory interleaving, concept of hierarchical memory organization, cache memory, cache size vs. Block size, mapping functions, replacement algorithms, write policies.

3L + 0T + 0P Unit-1.0 7 hrs. Introduction: Concept of Operating Systems, Generations of Operating systems, Types of Operating Systems, OS Services, System Calls, Structure of an OS-Layered, Monolithic, Microkernel Operating Systems, Concept of Virtual Machine. Case study on UNIX and WINDOWS Operating System. Unit-2.0 8 hrs. Processes: Definition, Process Relationship, Different states of a Process, Process State transitions, Process Control Block (PCB), Context switching. Thread: Definition, Various states, Benefits of threads, Types of threads, Concept of multithreads Process Scheduling: Foundation and Scheduling objectives, Types of Schedulers, Scheduling criteria: CPU utilization, Throughput, Turnaround Time, Waiting Time, Response Time; Scheduling algorithms: Pre-emptive and Non pre-emptive, FCFS, SJF, RR; Multiprocessor scheduling: Real Time scheduling: RM and EDF. Unit-3.0 8 hrs. Inter-process Communication: Critical Section, Race Conditions, Mutual Exclusion, Hardware Solution, Strict Alternation, Peterson’s Solution, The Producer - Consumer Problem, Semaphores, Event Counters, Monitors, Message Passing, Shared Memory, Classical IPC Problems: Reader’s & Writer Problem, Dinning Philosopher Problem etc. Unit-4.0 5 hrs. Deadlocks: Definition, Necessary and sufficient conditions for Deadlock, Deadlock Prevention, and Deadlock Avoidance: Banker’s algorithm, Deadlock detection and Recovery. Unit-5.0 7 hrs. Memory Management: Basic concept, Logical and Physical address map, Memory allocation: Contiguous Memory allocation – Fixed and variable partition–Internal and External fragmentation and Compaction; Paging and Segmentation: Principle of Advantages and Disadvantages of paging and segmentation. Virtual Memory: Basics of Virtual Memory – Hardware and control structures – Not recently used (NRU) and Least Recently used (LRU). Unit-6.0 7 hrs. File Management: Concept of File, Access methods, File types, File operation, Directory structure, File System structure, Allocation methods (contiguous, linked, indexed), Free- space management (bit vector, linked list, grouping), directory implementation (linear list, hash table), efficiency and performance. Disk Management: Disk structure, Disk scheduling - FCFS, SSTF, SCAN, C-SCAN, 5 Disk reliability, Disk formatting, Boot-block, Bad blocks I/O Hardware: I/O devices, Device controllers, Direct memory access, Principles of I/O Software: Goals of Interrupt handlers, Device drivers, Device independent I/O software, Secondary-Storage Structure.

3L + 0T + 0P Unit-1.0 7 hrs. Introduction: Characteristics of algorithm. Analysis of algorithm: Asymptotic analysis of complexity bounds – best, average and worst-case behavior; Performance measurements of Algorithm, Time and space trade-offs, Analysis of recursive algorithms through recurrence relations: Substitution method, Recursion tree method and Masters’ theorem. Unit-2.0 7 hrs. Introduction to Divide and Conquer paradigm: Binary Search, Quick and Merge sorting techniques, linear time selection algorithm, Strassen’s Matrix Multiplication, Karatsuba Algorithm for fast multiplication etc. Introduction to Heap: Min and Max Heap, Build Heap, Heap Sort Unit-3.0 7 hrs. Overview of Brute-Force, GreedyProgramming, Dynamic Programming, Branch- and- Bound and Backtrackingmethodologies. Greedy paradigm examples of exact optimization solution: Minimum Cost Spanning Tree, Knapsack problem, Job Sequencing Problem, Huffman Coding, Single source shortest path problem. Unit-4.0 7 hrs. Dynamic Programming, difference between dynamic programming and divide and conquer, Applications: Fibonacci Series, Matrix Chain Multiplication, 0-1 Knapsack Problem, Longest Common Subsequence, Travelling Salesman Problem, Rod Cutting, Bin Packing. Heuristics – characteristics and their application domains. Unit-5.0 7 hrs. Graph and Tree Algorithms:Representational issues in graphs, Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS); Shortest path algorithms: Bellman- Ford algorithm,Dijkstra’s algorithm & Analysis of Dijkstra’s algorithm using heaps, Floyd-Warshall’s all pairs shortest path algorithm.Transitive closure, Topological sorting, Network Flow Algorithm, Connected Component Unit-6.0 7 hrs. Tractable and Intractable Problems: Computability of Algorithms, Computability classes – P, NP, NP-complete and NP-hard. Cook’s theorem, Standard NP-complete problems and Reduction techniques.Approximation algorithms, Randomized algorithms Edition, Michael T Goodrich and Roberto Tamassia, Wiley. 3. Algorithms—A Creative Approach, 3RD Edition, UdiManber, Addison- Wesley, Reading, MA. 8

3L + 0T + 0P Unit-1.0 7 hrs. Fundamentals of Digital Systems and logic families: Digital signals, digital circuits, AND, OR, NOT, NAND, NOR and Exclusive-OR operations, Boolean algebra, examples of IC gates, number systems-binary, signed binary, octal hexadecimal number, binary arithmetic, one’s and two’s complements arithmetic, codes, error detecting and correcting codes, characteristics of digital lCs, digital logic families, TTL, Schottky TTL and CMOS logic, interfacing CMOS and TTL, Tri - state logic. Unit-2.0 7 hrs. Combinational Digital Circuits: Standard representation for logic functions K-map representation, simplification of logic functions using K-map, minimization of logical functions. Don’t care conditions, Multiplexer, DeMultiplexer/Decoders, Adders, Subtractors, BCD arithmetic, carry look ahead adder, serial adder, ALU, elementary ALU design, popular MSI chips, digital comparator, parity checker/generator, code converters, priority encoders, decoders/drivers for display devices, Q-M method of function realization. Unit-3.0 7 hrs. Sequential circuits and systems: A 1-bit memory, the circuit properties of Bistable latch, the clocked SR flip flop, J- K-T and D types flip flops, applications of flip flops, shift registers, applications of shift registers, serial to parallel converter, parallel to serial converter, ring counter, sequence generator, ripple (Asynchronous) counters, synchronous counters, counters design using flip flops, special counter IC’s, asynchronous sequential counters, applications of counters. Unit-4.0 7 hrs. A/D and D/A Converters: Digital to analog converters: weighted resistor/converter, R- 2RLadder D/A converter, specifications for D/A converters, examples of D/A converter lCs, sample and hold circuit, analog to digital converters: quantization and encoding, parallel comparator A/D converter, successive approximation A/D converter, counting A/D converter, dual slope A/D converter, A/D converter using Voltage to frequency and voltage to time conversion, specifications of A/D converters, example of A/D converter ICs. Unit-5.0 7 hrs. Semiconductor memories: Memory organization and operation, expanding memory size, classification and characteristics of memories, sequential memory, read only memory (ROM), read and write memory(RAM), content addressable memory (CAM), charge de coupled device memory (CCD), commonly used memory chips, ROM as a PLD. Unit-6.0 7 hrs. Programmable logic devices Programmable logic array, Programmable array logic, complex Programmable logic devices (CPLDS), Field Programmable Gate Array (FPGA). 9

3L + 0T + 0P Unit-1.0 7 hrs. Introduction: HR Role and Functions, Concept and Significance of HR, Changing role of HR managers - HR functions and Global Environment, role of a HR Manager. Human Resources Planning: HR Planning andRecruitment: Planning Process - planning at different levels - Job Analysis Unit-2.0 7 hrs. Recruitment and selection processes - Restructuring strategies - Recruitment-Sources of Recruitment-Selection Process-Placement and Induction-Retention of Employees. Training and Development: need for skill upgradation - Assessment of training needs - Retraining and Redeployment methods and techniques of training employees and executives – performance appraisal systems. Unit-3.0 7 hrs. Performance Management System: Definition, Concepts and Ethics-Different methods of Performance Appraisal- Rating Errors Competency management. Industrial Relations : Factors influencing industrial relations - State Interventions and Legal Framework - Role of Trade unions - Collective Bargaining - Workers; participation in management. Unit-4.0 7 hrs. Organizational Behaviour: Definition, Importance, Historical Background, Fundamental Concepts of OB, Challenges and Opportunities for OB. Unit-5.0 7 hrs. Personality and Attitudes: Meaning of personality, Personality Determinants and Traits, Development of Personality, Types of Attitudes, Job Satisfaction. Unit-6.0 7 hrs. Leadership: Definition, Importance, Theories of Leadership Styles. Organizational Politics: Definition, Factors contributing to Political Behavior. Conflict Management: Traditional vis-a-vis Modern View of Conflict, Functional and Dysfunctional Conflict, Conflict Process, Negotiation - Bargaining Strategies, Negotiation Process.

3L + 0T + 0P We as human being are not an entity separate from the environment around us rather we are a constituent seamlessly integrated and co-exist with the environment around us. We are not an entity so separate from the environment that we can think of mastering and controlling it rather we must understand that each and every action of ours reflects on the environment and vice versa. Ancient wisdom drawn from Vedas about environment and its sustenance reflects these ethos. There is a direct application of this wisdom even in modern times. Idea of an activity based course on environment protection is to sensitize the students on the above issues through following two type of activities: (a) Awareness Activities: i) Small group meetings about water management, promotion of recycle use, generation of less waste, avoiding electricity waste ii) Slogan making events iii) Poster making events iv) Cycle rally v) Lectures from experts (b) Actual Activities: i) Plantation ii) Gifting a tree to see its full growth iii) Cleanliness drive iv) Drive for segregation of waste v) To live some big environmentalist for a week or so to understand his work vi) To work in kitchen garden for mess vii) To know about the different varieties of plants viii) Shutting down the fans and ACs of the campus for an hour or so 12

0L + 0T + 2P Preform any ten Experiments 1. Given a 4-variable logic expression, simplify it using appropriate technique and simulate the same using basic gates. 2. Design a 4 bit full adder and subtractor and simulate the same using basic gates. 3. Design Verilog HDL to implement simple circuits using structural, Data flow and Behavioural model. 4. Design Verilog HDL to implement Binary Adder-Subtractor Half and Full Adder, Half and Full Subtractor. 5. Design Verilog HDL to implement Decimal adder. 6. Design Verilog program to implement Different types of multiplexer like 2:1, 4:1 and 8:1. 7. Design Verilog program to implement types of De-Multiplexer. 8. Design Verilog program for implementing various types of Flip-Flops such as SR, JK and D. 9. Develop an ALP to multiply two 16-bit binary numbers. 10. Develop an ALP to find the sum of first 10 integer numbers. 11. Develop an ALP to find the largest/smallest number in an array of 32 numbers. 12. Develop an ALP to count the number of ones and zeros in two consecutive memory locations. 13

0L + 0T + 2P Preform all Experiments Operating System Lab: - 1. Write a program to implement FCFS scheduling algorithm. 2. Write a program to implement SJF scheduling algorithm. 3. Write a program to implement priority scheduling algorithm. 4. Write a program to implement round robin scheduling. 5. Write a program to implement banker’s algorithm. 6. Write a device driver for any device or peripheral. 7. Write a program to implement disk scheduling algorithm. 8. Write a program to implement dining philosopher problem. 9. Write a program to implement producer consumer problem. 10. Write a program to implement LRU page replacement algorithm. 14

0L + 0T + 2P Preform any ten Experiments 1. Sort a given set of elements using the Quick sort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted. The elements can be read from a file or can be generated using the random number generator. 2. Implement a Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted .The elements can be read from a file or can be generated using the random number generator. 3. Compute the transitive closure of a given directed graph using Warshall's algorithm. 4. Implement 0/1 Knapsack problem using Dynamic Programming. 5. From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijikstra’s algorithm. 6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm. 7. Print all the nodes reachable from a given starting node in a digraph using the BFS method. 8. Check whether a given graph is connected or not using the DFS method. 9. Find a subset of a given set S = {s1, s2,....., sN} of n positive integers whose sum is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6}and{1,8}.A suitable message is to be displayed if the given problem instance doesn't have a solution. 10. Implement any scheme to find the optimal solution for the Travelling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation. 11. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm. 12. Implement N Queen's problem using Backtracking. 15

0L + 0T + 2P Perform any ten Experiments 1. Universal Gates (i) Identification and verification of NAND gate (IC #7400) and NOR gate (IC #7402). (ii) Construction and Verification of all other gate (AND, OR, NOT, XOR) USING a) Only NAND gate b) Only NOR gate 2. Code Convertor & Parity Generator and checker. (i) Identification & verification of NOT (7404), AND (7408) OR (7432) & XOR (7486) gates. (ii) Design, construction and verification of 3-bit Binary to Gray convertor and 3-bit Grey to Binary convertor circuit. (iii) Design, construction and verification of 3-bit odd/even Parity Generator and 4-bit odd/even parity checker circuit. 3. Adder, Subtractor & Magnitude comparator circuits. (i) Design, construction and verification of Half Adder and Half Subtractor circuit. (ii) Design, construction and verification of Full Adder and Full Subtractor circuit. (iii) Design, construction and verification of 1-bit and 4-bit Magnitude comparator. (iv) BCD Adder/Subtractor 4. Decoder, MUX & DMUX (i) Construction and verification of BCD to 7-segment decoder using IC # 7447 (ii) Verification of 4:1 MUX, 8:1 MUX & 16:1 MUX. (iii) Verification of 1:4 DMUX, 1:8 DMUX (iv) Cascading of MUIX and Cascading of Decoders. 5. Latches and Flip Flops (i)Construction and Verification of a Latch circuit using NAND/NOR gates. (ii) Construction and Verification of S-R Flip Flop using above Latch circuits. (iii) Verification of J-K Flip Flop using IC # 7476 (Dual J-KFF) (iv) Construction and Verification of D-Flip Flop and T-Flip Flop using J-K FF (IC #7476). (v) Construction and Verification of Master Slave J-K Flip Flop. 6. Shift Registers (i) Verification of D-FF using IC # 7474 (Dual D- FF). (ii) Construction and verification of a 2-bit Shift Right Register using IC # 7474 (iii) Construction and verification of a 2-bit Shift Left Register using IC # 7474 (iv) Verification of SISO, SIPO, PISO & PIPO Shift Registers. 7. Synchronous & Asynchronous Counters (i) Construction and verification of 2-bit Ripple counter using J-K FF. (ii) Construction and verification of Mod-3 up and Mod-3 down synchronous counter. (iii) Construction and verification of 2-bit Ring counter using J-K FF. (iv) Construction and verification of 2-bit twisted Ring (Johnson) counter using J-K FF. 8. Design and construction of a 4 bit sequence generator 9. Digital to Analog Converter (DAC). Construction & Verification of D/A converters using following methods. a) Weighted Resistor type b) R-2R ladder network type 10. Analog to Digital Converter (ADC). Construction & Verification of A/D Converter using following methods. a) Counter type b) Successive Approximation type 11. Familiarization with multisim. Design of various Digital Circuits using Multisim. 16