Algorytmy i struktury danych w C#

Weekly outline

• 

  General

  Algorytmy i struktury danych w C#

  • 
  • Zawiadomienia i ogłoszenia Forum
  • 
    

    Wykłady

  • Analiza algorytmu Euklidesa SCORM package
  • Złożoność obliczeniowa algorytmów SCORM package
  • Metody projektowania algorytmów SCORM package
  • Wyszukiwanie połówkowe SCORM package
  • Elementarne metody sortowania SCORM package
  • Drzewa w notacji nawiasowej SCORM package
  • Drzewa poszukiwań binarnych SCORM package
  • Kopce i kolejki priorytetowe SCORM package
  • 
    

    Literatura

  • Banachowski, Diks, Rytter: Algorytmy i struktury danych URL
  • Cormen, Leiserson, Rivest: Wprowadzenie do algorytmów URL
  • Dasgupta, Papadimitriou, Vazirani: Algorytmy URL
  • Harel: Rzecz o istocie informatyki. Algorytmika URL
  • Wirth: Algorithms and Data Structures File
• 

  26 lutego - 4 marca

  Pomiar czasu wykonania

  • Przykład: Testowanie poprawności algorytmu Euklidesa Page
  • Przykład: Algorytm Steinhausa w C# Page
  • Przykład: Algorytm Kaprekara w C# Page
  • Zadanie: Praca na zajęciach 1 Assignment
  • Rozwiązanie: Pomiar czasu wykonania algorytmu Euklidesa Page
  • Wyniki: Pomiar czasu wykonania algorytmu Euklidesa File
  • Zadanie: Praca domowa 1 Assignment
  • Materiały dodatkowe

  • Ważniak: Własność stopu URL
  • Artykuł: Wokół Problemu Steinhausa z teorii liczb File
  • Artykuł: Algorytm i liczby Kaprekara File
  • Łamiblog: Kaprekar 2008 URL
• 

  5 marca - 11 marca

  Wyciąganie kulek z worka

  • Przykład: Algorytm Fishera i Yatesa w wersji konsolowej Page
  • Przykład: Algorytm Fishera i Yatesa w wersji graficznej Page
  • Przykład: Algorytm Durstenfelda w wersji konsolowej Page
  • Przykład: Algorytm Durstenfelda w wersji graficznej Page
  • Zadanie: Praca na zajęciach 2 Assignment
  • Rozwiązanie: Algorytm Biało-Czarne 1 w wersji graficznej Page
  • Zadanie: Praca domowa 2 Assignment
  • Rozwiązanie: Algorytm Biało-Czarne 2 w wersji graficznej Page
  • Materiały dodatkowe

  • Opis: Tasowanie elementów ciągu URL
• 

  12 marca - 18 marca

  Znajdowanie przywódcy ciągu

  • Problem: Znajdowanie silnego przywódcy Page
  • Przykład: Znajdywanie silnego przywódcy Page
  • Zadanie: Praca na zajęciach 3 Assignment
  • Rozwiązanie: Przywódca pikseli obrazka Page
  • Zadanie: Praca domowa 3 Assignment
  • Rozwiązanie: Wyszukiwanie przywódców dowolnego rzędu Page
  • Materiały dodatkowe

  • Ważniak: Przywódca ciągu URL
• 

  19 marca - 25 marca

  Metoda dziel i zwyciężaj

  • Przykład: Rekurencyjne sumowanie liczb Page
  • Przykład: Rekurencyjny przywódca Page
  • Zadanie: Praca na zajęciach 4 Assignment
  • Rozwiązanie: Rekurencyjne wyszukiwanie połówkowe Page
  • Problem: Rekurencyjne wyszukiwanie połówkowe Page
  • Zadanie: Praca domowa 4 Assignment
  • Materiały dodatkowe

  • Ważniak: Metoda dziel i zwyciężaj URL
  • Ważniak: Wyszukiwanie połówkowe URL
  • Coma - "Na pół" URL
• 

  26 marca - 1 kwietnia

  Programowanie zachłanne

  • Zadanie: Praca na zajęciach 5 Assignment
  • Rozwiązanie: Sortowanie przez wybieranie w wersji graficznej Page
  • Przykład: Minimalne sklejanie par Page
  • Rozwiązanie: Wyszukiwanie połówkowe 1 Page
  • Zadanie: Praca domowa 5 Assignment
  • Materiały dodatkowe

  • Ważniak: Minimalne Sklejanie Par URL
  • Select-sort with Gypsy folk dance URL
• 

  2 kwietnia - 8 kwietnia

  Wielkanoc
