Course details

Algorithms (in English)

IALe Acad. year 2021/2022 Winter semester 5 credits

Current academic year

Overview of fundamental data structures and their exploitation. Introduction to time complexity of algorithms. Specification of abstract data types (ADT). Specification and implementation of ADT's: lists, stack and its exploitation, queue, searching table. Algorithms upon the binary trees. Searching: sequential, in the ordered and in not ordered array, searching with the guard (sentinel), binary search, search tree, balanced trees (AVL). Searching in hash-tables. Ordering (sorting), principles, sorting without the moving of items, sorting with multiple keys. Most common methods of sorting: Select-sort, Bubble-sort, Heap-sort, Insert-sort and its variants, Shell-sort, recursive and non-recursive notation of the Quick sort, Merge-sort, List-merge-sort, Radix-sort.

Guarantor

Honzík Jan M., prof. Ing., CSc. (DIFS)

Language of instruction

English

Completion

Credit+Examination (written)

Time span

  • 39 hrs lectures
  • 13 hrs projects

Assessment points

  • 51 pts final exam
  • 14 pts mid-term test
  • 35 pts projects

Department

Department of Information Systems (UIFS)

Lecturer

Burgetová Ivana, Ing., Ph.D. (DIFS)
Honzík Jan M., prof. Ing., CSc. (DIFS)

Instructor

Burgetová Ivana, Ing., Ph.D. (DIFS)
Křena Bohuslav, Ing., Ph.D. (DITS)

Subject specific learning outcomes and competences

  • The student will learn the fundamentals of algorithm complexity and their intention.
  • He/she acquaints with basic abstract data types and to commands its implementation and exploitation.
  • He/she learns and commands recursive and non recursive notation of basic algorithms.
  • Student will become familiar with different variants of search tables and understand their properties.
  • Student overrules the implementation and analysis of most used algorithms for searching and sorting.

Learning objectives

The student will learn the fundamentals of algorithm complexity and will be able to use gained knowledge in the design of programs. Student acquaints with basic abstract data types and learn how to implement nad use them. The student learns and commands recursive and non-recursive notation of basic algorithms and will be able to use gained knowledge in the design of programmes. Student understands the implementation and analysis of most of the used algorithms for searching and sorting.

Recommended prerequisites

Prerequisite knowledge and skills

  • Basic knowledge of the programming in procedural programming language (knowledge of programming language C will be essential for solving homework problems).
  • Knowledge of secondary school level mathematics.

Study literature

  • Amsbury, W: Data Structures: From Arrays to Priority Queues.
  • Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
  • Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms, Cambridge: MIT Press, 2009
  • Honzík, J., Hruška, T., Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
  • Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
  • Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
  • Horovitz, Sahni: Fundamentals of Data Structures.
  • Horowitz, Sahni: Fundamentals of Data Structures in C, University Press, 2010
  • Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms.
  • Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms, Addison Wesley, 1983.
  • Kruse, R.L.: Data Structures and Program Design. Prentice- Hall,Inc. 1984
  • Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
  • Sedgewick,R.:Algoritmy v C. (Základy. Datové struktury. Třídění. Vyhledávání.) Addison Wesley 1998. Softpress 2003.

Syllabus of lectures

  • Overview of data structures. Abstract data type and its specification.
  • Specification, implementation and exploitation of ADT list.
  • Specification, implementation and exploitation of ADT stack, queue. Numeration of expressions with the use of stack.
  • ADT array, set, graph, binary tree.
  • Algorithms upon the binary tree.
  • Searching, sequential, in the array, binary search.
  • Binary search trees, AVL tree.
  • Hashing-tables.
  • Ordering (sorting), principles, without movement, multiple key.
  • Most common methods of sorting of arrays, sorting of files.
  • Recursion, backtracking algorithms.
  • Proving the programs, costruction of proved programmes.

Syllabus - others, projects and individual work of students

  • Two home assignments

Progress assessment

  • Two evaluated  home assignments - 25 points
  • Mid-term written examination - 14 point
  • Final written examination - 51 points
  • Elaboration of short examples during lectures - 10 points

Exam prerequisites

  • Gain a minimum of 15 points per semester.

  • If plagiarism or illegal collaboration on projects or homework assignments is discovered, credit will not be awarded and disciplinary action will be considered.

Back to top