Microprocessor & Microcontroller Model Questions

CYCLE TEST – III

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

Sub Code : CS2252 Year : II

Subject Name : Microprocessor & Microcontroller Semester : IV

Total Marks : 60 Duration : 2 hrs

PART-A

Answer all the questions 10x2=20 Marks

1. What is coprocessor?
2. Name the three bus allocation schemes used in loosely coupled multiprocessor configuration
3. What are the functional parts of control unit in 8087
4. How many I/O channel are available in8089
5. What is DMA data transfer
6. What is key de bouncing
7. Draw the command word format for 8251
8. What are the modes of operation in 8253?
9. What is the difference between simplex and Duplex?
10. Draw the command word format for 8255.

PART - B

Answer any Four Questions 4 x10 =40 Marks

11. Explain in detail with neat diagram about the keyboard and display controller (10)

12. Describe the architecture of 8253 (10)

13. Explain the programmable interrupt controller 8259 with neat diagram (10)

14. Explain in detail about the multiprocessor configuration (10)

15. Explain the architecture of 8089 with neat diagram (10)

COM+: Definition

COM+ Tutorial from Scratch has two parts. Part I has basic concept of COM+ and its related topics. Part II will teach you how to use COM+ in real world applications.


This article is an extended version of my previous article " What COM+ exactly is?". This tutorial explains what is COM+ and how it works in real world applications. I have used Windows 2000 and VC++ 6.0.
Windows DNA is the first steps to understand COM+.
Windows DNA
Windows DNA is a framework that describes how to develop multi-tier, high performance, scalable, and distributed applications over the network. The goal of DNA is to provide enterprise level solutions which is suitable for any size. The heart of DNA is an integrated programming model based on COM+. In other words, Windows DNA is a way to provide an enterprise based solutions from Microsoft.
Windows DNA Architecture :















Windows DNA consists of three layers

1. The Presentation Layer

This layer is responsible for information gathering from user, performing basic validation of user input, sending it to the business layer and again receiving results of the business layer and presenting these results to the user in a viewable formats such as VB forms. This layer consists tools such as VB, HTML, DHTML, Win32 applications, Client-Server scripting, Java Applets, Netscape Plug-Ins, ActiveX controls

2. The Business Layer

This layer is responsible for receiving input from the presentation layer, interacting with the data access layer to process the information and sending back the processed information to the presentation layer. This layer provides business rules and services to help to write scalable applications. These services are tightly integrated with each other and the underlying operating system and exposed in a unified way through COM. They include the following:
Web services, through Microsoft Internet Information Server ( IIS ).
Transaction and component services, through Microsoft Transaction Server ( MTS ).
Queuing and asynchronous services, through Microsoft Message Queue Server ( MSMQ).
Server-side scripting, via Active Server Pages (ASP).
Interoperability services, such as the COM Transaction Integrator ( COMTI ) for accessing the IBM Customer Information Control System (CICS) and IBM Infromation Management Systems (MIS).
3. The Data Access Layer
This layer directly interact with the data which usually reside in the databases such as SQL Server or Oracle. This layer is responsible for storage, retrieval, and general maintenance of data as well integrity of data. The Windows DNA approach of data access is called "Universal Data Access'. UDA is a set of system level and application level programming models called OLE-DB, ADO and RDO.
COM+: Definition

In 1992, Microsoft evolved OLE ( Object linking and embedding ) which was named as COM ( 1995 ) later with new enhancements and features. In 1996, COM started supporting distributing computing and Microsoft named it as DCOM ( Distributed COM). At the same time Microsoft developed one new transaction server called Microsoft Distributed Transaction Coordinator (MDTC) which was enhanced to Microsoft Transaction Server (MTS) in 1997. In 1997, Microsoft developed one more server for queuing services called Microsoft Message Queue Server ( MSMQ). Now what??? After all these development, In 1999, Microsoft combined all these services in an integrated runtime environment which is called COM+. In other words, COM+ is an integrated environment which provides developers COM, MTS, MSMQ and some other services.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT I QUESTIONS 1

