Title:

Selected Chapters on Algorithms

Code:VKD
Ac.Year:2010/2011
Term:Summer
Curriculums:
ProgrammeBranchYearDuty
CSE-PHD-4DVI4-Elective
IT-PHD-3DIT3-Elective
Language:Czech
Completion:examination (verbal)
Type of
instruction:
Hour/semLecturesSem. ExercisesLab. exercisesComp. exercisesOther
Hours:390000
 ExaminationTestsExercisesLaboratoriesOther
Points:00000
Guarantee:Honzík Jan M., prof. Ing., CSc., DIFS
Faculty:Faculty of Information Technology BUT
Department:Department of Information Systems FIT BUT
 
Learning objectives:
  To command the behaviour of the advanced algorithms and data structures. To be acquainted with their fatures, conplexity and applications.
Description:
  The subject is pointed to advances methods of analysis techniques in areas of dynamic programming, advanced data structures like B-Trees, Binomial Trees and Heaps, Fibonacci Heaps, Red-Black Trees, Skip-Lists, Splay Trees.
Knowledge and skills required for the course:
  
  • Knowledge of the algorithmization on the master degree level 
Subject specific learning outcomes and competences:
  
  • Student shows the creative capabilities in edvanced algoritmhs on the doctoral level in project like woek

 

Generic learning outcomes and competences:
  
  • Student shows high quality presentation of the results of the project assigned
Syllabus of lectures:
 
  • Recursion: The substitution method, the iteration method, the master method, proof of the master method
  • Counting and probability
  • Dynamic programming
  • Greedy algorithms
  • Medians and Order Statistics
  • Red-Black Trees
  • Splay Tree
  • Skip-Lists
  • B-Trees
  • Binomial Tree
  • Binomial Heap
  • Fibonacci Heap
  • Polynomial and FFT
Fundamental literature:
 
  • Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, London, England 1990.
Study literature:
 Cormen,T.H., Leiserson,C.E.,Rivest,R.L.: Introduction to Algorithms. MIT Press, Cambridge
Exam prerequisites:
  Passing the presentation of the project assigned