• 

  9 kwietnia - 15 kwietnia

  Sortowanie bąbelkowe
  

  • Ilustracja: Algorytmy sortowania URL
  • Zadanie: Praca na zajęciach 6 Assignment
  • Rozwiązanie: Sortowanie bąbelkowe w wersji graficznej Page
  • Przykład: Elementarne algorytmy sortowania w wersji konsolowej Page
  • Materiały dodatkowe

  • Ważniak: Sortowanie bąbelkowe URL
  • Przykład z wykładu 1 Page
  • Przykład z wykładu 2 Page
  • Przykład z wykładu 3 Page
  • Bubble-sort with Hungarian ("Csángó") folk dance URL
• 

  16 kwietnia - 22 kwietnia

  Sortowanie przez wstawianie połówkowe

  
  

  • Dane: Protokół egzaminacyjny z algorytmów Page
  • Przypomnienie: Wyszukiwanie połówkowe Page
  • Przykład: Sortowanie przez wstawianie Page
  • Zadanie: Praca na zajęciach 7 Assignment
  • Rozwiązanie: Sortowanie przez wstawianie połówkowe od tyłu Page
  • Zadanie: Praca domowa 6 Quiz
  • Zadanie: Praca domowa 7 Assignment
  • Materiały dodatkowe

  • Ważniak: Sortowanie przez wstawianie z wyszukiwaniem połówkowym URL
  • Fajny link URL
  • Insert-sort with Romanian folk dance URL
• 

  23 kwietnia - 29 kwietnia

  Kolokwium
• 

  30 kwietnia - 6 maja

  Majówka
• 

  7 maja - 13 maja

  Sortowanie przez scalanie

  • Sortowanie szybkie

  • Zadanie: Praca na zajęciach 8 Assignment
  • Przykład: Sortowanie przez scalanie Page
  • Przykład: Sortowanie szybkie z podziałem na trzy Page
  • Zadanie: Praca domowa 8 Assignment
  • Rozwiązanie: Uproszczone sortowanie szybkie Page
  • Materiały dodatkowe

  • Ważniak: Sortowanie przez scalanie (MergeSort) URL
  • Ważniak: Sortowanie szybkie (QuickSort) URL
  • Przykład: Sortowanie szybkie/kod - Wikiźródła, teksty i materiały źródłowe URL
  • Rozwiązanie: Sortowanie na dwóch wątkach Page
• 

  14 maja - 20 maja

  Reprezentacja dowiązaniowa list i drzew

  • Zadanie: Praca na zajęciach 9 Assignment
  • Przyklad: Notacja nawiasowa drzew w C# Page
  • Przykład: Drzewo File
  • Przykład: Rysowanie drzewa Page
  • Materiały dodatkowe

  • Rozwiązanie: Reprezentacja dowiązaniowa listy Page
  • Rozwiązanie: Reprezentacja dowiązaniowa drzewa Page
• 

  21 maja - 27 maja

  Podróż po Polsce

  • Mapa: Podział administracyjny Polski URL
  • Dane: Listy sąsiadujących miast Page
  • Rozwiązanie: Podróż po Polsce Page
  • Ilustracja: Podróż po Polsce File
  • Potomkowie Adama

  • Link: Potomkowie Adama URL
  • Dane: Drzewo jako zbiór par Page
  • Zadanie: Praca na zajęciach 10 Assignment
  • Rozwiązanie: Potomkowie Adama Page
• 

  28 maja - 3 czerwca

  Przeglądanie drzewa binarnego
  

  • Przykład: Drzewo binarne URL
  • Rozwiązanie: Rysowanie drzewa binarnego Page
  • Rozwiązanie: Przeglądanie drzewa binarnego Page
  • Wstawianie wartości do drzewa BST

  • Przykład: Drzewo BST URL
  • Zadanie: Praca na zajęciach 11 Assignment
  • Rozwiązanie: Wyszukiwanie w drzewie BST Page
  • Rozwiązanie: Budowanie drzewa BST Page
  • Materiały dodatkowe

  • Ważniak: Proste słowniki - drzewa poszukiwań binarnych URL
• 

  4 czerwca - 10 czerwca

  Budowanie i rysowanie kopca

  • Przykład: Rekurencyjne naprawianie kopca Page
  • Przykład: Iteracyjne naprawianie kopca Page
  • Rozwiązanie: Budowanie i rysowanie kopca Page
  • Kopiec jako kolejka priorytetowa

  • Przykład: Wstawianie i usuwanie wartości z kopca Page
  • Zadanie: Praca na zajęciach 12 Assignment
  • Rozwiązanie: Sortowanie przez kopcowanie Page
  • Materiały dodatkowe

  • Ważniak: Sortowanie kopcowe (HeapSort) URL
• 

  11 czerwca - 17 czerwca

  Kolokwium II
• 

  18 czerwca - 24 czerwca

  Zaliczenie

  • Plusy z ćwiczeń laboratoryjnych Assignment
  • Zapisy na egzamin ustny Choice