16.            What do you mean by ²Best case-Efficiency” of an algorithm?

The ²Best case-Efficiency” of an algorithm is its efficiency for the Best-case input of size n, which is an input(or inputs)  of size n for which the algorithm runs the fastest among all possible inputs of that size.

    Ex: if you want to sort a list of numbers in ascending order when the numbers are given in ascending order. In this running time will be the smallest.

17.            Define the ²Average-case efficiency” of an algorithm?

The ²Average-case efficiency” of an algorithm is its efficiency for the  input of size n,  for which the algorithm runs between the best case and the worst case among all possible inputs of that size.

18.            What do you mean by “Amortized efficiency”?

The “Amortized efficiency” applies not only a single run of an algorithm but rather to a sequence of operations performed on the same data structure. It turns out that in some situations a single operation can be expensive ,but the total  time for an entire sequence of n such operations is always significantly better than the worst case efficiency of that single operation multiplied by n. This is known as “Amortized efficiency”.

19.            How to measure the algorithm’s efficiency?

It is logical to investigate the algorithm’s efficiency as a function of some parameter n indicating the algorithm’s input size.

Example: It will be the size of the list for problems of sorting, searching, finding the list’s smallest element, and most other problems dealing with lists.

20.            What is called the basic operation of an algorithm?

            The most important operation of the algorithm is the operation contributing the most to the total running time is called basic operation of an algorithm.

21.            How to measure an algorithm’s running time?

Let C_op be the time of execution of an algorithm’s basic iteration on a particular computer and let C (n) be the number of times this operation needs to be executed for this algorithm.  Then we can estimate the running time T(n) of a program implementing this algorithm on that computer by the formula

                                    T(n)   ≈  C_op C(n)

22.            Define order of growth.

            The efficiency analysis framework concentrates on the order of growth of an algorithm’s basic operation count as the principal indicator of the algorithm’s efficiency.  To compare and rank such orders of growth we use three notations

1)                                                      O (Big oh) notation

2)                                                      Ω (Big Omega) notation &

3)                                                      Θ (Big Theta) notation

23.            Define Big oh notation May/June 2006, April/May 2008

A function t(n) is said to be in O(g(n)) denoted t(n) ε O (g(n)), if t(n) is bounded above by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some non negative integer n₀ such that

                                    T (n) < c g (n) for n > n₀

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT I QUESTIONS

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS

UNIT –I

  1.                What is an Algorithm?  May/June 2006, Nov/Dec 2008

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time

2.                State the Euclid’s algorithm for finding GCD of two given numbers.

ALGORITHM Euclid (m, n)

// Computes gcd(m,n) by Euclid’s algorithm

//Input   : Two nonnegative, not-both-zero integers m and n

//Output: Greatest common divisor of m and n

while n ¹ 0 do

                                    r ß m mod n

                                    m ß n

                                    n ß r

return m.

3.                What are Sequential Algorithms?

The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.

4.                What are Parallel Algorithms?

The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.

5.                What is Exact and Approximation algorithm?

The principal decision to choose solving the problem exactly is called exact algorithm.

The principal decision to choose solving the problem approximately is called Approximation algorithm.

6.                What is Algorithm Design Technique?  Nov/Dec 2005

            An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

7.                Define Pseudo code.

A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS PART B QUESTIONS

PART-B

I-UNIT

1. (a) Describe the steps in analyzing & coding an algorithm. (10)

    (b) Explain some of the problem types used in the design of

          algorithm. (6)

2.(a) Discuss the fundamentals of analysis framework . (10)

   (b) Explain the various asymptotic notations used in algorithm design. (6)

3. (a) Explain the general framework for analyzing the efficiency of algorithm. (8)

    (b) Explain the various Asymptotic efficiencies of an algorithm. (8)

