Search This Blog

COMPUTER GRAPHICS CS2401 ANNA UNIVERSITY QUESTION PAPER |CS2401 CG NOVEMBER/DECEMBER 2011 PREVIOUS YEAR QUESTION PAPER

Saturday, January 28, 2012 · 0 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Seventh Semester
Computer Science and Engineering
CS 2401 — COMPUTER GRAPHICS
(Common to Information Technology)
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. Write down any two line attributes.
2. Differentiate window and viewport.
3. What are spline curves?
4. Define quadric surfaces.
5. What is animation?
6. Define keyframes.
7. What do you mean by shading of objects?
8. What is texture?
9. Define fractals.
10. Differentiate Mandelbrot and Julia sets.


PART B — (5 × 16 = 80 marks)


11. (a) Write down and explain the midpoint circle drawing algorithm. Assume 10 cm as the radius and co-ordinate origin as the centre of the circle.
Or
(b) Explain in detail the Cohen-Sutherland line clipping algorithm with an example.
12. (a) Differentiate parallel and perspective projections and derive their projection matrices.
Or
(b) With suitable examples, explain all 3D transformations.
13. (a) Write notes on RGB and HSV color models.
Or
(b) Discuss the following:
(i) Methods to draw 3D objects. (8)
(ii) Basic OPENGL operations. (8)
14. (a) Explain the following:
(i) Adding texture to faces. (8)
(ii) Adding shadows of objects. (8)
Or
(b) Write down and explain the details to build a camera in a program.
15. (a) Write notes on Peano curves.
Or
(b) Write about random fractals in detail.
—————————


LINEAR INTEGRATED CIRCUITS AND APPLICATIONS EE2254 ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER | EE2254 LICA PREVIOUS YEAR QUESTION PAPER NOVEMBER/DECEMBER 2011

· 0 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fourth Semester
Electrical and Electronics Engineering
EE 2254 — LINEAR INTEGRATED CIRCUITS AND APPLICATIONS
(Common to Instrumentation & Control Engineering and Electronics &
Instrumentation Engineering)
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. List the basic processes used in IC Fabrication.
2. What is meant by ion implantation?
3. What is thermal drift?
4. Define Input offset voltage.
5. Draw the circuit of first order active filter.
6. Draw the circuit diagram of sample and hold circuit.
7. Define capture range of PLL.
8. What are one, two and four quadrant multipliers?
9. What are the disadvantages of linear voltage regulators?
10. What is isolation amplifier?
PART B — (5 × 16 = 80 marks)


11. (a) (i) Explain the process of epitaxial growth in IC fabrication process with neat diagrams. (8)
(ii) With neat sketches explain the fabrication of diodes. (8)
Or
(b) (i) Explain the different isolation techniques. (8)
(ii) Describe in detail about the diffusion process of IC fabrication.(8)
12. (a) Explain in detail about the frequency compensation applied to operational amplifiers. (16)
Or
(b) Draw and explain the working of operational amplifier as 
(i) Integrator. (8)
(ii) Differentiator. (8)
13. (a) Explain the following applications of operational amplifiers.
(i) Voltage to current converter. (8)
(ii) Clamper. (8)
Or
(b) Explain in detail the working of
(i) Weighted resistor type DAC. (8)
(ii) Dual slope type ADC. (8)
14. (a) (i) Explain the working of voltage controlled oscillators. (8)
(ii) What is PLL? Explain its application as frequency multiplier. (8)
Or
(b) Explain the astable and bistable operation of IC 555 with necessarywaveforms. (16)
15. (a) Draw and explain the application of IC 723 as low voltage regulator and high voltage regulator. (16)
Or
(b) (i) Explain the block diagram of ICL 8038 function generator IC. (8)
(ii) Write short notes on opto couplers. (8)


HIGH VOLTAGE ENGINEERING EE2353 ANNA UNIVERSITY QUESTION PAPER | EE2353 HIGH VOLTAGE ENGINEERING ANNA UNIVERSITY NOV/DEC 2011 QUESTION PAPER

