Education In Pakistan

Papers, Notes, Books & Help For Students

UPDATED EDUCATIONAL NEWS INTERVIEW HELP FOR ALL JOBS ONLINE BOOKS SCHOLARSHIPS AVAILABLE INTERNSHIP JOBS

Tag: VU CS501-

VU CS502- Fundamentals of Algorithms (Session – 4) FinalTerm solved unsolved past papers Spring 2010

VU CS502- Fundamentals Of Algorithms (Session – 4) FinalTerm Solved Unsolved Past Papers Spring 2010

FINALTERM  EXAMINATION

Spring 2010

CS502- Fundamentals of Algorithms (Session – 4)

Time: 90 min

Marks: 58

Question No: 1    ( Marks: 1 )    – Please choose one

 An optimization problem is one in which you want to find,

► Not a solution

► An algorithm

► Good solution

       ► The best solution

Question No: 2    ( Marks: 1 )    – Please choose one

 Although it requires more complicated data structures, Prim’s algorithm for a minimum spanning tree is better than Kruskal’s when the graph has a large number of vertices.

       ► True

► False

Question No: 3    ( Marks: 1 )    – Please choose one

 If a problem is in NP, it must also be in P.

       ► True

► False

► unknown

Question No: 4    ( Marks: 1 )    – Please choose one

 What is generally true of Adjacency List and Adjacency Matrix representations of graphs?

► Lists require less space than matrices but take longer to find the weight of an edge (v1,v2)

       ► Lists require less space than matrices and they are faster to find the weight of an edge (v1,v2)

► Lists require more space than matrices and they take longer to find the weight of an edge (v1,v2)

► Lists require more space than matrices but are faster to find the weight of an edge (v1,v2)

Question No: 5    ( Marks: 1 )    – Please choose one

 If a graph has v vertices and e edges then to obtain a spanning tree we have to delete

► v edges.

► v – e + 5 edges

►  v + e edges.

       ► None of these

Question No: 6    ( Marks: 1 )    – Please choose one

 Maximum number of vertices in a Directed Graph may be |V2|

       ► True

► False

Question No: 7    ( Marks: 1 )    – Please choose one

 The Huffman algorithm finds a (n) _____________ solution.

       ► Optimal

► Non-optimal

► Exponential

► Polynomial

Question No: 8    ( Marks: 1 )    – Please choose one

 The Huffman algorithm finds an exponential solution

► True

       ► False

Question No: 9    ( Marks: 1 )    – Please choose one

 The Huffman algorithm finds a polynomial solution

► True

       ► False

Question No: 10    ( Marks: 1 )    – Please choose one

 The greedy part of the Huffman encoding algorithm is to first find two nodes with larger frequency.

► True

       ► False

   

Question No: 11    ( Marks: 1 )    – Please choose one

 The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the postfix of any other.

► True

       ► False

Question No: 12    ( Marks: 1 )    – Please choose one

 Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.

► True

       ► False

Question No: 13    ( Marks: 1 )    – Please choose one

 Shortest path problems can be solved efficiently by modeling the road map as a graph.

       ► True

► False

Question No: 14    ( Marks: 1 )    – Please choose one

 Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.

► True

       ► False

   

Question No: 15    ( Marks: 1 )    – Please choose one

 Bellman-Ford allows negative weights edges and negative cost cycles.

► True

       ► False

Question No: 16    ( Marks: 1 )    – Please choose one

 The term “coloring” came form the original application which was in architectural design.

       ► True

► False

Question No: 17    ( Marks: 1 )    – Please choose one

 In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.

       ► True

► False

Question No: 18    ( Marks: 1 )    – Please choose one

 Dijkstra’s algorithm is operates by maintaining a subset of vertices

       ► True

► False

Question No: 19    ( Marks: 1 )    – Please choose one

 The difference between Prim’s algorithm and Dijkstra’s algorithm is that Dijkstra’s algorithm uses a different key.

       ► True

► False

Question No: 20    ( Marks: 1 )    – Please choose one

 Consider the following adjacency list:

 

