Module also offered within study programmes:
General information:
Name:
Analysis of Algorithms
Course of study:
2016/2017
Code:
JIS-2-021-SW-s
Faculty of:
Physics and Applied Computer Science
Study level:
Second-cycle studies
Specialty:
Systemy wbudowane i rekonfigurowalne
Field of study:
Applied Computer Science
Semester:
0
Profile of education:
Academic (A)
Lecture language:
Polish
Form and type of study:
Full-time studies
Responsible teacher:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Academic teachers:
dr hab. inż. Gawroński Przemysław (gawron@newton.ftj.agh.edu.pl)
Module summary

Doświadczalna analiza czasowej złożoności obliczeniowej algorytmów; grafowych, wyszukiwania wzorca, rozwiązujących problemy NP-zupełne, wykorzystujących metody Monte Carlo i Las Vegas.

Description of learning outcomes for module
MLO code Student after module completion has the knowledge/ knows how to/is able to Connections with FLO Method of learning outcomes verification (form of completion)
Social competence
M_K001 Student potrafi w sposób przejrzysty zaprezentować wyniki analizy problemu algorytmicznego. IS2A_K05 Activity during classes,
Presentation,
Execution of a project,
Participation in a discussion
Skills
M_U001 Student potrafi zaproponować i zaimplemementować  rozwiązanie problemu NP-zupełnego. IS2A_U01, IS2A_U09 Presentation,
Project,
Participation in a discussion,
Execution of a project
M_U002 Student ptrafi praktycznie zbadać złożonośc obliczeniowa problemu algorytmicznego. IS2A_U01 Presentation,
Project
Knowledge
M_W001 Student zna metody praktycznej analizy złożoności obliczeniowej i poprawności algorytmów. IS2A_W09 Presentation,
Activity during classes,
Participation in a discussion,
Execution of a project
M_W002 Student zna pojęcie NP-zupełności. IS2A_W09 Presentation,
Project,
Participation in a discussion,
Execution of a project
FLO matrix in relation to forms of classes
MLO code Student after module completion has the knowledge/ knows how to/is able to Form of classes
Lecture
Audit. classes
Lab. classes
Project classes
Conv. seminar
Seminar classes
Pract. classes
Zaj. terenowe
Zaj. warsztatowe
Others
E-learning
Social competence
M_K001 Student potrafi w sposób przejrzysty zaprezentować wyniki analizy problemu algorytmicznego. - - - + - + - - - - -
Skills
M_U001 Student potrafi zaproponować i zaimplemementować  rozwiązanie problemu NP-zupełnego. - - - + - + - - - - -
M_U002 Student ptrafi praktycznie zbadać złożonośc obliczeniowa problemu algorytmicznego. - - - + - + - - - - -
Knowledge
M_W001 Student zna metody praktycznej analizy złożoności obliczeniowej i poprawności algorytmów. - - - + - + - - - - -
M_W002 Student zna pojęcie NP-zupełności. - - - + - + - - - - -
Module content
Project classes:

Studenci w dwuosobowych zespołach będą analizować i implementować rozwiązania dwóch wybranych problemów algorytmicznych, z których jeden będzie z grupy problemów NP-zupełnych.

Przykładowe zadania projektowe:

1. Problem wyszukiwanie wzorca: algorytm Knutha-Morrisa-Prata, automat skończony, algorytm Karpa-Rabina.

2. Algorytmy teorioliczbowe: system kryptograficzny RSA, algorytmy generacji liczb pierwszych, algorytmy rozkłady na czynniki pierwsze.

3. Algorytmy randomizowane: metoda Monte Carlo, metoda Las Vegas.

4. Algorytmy grafowe: algorytm Floyda-Warshalla, algorytm Johnsona, algorytm Forda-Fulkersona, algorytm Edmondsa-Karpa,

5. Programowanie liniowe, algorytm sympleks.

6. Problemy NP-zupełne: cykl Hamiltona, problem kliki, problem komiwojażera, problem kolorowania grafu, problemy podziału zbioru, problemy pokrycia, gry i układanki.

7. Algorytmy aproksymacyjne.

Efekty kształcenia:
- student potrafi zebrać informacje potrzebne do realizacji projektu.
- student potrafi zaimplementować rozwiązanie problemu algorytmicznego i zebrać dane do analizy złożoności obliczeniowej.
- student potrafi pracować w zespole dwuosobowym nad wykonaniem projektu.

Seminar classes:

