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

`C, C++, Java` | `Pascal` |

`for` ` (i = 0; i < N; i++) ` ` p(i); ` | `FOR` ` i := 1 ` ` p(i); ` |

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?

`C, C++, Java` | `Pascal` |

`if` ` (x >= 0) ` ` if` ` (x > 0)` ` y = x + 1; ` `else` ` ` ` y = x - 1; ` | `IF` ` (x >= 0) ` ` IF` ` (x > 0) ` ` y := x + 1 ` `ELSE` ` ` ` y := x - 1; ` |

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^{ 6} 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^{5} 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)

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^{ 4} 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^{ 5} 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!

Hamburg University

of Technology

Am Schwarzenberg-Campus 1

21073 Hamburg

E-mail: pressestelle(at)tuhh.de