Latest Post

       FREQUENTLY ASKED QUESTIONS

                 DEL LAB GROUP A 

       (COMBINATIONAL CIRCUITS)


1. Difference between combinational & Sequential Circuit? With Examples.

  Combinational circuits are defined as the time independent circuits which do not depends upon previous inputs to generate any output are termed as combinational circuits. Sequential circuits are those which are dependent on clock cycles and depends on present as well as past inputs to generate any output.
Combinational Circuit –
  1. In this output depends only upon present input.
  2. Speed is fast.
  3. It is designed easy.
  4. There is no feedback between input and output.
  5. This is time independent.
  6. Elementary building blocks: Logic gates
  7. Used for arithmetic as well as boolean operations.
  8. Combinational circuits don’t have capability to store any state.
  9. As combinational circuits don’t have clock, they don’t require triggering.
  10. These circuits do not have any memory element.
  11. It is easy to use and handle.
Examples – Encoder, Decoder, Multiplexer, Demultiplexer
Sequential Circuit –
  1. In this output depends upon present as well as past input.
  2. Speed is slow.
  3. It is designed tough as compared to combinational circuits.
  4. There exists a feedback path between input and output.
  5. This is time dependent.
  6. Elementary building blocks: Flip-flops
  7. Mainly used for storing data.
  8. Sequential circuits have capability to store any state or to retain earlier state.
  9. As sequential circuits are clock dependent they need triggering.
  10. These circuits have memory element.
  11. It is not easy to use and handle.
    1. Examples – Flip-flops, Counters
      Block Diagram –

      2.What is Minterm & Maxterm, SOP & POS forms?

      minterm is a Boolean expression resulting in 1 for the output of a single cell, and 0s for all other cells in a Karnaugh map, or truth table.
      maxterm is a sum (OR) of all the variables in the function, in direct or complemented form. A maxterm has the property that it is equal to 0 on exactly one row of the truth table.

      Minterm: A minterm is a product term in boolean function in which every element is present is either in normal or in complemented form.
      For example if F(a,b,c) is a boolean function then the possible minterms would be abc, abc’, ab’c, ab’c’, a’bc, ab,c, a’b’c, a’b’c’ . that is for n varibale boolean function there would be 2^n possible minterms.
      There are used for sum of product(SOP) canonical forms, which is also called disjunctive normal form(DNF). The value correspond to 1 or true is selected as minterm.
      Maxterm: A maxterm is a sum term in boolean function in which every element is present is either in normal or in complemented form.
      For example if F(a,b,c) is a boolean function then the possible maxterms would be (a+b+c), (a+b+c’), (a+b’+c), ( a+b’+c’), (a’+b+c), ( a+b’+c), ( a’+b’+c), (a’+b’+c’) . that is for n varibale boolean function there would be 2^n possible maxterms.
      There are used for product of sum(POS) canonical forms, which is also called conjunctive normal form(CNF). The value correspond to 0 or false is selected as maxterm.

BCD ADDER

1. What is difference between BCD and Binary number system?

    Binary Codes:-
A binary code is basically used for representation of the binary bits 0 and 1 which are used as group of binary digits and are used for processing computer instructions and data,text and string representation,pulse code modulation in communicating across the channels,short and long distance over telephones.
A binary code can be generally classified as numeric code and alphanumeric code.Alphanumeric code contains alphabets and decimal numbers as a sequence of 0 and 1.Numeric codes only represent information in the form of 0 and 1.
For example 1:-
00010110110 is a representation of a binary number.
BCD codes:-
BCD stands for binary coded decimal in which the digits of a decimal number are encoded and are grouped into four binary digits one at a time.Its mainly used for accurate representation of decimal number and it's conversion to and fro with other number system.But the disadvantage is that arithmetic circuits to design it is complex and storage capacity is less.
The BCD can be categorised as either weighted and non weighted code.Weighted code is again further classified as positive or negative weighted code.
The positive weighted codes are 8421,2421,5211,4311 and negative weighted codes are 642–3, 631–1, 74–2–1.
To represent BCD code in the form 0 to 9 specific rules are applied.For example in a particular addition of BCD of 2 number if the result is larger than 9 it is treated as illegal code and extra 6(0110) is added to it to correct the result.
For example 8 + 5 in binary is 13. So it is a illegal code and extra 6 needs to be added to it.

