# VU CS502- Fundamentals Of Algorithms FinalTerm Solved Unsolved Past Papers FALL 2004

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
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.

# VU CS601 – DATA COMMUNICATION FINALTERM Solved Unsolved Past Papers FALL 2004

FINAL TERM EXAMINATION

Total Marks:60

SEMESTER FALL 2004

CS601-DATA COMMUNICATION                                                                                      Duration:120min

Name

PVC Name/Code

Date

Maximum Time Allowed: (2 Hours)

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

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

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

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 4th 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?

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

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

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.

a timer

a buffer

a dedicated line

# VU CS601 – DATA COMMUNICATION FINALTERM Solved Unsolved Past Papers FALL 2004

FINAL TERM EXAMINATION

Total Marks:60

SEMESTER FALL 2004

CS601-DATA COMMUNICATION                                                                                      Duration:120min

Name

PVC Name/Code

Date

Maximum Time Allowed: (2 Hours)

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

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

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

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 4th 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?

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

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

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.

a timer

a buffer

a dedicated line