środa, 30 kwietnia 2014

Tydzień 11: typy uogólnione

Ćwiczenia

  1. Zaimplementuj stos parametryzowany typem elementów przechowywanych na stosie.
  2. Napisz własne drzewo BST, parametryzowane typem elementów przechowywanych w drzewie. Porządek powinien być zadany jako java.util.Comparator lub java.util.Comparable.
  3. Napisz procedurę sortującą tablicę dowolnego typu. Porządek definiujemy jak w zadaniu 2.

Laboratorium

  1. Zaimplementuj własną reprezentację drzewa (może być binarne), które w każdym węźle przechowuje obiekty tego samego typu. Twoje drzewo powinno udostępniać następujące operacje:
    • tworzenie pustego drzewa,
    • dodawanie elementu w określonym miejscu drzewa,
    • wypisanie wszystkich elementów drzewa,
    • wyliczenie rozmiaru drzewa,
    • wyliczenie wysokości drzewa,
    • sprawdzenie, czy drzewo zawiera wskazany element.
  2. Zaimplementuj drzewo BST przechowujące wartości tego samego typu. Algorytm porównujący może być dostarczany w postaci (do wyboru) Comparatora lub interfejsu Comparable. Twoje drzewo powinno udostępniać nastepujące operacje:
    • tworzenie pustego drzewa,
    • dodawanie elementu do drzewa,
    • sprawdzenie, czy drzewo zawiera wskazany element,
    • wypisanie wszystkich elementów drzewa w kolejności rosnącej.

Praca domowa nr 8

Zadanie nr 2 (drzewo BST). Termin oddania:  7 maja 2014 r.

Polecane linki

Generics in the Java Programming Language - tutorial
Java Generics FAQ 

wtorek, 22 kwietnia 2014

Tydzień 10: wyjątki, JUnit

W moodle'u jest dostępna treść pierwszego dużego zadania zaliczeniowego. Termin oddania: 30 kwietnia 2014 r.

Ćwiczenia

URI (ang. Uniform Resource Identifier) jest standardem internetowym umożliwiającym łatwą identyfikację zasobów w sieci. Poniżej fragment odpowiedniego dokumentu RFC, który określa jak wygląda URI.
/**
* An example URI and its component parts. [rfc3986]
*
* foo://example.com:8042/over/there?name=ferret#nose
* \_/ \______________/\_________/ \_________/ \__/
* | | | | |
* scheme authority path query fragment
*
* The pattern is
* <scheme> : <authority> / <path> ? <query> # <fragment>
*/ 
oraz szkielet walidatora sprawdzającego poprawność URI.
public class CustomURIValidator {
String scheme, authority, path, query, fragment;
public void validate(String uri) throws ... {
...
validateScheme();
validateAuthority();
validatePath();
}
/** 
  * @return true if c is either ALPHA, DIGIT, ’-’, ’.’, ’_’ 
  * or ’~’ 
 **/
public static boolean isUnreservedCharacter(char c) { ... }

private void validateAuthority() throws EmptyComponentException,
   ComponentTooLongException {
   if (authority == null || authority.length() < 1)
        throw new EmptyComponentException("authority");
   if (authority.length() > 255)
        throw new ComponentTooLongException("authority",255);
}

private void validatePath() throws ComponentTooLongException,    
    IllegalCharacterException {
    //leave blank
}

private void validateScheme() throws ... { ... }
}
  1. Uzupełnij metodę validate o kod dzielący URI na składowe i przypisujący składowe do odpowiednich pól walidatora.
  2. Uzupełnij metodę validateScheme() tak, aby spełnione były następujące wymagania:
    • schemat musi być niepusty.
    • schemat nie może być dłuższy niż 255 znaków.
    • schemat może zawierać jedynie litery, cyfry, myślnik, kropkę, znak podkreślenia lub tyldę (tzw. unreserved characters).
    Jeśli któreś z powyższych wymagań nie jest spełnione, powinien być rzucony odpowiedni wyjątek.
  3. public class IllegalCharacterException extends Exception {
        public IllegalCharacterException(String msg) {
            super(msg); 
        }
    }
    public class EmptyComponentException extends Exception {
        public EmptyComponentException(String msg) { 
            super(msg); 
        }
    }
    public class ComponentTooLongException extends Exception {
        public ComponentTooLongException(String component, int expected) {
             super("The " + component + " component can not be longer than"
                   + expected);
        }
    }
    
  4. Dodajmy nowy wyjątek InvalidCustomURIException:
    public class InvalidCustomURIException extends Exception {/*...*/}
    public class IllegalCharacterException 
           extends InvalidCustomURIException {/*...*/}
    public class EmptyComponentException 
           extends InvalidCustomURIException {/*...*/}
    public class ComponentTooLongException 
           extends InvalidCustomURIException {/*...*/}
    
    Zmień kod metody validate w ten sposób, aby rzucany był jeden wyjątek InvalidCustomURIException zawierający w sobie informacje o wszystkich błędach ze wszystkich składowych. Możesz zmienić kod wyjątków.

