Papers, Notes, Books & Help For Students

FINALTERM EXAMINATION

SEMESTER FALL 2004

CS502-FUNDAMENTALS OF ALGORITHM-3

Please read the following instructions carefully before attempting any of the questions:

1. Attempt all questions. All Questions carry Equal Marks.

2. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong with any of the questions, attempt it to the best of your understanding.

b. If you believe that some essential piece of information is missing, make an appropriate assumption and use it to solve the problem.

**WARNING: Please note that Virtual University takes serious note of unfair means. Anyone found involved in cheating will get an `F` grade in this course.

For Teacher’s use only

Question

Q1

Q2

Q3

Q4

Q5

Q6

Q7

Total

Marks

Some results you may need: Σ=+=ninni12)1( , Σ=++=ninnni1232632 , Σ=−−=+nixxxni111)1(

Question No: 1

Marks: 20

Indicate whether true or false. Beware of guessing: correct answer +5pts, no answer 0pts

(a) In Prim’s algorithm, the additional information maintained by the algorithm is the length of

the shortest edge from vertex v to points already in the tree.

A) TRUE

B) FALSE

C) UNKNOWN

(b) 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.

A) TRUE.

B) FALSE

C: UNKNOWN

(c) If a problem is NP-complete, it must also be in NP.

A) TRUE.

B) FALSE

C) UNKNOWN

(d) What is the worst-case runtime complexity of the following C function

int function(int n){

int i, j, k;

k = n;

for(i=-100; i<10*log(n);i++){

k = k/2;

}

for(j=i; j> n; j–){

k=j/2;

}

return k;

}

What order is the execution of this code

a) O(log n)

b) O(n)

c) O(n log n)

d) O(n2)

e) O(n2 log n)

Question No: 4

Marks: 5

Suppose Prim’s algorithm is applied to the weighted graph shown here starting at vertex a to find a minimum cost spanning tree. State the edges that would be added to the tree in the order that they are added. Name an edge using its endpoints, in alphabetical order. For example, the edge joining vertices p and q should be called {p, q}, not {q, p}. Given a choice of edges at any point, choose the one that would be first alphabetically. For example, given the possibility of choosing either {x, z} or {w, y}, you should choose {w, y} (because w proceeds x).

Question No: 5

Marks: 10

Consider the digraph on five nodes, labeled 0 through 4, with six directed edges

0→1, 1→4, 4→0, 0→2, 2→3, 3→2

List the strongly connected components of this digraph.

Question No: 2

Marks: 5

What is the solution to the recurrence T(n) = 2T(n/2)+1, T(1) = 1

T(n) =

Question No: 3

Marks: 5

The first diagram shown below is a tree which is a heap. The items in the heap are now to be sorted using heapsort. The following diagram shows the tree after all items have been sorted. Show the contents of the tree as it would appear after each of the first six passes of heapsort.

Question No: 6

Marks: 10

Consider the following 21 character message that consists of 3 a’s, 7 c’s, 6 t’s, and 5 g’s:

a a c c c c a c t t g g g t t t t c c g g

Are the following 43 bits a possible Huffman encoding of the message above?

0000001111000101010010010010101010111001001

Justify your answer as concisely and rigorously as possible.

Question No: 7

Marks: 20

In the following graph, edges are labeled with upper case letters. Edge weights are given as numbers next to edges.

Recall that Dijkstra’s algorithm finds the shortest path from v1 to all other vertices by adding edges that make shortest paths. For the graph shown above, each edge is bidirectional; that is, you can travel on either direction on it for the same cost. List the edges in the order chosen by Dijkstra’s algorithm.

FINAL TERM EXAMINATION

Total Marks:60

SEMESTER FALL 2004

CS601-DATA COMMUNICATION Duration:120min

StudentID/LoginID

Name

PVC Name/Code

Date

Maximum Time Allowed: (2 Hours)

Please read the following instructions carefully before attempting any question:

1. This examination is closed book, closed notes, closed neighbors.

2. Answer all questions.

a. There is no choice.

b. You will have to answer correctly all questions in this examination to get the

maximum possible marks.

3. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong with any of the questions, attempt it to

the best of your understanding.

b. If you believe that some essential piece of information is missing, make an

appropriate assumption and use it to solve the problem.

4. Examination also consists of multiple-choice questions. Choose only one choice as your

answer.

a. If you believe that two (or more) of the choices are the correct ones for a particular

question, choose the best one.

b. On the other hand, if you believe that all of the choices provided for a particular

question are the wrong ones, select the one that appears to you as being the least

wrong.

**WARNING: Please note that Virtual University takes serious note of unfair means. Anyone found involved in cheating will get an `F` grade in this course.

For Teacher’s use only

Question Q1 Q2 Q3 Q4 MCQs Total

Marks

Question No: 1 Marks:12

Apply the Hamming code algorithm to transmit the seven bit data 1100111. Invert the 4^{th} bit of the

transmitted data and prove it at receiving end. The combination used to calculate each of the four r values for a seven bit data sequence are as follows:

r1: bits 1, 3, 5, 7, 9, 11

r2: bits 2, 3, 6, 7, 10, 11

r3: bits 4, 5, 6, 7

r4: bits 8, 9, 10, 11

Question No: 2 Marks:12

Describe the following functions of transport layer of OSI model?

1) Service-point addressing

2) Connection Control