4. (a) Explain the basic efficiency classes. (10)

    (b) Explain briefly the concept of algorithmic strategies. (6)

5. Describe briefly the notions of complexity of an algorithm. (16)

6. (a) What is Pseudo-code?Explain with an example. (8)

    (b) Find the complexity C(n) of the algorithm for the worst

     case,best case and average case.(Evaluate average case complexity for n=3,Where n is the   

     number of inputs) (8)

7. Set up & solve a recurrence relation for the number of key comparisons made by above  

     pseudo code. (4)

II-UNIT

1) Write a pseudo code for divide & conquer algorithm for merging two sorted arrays in to a single sorted one.Explain with example. (12)

2) Construct a minimum spanning tree using Kruskal’s algorithm with your own example. (10)

3) Explain about Knapsack Problem with example

4) Explain Dijikstra algorithm (8)

5) Define Spanning tree.Discuss design steps in Prim’s algorithm to construct minimum spanning   

    tree with an example. (16)

6)Explain Kruskal’s algorithm. (8)

7) Explain about binary search with example.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT V QUESTIONS

UNIT V

1) Define tractable and intractable problems

Problems that can be solved in polynomial time are called tractable problems, problems that cannot be solved in polynomial time are called intractable problems.

2) Explain the theory of computational complexity

A problem's intractability remains the same for all principal models of computations and all reasonable input encoding schemes for the problem under consideration

3)Explain class P problems

Class P is a class of decision problems that can be solved in polynomial time by(deterministic) algorithms. This class of problems is called polynomial.

4)Explain undecidable problems

If the decision problem cannot be solved in polynomial time, and if the decision problems cannot be solved at all by any algorithm. Such problems are called Undecidable.

5) Explain the halting problem

Given a computer program and an input to it,determine whether the program will halt on that input or continue working indefinitely on it.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT IV QUESTIONS

UNIT IV

l) Explain Backtracking

The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.

> If a partially constructed solution can be developed further without violating the problem's constraints, it is done by taking the first remaininig legitimate option for the next component.

> If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.

In this case, the algorithm backtracks to replace the last component of the partially constructed solution with its next option

2) Explain State Space Tree

If it is convenient to implement backtracking by constructing a tree of choices being made, the tree is called a state space tree. Its root represents an initial state before the search for a solution begins.

3) Explain promising and nonpromising node

A node in a state space tree is said to be promising if it corresponds to a partially constructed solution that may still lead to a complete solution;otherwise it is called nonpromising

4) Explain n-Queens problem

The problem is to place n queens on an n by n chessboard so that no two queens attack each other by being in the same row or same column or on the same diagonal.

5) Explain Subset-Sum Problem

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT III QUESTIONS

UNIT III

1)Define Dynamic Programming

Dynamic programming is a technique for solving problems with overlapping problems. Typically, these subproblems arise from a recurrence relating a solution to a given problem with solutions to its smaller subproblems of the same type. Rather than solving overlapping subproblems again and again, dynamic programming suggests solving each of the smaller sub problems only once and recording the results in a table from which we can then obtain a solution to the original problem.

2) Define Binomial Coefficient

                                                                                         n

The Binomial Coefficient, denoted C(n,k) or   k     is the number of Combinations(subsets) of k elements from an n-element set(0<k<n). The name "binomial coefficients" comes from the participation of these numbers in the so called binomial formula

(a+b)ⁿ =(n,0)aⁿ+..........+C(n,i)a^n-ibⁱ+.......+C(n,n)bⁿ

3) Define Transitive closure

The transitive closure of a directed graph with n vertices can be defined as the n by n Boolean matrix T = {ti,}, in which the element in the i^th row (1<i<n) and the j^th column (l<j<n) is 1 if there exists a non trivial directed path from the i^th vertex to j^th vertex ; otherwise , t_ij is 0.

4) Explain Warshalls algorithm

Warshall's algorithm constructs the transitive closure of a given digraph with n vertices through a series of n by n Boolean matrices  R⁽⁰⁾, ………, R^(k-l)R^(k),…….., R⁽ⁿ⁾

