|
|
Main menu for Browse IS/STAG
Course info
KIV / ADT
:
Course description
Department/Unit / Abbreviation
|
KIV
/
ADT
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Applications 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
|
326 / -
|
0 / -
|
0 / -
|
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 |
No
|
Fundamental course |
Yes
|
Fundamental theoretical course |
No
|
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 main objective is to provide insight into the meaning of Abstract Data Types (ADTs). The students will learn about the most commonly used ADTs and their properties, focusing mainly on their interface and on the overview level also on their performance in the sense of expected speed of performing particular operations. The discussed ADS include queues, stacks, lists, tables, graphs and trees. The second objective is to demonstrate the possibilities of applying ADTs for solving common programming tasks, using existing implementations of ADTs.
|
Requirements on student
|
Submitting assignment solutions, midterm, solving problems during lectures.
Deadline for course credit is end of june.
|
Content
|
1. Problem, algorithm, program. Programming language. Program execution.
2. Generic programming. Recursve programs.
3. Computational complexity. O-notation, Omega-notation, Theta-notation. Practical examples.
4. Sorting - algoritms, their complexity.
5. Abstract data types, ADT Stack.
6. ADT Queue. Using ADTs for solving problems.
7. List. Iterator.
8. Set. Table. Dictionary. Hash function.
9. Ordered data structures.
10. Graphs, solving problems by breadth-first search.
11. Graphs, solving problems by depth-first search. Topological ordering.
12. Priority queue. Paradigm and properties of greedy algorithms.
13. Composite data structures and their application for problem solving.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
-
Guarantors:
Ing. Miloslav Konopík, Ph.D. ,
-
Lecturer:
Ing. Miloslav Konopík, Ph.D. (100%),
-
Tutorial lecturer:
Ing. Miloslav Konopík, Ph.D. (100%),
Ing. Jiří Martínek, Ph.D. (100%),
Ing. František Pártl (100%),
Ing. Martin Prantl, Ph.D. (100%),
Ing. Ondřej Pražák (100%),
Ing. Michal Seják (100%),
Ing. Jakub Sido (100%),
|
Literature
|
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Preparation for comprehensive test (10-40)
|
13
|
Preparation for an examination (30-60)
|
26
|
Undergraduate study programme term essay (20-40)
|
39
|
Total
|
130
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
to understand the representation of numbers, characters and strings in a computer |
to understand the work with user input and output, including using input and output files |
to describe the process of exection of a simple program on a computer |
to decompose problems into simpler problems and to write the decomposition down in a form of a program with subroutines |
to understand the meaning of subroutine parameters and return value |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
to build simple computer programs in an imperative programming language |
to perform elemntary mathematical derivations |
to interpret simple computer programs and to understand their function from the source code |
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 |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
to describe the function of basic data structures from the user point of view |
to interpret expressions on computational complexity of algorithms in terms of O, Omega and Theta notation |
to determine the expected computational complexity of operations performed on basic data structures |
Skills - skills resulting from the course: |
to analyze simple programs and to determine their computational complexity |
to build algorithms that use exiting implementations of basic data structures |
to build compound data structures tailored for particular programming tasks |
to choose appropriate data structures for solving programming tasks |
Competences - competences resulting from the course: |
N/A |
N/A |
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 |
Skills - skills achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
Test |
Seminar work |
Continuous assessment |
Competences - competence achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
Combined exam |
Test |
|
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 |
Task-based study method |
Self-study of literature |
Discussion |
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 |
Self-study of literature |
Competences - the following training methods are used to achieve the required competences: |
Lecture |
Lecture with visual aids |
Task-based study method |
Practicum |
|
|
|
|