Which of the following graph(s) describe(s) the above adjacency list?

       ► 

 

 

 

 

 

Question No: 21    ( Marks: 1 )    – Please choose one

 We do sorting to,

► keep elements in random positions

► keep the algorithm run in linear order

► keep the algorithm run in (log n) order

       ► keep elements in increasing or decreasing order

Question No: 22    ( Marks: 1 )    – Please choose one

 After partitioning array in Quick sort, pivot is placed in a position such that

       ► Values smaller than pivot are on left and larger than pivot are on right

► Values larger than pivot are on left and smaller than pivot are on right

       ► Pivot is the first element of array

► Pivot is the last element of array

Question No: 23    ( Marks: 1 )    – Please choose one

 Merge sort is stable sort, but not an in-place algorithm

       ► True  (p#54)

► False

Question No: 24    ( Marks: 1 )    – Please choose one

 In counting sort, once we know the ranks, we simply _________ numbers to their final positions in an output array.

► Delete

       ► copy (p#57)

► Mark

► arrange

Question No: 25    ( Marks: 1 )    – Please choose one

 Dynamic programming algorithms need to store the results of intermediate sub-problems.

       ► True   p#75)

 

► False

Question No: 26    ( Marks: 1 )    – Please choose one

 A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute.

       ► O (q) (p= 84)

► O (1)

► O (n2)

► O (n3)

Question No: 27    ( Marks: 2 )

 Give a detailed example for 2-d maxima problem.

 

Question No: 28    ( Marks: 2 )

 Differentiate between back edge and forward edge.

 

Question No: 29    ( Marks: 2 )

 How the generic greedy algorithm operates in minimum spanning tree?

 

 

Question No: 30    ( Marks: 2 )

 What are two cases for computing  assuming we already have the previous matrix  using Floyed-Warshall algorithm?

 

 

 

 

Question No: 31    ( Marks: 3 )

 Describe Minimum Spanning Trees Problem with examples.

 

 

 

Question No: 32    ( Marks: 3 )

 What is decision problem, also explain with example?

 

 

 

Question No: 33    ( Marks: 3 )

 Prove that the generic TRAVERSE (S) marks every vertex in any connected graph exactly once and the set of edges (v, parent (v)) with parent (v) ¹F form a spanning tree of the graph.

 

 

Question No: 34    ( Marks: 5 )

 Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence?

 

 

 

 

 

Question No: 35    ( Marks: 5 )

 Prove the following lemma,

Lemma: Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) ∈ E. If this edge is a tree, forward or cross edge, then f[u] > f[v]. If this edge is a back edge, then f[u] ≤ f[v]

 

 

 

 

 

 

 

Question No: 36    ( Marks: 5 )

 What is the cost of the following graph?

VU CS502- Fundamentals Of Algorithms (Session – 4) FinalTerm Solved Unsolved Past Papers Spring 2010

VU CS501- Advance Computer Architecture (Session – 1) FinalTerm solved unsolved past papers Fall 2008

VU CS501- Advance Computer Architecture (Session – 1) FinalTerm Solved Unsolved Past Papers Fall 2008

FINALTERM EXAMINATION

Fall 2008

CS501- Advance Computer Architecture (Session – 1)

Marks: 75

Question No: 1 ( Marks: 1 ) – Please choose one

Which one of the following is the memory organization of SRC processor?

  • 28 * 8 bits
  • 216 * 8 bits
  • 232 * 8 bits
  • 264 * 8 bits

Question No: 2 ( Marks: 1 ) – Please choose one

Type A format of SRC uses ———–instructions

  • two
  • three
  • four
  • five

Question No: 3 ( Marks: 1 ) – Please choose one

The instruction —————will load

the register R3 with the contents of the memory

location M [PC+56]

  • Add R3, 56
  • lar R3, 56
  • ldr R3, 56
  • str R3, 56

Question No: 4 ( Marks: 1 ) – Please choose one

Which format of the instruction is called the accumulator?

  • 3-address instructions
  • 3-address instructions
  • 2-address instructions
  • 1-address instructions
  • 0-address instructions

Question No: 5 ( Marks: 1 ) – Please choose one

Which one of the following are the code size

and the Number of memory

bytes respectively for a 2-address instruction?

  • 4 bytes, 7 bytes
  • 7 bytes, 16 bytes
  • 10 bytes, 19 bytes
  • 13 bytes, 22 bytes

Question No: 6 ( Marks: 1 ) – Please choose one

Which operator is used to name registers, or part of registers, in the Register

Transfer Language?

  • :=
  • &
  • %
  • ©

Question No: 7 ( Marks: 1 ) – Please choose one

The transmission of data in which each character is self-contained units with its

own start and stop bits is ———–

  • Asynchronous
  • Synchronous
  • Parallel
  • All of the given options

Question No: 8 ( Marks: 1 ) – Please choose one

Circuitry that is used to move data is called ————-

  • Bus
  • Port
  • Disk
  • Memory

Question No: 9 ( Marks: 1 ) – Please choose one

Which one of the following is NOT a technique used when the CPU wants to

exchange data with a peripheral device?

  • Direct Memory Access (DMA).
  • Interrupt driven I/O
  • Programmed I/O
  • Virtual Memory

Question No: 10 ( Marks: 1 ) – Please choose one

Every time you press a key, an interrupt is generated.

This is an example of

  • Hardware interrupt
  • Software interrupt
  • Exception
  • All of the given

Question No: 11 ( Marks: 1 ) – Please choose one

The interrupts which are pre-programmed and the processor automatically finds

the address of the ISR using interrupt vector table are

  • Maskable
  • Non-maskable
  • Non-vectored
  • Vectored

Question No: 12 ( Marks: 1 ) – Please choose one

Which is the last instruction of the ISR that is to be executed when the ISR

terminates?

  • IRET
  • IRQ
  • INT
  • NMI

Question No: 13 ( Marks: 1 ) – Please choose one

If NMI and INTR both interrupts occur simultaneously, then which one has the

precedence over the other

 

  • NMI
  • INTR
  • IRET
  • All of the given

Question No: 14 ( Marks: 1 ) – Please choose one

Identify the following type of serial communication error condition:

The prior character that was received was not still read by the CPU and is

over written by a new received character.

  • Framing error
  • Parity error
  • Overrun error
  • Under-run error

Question No: 15 ( Marks: 1 ) – Please choose one

———-the device usually means reading its status register every so often until

the device’s status changes to indicate that it has completed the request.

  • Executing
  • Interrupting
  • Masking
  • Polling

Question No: 16 ( Marks: 1 ) – Please choose one

Which I/O technique will be used by a sound card that may need to access data

stored in the computer’s RAM?

  • Programmed I/O
  • Interrupt driven I/O
  • Direct memory access(DMA)
  • Polling

Question No: 17 ( Marks: 1 ) – Please choose one

For increased and better performance we use _____ which are usually made of glass.

  • Coaxial Cables
  • Twisted Pair Cables
  • Fiber Optic Cables
  • Shielded Twisted Pair Cables

Question No: 18 ( Marks: 1 ) – Please choose one

In _____ if we find some call party busy we can have provision of call waiting.

  • Delay System
  • Loss System
  • Single Server Model
  • None of the given

Question No: 19 ( Marks: 1 ) – Please choose one

In ____ technique memory is divided into segments of variable sizes depending upon

the requirements.

  • Paging
  • Segmentation
  • Fragmentation
  • None of the given

Question No: 20 ( Marks: 1 ) – Please choose one

For a request of data if the requested data is not present in the cache, it is called a _____

  • Cache Miss
  • Spatial Locality
  • Temporal Locality
  • Cache Hit

Question No: 21 ( Marks: 1 ) – Please choose one

An entire _____ memory can be erased in one or a few seconds which is much faster

than EPROM.

  • PROM
  • Cache
  • EEPROM
  • Flash Memory

Question No: 22 ( Marks: 1 ) – Please choose one

________chips have quartz windows and by applying ultraviolet light data can be

erased from them.

  • PROM
  • Flash Memory
  • EPROM
  • EEPROM

Question No: 23 ( Marks: 1 ) – Please choose one

The _______signal coming from the CPU tells the memory that some interaction is

required between the CPU and memory.

  • REQUEST
  • COMPLETE

None of the given

Question No: 24 ( Marks: 1 ) – Please choose one

______ is a combination of arithmetic, logic and shifter unit along with some

multiplexers and control unit.

  • Barrel Rotator
  • Control Unit
  • Flip Flop
  • ALU

Question No: 25 ( Marks: 1 ) – Please choose one

1. In Multiple Interrupt Line, a number of interrupt lines are provided between the

____________________ module.

  • CPU and the I/O

 

 

  • CPU and Memory
  • Memory and I/O
  • None of the given

Question No: 26 ( Marks: 1 ) – Please choose one

The data movement instructions ___________ data within the machine and to

or from input/output devices.

  • Store
  • Load
  • Move
  • None of given

Question No: 27 ( Marks: 1 ) – Please choose one

CRC has ———— overhead as compared to Hamming code.

  • Equal
  • Greater
  • Lesser
  • None of the given

Question No: 28 ( Marks: 1 ) – Please choose one

The ________ is w-bit wide and contains a data word, directly connected to the data

bus which is b-bit wide memory address register (MAR) .

  • Instruction Register(IR)
  • memory address register (MAR)
  • memory Buffer Register(MBR)
  • Program counter (PC)

Question No: 29 ( Marks: 1 ) – Please choose one

In_______technique, a particular block of data from main memory can be placed in

only one location into the cache memory .

  • Set Associative Mapping
  • Direct Mapping
  • Associative Mapping
  • Block Placement

Question No: 30 ( Marks: 1 ) – Please choose one

_______ indicate the availability of page in main memory.

  • Access Control Bits
  • Used Bits
  • Presence Bits
  • None of the given

Question No: 31 ( Marks: 1 )

What are the hardware interrupts in a computer system?Mention its utility.

Question No: 32 ( Marks: 1 )

Consider a LAN, using bus topology. If we replace the bus with a switch, what change

will occur in such a configuration?

Question No: 33 ( Marks: 2 )

Where do you find the utility of hardware interrupts in a computer system?

Question No: 34 ( Marks: 2 )

Differentiate between CPU register and Cache Memory.

Question No: 35 ( Marks: 3 )

Name three important schemes that are commonly used for error control.

Question No: 36 ( Marks: 3 )

What do you understand by the term data synchronization ?

Explain briefly the following schemes of data synchronization in your own words

Synchronous transmission

Asynchronous transmission

Question No: 37 ( Marks: 3 )

Differenciate between Spatial Locality And Temporal Locality .

Question No: 38 ( Marks: 5 )

Given a 16-bit parallel output port attached with the FALCON-A CPU as shown in the figure. The

port is mapped onto address DEh of the FALCON-A s I/O space. Sixteen LED branches are

used to display the data being received from the FALCON-A s data bus. Every LED branch is

wired in such a way that when a 1 appears on the particular data bus bit, it turns the LED on; a 0

turns it off.

Which LEDs will be ON when the instruction

out r2, 222

executes on the CPU? Assume r2 contains 1234h.

Question No: 39 ( Marks: 5 )

Consider a 4 way set-associative cache with 256KB capacity and 32 byte lines

a) How many sets are there in the cache?

b) How many bits of address are required to select a set in cache?

Question No: 40 ( Marks: 10 )

Describe the following features of FALCON-A Assembler

Symbol Table

I/O Ports

List File

Single Step

Error Log

Question No: 41 ( Marks: 10 )

How many platters are required for a 40GB disk if there are 1024

bytes/sector, 2048 sectors per track and 4096 tracks per platter

How many platters are required for a 80GB disk if there are 1024

bytes/sector, 2048 sectors per track and 4096 tracks per platter

 

 

 

 

 

 

 

 

 

 

 

 

 

VU CS501- Advance Computer Architecture (Session – 1) FinalTerm Solved Unsolved Past Papers Fall 2008

Education In Pakistan © 2016