Course detail
Algorithms and Data Structures
FEKT-BPC-ALDAcad. year: 2022/2023
The first part of the course is focused on introducing students to the basic concepts: algorithm, time and memory complexity of the algorithm, data container / collection.
The second part of the course deals with the concepts: abstract data type: (Vector, Stack, Queue, Set, Tree) and the use of iterators for these data types.
In the third part, students will learn about recursive and non-recursive algorithms, sorting and searching algorithms.
Language of instruction
Czech
Number of ECTS credits
7
Mode of study
Not applicable.
Guarantor
Learning outcomes of the course unit
The student is able:
- analyze the task using a flowchart;
- to determine its time and memory complexity for a simple algorithm;
- use basic abstract data types (Vector, Stack, Queue, Set, Tree) and use iterators for these data types.
- solve the problem using recursive and non-recursive algorithms;
- design and implement basic sorting and searching algorithms;
- correctly determine the data type for a given type of calculation (basic data types, pointer type to data type, and composite data type);
- work with dynamically allocated memory (acquisition and release of memory, manipulation of data in allocated memory);
- work with standard inputs, outputs and files;
- analyze the task using a flowchart;
- to determine its time and memory complexity for a simple algorithm;
- use basic abstract data types (Vector, Stack, Queue, Set, Tree) and use iterators for these data types.
- solve the problem using recursive and non-recursive algorithms;
- design and implement basic sorting and searching algorithms;
- correctly determine the data type for a given type of calculation (basic data types, pointer type to data type, and composite data type);
- work with dynamically allocated memory (acquisition and release of memory, manipulation of data in allocated memory);
- work with standard inputs, outputs and files;
Prerequisites
Attending BPC-UDP course or similar.
Co-requisites
Not applicable.
Planned learning activities and teaching methods
Techning methods include lectures and computer laboratory lectures. Students have to create assignments during the computer laboratory lectures.
Assesment methods and criteria linked to learning outcomes
Up to 40 points for the laboratory lectures (2 tests, up to 20 points each). Minimal needed points from laboratory lectures is 15.
Up to 60 points for the final examination. Minimal needed points from final examination is 20.
The course exam will take place in person.
Up to 60 points for the final examination. Minimal needed points from final examination is 20.
The course exam will take place in person.
Course curriculum
1. Introduction to the course, the concept of algorithm, time and memory complexity, dynamic memory allocation, API design for working with files.
2. Abstract data types, signature of abstract data type, concept (collection / container), concept of linear and nonlinear data structure (array, one-way bound list), description and properties of ADT: Stack, implementation of ADT Stack using array and single linked list. ADT TStack_array, ADT TStack_list.
3. Description and properties of ADT: Queue, Set, ADT TQueue_list, ADT TQueue_array, concept of iterator, use of iterators in ADT.
4. Description and properties of ADT: Set, Tree, (SkipList), unordered and ordered collections.
5. Introduction to sorting algorithms, properties of sorting methods, external and internal sorting, "in situ / in place" sorting. Algorithms Insert Sort, derivation of algorithm complexity.
6. Sorting by direct exchange (BubbleSort), modification of BubbleSort algorithm, derivation of algorithm complexity, sorting by direct selection (SelectSort), derivation of algorithm complexity
7. Recursive and iterative algorithm, use of recursion to calculate Fibonacci sequence, Wildcard matching (wildcards? *). Variants of recursive algorithms: direct, indirect recursion (recursion with auxiliary function).
8. More efficient methods of internal sorting - Shell Sort, Quick Sort
9. Trees - basic information, sorting using a heap
10. External sorting with the same number of input and output files, deriving the complexity of the algorithm. External sorting using internal sorting, complexity derivation.
11. Search in linear data structure, Binary field search, algorithm complexity. Binary search trees, determining the complexity of the algorithm.
12. Hashing.
13. AVL trees, B-trees, end of the course.
2. Abstract data types, signature of abstract data type, concept (collection / container), concept of linear and nonlinear data structure (array, one-way bound list), description and properties of ADT: Stack, implementation of ADT Stack using array and single linked list. ADT TStack_array, ADT TStack_list.
3. Description and properties of ADT: Queue, Set, ADT TQueue_list, ADT TQueue_array, concept of iterator, use of iterators in ADT.
4. Description and properties of ADT: Set, Tree, (SkipList), unordered and ordered collections.
5. Introduction to sorting algorithms, properties of sorting methods, external and internal sorting, "in situ / in place" sorting. Algorithms Insert Sort, derivation of algorithm complexity.
6. Sorting by direct exchange (BubbleSort), modification of BubbleSort algorithm, derivation of algorithm complexity, sorting by direct selection (SelectSort), derivation of algorithm complexity
7. Recursive and iterative algorithm, use of recursion to calculate Fibonacci sequence, Wildcard matching (wildcards? *). Variants of recursive algorithms: direct, indirect recursion (recursion with auxiliary function).
8. More efficient methods of internal sorting - Shell Sort, Quick Sort
9. Trees - basic information, sorting using a heap
10. External sorting with the same number of input and output files, deriving the complexity of the algorithm. External sorting using internal sorting, complexity derivation.
11. Search in linear data structure, Binary field search, algorithm complexity. Binary search trees, determining the complexity of the algorithm.
12. Hashing.
13. AVL trees, B-trees, end of the course.
Work placements
Not applicable.
Aims
The aim of the course is to familiar students with basic concepts of algorithm and data structures such as: the concept of algorithm, computational and memory complexity of the algorithm, abstract data type, recursive and non-recursive algorithms, sorting and searching algorithms.
Specification of controlled education, way of implementation and compensation for absences
The computer exercises is mandatory, the properly excused missed computer exercises can be compensate.
Recommended optional programme components
Not applicable.
Prerequisites and corequisites
- compulsory prerequisite
Introduction to Programming
Basic literature
PROKOP, Jiří. Algoritmy v jazyku C a C++. Praha: Grada Publishing, 2008. 176 s. ISBN 978-80-247-3929-8 (CS)
VEČERKA, Arnošt. Základní algoritmy. Skriptum Olomouc 2007. 91 s. (CS)
WRÓBLEWSKI,Piotr. Algoritmy – Datové struktury a programovací techniky. Brno: Computer Press, 2004. 351 s. ISBN 80-251-0343-9 (CS)
VEČERKA, Arnošt. Základní algoritmy. Skriptum Olomouc 2007. 91 s. (CS)
WRÓBLEWSKI,Piotr. Algoritmy – Datové struktury a programovací techniky. Brno: Computer Press, 2004. 351 s. ISBN 80-251-0343-9 (CS)
Recommended reading
Not applicable.
Elearning
eLearning: currently opened course
Classification of course in study plans
- Programme BPC-AMT Bachelor's 1 year of study, summer semester, compulsory
Type of course unit
Lecture
26 hod., optionally
Teacher / Lecturer
Syllabus
1. Introduction to the course, the concept of algorithm, time and memory complexity, dynamic memory allocation, API design for working with files.
2. Abstract data types, signature of abstract data type, concept (collection / container), concept of linear and nonlinear data structure (array, single linked list), description and properties of ADT: Stack, implementation of ADT Stack using array and single linked list.
3. Description and properties of ADT: Queue, Set, concept of iterator, use of iterators in ADT.
4. Description and properties of ADT: Set, Tree, unordered and ordered collections.
5. Introduction to sorting algorithms, properties of sorting methods, external and internal sorting, "in situ / in place" sorting. Algorithms Insert Sort, derivation of algorithm complexity.
6. Sorting by direct exchange (BubbleSort), modification of BubbleSort algorithm, derivation of algorithm complexity, sorting by direct selection (SelectSort), derivation of algorithm complexity
7. Recursive and iterative algorithm, use of recursion to calculate Fibonacci sequence, Wildcard matching (wildcard symbols ?*). Variants of recursive algorithms: direct, indirect recursion (recursion with auxiliary function).
8. More efficient methods of internal sorting - Shell Sort, Quick Sort.
9. Trees - basic information, sorting using a heap.
10. External sorting with the same number of input and output files, deriving the complexity of the algorithm. External sorting using internal sorting, complexity derivation.
11. Search in linear data structure, Binary field search, algorithm complexity. Binary search trees, determining the complexity of the algorithm.
12. ADT Skip list. ADT Hash table - hashing, choice of hash function, collision. Collision resolution methods: chaining, open addressing and searching for a free position in the hash table. Expected complexity of hash table operations.
13. AVL trees, end of the course.
2. Abstract data types, signature of abstract data type, concept (collection / container), concept of linear and nonlinear data structure (array, single linked list), description and properties of ADT: Stack, implementation of ADT Stack using array and single linked list.
3. Description and properties of ADT: Queue, Set, concept of iterator, use of iterators in ADT.
4. Description and properties of ADT: Set, Tree, unordered and ordered collections.
5. Introduction to sorting algorithms, properties of sorting methods, external and internal sorting, "in situ / in place" sorting. Algorithms Insert Sort, derivation of algorithm complexity.
6. Sorting by direct exchange (BubbleSort), modification of BubbleSort algorithm, derivation of algorithm complexity, sorting by direct selection (SelectSort), derivation of algorithm complexity
7. Recursive and iterative algorithm, use of recursion to calculate Fibonacci sequence, Wildcard matching (wildcard symbols ?*). Variants of recursive algorithms: direct, indirect recursion (recursion with auxiliary function).
8. More efficient methods of internal sorting - Shell Sort, Quick Sort.
9. Trees - basic information, sorting using a heap.
10. External sorting with the same number of input and output files, deriving the complexity of the algorithm. External sorting using internal sorting, complexity derivation.
11. Search in linear data structure, Binary field search, algorithm complexity. Binary search trees, determining the complexity of the algorithm.
12. ADT Skip list. ADT Hash table - hashing, choice of hash function, collision. Collision resolution methods: chaining, open addressing and searching for a free position in the hash table. Expected complexity of hash table operations.
13. AVL trees, end of the course.
Exercise in computer lab
39 hod., compulsory
Teacher / Lecturer
Syllabus
1. Brief review of the standard C libraries: format strings printf, scanf. Implementation of ADT TVector, saving vector to file using API.
2. ADT: TStack_array, TStack_list.
3. ADT: TQueue_list.
4. ADT: Finalize TQueue_list, TQueue_array, iterator implementation.
5. Test #1 (ADT).
6. Algorithms: Insert Sort, Select Sort, Bubble Sort.
7. Algorithms: Bubble Sort (including optimization with auxiliary flag), Bubble Sort (with calculation of the index of the last change), Shaker Sort, TVector element struct (sorting of structure-type elements according to different keys).
8. Recursive algorithms: Factorial, Fibonacci sequence, wildcard matching.
9. Advanced sorting algorithms: Shell Sort, Quick Sort, Heap Sort, Merge Sort.
10. Algorithms: External sorting with equal number of input/output files.
11. Array search (ADT Set with binary search).
12. Hashing (ADT Set implemented by Hash map).
13. Test #2 (Algorithms).
2. ADT: TStack_array, TStack_list.
3. ADT: TQueue_list.
4. ADT: Finalize TQueue_list, TQueue_array, iterator implementation.
5. Test #1 (ADT).
6. Algorithms: Insert Sort, Select Sort, Bubble Sort.
7. Algorithms: Bubble Sort (including optimization with auxiliary flag), Bubble Sort (with calculation of the index of the last change), Shaker Sort, TVector element struct (sorting of structure-type elements according to different keys).
8. Recursive algorithms: Factorial, Fibonacci sequence, wildcard matching.
9. Advanced sorting algorithms: Shell Sort, Quick Sort, Heap Sort, Merge Sort.
10. Algorithms: External sorting with equal number of input/output files.
11. Array search (ADT Set with binary search).
12. Hashing (ADT Set implemented by Hash map).
13. Test #2 (Algorithms).
Elearning
eLearning: currently opened course