wtorek, 28 kwietnia 2015

Tydzień 10: 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 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. 
    Napisz prostą aplikację testującą działanie Twojego drzewa.

Praca domowa nr 11 (dodatkowa) 

Zadanie o drzewie BST. Termin oddania: 6 maja 2015 r.

wtorek, 21 kwietnia 2015

Tydzień 9: wyjątki, JUnit

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

Praca domowa nr 10

Zadanie 4. Rozwiązanie należy wysłać mailem. W temacie wiadomości powinien znaleźć się ciąg PO oraz numer pracy domowej (tutaj: 10). Pliki źródłowe powinny być spakowane zip-em. Nazwa pliku powinna zawierać imię i nazwisko autora.

wtorek, 14 kwietnia 2015

Tydzień 8: klasówka treningowa

Ćwiczenia

Majówka - klasówka z roku 2013/2014.
Głosowanie - klasówka poprawkowa z roku 2013/2014.

Laboratorium

Laboratorium jest odwołane z powodu Olimpiady Informatycznej.

Praca domowa nr 9

Rozgrywki piłkarskie - klasówka z roku 2012/2013. Rozwiązanie należy oddać w wersji papierowej, napisane ręcznie. Termin oddania: 22 kwietnia 2015 r. Tej pracy domowej nie można poprawiać.

środa, 8 kwietnia 2015

Film: Inheritance, Polymorphism, & Testing

Ciekawy wykład o programowaniu bez if-ów, między innymi na przykładzie wyrażeń.

wtorek, 7 kwietnia 2015

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

  1. Zaimplementuj drzewo BST przechowujace liczby całkowite. Chcemy uniknąć dużej liczby testów (czy jest lewe dziecko, czy jest prawe dziecko,...) w kodzie. Jak będziesz reprezentować puste drzewo? Wskazówka: użyj polimorfizmu.
  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 zadanym priorytetem.
    • String[] pobierz() – pobiera z kolejki wszystkie napisy obiekty o najmniejszej wartości priorytetu (moze byc 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ę realizujacą 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 nr8

Zadanie o drzewie BST. Termin oddania: 15 kwietnia 2015 r.

Rozwiązanie należy wysłać mailem. W temacie wiadomości powinien znaleźć się ciąg PO oraz numer pracy domowej (tutaj: 8). Pliki źródłowe powinny być spakowane zip-em. Nazwa pliku powinna zawierać imię i nazwisko autora.