Course detail
Algorithms
FIT-IALAcad. year: 2014/2015
Overview of fundamental data structures and their exploitation. Principles of dynamic memory allocation. Specification of abstract data types (ADT). Specification and implementation of ADT's: lists, stack and its exploitation, queue, set, array, searching table, graph, binary tree. 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 variants, Shell-sort, recursive and non-recursive notation of the Quick sort, Merge-sort,List-merge-sort, Radix-sort. Recursion and backtrack algorithms. Searching the patterns in the text. Proving of correctness of programs, construction of proved programs.
5 ECTS credits represent approximately 125-150 hours of study workload:
- 39 hours of lectures
- 26 hours for two home assignments
- 35 hours of project work
- 20 hours of continual study
- 30 hours of study for midterm and final examination
Language of instruction
Number of ECTS credits
Mode of study
Guarantor
Department
Learning outcomes of the course unit
- Student will acquaint with the methods of proving of correctness of programs and with construction of proved programs and learn their significance.
- 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.
- Student will learn the principles of dynamic memory allocation and will be use them on the model system.
- He/she learns and commands recursive and non recursive notation of basic algorithms.
- Student overrules the implementation and analysis of most used algorithms for searching and sorting.
-
Student learns terminology in Czech and English language
-
Student learns to participate on the small project as a member of small team
-
Student learns to present and defend the results of the small project
Prerequisites
- Basic knowledge of the programming in procedural programming language
- Knowledge of secondary school level mathematics
Co-requisites
Planned learning activities and teaching methods
Assesment methods and criteria linked to learning outcomes
- to earn min. 20 points within the semester
-
Plagiarism and not allowed cooperation will cause that involved students are not classified and disciplinary action can be initiated.
Course curriculum
- 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, construction of proved programs.
- Two home assignments
- Project with a mini-defense for a team of students.
Syllabus - others, projects and individual work of students:
Work placements
Aims
Specification of controlled education, way of implementation and compensation for absences
- Evaluated home assignments - 20 points
- Mid-term written examination - 14 point
- Evaluated project with the defense - 15 points
- Final written examination - 51 points; The minimal number of points which can be obtained from the final written examination is 20. Otherwise, no points will be assigned to a student.
Recommended optional programme components
Prerequisites and corequisites
- recommended prerequisite
Introduction to Programming Systems
Basic literature
Recommended reading
Classification of course in study plans
Type of course unit
Lecture
Teacher / Lecturer
Syllabus
- 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, construction of proved programs.