W trakcie zajęć seminaryjnych studenci będą prezentować wyniki analizy wybranych dwóch problemów algorytmicznych zaimplementowanych w ramach zajęć projektowych.

Efekty kształcenia:
- student umie przygotować rozwiązanie wybranego problemu algorytmicznego.
- student potrafi przygotować i przedstawić wyniki analizy złożoności obliczeniowej danego problemu algorytmicznego.

Student workload (ECTS credits balance)
Student activity form Student workload
Summary student workload 78 h
Module ECTS credits 3 ECTS
Participation in project classes 30 h
Participation in seminar classes 15 h
Completion of a project 28 h
Preparation of a report, presentation, written work, etc. 5 h
Additional information
Method of calculating the final grade:

Ocena końcowa obliczana jest na podstawie wzoru:0.6 x ocena z projektu + 0.4 x ocena z seminarium.

Oceny ustalane będą zgodnie ze skalą ocen obowiązującą w regulaminie AGH, przyporządkowującą procent opanowania materiału konkretnej ocenie.

Prerequisites and additional requirements:

Znajomość podstawowych algorytmów i struktur danych, dobra znajomość jezyka C lub C++, Java.

Recommended literature and teaching resources:

1. Jon Kleinberg, Éva Tardos, Algorithm Design, ISBN-10: 0321295358
2. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein, Introduction to Algorithms, ISBN-10: 0262033844
3. Steven S. Skiena, The algorithm design Manual, ISBN 0-387-94860-0
4. Jeff Edmonds, How to Think About Algorithms, ISBN 9780521614108
5. Anany Levitin, Introduction to the Design and Analysis of Algorithms, ISBN 0132316811

Scientific publications of module course instructors related to the topic of the module:
  • P. Gawroński, M. J. Krawczyk, K. Kułakowski, Emerging communities in networks -
    a flow of ties, Acta Phys. Pol. B, 46, (2015), 911.
  • P. Gawroński, M. Nawojczyk, and K. Kułakowski, Opinion formation in an open sys-
    tem and the spiral of silence, Acta Phys. Pol. A, 127, (2015), A-45.
  • P. Gawroński, K. Malarz, M. J. Krawczyk, J. Malinowski, A. Kupczak, W. Sikora, K.
    Kułakowski, J. Wąs, and J.W. Kantelhardt, Strategies in crowd and crowd structure,
    Acta Phys. Pol. A, 123, (2013), 522.
  • A. Jarynowski, P. Gawroński, K. Kułakowski, How the competitive altruism leads to
    bistable homogeneous states of cooperation or defection, Lecture Notes in Computer
    Science, 7204 (2012) 543.
  • P. Gawroński, K. Kułakowski, M. Kampf and J. W. Kantelhardt, Evacuation in the
    Social Force Model is not stationary, Acta Phys. Pol. A, 121, (2012), B-77.
  • P. Gawroński, K. Kułakowski, Crowd dynamics – being stuck, Comp. Phys. Comm., 9,
    (2011), 1924.
  • P. Gawroński, K. Saeed, K. Kułakowski, Early warning of cardiac problems in crowd,
    Lect. Notes Artif. Int., 6071, (2010), 220
  • K. Kułakowski, P. Gawroński, To cooperate or to defect? Altruism and reputation,
    Phys. A, 388, (2009), 3581
  • P. Gawroński and K. Kułakowski, A numerical trip to social psychology: long-living
    states of cognitive dissonance, Lect. Notes in Computer Science, 4490, (2007), 43
  • P. Gawroński and K. Kułakowski, Heider balance in human networks, Proceedings of
    8th Granada Seminar, Eds. P. Garrido, J. Marro and M. A. Munoz, AIP Conf. Proc.
    779, Melville, NY, (2005) 93
  • P. Gawroński, P. Gronek, K. Kułakowski, The Heider balance and social distance, Acta
    Phys. Pol. B., 36, (2005), 2549
  • K. Kułakowski, P. Gawroński, P. Gronek, The Heider balance – a continuous approach,
    Int. J. Mod. Phys. C, 16, (2005), 707
Additional information:

Sposób i tryb wyrównania zaległości powstałych wskutek nieobecności studenta na zajęciach:

Nieobecność na zajęciach wymaga od studenta samodzielnego opanowania przerabianego na tych zajęciach materiału i jego zaliczenia w formie ustnej/pisemnej w wyznaczonym przez prowadzącego terminie. Student który bez usprawiedliwienia opuścił więcej niż 2 zajęcia może zostać pozbawiony, przez prowadzącego zajęcia, możliwości wyrównania zaległości.