Deck 10: Sorting Algorithms and Pipelined Systems

Question 1

______ have been developed specifically for pipelined systems.

A)utility software
B)speed up utilities
C)optimizing compilers
D)none of the above

Answer 1

optimizing compilers

Question 2

Which of the following is a combination of several processors on a single chip?

A)multicore architecture
B)risc architecture
C)cisc architecture
D)subword parallelism

Answer 2

multicore architecture

Question 3

The important feature of the VLIW is .....

A)ilp
B)cost effectiveness
C)performance
D)none of the mentioned

Answer 3

ilp

Question 4

The parallel execution of operations in VLIW is done according to the schedule determined by .....

A)sk scheduler
B)interpreter
C)compiler
D)encoder

Question 5

The VLIW processors are much simpler as they do not require of .....

A)computational register
B)complex logic circuits
C)ssd slots
D)scheduling hardware

Question 6

The VLIW architecture follows ..... approach to achieve parallelism.

A)misd
B)sisd
C)simd
D)mimd

Question 7

Which of the following is not a Pipeline Conflicts?

A)timing variations
B)branching
C)load balancing
D)data dependency

Question 8

Which of the following statements is NOT TRUE for Internal Sorting algorithms

A)usually deal with small number of elements
B)no of elements must be able to fit in process\s main memory
C)use auxilliary memory like tape or hard disk
D)ususally are of type compare-exchange

Question 9

In sorting networks for INCREASING COMPARATOR with input x,y select the correct output X', Y' from the following options

A)x\ = min { x , y } and y\ = min { x , y }
B)x\ = max { x , y } and y\ = min { x , y }
C)x\ = min { x , y } and y\ = max{ x , y }
D)x\ = max { x , y } and y\ = max { x , y }

Question 10

In sorting networks for DECREASING COMPARATOR with input x,y select the correct output X', Y' from the following options

A)x\ = min { x , y } and y\ = min { x , y }
B)x\ = max { x , y } and y\ = min { x , y }
C)x\ = min { x , y } and y\ = max{ x , y }
D)x\ = max { x , y } and y\ = max { x , y }

Question 11

Which of the following is TRUE for Bitonic Sequence
A. Monotonically increasing
B. Monotonically Decreasing
C. With cyclic shift of indices
D. First increasing then decreasing

A)a) and b)
B)a) and b) and d)
C)a) and b) and c)
D)a) and b) and c) and d)

Question 12

Which of the following is NOT a BITONIC Sequence

A){8, 6, 4, 2, 3, 5, 7, 9}
B){0, 4, 8, 9, 2, 1}
C){3, 5, 7, 9, 8, 6, 4, 2}
D){1, 2, 4, 7, 6, 0, 1}

Question 13

The procedure of sorting a bitonic sequence using bitonic splits is called

A)bitonic merge
B)bitonic split
C)bitonic divide
D)bitonic series

Question 14

While mapping Bitonic sort on Hypercube, Compare-exchange operations take place between wires whose labels differ in

A)one bit
B)two bits
C)three bits
D)four bits

Question 15

Which of following is NOT A WAY of mapping the input wires of the bitonic sorting network to a MESH of processes

A)row major mapping
B)column major mapping
C)row major snakelike mapping
D)row major shuffled mapping

Question 16

Which is the sorting algorithm in below given steps -
1) procedure X_SORT(n)
2) begin
3) for i := n - 1 downto 1 do
4) for j := 1 to i do
5) compare-exchange(aj, aj + 1);
6) end X_SORT

A)selection sort
B)bubble sort
C)parallel selcetion sort
D)parallel bubble sort

Question 17

The odd-even transposition algorithm sorts n elements in n phases (n is even), each of which requires ------------compare-exchange operations

A)2n
B)n2
C)n/2
D)n

Question 18

What is TRUE about SHELL SORT

A)moves elements only one position at a time
B)moves elements long distance
C)during second phase algorithm switches to odd even transposition sort
D)both 2 and 3

Question 19

Which is the fastest sorting algorithm

A)bubble sort
B)odd-even transposition sort
C)shell sort
D)quick sort

Question 20

Quicksort's performance is greatly affected by the way it partitions a sequence.

Question 21

Pivot in Quick sort can be selected as

A)always first element
B)always last element
C)always middle index element
D)randomly selected element

Question 22

Quick sort uses Recursive Decomposition

Question 23

In first step of parallelizing quick sort for n elements to get subarrays, which of the following statement is TRUE

A)only one process is used
B)n processes are used
C)two processes are used
D)none of the above

Question 24

In Binary tree representation created by execution of Quick sort, Pivot is at

A)leaf node
B)root of tree
C)any internal node
D)none of the above

Question 25

What is the worst case time complexity of a quick sort algorithm?

A)o(n)
B)o(n log n)
C)o(n2)
D)o(log n)