1) Are you familiar with at least one of the following programming languages:

• C
• C++
• Java
• Pascal

2) Consider the array a[ ]=[3,5,9,4,2,1] of n=6 integers

a) What will be the result of the procedure whoknows with respect to a[ ]?

b) What is the well-introduced name for the procedure?

procedure whoknows;

var
     la,r : integer;
     x : real;

     Procedure proc_s;

     Label 13;

     var
         i,j : integer;

     Begin
         i:=la;
         j:=2*i;
         x:=a[i];
         while (j<=r) do
         Begin
             if ((j<=r) and (a[j]<a[j+1])) then
             j=j+1;
             if (x>=a[j]) then
             goto 13;
             a[i]:=a[j];
             i:=j;
             j:=2*i
         End;
     13: a[i]=x
     End;

Begin
     la:=(n Div 2)+1;
     r:=n;
     While (la>1) do
     Begin
         la:=la-1;
         proc_s;
     End;
     While (r>1) do
     Begin
         x:=a[la];
         a[la]:=a[r];
         a[r]:=x;
         r:=r-1;
         proc_s
    End;
End;

3) Write down the disjunctive normal form (DNF) for the Boolean XOR-function. Transform this formula into a conjunctive normal form (KNF) using the distributive laws of a Boolean algebra!

4) Complete the following recursive function definition (in Java). The function toString should return a string with the decimal representation of x. (e.g., toString(-163) = "-0163").

String[ ] digits = {"0","1","2","3","4","5","6","7","8","9" };
static public String toString(int x) {
   if (x == 0) { return "0";}
   else { if (x < 0) {return "-" + toString( <SOLUTION1> ); }
        else {
          String digit = <SOLUTION2>;
          return toString(<SOLUTION3>) + digit;}
   }
}

5) Modify the definition of the function toString such that it uses a loop instead of recursion. The result of the function should remain unchanged.

String[ ] digits = {"0","1","2","3","4","5","6","7","8","9" };
public static String toString(int x){
   String result = < SOLUTION1>;
   String sign = "0";
   < SOLUTION2>
   while (<SOLUTION3>){
   < SOLUTION4>
   }
   return sign + result;
}

6) Let n be the number of leaves in a binary tree T. What is the minimum number of inner nodes in T?

7) How many KB memory does is take to hold a bit vector representation of the set of prime numbers less than 1.000.000?

8) Construct a binary search tree by inserting the sequence of keys in the order H, T, M, D, V, G. The nodes of the search tree are ordered based on alphabetical order.

9) Why does one use queues and not stacks as data structures to collect pending service requests for process scheduling?

10) Name one example for a simple data type and one example for a structured data type.

11) What is the value range of a signed 16-bit integer variable?

12) Restate one of the following for-loops with the help of a while-loop (let N be any integer value).

13) What is the difference between a while-loop and a do-while-loop (Pascal: repeat-until-loop)?

14) Given the following statements, what is the value of "y" if "x" equals to -2, 0, 2?

15) What are the values of pointer variables?

16) Two systems are connected with a bi-directional communication link. One system acts as a sender of information, partitioned into a sequence of messages. The other system receives this message sequence. Messages can get corrupted or lost. To allow the retransmission of corrupted or lost messages, a simple protocol is used. The receiver must acknowledge every message, the sender will retransmit a message if its acknowledgement is not received after a certain amount of time. The sender is only allowed to send a new message, if the previous message has been acknowledged by the receiver. This results in a "stop & wait" protocol, illustrated by the following picture.

Assume that the sender has always something to send and no messages are lost. Each message has a length of 1000 bits, each acknowledgement is 100 bits long. The throughput of the communication link equals 10 ⁶ bits per second, the distance between sender and receiver is 10km. The speed of the communication link is 2/3 of the speed of light, approximately 2·10⁵ km/s. Calculate the efficiency of this "stop & wait" protocol, where efficiency is the time to transfer only the messages in relation to the total time (including the acknowledgements).

17) A message of 12 bits is transmitted via a channel which exhibits a bit error rate of 10^-3.
     a) What is the probability of observing 3 bit errors?
     b) What is the probability of a correct reception?

18) What is meant by sampling and reconstruction of continuous-time signals ?

19) What is the definition of the z-Transform ?

20) What is the definition of the discrete-time Fourier transform ?

21) What is the definition of the discrete Fourier transform ?

22) Derive the difference equation for H(z) = Y(z)/X(z) = 1/(1-z^-1) ?

23) What is the binary value of the decimal number 0.75 ?

24) What is the decimal value of the binary number 11.01 ?

25) What is the definition of an orthogonal transform matrix A?

26) Write down the equations for g and for h in the expression
     

27) Given: div (one of Maxwell's equations)
     Determine:

28) Solve the following set of equations for U in a transmission line:

29) The electrical field of a guided electromagnetic wave is E(x,y,z,t) = A(z) F(x,y) exp(jz - jt) where F(x,y) is a transverse field distribution, A(z) an amplitude function,  = 6.2810 ⁶  m ^-1 the propagation constant and  = 310 ¹⁵  s ^-1 the angular frequency. What is the wavelength of this wave?

30) A red light-emitting diode emits radiation of mean free-space wavelength  = 0,66 µm and bandwidth  = 0,025 µm. The emitting area is A = 0.1 mm², the radiance S = 10 ⁴  Wcm ^-2 sr ^-1 . What power P is radiated from this diode into a cone of semiaperture  = 0.1 rad in a direction approximately normal to A?

31) What is the meaning and significance of positive and negative 'photoresist'?

32) The wave from problem (31) has a transverse field whose components in a Cartesian coordinate system are given in the form F(x,y) = {100, j100} mV/m. What kind of polarization has this wave?

33) In a Michelson interferometer for the measurement of displacements, a monochromatic wave  = 0,60 µm is reflected at normal incidence by a movable mirror. At a mirror position z _o interference with a reference wave leads to perfect extinction at the detector. When the mirror is moved, what is the minimum displacement z for the next extinction to occur?

34) Let be the Fourier transformation of a real signal x(t). What are the symmetry properties of and ?

35) The impulse response of a linear time invariant system is given by:

    a) What is the corresponding frequency response ?

    b) Compare c(t) to

with f(0) = 1, and f(t) = 0 for and answer the question, which system lends itself more easily to an implementation.

36) Explain the first Nyquist criterion using d(t) of question ????.

37) What is the message behind the term time-bandwith product?

38) Is it possible to transmit data at a rate of 10 ⁵ bit/sec via a channel of a bandwith   B = 100 Hz?

39) In a A/D converter the size of a quantization step is Q. The resulting prabability density function of the quantization error is

What is the resulting mean quantization noise power?

40) What type of system is shown in this figure?

41) What is the reason to choose 64 kbit/s as the rate for a digital telephone channel?

42) Assume a block code has a Hamming distance of d. How many bit errors can be

    a) detected,
    b) corrected ?

Click here to get the answers sheet!