Selftest Answers

1) Yes

2) a) a[ ] = [1,2,3,4,5,9]

    b) Heapsort


(Øa Ù b) Ú (a Ù Øb) = (Øa Ú a) Ù (Øa Ú Øb) Ù (a Ú b) Ù (b Ú Øb) = (Øa Ú Øb) Ù (a Ú b)


<SOLUTION1>:             -x
<SOLUTION2>: digits[x%10]
<SOLUTION3>: x/10


< SOLUTION1>:             ""
< SOLUTION2>: if (x<0) { sign = "-0"; x = -x;}
< SOLUTION3>: x != 0
< SOLUTION4>: result = digits[x%10] + result;
x = x / 10;

6) A binary tree with n leaves has at least n-1 inner nodes. The number of inner nodes is minimal if n=2 k and if the tree is balanced.

7) The bit vector representation takes 1.000.000-1 bits stating for each number between 1 and 1.000.000-1 whether this number is a prime number or not. This requires (1.000.0000-1) / (8 * 1024) 122 KB of memory.


9) Using stacks involves the danger that some requests will never be served. The reason is that new requests are stored at the top of the stack and thus served before the earlier requests which reside further down in the stack.

In queues (FIFO data structures), however, requests are served in the order in which they have entered the system. Thus all requests only spend a finite waiting time in the system.

10) Integer, long, short, cardinal, float, double, boolean, character, ...

Record, tuple, array, struct, union, vector

11) -32768 .. 32767.


C, C++, Java Pascal
i = 0;
while (i < N) {
i := 1;
     i = succ(i)

13) While-loop: The condition for leaving the loop is tested before an iteration step is executed. Do-while-loop: The condition for leaving the loop is tested after an iteration step is executed.

14) (dangling else problem)









15) Memory addresses.


TMess: 1000 bits : 106 bits/s = 1ms
TTotal: (1000 : 106) + (100 : 106) + 2 · (10km : 2·102 km/ms) = 1ms + 0.1ms + 0.1ms = 1.2ms
Efficiency: T Mess : T Total = 1ms : 1.2ms approx 0.83


          PsubE=binom(12 3)*(10exp-3)exp3*(1-10exp-3)exp9=~220*10exp-3

     b) PC = (1-10-3)12


18) A bandlimited continuous-time signal, having no frequency components above fb Hertz, is completely specified by samples that are taken at a uniform rate greater than 2fb Hertz. The frequency 2fb is known as the Nyquist rate. The reconstruction of the continuous-time signal from the discrete-time samples can be achieved by lowpass filtering with cutoff frequency fb.


          \begin{displaymath} X(z)=\sum_{n=-\infty}^{n=+\infty} \,x(n) z^{-n} \end{displaymath}


          \begin{displaymath} X(e^{j\Omega}))=\sum_{n=-\infty}^{n=+\infty} \, x(n) e^{-j \Omega n} \end{displaymath}


          \begin{displaymath} X(k)=\sum_{n=0}^{n=N-1} x(n) e^{-j 2 \pi/N k n} \quad \mbox{with k=0,1,..,N-1} \end{displaymath}



23) 0.11

24) 3.25

25) transpose(A)*A = A*transpose(A) = Identity_matrix

26) g=ae+bf; h=ce+df


          \begin{displaymath} \oint_{A} \vec{D}\mbox{ d}\vec{A} = \int_{V} \mbox{div}\vec{D}\mbox{ d}V =  \int_{V}\rho\mbox{ d}V = Q \end{displaymath}


          \begin{displaymath} \frac{\mbox{d}^2U}{\mbox{d}z^2} = (R'+j\omega L')(G'+j\omega C')U = \gamma^2U\end{displaymath}


          \begin{displaymath} \,U_1 = U_{10}\;e^{-\gamma z}\end{displaymath}

         \begin{displaymath} \,U_2 = U_{20}\; e^{\gamma z}\end{displaymath}

29) The wavelength is related to the propagation constant by $\beta$ = 2 $\pi/\Lambda$. Therefore, L = 1 µm.

30) The solid angle of the cone is $\Omega\,\approx\,\pi\alpha^2\,\approx\,$ 0.031 sr. The power into this cone is P = $\Omega\cdot$A$\cdot$ 0.31 W.

31) Photoresist is used in microelectronics to transfer mask patterns onto a surface for planar technologies like etching or deposition.Negative resist becomes insoluble (cross-linked) upon UV exposure, positive soluble.

32) Due the factor j the component Ey is lagging 90° in phase compared to Ex : Left circular polarization.

33) As the light travels back and forth along the extra path $\Delta$z, the next extinction occurs when
     2 |$\Delta$z| = $\lambda$.


          \begin{displaymath} \begin{array} \mbox{\vert}X\,(j\omega)\vert &amp; = &amp; \vert X\,(...  ...\arg\,\{X\,(j\omega)\} &amp; = &amp; -\arg\,\{X\,(j\omega)\}\end{array}\end{displaymath}


  a)         \begin{displaymath} C(j\omega) = e^{j \omega t_0}\quad\mbox{ for } \vert\omega\vert\ge\,\omega_N \quad \mbox{(ideal lowpass filter)}\end{displaymath}

  b)   c(t) cannot be realized, because it is non-causal
      d(t) does not have this deficiency.

36) Sampling d(t) at the rate $f_S = \frac{\omega_N}{\pi} = \frac{1}{T}$ leads to

          \begin{displaymath} d(kT) = \left\{ \begin{array} {rl} \frac{\omega_N}{\pi} &amp; \...  ...{for \,} kT=t_0 \ \mbox{0} &amp; \mbox{elsewere}\end{array}\rigth.\end{displaymath}

If data pulses are positioned at intervals of T ideal sampling results in zero intersymbol interference.

37) A shorter time pulse inevitably leads to a higher bandwith of the corresponding spectrum (and vice versa).

38) Yes, look at the channel capacity   $C\,=\,B\cdot ld\,[1\,+\,S/N]$ and sufficiency high S/N.


          \begin{displaymath} N= \int\limits_{-\infty}^{\infty}f(x)\cdot x^2\,dx = \frac{Q^2}{12}\quad \mbox{(R=1}\Omega\mbox{)}\end{displaymath}

40) Envelope demodulator for amplitude modulation.

41) The bandwidth of an analogue telephone channel is 3.5kHz. The sampling theorem suggests a sampling frequency at least doubling the signal bandwidth. A sampling frequency of 8kHz is selected. By means of nonlinear quantization an S/N of 60dB can be obtained using 8bit;   8kHz $ \cdot $ 8bit = 64kbit/s.

42). a) d - 1     b) (d - 1) / 2