• TODO: Noch keiner. Falls welche angelegt, hier eintragen! :)

TODO: Mit der Korrektur vergleichen/verbessern, falls ausgebessert → Diesen Kommentar löschen.

a) …erlaubt das Löschen des Listenkopfs in O(1)

b) …benötigt in der Regel eine Tabelle zur Speicherung von Zwischenergebnissen
…kann den Laufzeitaufwand beim Rucksackproblem signifikant reduzieren.

c) …final sein.
…aus Alpha geerbte Instanzmethoden unter Umständen überschreiben.

class Rectangle {int width, height; }

a)

class Cover{
    static boolean isSolved(boolean[][] used){
        for(int i = 0; i < used.length; i++){
            for(int j = 0; j < used[i].length; j++){
                if(!used[i][j]){
                    return false; 
                }
            }
        }
        return true; 
    }
}

b)

static void toggleRectangle(boolean[][] used, int row, int column, Rectangle r){
    for(int i = 0; i < used.length; i++){
        for(int j = 0; j < used[i].length; j++){
            used[row + i][column + j] = !used[row + i][column + j]; 
        }
    }
}

c)

static boolean fits( boolean[][] used, int row, int column, Rectangle r )
{
    assert ( row >= 0 && column >= 0 );
    if( used.length - row - r.height < 0 || 
        ( used.length > 0 && used[0].length - column - r.width < 0 ) )
        return false;
 
    for( int i = 0; i < r.height; ++i )
    {
        for( int j = 0; j < r.width; ++j)
            if( used[ row + i ][ column + j ] ) return false;
     }
     return true;
}

d)

TODO

TODO

TODO

a) Minimal: O() Maximal: O()

b)

static int height(TenTree tree){
    TODO
}

c)

static int longest(Tentree tree){
 
TODO
 
int without = 0; 
 
TODO
 
int with = 0; 
 
TODO
 
return Math.max(without, with);