2. What are the rules of BCD Addition?

In BCD addition of two numbers involve following rules:-
 i. Maximum value of the sum for two digits = 9 (max digit 1) + 9 (max digit 2) + 1 (previous addition carry) = 19
ii. If sum of two BCD digits is less than or equal to 9 (1001) without carry then the result is a correct BCD number.
iii.If sum of two BCD digits is greater than or equal to 10 (1010) the result is in-correct BCD number. Perform steps 4 for correct BCD sum.
iv.Add 6 (0110) to the result.

3. What is Binary Adder?

Full adders are devices used to add binary numbers. They are used in computers. They take two binary numbers and put them together to get a sum. In its most basic form, it uses two XOR gates, two AND gates, and an OR gate. These gates figure out what the numbers being sent in mean and if the digit needs to be turned on or not.
When solving this example: 1001 + 1100 (9 + 12 in decimal form), it would need five single bits to give an answer. The first digits in each number would go to one adder, 1 and 0. It would calculate that 1 + 0 = 1, so that first digit would be 1. The second digits from each are 0 and 0, and 0 + 0 = 0, so the second digit is 0. the third digit from each are 1 and 0, and 1 + 0 = 1, so the third digit is 1. The fourth digit in each are 1 and 1, and 1 + 1 = 10, but because this is a 2 digit number, it holds the first digit (0) and send the second digit to the next adder. The next adder sees 1, and 1 = 1, so the fifth digit is 1. If we take the sum digits in order, they come out as 10101 (21), so 1001 + 1100 = 10101 (9 + 12 = 21).
4. What are the rules of Binary Addition? 
5. Which are Basic Gates, Universal Gates and Derived Gates? 

Code Converter 

1. What is Gray Code? 
2. What are the properties of Gray Code? 
3. How to convert binary code to Gray code and Gray to Binary? 
4. How to Obtain Excess3 Code? 
5. Properties of Excess 3 Code? 
6. What is Combinational Circuit?

Multiplexer

 1. What is Mux, Demux, Decoder? 
2. Application of MUX, Demux 
3. Mux:=Ratio of Select lines with number of input lines 
4. Demux:= Ratio of select lines with number of Output Lines 
5. Working of MUX, DEMUX & Decoder

Comparator 

1. What is Comparator? 
2. Real time application of Comparator 
3. Which IC is used as 4 bit comparator? 
4. How Comparator IC works?

Parity Generator

 1. What is parity Bit?
 2. Types of Parity? Some data will be given you have to identify the parity of data.
 3. What is Parity Generator & Parity Detector? 
4. Applications of Parity Bit 

GROUP B (SEQUENTIAL CIRCUITS)

 Flip Flop Conversion ----

1. What is Flip Flop? 
2. Types of Flip Flop
 3. Truth Table and Excitation table of All Flip Flops 
4. What is truth table? 
5. What is excitation table? 
6. Full Form of J-K, S-R, D & T FF 
7. Drawback of S-R FF, Race around Condition, Master Slave J-K FF 
8. Process of Conversion of one FF to another. 
9. What is Preset and Clear input of FF?

Asynchronous Up/Down Counter--

 1. What is Counter?
 2. What is difference between Synchronous and Asynchronous Counter? 
 3. What is Ripple Counter? 
4. What is Register? 
5. What is up counter & Down Counter? 
6. How to design Combined UP and Down Counter?

MOD N Counter 

1. What is IC 7490? How it works? 
2. What is the output of mod n counter? 
3. How may IC require to design Mod 100 Counter? 
4. How many FF are used in IC 7490. 

Ring and Johnson Counter 

1. Which FF’s are used to design Ring and Johnson Counter? 
2. What is the real time application of Ring and Johnson Counter? 
3. Is it a Synchronous circuit or Asynchronous? 
4. Types of Registers

Sequence Generator 

1. What is Sequence Generator? 
2. How many Flip flops are used to design a given sequence (ex: 2-3-6-8-2 etc.) 
3. Which FFs are used to design sequence generator? 
4. What is the difference between Sequence Generator & Counter? 
5. Difference between Mealy and Moore circuit 