Each of these matrices provides certain information about directed paths in the digraph.

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT II QUESTIONS

UNIT II

1) Explain divide and conquer algorithms

Divide and conquer is probably the best known general algorithm design technique. It work according to the following general plan

i)A problem's instance is divided into several smaller instances of the same problem, ideally of about the same size.

ii) The smaller instances are solved

iii) If necessary, the solutions obtained for the smaller instances are combined to get a solution to the original problem

2) Define Merge Sort

Merge sort is a perfect example of a successful application of the divide and conquer technique. It sorts a given array A[0...n-l] by dividing it into two halves A[0...[n/2] - 1] and A[[n/2]....n-l], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.

3) Define Binary Search

Binary Search is remarkably efficient algorithm for searching in a sorted array. It works by comparing a search key K with the array's middle element A[m]. If they match, the algorithm stops; Otherwise, the same operation is repeated recursively for the first half of the array if K< A[m] and for the second half if K > A[m]

A[0].............A[m-l] A[m] A[m+l]............. A[n-l]

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS UNIT I QUESTIONS

CS2251 -DESIGN AND ANALYSIS OF ALGORITHMS

UNIT –I

  1.                What is an Algorithm?  May/June 2006, Nov/Dec 2008

An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time

2.                State the Euclid’s algorithm for finding GCD of two given numbers.

ALGORITHM Euclid (m, n)

// Computes gcd(m,n) by Euclid’s algorithm

//Input   : Two nonnegative, not-both-zero integers m and n

//Output: Greatest common divisor of m and n

while n ¹ 0 do

                                    r ß m mod n

                                    m ß n

                                    n ß r

return m.

3.                What are Sequential Algorithms?

The central assumption of the RAM model is that instructions are executed one after another, one operation at a time. Accordingly, algorithms designed to be executed on such machines are called Sequential algorithms.

4.                What are Parallel Algorithms?

The central assumption of the RAM model does not hold for some newer computers that can execute operations concurrently, i.e., in parallel algorithms that take advantage of this capability are called Parallel algorithms.

5.                What is Exact and Approximation algorithm?

The principal decision to choose solving the problem exactly is called exact algorithm.

The principal decision to choose solving the problem approximately is called Approximation algorithm.

6.                What is Algorithm Design Technique?  Nov/Dec 2005

            An algorithm design technique is a general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

7.                Define Pseudo code.

A Pseudo code is a mixture of a natural language and programming language like constructs. A pseudo code is usually more precise than a natural language, and its usage often yields more succinct algorithm descriptions.

DESIGN AND ANALYSIS OF ALGORITHMS SYLLABUS 2012

SYLLABUS

CS 2251                  DESIGN AND ANALYSIS OF ALGORITHMS                                  3 1 0 4

UNIT I                                                                                                                                 9

Algorithm Analysis – Time Space Tradeoff – Asymptotic Notations – Conditional asymptotic notation – Removing condition from the conditional asymptotic notation - Properties of big-Oh notation – Recurrence equations – Solving recurrence equations – Analysis of linear search.

UNIT II                                                                                                                               9

Divide and Conquer: General Method – Binary Search – Finding Maximum and Minimum – Merge Sort – Greedy Algorithms: General Method – Container Loading – Knapsack Problem.

UNIT III                                                                                                                             9

Dynamic Programming: General Method – Multistage Graphs – All-Pair shortest paths – Optimal binary search trees – 0/1 Knapsack – Travelling salesperson problem .

UNIT IV                                                                                                                             9

Backtracking: General Method – 8 Queens problem – sum of subsets – graph coloring – Hamiltonian problem – knapsack problem.

UNIT V                                                                                                                               9

Graph Traversals – Connected Components – Spanning Trees – Biconnected components – Branch and Bound: General Methods (FIFO & LC) – 0/1 Knapsack problem – Introduction to NP-Hard and NP-Completeness.

