Algorithmen und Programmierung III    

         WS 2002/2003                              Übung 1                                    H. Schweppe
         

       Ausgabe:    17.10.2002
       Abgabe:     29.10.2002   

Aufgabe 1.1  (4 P)  
Das folgende Programm soll feststellen, ob ein Dreieck mit Seitenlängen a, b und c gleichseitig (1), gleichschenklig(2) oder beliebig (3) ist. Der berechnete Wert ist 1,2 oder 3.

// pre: a,b,c > 0
int triangle (int a, int b, int c) {
if (a==b) {
    if(b==c) {
    //
    return 1;
    }
    else {  
                  Aufgabe: a) Geben Sie die
                                 
Invarianten (jeweils hinter //) an.
  
//gleichschenklig       Ist das Programm korrekt?
                                  

   
  return 2;                  Begründen Sie, warum das 
                                                                  Programm    korrekt /
fehlerhaft ist.
    }                                                           

 
}
else {
    if {b==c) {
    //
     return 2;
    }
    else {
    // return 3;
    }
} //post:  .
..

Aufgabe 1.2 ( 6 P)  

(a) Zeige: Wenn f(n) = O(g(n)) und d(n) = O(h(n)), dann ist  f(n)+d(n) = O(g(n) + h(n)).    (2P)

(b) Zeige: 3(n + 1) 7 + 2n log n =  O(n 7 ). (3P)

(c) Die Algorithmen A und B lösen dasselbe Problem.  A benötigt 10n log n Operationen, B braucht n 2 Operationen. Zu bestimmen ist das kleinste  n0 so dass A weniger Operationen als B benötigt für n  >=  n0  (2P)

Aufgabe 1.3 ( 8 P)

In Alp2  (Skript 2.11.4) wurde die Datenstruktur Stapel mit den Operationen 

   push(Object element)  und
 Object pop()

implementiert. Die Implementierung ist nicht typsicher. Implementieren Sie das Interface

public interface IntStack {
  
// throws Exception 

    public void pushInt(int element);
  
//post: element is top of stack

    public int popInt()
    throws Exception;
 
//pre: stack is not empty, otherwise exception thrown
  //result: top element of stack
  //post: stack without top element
}

als Klasse IntStackAdapter unter Verwendung des Adapter-Musters auf  Basis der Klasse Stack. 
Den Code für die Klasse Stack finden Sie hier. Testen Sie die Klasse mit Hilfe einer eigenen Klasse, z.B. als JUnit-Test-Klasse. 

Aufgabe 1.4 ( 8 P) (Wiederholung: verkettete Listen) 

Eine einfach verkettete Liste soll in situ umgedreht werden, d.h. die entsprechende Methode wirkt wie die bekannte Haskell-Funktion reverse ::[a] ->[a], jedoch ohne dabei alle Elemente zu kopieren.

Die Implementierung verwendet ein 'Wächterelement' (sentinel), das keine Nutzdaten enthält. 
Implementieren Sie neben der Methode 
public void reverse() auch die Methode printList(), die die Elemente der Liste 'links nach rechts' ausgibt. Das Quellcodefragment finden Sie hier. 
Selbstverständlich gehört eine Testsuite zur Lösung. Sie können die
reverse() rekursiv oder iterativ implementieren. Im zweiten Fall nicht die Schleifeninvariante vergessen!

Aufgabe 1.5 ( 4 P) (Wiederholung:Objektorientierung) 

a) Wir betrachten eine Klassenhierachie für geometrische Objekte. class Rechteck kann  man als Unterklasse von class Quadrat modellieren - oder umgekehrt. Geben Sie die entsprechenden Klassenfragmente an.  Gibt es Gründe, die für eine der Alternativen sprechen? 
(Kurze Begründung).

b) Angenommen  class B extends A {…} und  class C extends A {…}. Welche  der Anweisungen ist / sind falsch (knappe Begründung)?

1)   B b = new A();   
2)   A a = new B();
3) C a = (C) new B();
4)   keine

c) Gegeben sei eine Klasse  class Animal und eine Subklasse class Cat extends Animal. In beiden wird die Methode noise() vereinbart. Welche Methode wird in folgendem Codestück ausgeführt:

Animal s = new Cat();
System.out.println(s.noise());  

d) Die Klasse  Y erweitert  die Klasse X: class Y extends X {...}. Welche der folgenden cast-Operationen ist falsch /überflüssig /richtig?

X x = (X) new Y();
Y y = (Y) x; 
Y a = (Y) ((X) (new Y()));

Aufgabe 1.6  (Verständnisfragen 2 P)

a) Gibt es einen Unterschied zwischen Mustern (patterns) und Makros? 
b) Warum kann man einen Algorithmus normalerweise nicht wirklich durch eine Laufzeit-Messreihe (Benchmark) charakterisieren?
c) Gibt es Situationen (welche?), in denen ein Benchmark Algorithmen besser charakterisiert, als eine Laufzeitanalyse? 
d) richtig oder falsch: Die Verwendung eines Interface in Java, wie etwa in 1.4., ist mit Laufzeiteinbußen für das Programm verbunden (kurze Begründung) 

 

}