ASM & MUX Controller Method 

1. What is ASM Chart? How it is different from Flow Chart? 
2. What is MUX Controller Method? 
3. What is State Diagram? 
4. What is State Table? 
5. What is State Transition Table? 

GROUP C (VHDL) 

1. What is VHDL? 
2. Full Form of VHDL 
3. Different Modelling Style of VHDL 
4. What is Entity? 
5. What is component? 
6. What is port and their types? 
7. What is the difference between Data Flow, Behavioural & Structural Architecture? 
8. What is Library, Package etc. 
9. What Is Signal in VHDL? 
10.What is Statement? 
11.What is Process? 
12.What is sensitivity List? 
13.What is Simulation?

Full Adder 

1. What is HA, FA ? 
2. Truth table of half Adder, Full Adder, Half Substractor, Full Substractor 
3. Equations of half Adder, Full Adder, Half Substractor, Full Substractor 

MUX 

1. What is MUX? 
2. What is STD_Logic_Vector & STD_Logic? 
3. Syntax for Variable Definition. 
4. What is Concurrent and Sequential Statements? 

D FF

 1. What is D FF 
2. What is Behavioural Architecture? 
3. TT of D FF. 
4. What is CLKÉvent? Rising Edge Falling Edge? 

Counter 

1. What is UP/Down Counter? 
2. What are Triggering methods?

Savitribai Phule Pune University Second Year of Computer Engineering (2015 Course)

210243: Data Structures and Algorithms



Prerequisites: - FPL I and FPL II 

Course Objectives:

 To understand the standard and abstract data representation methods. 
 To acquaint with the structural constraints and advantages in usage of the data. 
 To understand the memory requirement for various data structures. 
 To operate on the various structured data. 
 To understand various data searching and sorting methods with pros and cons. 
 To understand various algorithmic strategies to approach the problem solution. 

Course Outcomes: On completion of the course, student will be able to– 

 To discriminate the usage of various structures in approaching the problem solution. 
 To design the algorithms to solve the programming problems. 
 To use effective and efficient data structures in solving various Computer Engineering domain problems. 
 To analyze the problems to apply suitable algorithm and data structure. 
 To use appropriate algorithmic strategy for better efficiency

Course Contents:

Unit I -Introduction to Algorithm and Data Structures 09 Hours -

Algorithms- Problem Solving, Introduction to Algorithms, Characteristics of algorithms, Algorithm design tools: Pseudo code and flowchart, Analysis of Algorithms, Complexity of algorithms- Space complexity, Time complexity, Asymptotic notation- Big-O, Theta and Omega, standard measures of efficiency. 
Data Structures- Data structure, Abstract Data Types (ADT), Concept of linear and Non-linear, static and dynamic, persistent and ephemeral data structures, and relationship among data, data structure, and algorithm, From Problem to Program. 
Algorithmic Strategies- Introduction to algorithm design strategies- Divide and Conquer, and Greedy strategy. 
Recurrence relation - Recurrence Relation, Linear Recurrence Relations, With constant Coefficients, Homogeneous Solutions. Solving recurrence relations 

Unit II Linear Data Structures Using Sequential Organization 09 Hours 

Sequential Organization, Linear Data Structure Using Sequential Organization, Array as an Abstract Data Type, Memory Representation and Address Calculation, Inserting an element into an array, Deleting an element, Multidimensional Arrays, Two-dimensional arrays, n- dimensional arrays, Concept of Ordered List, Single Variable Polynomial, Representation using arrays, Polynomial as array of structure, Polynomial addition, Polynomial multiplication, Sparse Matrix, Sparse matrix representation, Sparse matrix addition, Transpose of sparse matrix, String Manipulation Using Array. Case Study- Use of sparse matrix in Social Networks and Maps.

Unit III Linked Lists 09 Hours 

Concept, Comparison of sequential and linked organizations, Primitive operations, Realization of Linked Lists, Realization of linked list using arrays, Dynamic Memory Management, Linked list using dynamic memory management, Linked List Abstract Data Type, Linked list operations, Head pointer and header node, 
Types of linked list- Linear and circular linked lists, Doubly Linked List and operations, Circular Linked List, Singly circular linked list, Doubly circular linked list, Polynomial Manipulations - Polynomial addition, Multiplication of two polynomials using linked list. 
Generalized Linked List (GLL) concept, representation of polynomial and sets using GLL. Case Study- Garbage Collection.