TUTORIAL  = 15                                         Total = 60

TEXT BOOK:

1.                  Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second Edition, Universities Press, 2007. (For Units II  to V)

2.                  K.S. Easwarakumar, Object Oriented Data Structures using C++, Vikas Publishing House pvt. Ltd., 2000 (For Unit I)

REFERENCES:

1.      T. H. Cormen, C. E. Leiserson, R.L.Rivest, and C. Stein, "Introduction to Algorithms",      Second Edition, Prentice Hall of India Pvt. Ltd, 2003.

2.      Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, "The Design and Analysis of Computer Algorithms",  Pearson Education, 1999.

DESIGN AND ANALYSIS OF ALGORITHMS ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER DOWNLOAD

CS2251 - DESIGN AND ANALYSIS OF ALGORITHMS ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER DOWNLOAD

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2010.

Fourth Semester

Computer Science and Engineering

CS2251 - DESIGN AND ANALYSIS OF ALGORITHMS

(Regulation 2008)

Time: Three hours                                                                                                  Maximum:100 marks

Answer ALL Questions.

PART A- (10 X 2= 20 marks)

1. Differentiate Time complexity from Space complexity.

2. What is a Recurrence Equation?

3. What is called Substitution method?

4. What is an Optimal solution?

5. Define Multistage Graphs.

6. Define Optimal Binary Search Tree.

7. Differentiate Explicit and Implicit Constraints.

8. What is the difference between a Live Node and a Dead Node?

9. What is a Biconnected Graph?

10. What is a FIFO branch - and - bound algorithm?

PART B- (5 X 16 = 80 Marks)

NETWORKS TYPES

Personal Area Network

•A PAN is a network that is used for communicating among computers and computer devices (including telephones) in close proximity of around a few meters within a room

•It can be used for communicating between the devices themselves, or for connecting to a larger network such as the internet

•PAN’s can be wired or wireless

nPAN’s can be wired with a computer bus such as a universal serial bus: USB (a serial bus standard for connecting devices to a computer, where many devices can be connected concurrently)

nPAN’s can also be wireless through the use of  bluetooth (a radio standard designed for low power consumption for interconnecting computers and devices such as telephones, printers or keyboards to the computer) or IrDA (infrared data association) technologies.

Local Area Network

•A LAN is a network that is used for communicating among computer devices, usually within an office building or home

•LAN’s enable the sharing of resources such as files or hardware devices that may be needed by multiple users

•Is limited in size, typically spanning a few hundred meters, and no more than a mile

•Is fast, with speeds from 10 Mbps to 10 Gbps

•Requires little wiring, typically a single cable connecting to each device

•Has lower cost compared to MAN’s or WAN’s

LAN basics

nLAN’s can be either wired or wireless. Twisted pair, coax or fiber optic cable can be used in wired LAN’s

nNodes in a LAN are linked together with a certain topology. These topologies include:

nBus

nRing

nStar

nBranching tree

nA node is defined to be any device connected to the network. This could be a computer, a printer, a router, etc.

nA Hub is a networking device that connects multiple segments of the network together

nA Network Interface Card (NIC) is the circuit board that has the networking logic implemented, and provides a plug for the cable into the computer (unless wireless). In most cases, this is an Ethernet card inserted in a slot of the computer’s motherboard

nThe Network Operating System (NOS) is the software (typically part of the operating system kernel) that communicates with the NIC, and enables users to share files and hardware and communicate with other computers. Examples of NOS include: Windows XP, Windows NT, Sun Solaris, Linux, etc..

Computer Networks

•A computer network is a system for communicating between two or more computers and associated devices. It is an interconnection of computers for the purposes of sharing information and resources.

•A popular example of a computer network is the internet, which allows millions of users to share information

•Computer networks can be classified according to their size:

–Personal area network (PAN)

–Local area network (LAN)

–Metropolitan area network (MAN)

–Wide area network (WAN)