|
|
Main menu for Browse IS/STAG
Course info
KIV / IDT
:
Course description
Department/Unit / Abbreviation
|
KIV
/
IDT
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Implementations of Data Structures
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
5
Cred.
|
Type of completion
|
Combined
|
Type of completion
|
Combined
|
Time requirements
|
Lecture
2
[Hours/Week]
Tutorial
2
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
Yes in the case of a previous evaluation 4 nebo nic.
|
Included in study average
|
YES
|
Language of instruction
|
Czech
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
Yes in the case of a previous evaluation 4 nebo nic.
|
Summer semester
|
199 / -
|
6 / -
|
2 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Summer semester
|
Semester taught
|
Summer semester
|
Minimum (B + C) students
|
not determined
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
Czech
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
0
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
Yes
|
Fundamental course |
Yes
|
Fundamental theoretical course |
Yes
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
N/A
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
KIV/PPA or KIV/PPA-E
|
Courses depending on this Course
|
N/A
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The objective of the course is to demonstrate the implementations of basic abstract data types, i.e. stack, queue, list, table, priority queue, trees, graphs and more. The key instrument is the concept of computational complexity, whcih is going to be formally introduced and discussed in all practical cases. The course is an extension of KIV/ADS, it provides the students with the insight into how common abstract data types are implemented and what consequences do particular implementation choices have on the data structure properties.
|
Requirements on student
|
Homework assignments, midterm. Deadline for course credit is end of june.
|
Content
|
1. Problem, algorithm, program. Programming language, program execution. Object, class, instance.
2. Generic programming, interface, polymorphism. Recursive programs.
3. Computational complexity, O, Omega and Theta sets.
4. Sorting. InsertSort, ShellSort, QuickSort, MergeSort.
5. Abstract data types. Collections. Stack - implementation by an array and by a linked structure.
6. Elliminating recursion using a custom stack. Queue - possible implementations.
7. List, Iterator, possible implementations.
8. Table, hash table, hash function.
9. Trees, binary search tree, balanced trees.
10. Graph, implementation by incidence list/matrix. Breadth-first search.
11. Topologic ordering, Depth-first search.
12. Priority queue, heap.
13. Formalization and classification of problems. Problem classes P, NP and NP-C
|
Activities
|
|
Fields of study
|
Pro předmět existuje systém opor v LMS Moodle se všemi podstatnými informacemi a materiály
|
Guarantors and lecturers
|
-
Guarantors:
Doc. Ing. Libor Váša, Ph.D. ,
-
Lecturer:
Doc. Ing. Libor Váša, Ph.D. (100%),
-
Tutorial lecturer:
Ing. Milan Hotovec (100%),
Ing. Zuzana Káčereková (100%),
Ing. Alex König (100%),
Ing. Michal Nykl, Ph.D. (100%),
Ing. Jana Varnušková, Ph.D. (100%),
Doc. Ing. Libor Váša, Ph.D. (100%),
Ing. Natálie Vítová, M.Sc. (100%),
|
Literature
|
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Undergraduate study programme term essay (20-40)
|
39
|
Preparation for an examination (30-60)
|
26
|
Preparation for comprehensive test (10-40)
|
13
|
Total
|
130
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
to understand primitive data types used fro representing integers, floats and characters in a computer |
to understand basic control flow in imperative programming |
to describe programming principles in imperative programming language, with focus on control flow |
to demonstrate knowledge of basic math terminology and methods |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
to use some common integrated development environment on user level |
to perform basic mathematical derivations and calculations |
to construct simple programs in an imperative programming language |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
N/A |
N/A |
N/A |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
to interpret statements on algorithm complexity and complexity classes O, Omega and Theta |
to interpret statements on problem complexity, to understand statements on complexity classes P, NP and NP-C |
to describe the process of program execution in a computer, especially from the point of view of memory allocation in stack and on heap and the creation of stack frames |
to determine the computational complexity of operations on perticular implementations of abstract data types, in particular with the standard implementations |
to enumerate the most common sorting algorithms and to analyze their properties |
to enumerate the most common abstract data types, to describe their possible implementations and their resulting properties |
Skills - skills resulting from the course: |
to analyze and to compare algorithms from the point of view of their complexity class |
to implement programs using basic concepts of object oriented programming |
to implement advanced programs for processing of dynamic data structures |
to implememnt basic algorithm for procesing of graphs, i.e. the depth-first search, the breadth-first search and the topological ordering |
to implement basic algorithms for processing of tree data structures, i.e. pre-, in- and post-order traversal |
to design advanced data structures based on particular assignments, especially focusing on the choice of an appropriate imlementation of an abstract data type |
to build custom implementations of asbtract data types tailored for particular programming tasks |
Competences - competences resulting from the course: |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
Test |
Continuous assessment |
Seminar work |
Skills - skills achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
Test |
Continuous assessment |
Seminar work |
Competences - competence achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
Test |
Seminar work |
Continuous assessment |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Lecture with visual aids |
Lecture supplemented with a discussion |
Practicum |
E-learning |
Self-study of literature |
Cooperative instruction |
Task-based study method |
Individual study |
Skills - the following training methods are used to achieve the required skills: |
Lecture |
Lecture with visual aids |
Lecture supplemented with a discussion |
Practicum |
E-learning |
Task-based study method |
Cooperative instruction |
Self-study of literature |
Individual study |
Competences - the following training methods are used to achieve the required competences: |
Lecture |
Lecture with visual aids |
Practicum |
E-learning |
Task-based study method |
Self-study of literature |
Individual study |
|
|
|
|