środa, godz., 19.50-21.20, sala 325
Ogłoszenia
Omówienie zadań z egzaminu poprawkowego – wtorek, godzina 16 sala 103.
ZMIANA!!! Kolokwium odbędzie się 24 I.
Znowu frekwencja nie dopisała. Jeżeli chcą Państwo odrobić zajęcia, proszę o kontakt.
Na najbliższym repetytorium będę omawiał zadania z kolokwium. Będzie też można zobaczyć prace.
Naniosłem poprawki na wyniki. Nie spodziewam się ich już zmieniać, chyba że się komuś uda mnie przekonać, że ma rację.
Wstępne wyniki drugiego kolokwium. Sprawdzałem zadanie 1 i zadanie 2 z drugiej części. Jak na razie nie wiem, jak ocenić zadanie drugie, ale proszę nie spodziewać się dobrych ocen tam. Minimalnie mogą też zmienić się wyniki za zadanie pierwsze, przeczytam jeszcze raz i się zastanowię.
Obiecany przepis.
W związku z zainteresowaniem postaram się przynieść na kolejne repetytorium wszystkie zadania z kolokwium i z kartkówek. Poinformuję wcześniej, czy mi się uda, co zależy głównie o P. Rzechonka.
13 XII na repetytorium będzie drugie kolokwium. Zapraszam wszystkich gorąco.
Na poprzednim spotkaniu było bardzo mało osób. Jeśli będzie taka potrzeba, to możemy odrobić te zajęcia w innym terminie.
Lekka korekta wyników kolokwium.
Wstępne wyniki kolokwium. Miałem wątpliwości przy niektórych numerach indeksów. Jeśli kogoś nie ma na liście, proszę o kontakt. Wyniki są wstępne, bo nie jestem pewien, jak oceniać szacowania czasu oczekiwanego. Być może kilka ocen (tych w okolicach 4 pkt.) jeszcze podwyższę. Były 2 pkt. za algorytm, 1 pkt. za maksymalny i minimalny czas oraz 2 za czas oczekiwany.
Przypominam, że na najbliższym repetytorium jest kolokwium. Zapewne z tej okazji przeniesiemy się do większej sali.
Obiecany link do notatek na stronie p. Przemki Kanarek, znalezienie go nie było moim zdaniem trudne... złożoność QuickSort.
Od następnego spotkania chciałbym robić więcej zadań, tak jak umówiliśmy się. W szczególności przyglądać się będziemy zadaniom z ubiegłych lat.
Ustaliliśmy, że zajęcia odbywać się będą w sali 325.
Ustaliliśmy, że spotykamy się jak najwcześniej oraz możliwie skracamy przerwę, by skończyć o rozsądnej porze.
Co było (lub na pewno będzie)
Omówienie zadań z trzeciego kolokwium, wgląd w prace.
Kolokwium.
Algorytmy zachłanne raz jeszcze.
Algorytmy zachłanne – MST, kody Huffmana, problem szeregowania zadań.
Programowanie dynamiczne.
Omówienie zadań z drugiego kolokwium.
Drugie kolokwium.
Kopce dwumianowe - powtórka, kopce lewicujące, usuwanie z B-drzewa. pooglądaliśmy też sobie kolokwia i kartkówki.
Przypomnienie o tym, jak wstawiamy i usuwamy w drzewach AVL oraz jak wstawiamy do B-drzew (usuwanie za tydzień). Trochę o “ekstremalnych” własnościach drzew AVL, czyli jak wygląda maksymalnie niezbalansowane drzewo AVL i czemu jest interesujące.
Omówienie zadań i wyników kolokwium oraz omówienie zadań z kartkówki.
Kolokwium.
RadixSort, Sortowanie kubełkowe – detale, dyskusja, zadania. Na prośbę “sali” – mnożenie po rosyjsku. Krótka refleksja nad stałą w algorytmie magicznych piątek.
QuickSort – warianty (losowy element podziału, wybór jednego z kilku). Analiza przypadku średniego. Analiza przypadka pesymistycznego.
Algorytm scalający dwie posortowane listy “w miejscu”. K – posortowanie. “Ciągi Pratta” - sortowanie ciągu pod warunkiem, ze jest on 2 oraz 3 posortowany, uogólnienie na 2k i 3k posortowania. Algorytm sortujący w oparciu o te spostrzeżenia.
Notacja o oraz omega. Oczekiwana złożoność problemu (na prostym przykładzie).