Unit IV Stacks 09 Hours Stacks-

Concept, Primitive operations, Stack Abstract Data Type, Representation of Stacks Using Sequential Organization, stack operations, Multiple Stacks, Applications of Stack- Expression Evaluation and Conversion, Polish notation and expression conversion, Need for prefix and postfix expressions, Postfix expression evaluation, Linked Stack and Operations. 
Recursion- concept, variants of recursion- direct, indirect, tail and tree, Backtracking algorithmic strategy, use of stack in backtracking. 
Case Study- 4 Queens problem, Androidmultiple tasks/multiple activities and back stack. 

Unit V Queues 09 Hours 

Concept,Queue as Abstract Data Type, Realization of Queues Using Arrays , Circular Queue, Advantages of using circular queues, Multi-queues, Deque, Priority Queue, Array implementation of priority queue, Linked Queue and operations. 
Case study- Priority queue in bandwidth management.

Unit VI Sorting and Searching 09 Hours 

Searching- Search Techniques, Sequential search, variant of sequential search- sentinel search, Binary search, Fibonacci search. Case Study- Use of Fibonacci search in non-uniform access memory storage and in Optimization of Unimodal Functions. 
Sorting- Types of sorting-Internal and external sorting, General sort concepts-sort order, stability, efficiency, number of passes, Sorting methods- Bubble sort, Insertion sort, Selection sort, Quick sort, Heap sort, Shell sort, Bucket sort, Radix sort, Comparison of All Sorting Methods.
Case Study- Timsort as a hybrid stable sorting algorithm.

Books: 
Text: 1. Brassard & Bratley, ―Fundamentals of Algorithmics‖, Prentice Hall India/Pearson Education, ISBN 13-9788120311312. 2. Horowitz and Sahani, ―Fundamentals of Data Structures in C++‖, University Press, ISBN 10: 0716782928 ISBN 13: 9780716782926. 3. Goodrich, Tamassia, Goldwasser, ―Data Structures and Algorithms in C++‖, Wiley publication, ISBN-978-81-265-1260-7

Digital Electronics & Logic Design



Course Objectives:

  • To understand the functionality and design of Combinational and Sequential Circuits 
  • To understand and compare the functionalities, properties and applicability of Logic Families. 
  • To understand concept of programmable logic devices and ASM chart and get acquainted with design of synchronous state machines. 
  • To design and implement digital circuits using VHDL. 

Course Outcomes:

  • On completion of the course, student will be able to– 
  • Realize and simplify Boolean Algebraic assignments for designing digital circuits using KMaps. 
  • Design and implement Sequential and Combinational digital circuits as per the specifications. 
  • Apply the knowledge to appropriate IC as per the design specifications. 
  • Design simple digital systems using VHDL. 
  • Develop simple embedded system for simple real world application.

COURSE CONTENTS


Unit I - Combinational Logic Design 

Logic minimization: Representation of truth-table, Sum of Product (SOP) form, Product of Sum (POS) form, Simplification of logical functions, Minimization of SOP and POS forms using KMaps up to 4 variables and Quine-McCluskey Technique, realization of logic gates. 
Design of Combinational Logic: Code converter - BCD, Excess-3, Gray code, Binary Code. Half- Adder, Full Adder, Half Subtractor, Full Subtractor, Binary Adder (IC 7483), BCD adder, Look ahead carry generator, Multiplexers (MUX): MUX (IC 74153, 74151), MUX tree, Demultiplexers (DEMUX)- Decoder. (IC 74138, IC 74154). DMUX Tree, Implementation of SOP and POS using MUX, DMUX, Comparators, Parity generators and Checker, Priority Encoders.

Unit II -Sequential Logic Design 

Flip- flop: SR, JK, D, T; Preset & Clear, Master and Slave Flip Flops, Truth Tables and Excitation tables, Conversion from one type to another type of Flip Flop. Registers: Buffer register, shift register, Applications of shift registers. Counters: Asynchronous counter. Synchronous counter, ring counters, BCD Counter, Johnson Counter, Modulus of the counter (IC 7490). 
Synchronous Sequential Circuit Design: Models – Moore and Mealy, State diagram and State Tables, Design Procedure, Sequence generator and detector. Asynchronous Sequential Circuit Design: Difference with synchronous circuit design, design principles and procedure, applications.