· 0 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Sixth Semester
Electrical and Electronics Engineering
EE 2353 — HIGH VOLTAGE ENGINEERING
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What are the causes of over voltages in power system?
2. What is counter poise wire? Give its use.
3. Write the Paschen’s law.
4. What are two main reasons for long term break down in composite dielectrics?
5. Give the specifications for standard impulse wave.
6. What are the advantages of cascaded transformer method?
7. What is Rogowski coil? Give its limitations.
8. What are the limitations of series resistance micro ammeter method?
9. What are the tests conducted on surge arrester?
10. What is insulation coordination?
PART B — (5 × 16 = 80 marks)
11. (a) (i) Give the origin and characteristics of switching surges and explain the causes of over voltage due to switching surges in EHV and UHV system. (10)
(ii) Explain the control measures for over voltage due to switching surge. (6)
Or
(b) Elaborate the discussion on protection of power system equipments using protective devices. (16)
12. (a) Explain in detail the breakdown mechanism in non-uniform fields and phenomenon of Corona. (16)
Or
(b) (i) Describe the ageing and breakdown in composite dielectrics due to partial discharge. (8)
(ii) Describe the thermal breakdown mechanism of solid dielectrics. (8)
13. (a) (i) Explain the operation of simple voltage doubler circuit. (4)
(ii) Discuss the principle of operation of vande graff generator with neat sketch. (12)
Or
(b) (i) How the impulse current is generated using capacitor bank. Explain in detail. (8)
(ii) Write a brief note on resonant transformer method. (8)
14. (a) Tabulate and explain the methods used for the measurement of high voltages and high currents. (16)
Or
(b) With neat sketch explain the sphere gap arrangement method of high voltage
measurement and give the factors influencing the measurement. (16)
15. (a) Explain the power frequency and impulse voltage test conducted on bushings.
Or
(b) Discuss the dielectric power factor test and partial discharge test conducted on high voltage cables. (16)
———————––––


EC2353 ANTENNA AND WAVE PROPAGATION ANNA UNIVERSITY MODEL QUESTION PAPER | AWP EC2353 QUESTION PAPER NOVEMBER/DECEMBER 2011

· 2 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Sixth Semester
Electronics and Communication Engineering
EC 2353 —ANTENNA AND WAVE PROPAGATION
(Regulation 2008)
(Common to PTEC 2353 - Antenna and wave Propagation for B.E.( Part- time)
Fifth Semester Electronics and communication Engineering -Regulation 2009)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What is the significance of gain of an antenna?
2. Define effective aperture of an antenna.
3. Why is loop antenna called as magnetic dipole?
4. Define Pattern Multiplication.
5. State Babinet’s Principle.
6. What are the limitations of Lens antenna?
7. Why is log periodic antenna called so?
8. What are the features of microstrip antenna?
9. Define Critical frequency.
10. What is meant by Faraday rotation?
PART B — (5 × 16 = 80 marks)
11. (a) What are Hertizian dipoles? Derive the Electric and magnetic field quantities of Infinitesimal dipole and radiation pattern. (16)
Or
(b) Explain the following parameters of an antenna:
(i) Beam solid angle
(ii) Radiation pattern
(iii) Gain
(iv) Polarization
(v) Bandwidth. (16)
12. (a) Derive the field quantities and Radiation resistance of a half wavelength dipole. (16)
Or
(b) An antenna array consists of two identical isotropic radiators spaced by a distance of d= λ/4 meters and fed with currents of equal magnitude but with a phase difference ‘β’. Evaluate the resultant radiation for β=0o and thereby identify the direction of maximum radiation. (16)
13. (a) Explain the radiation mechanism of Microwave Horn antenna with diagram. (16)
Or
(b) Explain the special features of Parabolic Reflector antenna and discuss on different types of feed used with neat diagram. (16)
14. (a) With a neat sketch, explain the construction and operation of Multielement Yagi- Uda antenna. (16)
Or
(b) With necessary illustrations explain the radiation characteristics of microstrip antenna and mention its possible application. (16)
15. (a) (i) Explain the mechanism of ionospheric propagation with neat diagram. (8)
(ii) Discuss the effects of Earth’s magnetic field on ionosphere radio wave propagation? (8)
Or
(b) (i) Explain important features of ground wave propagation? (10)
(ii) Explain the terms:
(1) Optimum working frequency
(2) Skip distance
(3) Virtual height. (6)


