Education In Pakistan

Papers, Notes, Books & Help For Students

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

Tag: FALL 2004

VU CS502- Fundamentals of Algorithms FinalTerm solved unsolved past papers FALL 2004

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

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

VU CS601 – DATA COMMUNICATION FINALTERM solved unsolved past papers FALL 2004

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

 

 

 

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

 

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

 

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

VU CS601 – DATA COMMUNICATION FINALTERM solved unsolved past papers FALL 2004

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

 

 

 

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

 

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

 

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

Education In Pakistan © 2016