Unit III -Algorithmic State Machines

Algorithmic State Machines: Finite State Machines (FSM) and ASM, ASM charts, notations, construction of ASM chart and realization for sequential circuits, Sequence Generator, Types of Counters. 
VHDL: Introduction to HDL, Data Objects & Data Types, Attributes., VHDL- Library, Design Entity, Architecture, Modeling Styles, Concurrent and Sequential Statements
Design Examples: VHDL for Combinational Circuits-Adder, MUX, VHDL for Sequential Circuits, Synchronous and Asynchronous Counter.

Unit IV -Programmable Logic Devices 

ROM as PLD, Programmable Logic Array (PLA), Programmable Array Logic (PAL), Designing combinational circuits using PLDs

Unit V- Logic Families 

Classification of logic families: Unipolar and Bipolar Logic Families, Characteristics of Digital ICs: Speed, power dissipation, figure of merits, fan-out, Current and voltage parameters, Noise immunity, operating temperature range, power supply requirements. 
Transistor-Transistor Logic: Operation of TTL, Current sink logic, TTL with active pull up, TTL with open collector output, Schottkey TTL, TTL characteristics, TTL 5400/7400 series.
CMOS: CMOS Inverter, CMOS characteristics, CMOS configurations- Wired Logic, Open drain outputs.
Interfacing: TTL to CMOS and CMOS to TTL. Tristate Logic and Tristate TTL inverter.

Unit VI -Microcontrollers 

Comparison of typical microprocessor and microcontroller. Microcontroller 8051: Features, architecture, Pin description.
Programming model– Special Function Registers, addressing modes, instruction set, Timers and Counters, serial communication, interrupts, interfacing with ADC and DAC.

TEXT BOOKS 

1. R.P. Jain, ―Modern Digital Electronics‖, TMH, 2012, ISBN–13: 978-0-07- 066911-6. 
2. Stephen Brown, Zvonko Vranesic, ―Fundamentals of Digital Logic with VHDL Design‖, McGraw-Hill, ISBN–13:978-1-25-902597-6. 
3. Muhammas Mazidi, Janice Mazidi and Rolin McKinlay, ―The 8051 Microcontroller and Embedded Systems using Assembly and C‖, Pearson Education, ISBN-13: 9788131758991

REFRENCE BOOKS

1. John Yarbrough, ―Digital Logic applications and Design‖, Cengage Learning, ISBN – 13: 978-81-315-0058-3 
2. D. Leach, Malvino, Saha, ―Digital Principles and Applications‖, Tata McGraw Hill, ISBN – 13:978-0-07-014170-4. 
3. Anil Maini, ―Digital Electronics: Principles and Integrated Circuits‖, Wiley India Ltd, ISBN:978-81-265-1466-3. 
4. Norman B & Bradley, ―Digital Logic Design Principles, Wiley India Ltd, ISBN:978-81- 265-1258-4. 
5. Scott Mackenzie, ―The 8051 Microcontroller‖, Prentice Hall India, ISBN-13: 978- 0130195623

Discrete Mathematics -Paper Pattern


Course Objectives: 

  • To use appropriate set, function and relation models to understand practical examples, and interpret the associated operations and terminologies in context. 
  • Determine number of logical possibilities of events. 
  • Learn logic and proof techniques to expand mathematical maturity. 
  • Formulate problems precisely, solve the problems, apply formal proof techniques, and explain the reasoning clearly.

Course Outcomes: 


On completion of the course, student will be able to– 

  • Solve real world problems logically using appropriate set, function, and relation models and interpret the associated operations and terminologies in context. 
  • Analyze and synthesize the real world problems using discrete mathematics. 


Course Contents
Unit I :
Set Theory and Logic -09 Hours 