Question No: 3 Marks:10

Solve the following. Show all the work to get full credit.

1) If a periodic signal is decomposed into five sine waves with frequencies 1000, 2000,3000,4000,5000

Hz, what is the bandwidth?

2) What is the bit rate of the following signals?

a. A signal in which bit lasts for 0.001 seconds

b. A signal in which bit lasts for 2ms

Question No: 4 Marks:10

Briefly answer the following questions.

1) Give three examples each of Guided and Unguided Transmission Media?

2) Briefly describe how even parity and odd parity work?

Question No: 5 Marks: 2

In fiber optics, the signal source is __________ waves.

light

radio

infrared

very low frequency

Question No: 6 Marks: 2

Wave division multiplexing (WDM) is conceptually the same as FDM, except that the multiplexing and demultiplexing involve _________ signals.

analog

light

digital

periodic

Question No: 7 Marks: 2

Local loop is a connection between _______________ and ______________.

Subscriber’s handset and exchange

exchange and T-Lines

exchange and E-Lines

None of the above

Question No: 8 Marks: 2

In vertical redundancy check (VRC) a __________ bit is added to every data unit.

synchronization

framing

parity

interleaving

Question No: 9 Marks: 2

In cyclic redundancy checking, what is CRC?

The divisor

The remainder

The quotient

The dividend

Question No: 10 Marks: 2

Which error detection method involves polynomials?

CRC

VRC

LRC

Checksum

Question No: 11 Marks: 2

In stop and wait ARQ, if “data 1” has an error, the receiver sends a ________ frame.

NAK

NAK 0

NAK 1

NAK 2

Question No: 12 Marks: 2

Poll/Select line discipline requires _____________ to identify the packet recipient.

an address

a timer

a buffer

a dedicated line

FINAL TERM EXAMINATION

Total Marks:60

SEMESTER FALL 2004

CS601-DATA COMMUNICATION Duration:120min

StudentID/LoginID

Name

PVC Name/Code

Date

Maximum Time Allowed: (2 Hours)

Please read the following instructions carefully before attempting any question:

1. This examination is closed book, closed notes, closed neighbors.

2. Answer all questions.

a. There is no choice.

b. You will have to answer correctly all questions in this examination to get the

maximum possible marks.

3. Do not ask any questions about the contents of this examination from anyone.

a. If you think that there is something wrong with any of the questions, attempt it to

the best of your understanding.

b. If you believe that some essential piece of information is missing, make an

appropriate assumption and use it to solve the problem.

4. Examination also consists of multiple-choice questions. Choose only one choice as your

answer.

a. If you believe that two (or more) of the choices are the correct ones for a particular

question, choose the best one.

b. On the other hand, if you believe that all of the choices provided for a particular

question are the wrong ones, select the one that appears to you as being the least

wrong.

**WARNING: Please note that Virtual University takes serious note of unfair means. Anyone found involved in cheating will get an `F` grade in this course.

For Teacher’s use only

Question Q1 Q2 Q3 Q4 MCQs Total

Marks

Question No: 1 Marks:12

Apply the Hamming code algorithm to transmit the seven bit data 1100111. Invert the 4^{th} bit of the

transmitted data and prove it at receiving end. The combination used to calculate each of the four r values for a seven bit data sequence are as follows:

r1: bits 1, 3, 5, 7, 9, 11

r2: bits 2, 3, 6, 7, 10, 11

r3: bits 4, 5, 6, 7

r4: bits 8, 9, 10, 11

Question No: 2 Marks:12

Describe the following functions of transport layer of OSI model?

1) Service-point addressing

2) Connection Control

Question No: 3 Marks:10

Solve the following. Show all the work to get full credit.

1) If a periodic signal is decomposed into five sine waves with frequencies 1000, 2000,3000,4000,5000

Hz, what is the bandwidth?

2) What is the bit rate of the following signals?

a. A signal in which bit lasts for 0.001 seconds

b. A signal in which bit lasts for 2ms

Question No: 4 Marks:10

Briefly answer the following questions.

1) Give three examples each of Guided and Unguided Transmission Media?

2) Briefly describe how even parity and odd parity work?

Question No: 5 Marks: 2

In fiber optics, the signal source is __________ waves.

light

radio

infrared

very low frequency

Question No: 6 Marks: 2

Wave division multiplexing (WDM) is conceptually the same as FDM, except that the multiplexing and demultiplexing involve _________ signals.

analog

light

digital

periodic

Question No: 7 Marks: 2

Local loop is a connection between _______________ and ______________.

Subscriber’s handset and exchange

exchange and T-Lines

exchange and E-Lines

None of the above

Question No: 8 Marks: 2

In vertical redundancy check (VRC) a __________ bit is added to every data unit.

synchronization

framing

parity

interleaving

Question No: 9 Marks: 2

In cyclic redundancy checking, what is CRC?

The divisor

The remainder

The quotient

The dividend

Question No: 10 Marks: 2

Which error detection method involves polynomials?

CRC

VRC

LRC

Checksum

Question No: 11 Marks: 2

In stop and wait ARQ, if “data 1” has an error, the receiver sends a ________ frame.

NAK

NAK 0

NAK 1

NAK 2

Question No: 12 Marks: 2

Poll/Select line discipline requires _____________ to identify the packet recipient.

an address

a timer

a buffer

a dedicated line