ADVANCED COMPUTER ARCHITECTURE CS2354 NOVEMBER/DECEMBER 2011 ANNA UNIVERSITY QUESTION PAPER | CS2354 ACA PREVIOUS YEAR QUESTION PAPER

· 0 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Sixth Semester
Computer Science and Engineering
CS 2354 — ADVANCED COMPUTER ARCHITECTURE
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What is instruction level parallelism?
2. What are the advantages of loop unrolling?
3. What are the limitations of VLIW?
4. What is the use of branch-target buffer?
5. Distinguish between shared memory multiprocessor and message-passing multiprocessor.
6. Differentiate multithreading computers from multiprocessor systems
7. Define the terms cache miss and cache hit.
8. What is RAID?
9. What is a multi-core processor?
10. What is a cell processor?


PART B — (5 × 16 = 80 marks)


11. (a) (i) Explain the data and name dependencies with suitable example. (10)
(ii) Discuss about the benefits and limitations of static branch prediction and dynamic branch prediction (6)
Or
(b) Briefly explain how to overcome data hazards with dynamic scheduling using Tomasula’s approach. (16)
12. (a) (i) Describe the architecture of Itanium processor with the help of a block diagram. (8)
(ii) Explain how ILP is achieved in EPIC processors (8)
Or
(b) (i) Describe the architectural features of IA64 processor in detail.(8)
(ii) What are the advantages and disadvantages of software-based and hardware-based speculation mechanism? (8)
13. (a) (i) Briefly compare instruction level parallelism with thread-level parallelism. (8)
(ii) Explain the basic architecture of a distributed memory multiprocessor system. (8)
Or
(b) (i) Explain various memory consistency models in detail. (10)
(ii) What is multithreading and what are the advantages of multithreading? (6)
14. (a) What is meant by cache coherence problem? Describe various protocols for cache coherence. (16)
Or
(b) Briefly explain various I/O performance measures. (16)
15. (a) (i) Describe the architecture of typical CMT processor. (8)
(ii) Discuss the design issues for simultaneous multithreading. (8)
Or
(b) (i) Explain the architectural features of IBM cell processor in detail. (10)
(ii) Briefly compare SMT and CMP architectures. (6)


MICROPROCESSORS AND MICROCONTROLLERS CS2252 ANNA UNIVERSITY QUESTION PAPER | CS 2252 MICROPROCESSORS AND MICROCONTROLLERS NOVEMBER/DECEMBER 2011 QUESTION PAPER DOWNLOAD

· 2 comments



B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fourth Semester
Computer Science and Engineering
CS 2252 – MICROPROCESSORS AND MICROCONTROLLERS
(Common to Information Technology)
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. Identify the addressing mode of the following 8085 instruction.
(a) SHLD 2500H
(b) DCR E
2. Name the machine cycles needed to execute the 8085 instruction MVIB,4FH.
3. What are the general purpose registers in 8086?
4. Give the importance of the assembler directive EVEN.
5. What are the features of closely coupled multiprocessor systems?
6. What do you mean by CCW in an I/O processor?
7. How many address lines and data lines are necessary for accessing 32Kx8 memory?
8. What is DMA?
9. What are the differences between a microprocessor and a microcontroller?
10. How is the selection of particular register bank done in 8051?


PART B —(5 × 16 = 80 marks)


