0% found this document useful (0 votes)
54 views11 pages

IT IV 2018-Prev

weff

Uploaded by

Vraj Patel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
54 views11 pages

IT IV 2018-Prev

weff

Uploaded by

Vraj Patel
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 11
B. Teck. Dt+Lv sem —207 x DHARMSINH DESAI UNIVERSITY, NADIAD ] 12) FACULTY OF TECHNOLOGY B.TECH. SEMESTER IV [INFORMATION TECHNOLOGY] SUBJECT: (IT-402) COMPUTER ORGANIZATION Examination Date 2 20 Time : lo-co_to Lappes STRUCTION: 1. Answer each section in separate answer book. 2. Figures to the right indicate maximum marks for that question. 3. The symbols used carry their usual meanings. 4 5 Assume suitable data, if required & mention them clearly. Draw neat sketches wherever necessary. SECTION -1 Q.1 Doas directed. [10) (@) A CPU has 24-bit instructions. A program starts at address 300 (in decimal). Which one of [1] the following is a legal program counter (all values in decimal)? (A) 400 (B) 500 (C) 600 (D) 700 (b) In designing a computer's cache system, the cache block (or cache line) size is an important [1] parameter. Which one of the following statements is correct in this context? (A) A smaller block size implies better spatial locality (B) A smaller block size implies a smaller cache tag and hence lower cache tag overhead (C) A smaller block size implies a larger cache tag and hence lower cache hit time () A smaller block size incurs a lower cache miss penalty (©) _ Differentiate: RISC & CISC 2) (@) Consider a 4-way set associative cache consisting of 128 lines with a line size of 64 words. [2] ‘The CPU generates a 20-bit address of a word in main memory. What are the number of bits in the TAG, LINE and WORD fields respectively? (© Give names of gate, register and processor level components. 2] (f) “Branch instructions reduce the efficiency of instruction pipelining.” Justify 2] Q.2. Attempt Any TWO from the following questions. {10} (@) (j For high speed adder prove that SUM = x; ®y;®ci-1 = pi ©Gi @c-4 Bl ii) Suppose that the hex contents of two CPU register in the 32-bit processor are as follows (2) 001237654 R1=7654EDCB. The following store word instructions are executed to transfer the contents of these registers to main memory M. STORE RO, ADR STORE R1, ADR+4 Assuming that M is byte addressable, give the contents of all memory locations affected by the above code(A)if the computer is Big-endian (B)if the computer is Little-endian (b) @ A 12-bit Hamming code whose hexadecimal value is 0xE4F read from memory. What were [3 the original data bits in hexadecimal? Assume that not more than one bit is in error. Number the bits from left to right. (ii) Consider a three-word machine instruction ADD A[RO], @B R ‘The first operand (destination) “A[RO]” uses indexed addressing mode with RO as the index register. The second operand (source) “@B"” uses indirect addressing mode. A and B are memory addresses Fesiding at the second and third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand). How many memory cycles needed during the execution cycle of the instruction? (© @ Consider the following code sequence having five instructions Ito 15. 3 Tl: ADD R1 R2, R3 I [UL R7 R1,R3 13: SUB R4 R1, RS 14: ADDR3R2,R4 15: MUL R7 R8, R9 Consider the following three statements. ‘1: There is an anti-dependence between instructions I2 and IS 2: There is an anti-dependence between instructions 12 and 14 $3: Within an instruction pipeline an anti-dependence always creates on or more stalls. Which one of above statements is/are correct? Justify your Answer (ii) Compare memory mapped 1/O with /O mapped /0. [ Pant ak 9_ Q3 (a) Write programs for execute the operation X=(A*B)-(C*D)+(E/F) In 3-address , 2-address, 1. [5] address and O-address machine. (b) Given references to the following pages by a program 0.9018 187871282782383. [5] Calculate the hit ratio if there are four page frames available to it using FIFO, LRU and OPTIMAL page replacement algorithm. OR Q3 (a) ACPU, which addresses the data through its 6 registers in one of 12 different addressing [5] modes, is to be designed to support 10! arithmetic instructions, 15 logic instructions, 24 data moving instructions, 6 branch instructions, 5 control type instructions, of these instructions respectively 20%, 60%, 50%, 50% and 60% are either single operand or no operand instructions, and rest of are double operand type. What is the minimum size of the instruction? (b) An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32- [5] bytes. The processor generates 32-bit addresses. The cache controller maintains the tag information for each cache block comprising of the following. 1 Valid bit 1 Modified bit ‘As many bits as the minimum needed to identify the memory block mapped in the cache. ‘What is the total size of memory needed at the cache controller to store meta-data (tags) for the cache? SECTION - II Q.4 Doas directed. {10} (a) What is difference between auto increment and auto decrement addressing mode explain with [2] example. (b) For complete interconnection structure find number of edges, max node degree, where n=64. [2] (©) Define: Seek time and latency time 2] (d) Interpret the following 32-bit IEEE 754 format: C16E0000 21 (e) What is Belady’s anomaly? Explain with example. 2 Q.5 Attempt Any TIVO from the following questions. {10} (a) Give format of microinstruction and explain organization of microprogrammed based control [5] unit (b) Explain architecture of IAS machine with diagram. [5] (©) @ Consider an instruction pipeline with four stages (SI, $2, S3 and S4) each with [3] combinational circuit only whose delays are 5,6,11,8 ns. The pipeline registers are required between each stage and at the end of the last stage whose delays are Ins each. What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation? (ii) Consider a system with 2 level cache, Access times of levels 1 cache, level 2 cache and [2] main memory are 2ns ,12 ns and 400 ns respectively. The hit rates of level 1 and level 2 caches are 0.8 and 0.9 respectively. What is the average access time of the system ignoring the search time within the cache? Q6 (a) What are the advantages of Booth’s algorithm? Find the product of two numbers X=-5 and [5] Y=7 using booth’s algorithm. What is disadvantage of Booth’s algorithm? (b) Given memory portions of 100KB,500KB,200KB,300KB, and 600KB (in order), how would [5] each of the first fit, best fit algorithms place processes of 212KB,417KB,112KB, and 426KB(in order)? Which algorithm makes most efficient use of memory? Justify your answer. OR Q.6 (a) What is ALU expansion? What are the techniques for ALU expansion? Explain 2901-bit [5] slice ALU with diagram (b) Consider the following reservation table for a pipeline 13] 1 PRES ERE $1 |X x S2 x x S3 x Find the minimum average latency (MAL)? The MAL is average of minimum latency and minimum constant latency. Also draw task initiation diagram. nae. 9 of 9 DHARMSINH DESAI UNIVERSITY, NADIAD ] FACULTY OF TECHNOLOGY B.TECH. SEMESTER IV [LT] SUBJECT: (17403) Microprocessor Architecture, Programming & Interfacing. Examination; Regulgr Seat No Date 2 fo4)201g Day 5B Time Hoo to {oo pe Max. Marks: 60 INSTRUCTIONS: 1, Answer ench section in separate answer book. 2. Figures tothe right indicate maximum marks for that question. 3. The symbols used carry thelr usual meanings. 4. Assume suitable data, if required & mention them clearly. 5. Draw neat sketches wherever necessary. 6_No marks without justification, SECTION -1 QI Doas directed. {10} (a) In 8085 system, starting address of ROM is 0000h and RAM is CO00h. Size of the RAM [2] and ROM devices are 4Kbytes. What address is most appropriate to initialize SP? Why? (b) In 8051, Find the 8-bit Bit address of bit 0 of byte address 21h. pa) (©) What is the worst case minimum pulse width required for TRAP interrupt signal ? Why [2] (@) Write 4 different instructions which will perform the same job of moving a content of [2] memory location 00 to O1(using register addressing and direct addressing) in 8051, Assume Bank 0 Is selected. (©) If 8085 sends three *INTA pulses for INTR response, it would have received opcode for [2] one of the RST instruction during first “INTA pulse. State true/false and justify. Q2 Attempt Any TWO from the following questions, 19} ® me 51 200s 400us In 8085 system, as shown in above figure, both RST 7.5 and TRAP interrupts arrive at the same time, Assume maskable interrupt system is already enabled, RST 7.5 is unmasked and RST 7.8 & TRAP interrupt service routines take 200 wS each. Describe the response of 8085 and execution of program for following 2 cases: Case 1: If EI is written at middle of the TRAP interrupt service routine and EI is written at the end of the RST 7.5 interrupt service routine. Case 2: If EI is written at the end of the TRAP interrupt service routine and El is written at the beginning of the RST 7.5 interrupt service routine. @) 2100 LXTH, 1234h 15 MVIA, 55h INRM ‘What is the size of INR M instruction, Specify the content of address bus and data bus for every T states when instruction INR M is executed. Name the machine eycles also, Assume 4 T-states are required for op-code fetch cycle. Page r |: Q3 Q3 Q4 (©) Draw the neat circuit diagram to interface SKbytes external data memory whose 151 starting address is 2000H which could be used for both running the program as well as storing the data. Do the absolute decoding. fa) (SI Identify the port address of the output port in the above figure. W. each LED one by one continuously. ite a program to glow (b) 8-bit DAC is connected to 8-bit latch whose port address is 1800H. DAC is configured for [5] 0 to 10 V output. Write a program to generate SV square wave at the output. OR (a) How many input and output port pins required to interface simple 8-bit ADC with the [2] 8085 ? (b) Mdentify addressing modes for following instruction: BL 1, MOVC A,@DPTR+A 2. SIMP NEXT. 3. MOV 00,01 4, MOVX A, @DPTR (©) Write a subroutine to transfer 1 byte data on SOD pin of 8085 asynchronously assuming [S| data is passed in B register of 8085.State your assumptions very clearly, if any and draw neat flow chart, Assume bit delay routine is ayailable and does not destroy any registers. SECTION - It Do as directed. 10) (a) What are the states of the Auxiliary Carry(AC), Zero(Z) and parity(S) flags after [1] ‘executing the following 8085 program? Justify your answer. What is the final answer in ‘Acc. MVIL, Ssh MVI A, ABh ADDL. (b) In 8085, two byte instructions can be completed in one machine cycle, State T/F with [1] ication, signals identify opcode fetch eycle ? What is the logic levels of those signals, 1") (a) ‘-bit parallel inpuvloutput port operation is possible using RIM/SIM instruction, ” [1] State TF ication. (© Ifyou do not want to do hand coding to generate machine code from mnemonics, which [1] software package is used ? (f) After reset, during 1" machine cycle, address bus of 8085 will have value uy (g) Two PUSH instructions are used in a sub-routine and only one POP instruction is used 1] before returning from the sub-routine, Explain what happens when RET instruction is executed. (h) What is the availability of the data (in terms of number of T-states) on the data bus when [1] read/write operation performed by 8085? (0 Which logical instruction will be used to reset a particular bit in a byte without affecting [1] the other bits? (i) There is no harm if the stack size is 60 bytes and the depth of nested subroutines is 20 [1] (assuming there is no PUSH and POP instructions in nested subroutines). State T/F and justify. fage a) Qs 110) (@) Write a program to count od numbers from given 100 8-bit unsigned numbers. Draw [5 the neat flow chart and state your assumptions very clearly if any . Also explain your logie clearly. OR (a) Write a program to count negative numbers from given 100 8-bit signed numbers, Draw [8] neat flow chart and state your assumptions very clearly. Explain your logic clearly. oe da = " 3 *E2 “EL ~ ac aes a2 5 oft mt by we [Assume memory decoder outputs are labeled as 00 to O7. Which output of the decoder is to be connected to & of memory device to map the device to processor address space of AOVOH to BFFFH. Also specify the address ranges which will be selected by other valid outputs of the decoder, Q6 (a) Ina subroutine, stack is to be balanced. Justify your answer. ri {b) Ina bigeendian machine, a 16-bit number 1234H is to be saved at S-bit wide memory [2] location 2100H and 2101h, show how it will be stored. {@) Itmemory chip size is 256x1 bits, how many chips are required to make up 1K-byte 21 memory ? (2) 118085 is operating at 1 Mhz eloek, how much time 8085 will take to transfer one byte RI information to peripheral device connected as memory mapped 1/0 ? Show your caleulation. (© LOOP: LXTH,FFFFH ro DCXH NZ LOOP NOP. Find the mistakes in the above program and modify the program so that when HL reaches to zero, program should come out from the loop. OR 2 Name the machine eycles required to complete [2] Q.6 (a) What is the size of a RST7 instruct In, (b) 2100 LXI'SP, 10008 21 LXIH, 123411 PUSH It Draw the stack frame when PUSH H instruction is executed. (© How many machine cycles XTHL instruction will have? Name them: 1 (@) Explain the following instruction with example: i (@MOVAB Gi)INRM ii) LDAXD (jv) DCXD Qu Q2 Q3 FACULTY OF TECHNOLOGY B.TECH. SEMESTER IV [IT] SUBJECT: (IT 406) DATA STRUCTURES & ALGORITHM Seat No Day : Max. Marks 60 2) DHARMSINH DESAI UNIVERSITY, NADIAD. Examination Date Time INSTRUCTION! I. Answer each section in soparate answer book, 2. Figures to the right indicate maximum marks for that question, 3. The symbols used carry their usual meanings. 4, Assume suftable data if required & mention them clearly 5._Draw neat skeiches wherever nevessery. SECTION ~I Do as directed. [19] (a) Draw the tree and convert it into Binary tree: G(H(), L(M.N)) 1 (b) Consider a node X in a Binary Tree. Given that X has two children, let Y be inorder [2] successor of X. Which of the following is true about Y? justify (A) Y has no right child (B) Y has no left child (C) Y has both children (D) None of the above (©) Draw the Digital Search tree (OST) for the following data RI 4000,0010, 1001,0001, 1100,0000 (d)_ Write down difference between array and link list in terms of data structure. 1 (©) Explain At least two real world application where following data structures are used: [2] 1) Binary Search tree 2) Tries 3) stack 4) Queue Suppose an array of double a[2000]{1000] is represented in column-major order format, Find the address of element a {50} [600]. Array index start from 0 and Base address =2000. Attempt Any TWO from the following questions. (19) (a) Write an algorithm of tower of Hanoi. Calculate it for 3 disk show output. 51 (b) Write down code/algorithm for following operation using Singly link list 5] 1) Insert new node having value A after node having have value B. 2) Delete a node after node having value B 3) _ Insert new node at the start of link list. (©) Convert the following expressions from infix to prefix: Show status of scan Input, [5] stack, and output of every character scan. 1. @(A*B)«C/D)*E) [Show stack value and output value on every character scan] Attempt following questions. AS DS) ° Write Algorithm/Code of all-pair shortest path. find the all pair shortest path from node a. (b) Write down algorithm/code of insertion sort and perform insertion sort on following [5] data 21 55.68 19 89 71 15 oR Q3 Q4 Qs Q6 Q6 Attempt following questions. (a) Write down algorithm of insertion into binary search tree (BST). [5] ) 5] Write down code for in order, preorder and post order of binary tree and write in- order preorder and post order traversal of binary tree given in figure. SECTION - I Doas directed, [10] {a) Which of the following sorting algorithm in its typical implementation gives best [2] performance when applied on an array which is sorted or almost sorted? Discuss it with example. (A) Quick Sort (B) Heap Sort (C) Merge Sort (D) Insertion Sort (b) Explain advantages of stack , Queue , Circular Queue and Binary search tree 2 (©) You have to sort 1 GB of data with only 100 MB of available main memory. Which [2] sorting technique will be most appropriate? (A) Heap sort (B) Merge sort (C) Quick sort (D) Insertion sort (@)_ Perform radix sort on following data using BinSort on lower di R 126, 328, 636, 341, 416, 131, 328 (© You have to sort 1 GB of data with only 100 MB of available main memory. Which [2] sorting technique will be most appropriate? (A) Heap sort (B) Merge sort (C) Quick sort (D) Insertion sort Attempt Any TWO from the following questions. [10 (a) Write down algorithm for quick sort. 15] (b) Draw the 2-3 tree for following data: 15] 1,2,4,5,6,8,11,12,14,15,16,30,50 {note: show each tree during every insertion] (©) Create Max-heap tree for the following data:[ show each and every tree] 15) 220,550,770,580,990,999,1111,30 Attempt following questions. (a) Define hashing and discuss following hashing techniques in detail with example. 6) 1) Mid square method 2) Division method 3) Folding method 4) Digit analysis (b) Draw the 2-3-4 tree for the following data: :{ show each and every tree] (5) 11,22,33,44,55,66,77,88,99,101,111,121,131 OR Attempt following questions. Draw the Red black tree for the following data show each and every iteration ) (a) 78, 99,88,50,60,55,54,51 Draw the AVL tree for the following data Is] (b) 50,60,70,80,90,10,99 Page 20f 2 DHARMSINH DESAI UNIVERSITY, NADIAD }) FACULTY OF TECHNOLOGY B.TECH. SEMESTER IV [IT] SUBJECT: (11407) COMPUTER & COMMUNICATION NETWORK Examination : Rayo Seat No e Date 2 dp fegfzer. Day Time 2a. to Toppy Max. Marks INSTRUCTIONS: 1 2 3 4. 5. Qu Q3 Q3 “Answer each section in separate answer book. Figures tothe right indicate maximum marks for that question. ‘The symbols used carry their usual meanings. ‘Assume suitable data, iPrequired & mention them clearly Draw neat sketches wherever necessary, SECTION -I Do as directed. {10} (@) Three bank employees are using the corporate network. The first employee uses a [2] web browser to view a company web page in order to read some announcements. The second employee accesses the corporate database to perform some financial transactions. The third employee participates in an important live audio conference with other corporate managers in branch offices. If QoS is implemented on this network, what will be the priorities from highest to lowest of the different data types? (b) The address 43:7B:6C:DE:10:00 has been shown as the source address in an Ethernet [2] frame. What will the receiver do when it receives the frame? Accept or discard? Why? (©) What is silly window syndrome? Suggest the solution, Ry (4) Which fields of the IPv4 header change from router to router? RI (©) Explain the meaning of following socket primitive: RI BIND, LISTEN, ACCEPT and CONNECT. Attempt Any TWO from the following questions. {10} (a) Write short note on frame format of HDLC protocol. 15] (6) A5.1 km long broadcast LAN has 10” bps bandwidth and uses CSMAJCD algorithm [5] to detect collision. The signal travels along the wire at 2.5 10° m/s. What is the minimum packet size that can be used on this network? (©) A large number of consecutive IP address are available starting at 198.16.0.0/16. Is} ‘Suppose that four organizations, A, B, C and D request 4000, 2000, 4000, and 8000 address, respectively, and in that order. For each of these, find the first IP address assigned, the last IP address assigned, and the mask in the w.x.y.2/s notation. (a) Using 5-bit sequence numbers, what is the maximum size of the send and receive [4] Windows for each of the following protocols? a. Stop-and-Wait ARQ b, Go-Back-NARQ c. Selective-Repeat ARQ (6) Compare OSI and TCP/IP reference model in detail, (61 oR (a) Write a note on guided transmission media. 16) (b) What is hidden station and exposed station problem in wireless LAN? (4) Page tof 2 Q4 Qs Q6 Q6 SECTION - IL Do as directed. [10} (a) What is piggybacking? Is there any drawback of it? 2) (b) How transport layer provides process to process delivery? 2) (©) Consider the following statements regarding the slow start phase of the TCP [2] ‘congestion control algorithm. Which one of the following is correct? (i) The cwnd increase by 2 MSS on every successful acknowledgement. (i) The cwnd approximately doubles on every successful acknowledgement. (iii) The ewnd increase by 1 MSS every round trip time. (iv) The ewnd approximately doubles every round trip time. (@) During an FTP session the data connection is opened ___and control connection is [2] opened ___(exactly once, exactly twice, as many time as necessary) (e) What is Encryption? What is Confidentiality? 2) ‘Attempt Any TWO from the following questions. {10} (a) What is name-address resolution? Discuss the resolvers in detail. 15] (b) Define fragmentation. Why the IPv4 protocol needs to fragment some packets? 65] (©) How does TCP establish the connection to communicate using three way {5} handshaking? (a) Create an internetwork with four LANs and four bridges. The bridges connect the [6] LANSas follows. a) B4 connects LAN 2 and LAN 4 respectively on ports 1 and 2. b) B3 connects LAN 2, LAN 3, and LAN 4 respectively on ports 1, 2, and 3. ¢) B2 connects LAN 1 and LAN 3 respectively on ports 1 and 2. 4) BI connects LAN | and LAN 2 respectively on ports 1 and 2. 1. Draw the resulting intemetwork. 2. Find the spanning tree where BI is the root bridge 3. Show the resulting forwarding and the blocking ports. (b) A computer network uses polynomial over GF(2) for error checking with 8 bits as [4] information bits and uses x? + x + 1 as the generator polynomial to generate the check bits, In this network, the message 01011011 is transmitted as__(show calculation) OR (a) Consider the following network topology (6) How a and b build their routing tale using Link state routing protocol? (b) Which difficulties encounter when trying to build a bridge between 802.X to 802.Y? [4] Page 202 Iyv_Se™ onan rats aun 1D Sst Rihana INSTRUCTIONS: L.Answer each section in separate answer book. 2. Figures to the right indicate maximum marks for that question, 3. The symbols used carry their usual meanings. 4, Assume suitable data, if required & mention them clearly 5__Draw neat sketches wherever necessary SECTION-1 O41 Doas directed. 110) @ 1 ax AG : e [02] Evaluate fj, Tax by applying Simpson's 3/8 rule with h=1/6 (>) The probable error of the correlation co-efficient of 16 pairs of values is 0.085. Find (62) the value of correlation co-efficient. © Evaluate A? (= @ Given up +g = 1.9243, + uy = 1.9590 uz + ue = 1,9823,and us + us = 1021 1.9956 find uy . (©) Out of Regula — Falsi method and Newton ~ Raphson method, the rate of 101] convergence is faster for 02) 1 , =i) interval of difference being unity. (The incidence of occupational disease in an industry is such that the workmen have 101] 10% chance of suffering from it. What is the probability that in a group of seven . five workmen will suffer from it’ 2 Attempt Any THREE from the following questions 112) (@ Use Milne's method to find y(0.3) from y' = x* + y?,y(0) = 1. Find the initial values y(-0.1), y(0.1) and y(0.2) from Taylor's series method. (©) Ina partially destroyed laboratory record, only the lines of regression of y om x and x on y are available as 4x-5y+33=0 and 20x-9y~107 respectively. Calculate %,9 and the coefficient of correlation between x and y. (© Find the value of cos /.747 using the values given in the table below x 170 174 ~[178 [182 [186 sinx. [0.9916 | 0.9857 [0.9781 [0.9691 | 0.9584 (@ By using the Regula ~ Falsi method, find the root, correct to two decimal places, of the equation x logyox — 1.2 = 0 that lies between two and three. 3 (@ The sale and expenditure of 10 companies are given below. Find co-efficient of [41 correlation between sale and expenditure. Sale 50 55] 55 60 | 65 [65 | 65] 60] 60 | 50 Expenditure [IT [13 [14 [16 [16 [15 [15 [4 [3] (©) Solve the equations by Gauss-Seidel method. 4 10x +2y+2=9 ; -2x+3y+10z=22 ; 2x + 20y -2; OR Q3 @ Using Runge ~ Kutta method solve y(0.2) given that y’ =xy + y?,y(0.1) = UI 1.1169, take h=0.1 uo \ © Prove that up + uyx + uzx? + 2 i Hence sum the series 1-2 +2-3x+3-4x24 SECTION - 11 Q4 Doasdirected, {10} (© Find the curl of the vector 7” = (x? + yz)i + (y? + 2x)f + (22 + xy) at he point 1 - (1, 2,3) (b) Find the directional derivative of the function f =xy+yz + zx in the direction of [21 the vector 27+ 37+ 6K at the point (3, 1, 2) (© Evaluate, using Cauchy's integral formula ry J. GE% dz around a rectangle with vertices 241 ,-2 +1. (® Under the transformation w 2, find the image of |z — 2i] @ ©) Form the difference equation from y, = 2" (A+Bn). re QS Attempt Any THREE from the following questions 1] (® Determine the region of the w-plane into which the region. 3Sx <1 and }

You might also like