Laboratorium

  1. Zaprojektuj interfejs Stos reprezentujący stos liczb całkowitych.
  2. Zaimplementuj interfejs Stos za pomocą tablicy liczb całkowitych. Rozmiar tablicy ma być podany w konstruktorze. Twoja implementacja powinna rzucać odpowiedni wyjątki (trzeba je zdefiniować) przy próbie zdjęcia elementu z pustego stosu i położenia elementu na przepełniony stos.
  3. Napisz klasę z testami JUnit dla Twojego stosu (albo dla implementacji kolegi z ławki obok).
  4. Napisz program, który wczytuje wyrażenie w odwrotnej notacji polskiej (+, −, *, /) i wylicza jego wartość używając stosu z poprzedniego zadania.
W tym tygodniu z powodu pierwszego zadania zaliczeniowego nie ma pracy domowej. Ale za tydzień będzie :)

środa, 16 kwietnia 2014

Tydzień 9: klasówka przygotowawcza, wyjątki

Ćwiczenia

Probówki (klasówka poprawkowa z roku 2009/2010).

Z powodu świąt i przyszłotygodniowej klasówki w tym tygodniu nie ma pracy domowej. 

środa, 9 kwietnia 2014

Tydzień 8: klasówka przygotowawcza, interfejsy

Przypomnienie: 23 kwietnia (środa po świętach) na wykładzie jest klasówka.

Ćwiczenia

Aukcje (klasówka poprawkowa z roku 2008/2009).

Laboratorium

  1. Zaimplementuj drzewo BST przechowujące liczby całkowite. Chcemy uniknąć dużej liczby testów (czy jest lewe dziecko, czy jest prawe dziecko,...). Wskazówka: trzeba odpowiednio reprezentować puste drzewo przy pomocy polimorfizmu/interfejsów.
  2. Kolejka priorytetowa to struktura danych, do której można wstawiać elementy i z niej je pobierać. Kolejność pobierania elementów zależy od priorytetu tych elementów, najpierw wydawane są elementy o wyższym priorytecie. Zdefiniuj i zaimplementuj interfejs KolejkaPriorytetowa z operacjami:
    • void dodaj(int priorytet, String s) – dodaje do kolejki nowy napis z żądanym priorytetem.
    • String[] pobierz() – pobiera z kolejki wszystkie napisy obiekty o najmniejszej wartości priorytetu (może być ich wiele, stad wynikiem jest tablica). Pobrane elementy są usuwane z kolejki.
    • boolean czyPusta() – wynikiem jest true wtedy i tylko wtedy, gdy w kolejce nie ma już elementów.
    Zdefiniuj klasę realizującą ten interfejs za pomocą jednej z metod: lista posortowana, kopiec, drzewo BST.
    Napisz program, który wczyta ze standardowego wejścia kilka napisów, a następnie wypisze wczytany zbiór posortowany (za pomocą KolejkiPriorytetowej) ze względu na liczbę wystapień litery a w napisie.

Praca domowa nr 7 

Arimaa (klasówka poprawkowa z roku 2011/2012). Rozwiązanie należy oddać w wersji papierowej, napisane ręcznie. Termin oddania: 16 kwietnia 2014 r. Tej pracy domowej nie można poprawiać.

środa, 2 kwietnia 2014

Tydzień 7: wyrażenia cz. 2

Ćwiczenia

Kontynuujemy zadanie o wyrażeniach z poprzedniego tygodnia. Dziś dodamy upraszczanie wyrażeń. Chcemy, aby wyrażenia tworzyły się w postaci uproszczonej zgodnie z takimi regułami:

  • stała + stała → stała
  • 0 + wyrażenie → wyrażenie
  • wyrażenia + 0 → wyrażenie
  • stała * stała → stała
  • 1 * wyrażenie → wyrażenie
  • wyrażenie * 1 → wyrażenie

Laboratorium

Laboratorium jest odwołane z powodu Olimpiady Informatycznej.