Discrete Mathematics, Significance of Discrete Mathematics in Computer Engineering.
  • Sets– Naïve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Need for Sets, Representation of Sets, Set Operations, cardinality of set, principle of inclusion and exclusion.
  • Types of Sets – Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets. Introduction to bounded and unbounded sets and multiset. Countability of Rational Numbers Using Cantor Diagonalization Argument, power set. 
  • Propositional Logic- logic, Propositional Equivalences, Application of Propositional Logic-Translating English Sentences, Proof by Mathematical Induction and Strong Mathematical Induction.
 Unit II
 Relations and Functions -09 Hours 
  • Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations , Closures of Relations, Equivalence Relations, Partial Orderings, partitions, Hasse Diagram, Lattices, Chains and Anti-Chains, Transitive Closure and Warshall‘s Algorithm, n-Ary Relations and their Applications.
  •  Functions- Surjective, Injective and Bijective functions, Inverse Functions and Compositions of Functions, The Pigeonhole Principle.

Unit III 
Counting -09 Hours 

The Basics of Counting, rule of Sum and Product, Permutations and Combinations, Binomial Coefficients and Identities, Generalized Permutations and Combinations, Algorithms for generating Permutations and Combinations. 


Unit IV 
Graph Theory -09 Hours 

Graphs and Graph Models, Graph Terminology and Special Types of Graphs, Representing Graphs and Graph Isomorphism, Connectivity, Euler and Hamilton Paths, Single source shortest path- Dijkstra's Algorithm, Planar Graphs, Graph Colouring. Case Study- Web Graph, Google map.

Unit V 
Trees -09 Hours 

Introduction, properties of trees, Binary search tree, decision tree, prefix codes and Huffman coding, cut sets, Spanning Trees and Minimum Spanning Tree, Kruskal‘s and Prim‘s algorithms, The Max flow- Min Cut Theorem (Transport network). Case Study- Game Tree, Mini-Max Tree. 

Unit VI 
Algebraic Structures and Coding Theory -09 Hours

The structure of algebra, Algebraic Systems, Semi Groups, Monoids, Groups, Homomorphism and Normal Subgroups, and congruence relations, Rings, Integral Domains and Fields, coding theory, Polynomial Rings and polynomial Codes, Case Study- Brief introduction to Galois Theory –Field Theory and Group Theory. 


 REFERENCE BOOKS

1. Kenneth H. Rosen, ―Discrete Mathematics and its Applications‖, Tata McGraw-Hill, ISBN 978-0-07-288008-3, 7th Edition.

 2. C. L. Liu, ―Elements of Discrete Mathematics‖, TMH, ISBN 10:0-07-066913-9.

3. Bernard Kolman, Robert C. Busby and Sharon Ross, ―Discrete Mathematical Structures‖, Prentice-Hall of India /Pearson, ISBN: 0132078457, 9780132078450. 

4. N. Biggs, ―Discrete Mathematics‖, 3rd Edition, Oxford University Press, ISBN 0 –19 850717 – 8.

 5. Narsingh Deo, ―Graph with application to Engineering and Computer Science‖, Prentice Hall of India, 1990, 0 – 87692 – 145 –

 6. Dr. K. D. Joshi, ―Foundations of Discrete Mathematics‖, New Age International Limited, Publishers, January 1996, ISBN: 8122408265, 9788122408263

 7. C.D. Cantrell, ―Modern Mathematical Methods for Engineers‖, Cambridge University Press, ISBN-0521670497 

8. Eric Gossett, ―Discrete Mathematical Structures with Proofs‖, Wiley India Ltd, ISBN:978-81-265-2758-8.

 9. Sriram P & Steven S, ―Computational Discrete Mathematics‖, Cambridge University Press, ISBN 13: 978-0-521-73311-3.

FREE PAID E-BOOKS ::

(CLICK THE TITLE BUTTON TO DOWNLOAD  E-BOOKS)

Kenneth H. Rosen, ―Discrete Mathematics and its Applications‖, Tata McGraw-Hill, ISBN 978-0-07-288008-3, 7th Edition.


C. L. Liu, ―Elements of Discrete Mathematics‖, TMH, ISBN 10:0-07-066913-9.

Schaum's Outlines Discrete Mathematics

Discrete Mathematics For Computer Science




MKRdezign

Contact Form

Name

Email *

Message *

Powered by Blogger.
Javascript DisablePlease Enable Javascript To See All Widget