11. (a) Explain the Intel 8085 Microprocessor architecture with neat diagram. (16)
Or
(b) (i) Discuss the different groups of instruction set of 8085 with suitable examples.(8)
(ii) Write an 8085 ALP to find the largest number in a array of 10 data. Starting address of the array of data is 4250H. (8)
12. (a) (i) Explain the various addressing modes of 8086 processor with suitable examples. (10)
(ii) Compare macro and procedure. (6)
Or
(b) (i) Write an 8086 ALP to find the sum of numbers in the array of 12 elements. (8)
(ii) What is BIOS? Discuss the various BIOS function calls. (8)
13. (a) (i) Draw the block diagram of 8087 numeric Data processor and explain. (10)
(ii) Discuss briefly the data types supported by 8087 Numeric Data Processor. (6)
Or
(b) (i) Explain the block diagram of 8089 I/O processor. (10)
(ii) Discuss the schemes used to solve the bus arbitration problem in multiprocessors (6)
14. (a) Explain the 8251 USART with neat block diagram. Also explain its mode word, command word and status word. (16)
Or
(b) Describe the block diagram of 8259 Programmable Interrupt Controller and its priority modes. (16)
15. (a) (i) Draw the pin diagram of 8051 microcontroller and explain the functions of each pin. (10)
(ii) Discuss briefly the various registers in 8051 microcontroller. (6)
Or
(b) (i) Explain the interfacing of 4×4 matrix keyboard to the 8051 microcontroller with neat diagram. (10)
(ii) Briefly write about the IE and IP register in 8051 microcontroller. (6)



DATABASE MANAGEMENT SYSTEMS CS2255 MODEL QUESTION PAPER | CS 2255 DBMS QUESTION PAPER NOVEMBER/DECEMBER 2011

· 0 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fourth Semester
Computer Science and Engineering
CS 2255 — DATABASE MANAGEMENT SYSTEMS
(Common to Information Technology)
(Regulation 2008)
Time : Three hours                                                             Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What is a data model?
2. With an example explain what a derived attribute is?
3. Consider the following relation :
EMP (ENO, NAME, DATE_OF_BIRTH, SEX, DATE_OF_JOINING, BASIC_PAY, DEPT) Develop an SQL query that will find and display the average BASIC_PAY in each DEPT.
4. List the two types of embedded SQL SELECT statements.
5. Consider the following relation :
R (A, B, C, D, E)
The primary key of the relation is AB. The following functional
dependencies hold :
A →C
B →D
AB →
Is the above relation in second normal form?
6. Consider the following relation : R(A, B, C, D)
The primary key of the relation is A. The following functional dependencies
hold :
A →B,C 
B →
Is the above relation in third normal form?
7. List the two commonly used Concurrency Control techniques.
8. List the SQL statements used for transaction control.
9. What are ordered indices?
10. Distinguish between sparse index and dense index.
PART B — (5 × 16 = 80 marks)
11. (a) (i) Construct an E-R diagram for a car-insurance company whose customers own one or more cars each. Each car has associated with it zero to any number of recorded accidents. State any assumptions you make. (6)
(ii) A university registrar’s office maintains data about the following entities :
(1) Courses, including number, title, credits, syllabus, and prerequisites;
(2) Course offerings, including course number, year,
semester, section number, instructor, timings, and classroom;
(3) Students, including student-id, name, and program; and
(4) Instructors, including identification number, name,
department, and title. Further, the enrollment of students in courses and grades awarded to students in each course they are enrolled for must be appropriately modeled. Construct an E-R diagram for the registrar’s office. Document all assumptions that you make about the mapping constraints. (10)
Or
(b) (i) With a neat sketch discuss the three-schema architecture of a DBMS. (8)
(ii) What is aggregation in an ER model? Develop an ER diagram using aggregation that captures the following information : 
Employees work for projects. An employee working for a particular project uses various machinery. Assume necessary attributes. State any assumptions you make. Also discuss about the ER diagram you have designed. (2 + 6)
12. (a) (i) Explain the distinctions among the terms primary key, candidate key, and super key. Give relevant examples. (6)
(ii) What is referential integrity? Give relevant example. (4)
(iii) Consider the following six relations for an Order-processing Database Application in a Company :
CUSTOMER (CUSTNO, CNAME, CITY)
ORDER (ORDERNO, ODATE, CUSTNO, ORD_AMT)
ORDER_ITEM (ORDERNO, ITEMNO, QTY)
ITEM (ITEMNO, ITEM_NAME, UNIT_PRICE)
SHIPMENT (ORDERNO, ITEMNO, WAREHOUSENO,
SHIP_DATE)
WAREHOUSE (WAREHOUSENO, CITY)
Here, ORD_AMT refers to total amount of an order; ODATE is the date the order was placed; SHIP_DATE is the date an order is shipped from the warehouse. Assume that an order can be shipped from several warehouses. Specify the foreign keys for
this schema, stating any assumptions you make. (6)
Or
(b) With relevant examples discuss the various operations in Relational Algebra. (16)
13. (a) Define a functional dependency. List and discuss the six inference rules for functional dependencies. Give relevant examples. (16)
Or
(b) (i) Give a set of Functional dependencies for the relation schema R(A,B,C,D,E) with primary key AB under which R is in 2NF but not in 3NF. (5)
(ii) Prove that any relation schema with two attributes is in BCNF.(5)
(iii) Consider a relation R that has three attributes ABC. It is decomposed into relations R1 with attributes AB and R2 with attributes BC. State the definition of lossless-join decomposition with respect to this example. Answer this question concisely by
writing a relational algebra equation involving R, R1, and R2. (6)
14. (a) (i) Define a transaction. Then discuss the following with relevant examples : (8)
(1) A read only transaction
(2) A read write transaction
(3) An aborted transaction
(ii) With a neat sketch discuss the states a transaction can be in. (4)
(iii) Explain the distinction between the terms serial schedule and serializable schedule. Give relevant example. (4)
Or
(b) (i) Discuss the ACID properties of a transaction. Give relevant example. (8)
(ii) Discuss two phase locking protocol. Give relevant example. (8)
15. (a) (i) When is it preferable to use a dense index rather than a sparse index? Explain your answer. (4)
(ii) Since indices speed query processing, why might they not be kept on several search keys? List as many reasons as possible.(6)
(iii) Explain the distinction between closed and open hashing. Discuss the relative merits of each technique in database applications. (6)
Or
(b) Diagrammatically illustrate and discuss the steps involved in processing a query.(16)


EMBEDDED SYSTEMS IT2354 NOVEMBER/DECEMBER 2011 QUESTION PAPER | IT2354 EMBEDDED SYSTEMS PREVIOUS YEAR QUESTION PAPER

· 1 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Sixth Semester
Information Technology
IT 2354 — EMBEDDED SYSTEMS
(Common to Computer Science and Engineering)
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. Find the timer’s clock frequency and its period for 8051. Assuming that XTAL = 11.0592 MHz.
2. What are the challenges in embedded computing system design?
3. What are the stages in an ARM pipeline?
4. When would you prefer to use busy-wait I/O over interrupt-driven I/O?
5. Define thread.
6. What is scheduling policy? Mention the scheduling states of a process.
7. What is the function of locator?
8. Write short notes on in-circuit-emulator.
9. List the levels of CMM.
10. What are the requirements for embedded system design?
PART B — (5 × 16 = 80 marks)
11. (a) Explain the major levels of embedded system design process with an example. (16)
Or
(b) Explain the instruction sets and condition codes of ARM processor with an example for each. (16)
12. (a) Explain the following memory systems :
(i) Two-level cache (5)
(ii) Direct-mapped cache (5)
(iii) Set-associative cache. (6)
Or
(b) Draw a UML sequence diagram for copying characters from an input to an output device using interrupt-driven I/O. The diagram should include the two devices and the two I/O handlers. (16)
13. (a) For the periodic processes given below, find a valid schedule
(i) Using standard RMS, and
(ii) Adding one unit of overhead for each context switch. (16) 
Process CPU time Dead line
P1   2  30
P2   4  40
P3   7 120
P4   5 60
P5   1 15
Or
(b) Explain the following :
(i) Blocking interprocess communication (5)
(ii) Nonblocking interprocess communication (5)
(iii) Shared memory communication. (6)
14. (a) Explain the multi-state systems and function sequences. (16)
Or
(b) Explain the following :
(i) ROM Emulators (8)
(ii) Remote Debuggers. (8)
15. (a) (i) Explain the case study of Audio players. (8)
(ii) Explain the design example of software modem. (8)
Or
(b) Explain the advanced techniques for specification with an example. (16)


SOFTWARE ENGINEERING AND QUALITY ASSURANCE IT2251 ANNA UNIVERSITY MODEL QUESTION PAPER | SEQA IT 2251 PREVIOUS YEAR QUESTION PAPER NOVEMBER/DECEMBER 2011

· 1 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fourth Semester
Information Technology
IT 2251 – SOFTWARE ENGINEERING AND QUALITY ASSURANCE
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What is meant by Independent Verification and Validation?
2. Differentiate Waterfall model with V-Model.
3. Name the components of CASE tools for structured methodology.
4. List the steps involved in requirements elicitation and analysis.
5. What is meant by heuristic evaluation?
6. List out the steps involved in real time software design.
7. What is meant by Boundary value analysis?
8. Define the term process maturity.
9. Name any four quality control tools.
10. State the benefits of QFD.
PART B — (5 × 16 = 80 marks)
11. (a) (i) Describe the process model which defines a network of activities. (8)
(ii) State as to why the first system is always a throw away system? Explain the concept with advantages and disadvantages. (8)
Or
(b) (i) Draw a system engineering hierarchy diagram and explain the concept. (8)
(ii) Explain the process model that combines the elements of waterfall and iterative fashion. (8)
12. (a) Give a brief description of software prototyping and briefly discuss the various prototyping techniques. (16)
Or
(b) With an example describe the three process steps for transforming a dataflow diagram to a structure chart. (16)
13. (a) (i) Draw a translating diagram for analysis model into a software design Specification. (8)
(ii) Give a complete template for documentation design specification. (8)
Or
(b) (i) Which is a measure of interconnection among modules in a program structure?Explain. (8)
(ii) What is the difference between Level-0 and Level-1 DFD? Draw a Level-0 and Level-1 DFD for safe Home Security System. (8)
14. (a) (i) What are all the formulas for cyclomatic complexity? Calculate cyclomatic Complexity for greatest of three numbers. (8)
(ii) How would you derive test cases for the given project? Explain in detail. (8)
Or
(b) (i) Narrate the path testing procedure in detail with a sample code.(8)
(ii) Explain the different integration testing approaches. (8)
15. (a) Explain how software process assessment helps software organizations to improve themselves. (16)
Or
(b) Write detailed notes on ISO9000 series of quality management standards. (16)


DESIGN AND ANALYSIS OF ALGORITHMS CS2251 ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER | CS 2251 DAA NOVEMBER/DECEMBER 2011 QUESTION PAPER

· 0 comments


B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.
Fourth Semester
Computer Science and Engineering
CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PART A — (10 × 2 = 20 marks)
1. What do you mean by linear search?
2. What is the properties of big-Oh notation.
3. What greedy algorithms?
4. What Knapsack problem?
5. What is traveling salesperson problem?
6. What do you mean by multistage graphs?
7. State the general backtracking method?
8. What is graph cloning?
9. What is spanning tree? Give an example.
10. What is NP Completeness?
PART B — (5 × 16 = 80 marks)
11. (a) (i) Define Asymptotic notations. Distinguish between Asymptotic notation and conditional asymptotic notation. (10)
(ii) Explain how the removing condition is done from the conditional Asymptotic notation with an example. (6)
Or
(b) (i) Explain how analysis of linear search is done with a suitable illustration. (10)
(ii) Define recurrence equation and explain how solving recurrence equations are done. (6)
12. (a) What is divide and conquer strategy and explain the binary search with suitable example problem.
Or
(b) Distinguish between Quick sort and Merge sort, and arrange the following numbers in increasing order using merge sort. (18, 29, 68, 32, 43,37, 87, 24, 47, 50)
13. (a) (i) Explain the multistage graph problem with an example. (8) 
          (ii) Find an optimal solution to the knapsack instance n = 7, m= 15 (p1, p2, p3, ….p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, w3, ... w7) (2, 3, 5, 7, 1, 4, 1) (8)
Or
(b) Describe binary search tree with three traversal patterns? Give suitable example with neat diagram for all three traversal of binary search tree.. (16)
14. (a) (i) How does backtracking work on the 8 Queens problem with suitable example? (8)
(ii) Explain elaborately recursive backtracking algorithm? (8)
Or
(b) What is Hamiltonian problem? Explain with an example using backtracking. (16)


15. (a) Write a complete LC branch-and-bound algorithm for the job sequencing with deadlines problem. Use the fixed tuple size formulation. (16)
Or
(b) Write a non-deterministic algorithm to find whether a given graph contains a Hamiltonian cycle. (16)