|
|
Main menu for Browse IS/STAG
Course info
KIV / PT-E
:
Course description
Department/Unit / Abbreviation
|
KIV
/
PT-E
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Programming Techniques
|
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
3
[Hours/Week]
Tutorial
2
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
English
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
0 / -
|
0 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
5 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Winter semester
|
Semester taught
|
Winter semester
|
Minimum (B + C) students
|
10
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
English
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
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 |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
KIV/PT
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
N/A
|
Courses depending on this Course
|
KSO/SBZIM
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The aim of subject is to provide information to students in field od data structures (trees, fraphs, hashing tables, dictionaries) and algorithms }sorting, searching, sets and graphs algorithms, text-processing algorithms, basic compression and cryptography algorithms etc.) widely used in compurer science.
|
Requirements on student
|
Credit: software implementation of given task, creation of programmer and user documentation
Exam: written test (score atl least 50%), supplementary questions
Notice:
The dates and form of verification of compliance with the requirements may be adjusted with regard to the measures announced in connection with the development of the epidemiological situation in the Czech Republic.
|
Content
|
1. Complexity of algorithms - revision and extension of knowledge. Abstract data types
2. Searching and sorting algorithm - medians, quantils, bucket sort, radix sort, comparison of sorting algorithms
3. Data structures I - stack, queue, list, dictionary, inverted list
4. Data structures II - balanced searching trees (AVL, Red-Black, B), hash tables, graphs, sets
5. Graph algorithms - shortest path (Dijkstra, Floyd-Warshall), minimum spanning tree (Prim-Jarnik, Kruskal), bipartite graphs
6. Sets algorithms - generating of permutations and subsets
7. Text algorithms - string agreement, aproximate agreement, shortest and longest common subsequence
8. Data compression I - lossless algorithms (RLE, LZW, Huffman, arithmetic coding)
9. Data compression II - lossy methods (JPEG, wavelet compression, fractal compression
10. Cryptography - introduction, basic algorithms.
11. Programmer practice - using suitable data structures,effect of cache on program running, effect of floating point implementation of real numbers on calculation
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
-
Basic:
Töpfer, Pavel. Algoritmy a programovací techniky. 1. vyd. Praha : Prometheus, 1995. ISBN 80-85849-83-6.
-
Basic:
Cormen, Thomas H. Introduction to algorithms. MIT Press, 2009. ISBN 978-0262033848.
-
Recommended:
Sedgewick, Robert. Algorithms in Java. Pts. 1-4, Fundamentals, data structures, sorting, searching. 3rd ed. Boston : Addison-Wesley, 2003. ISBN 0-201-36120-5.
-
Recommended:
Goodrich, Michael T.; Tamassia, Roberto. Data structures and algorithms in Java. John Wiley & Sons, 2005. ISBN 0-471-73884-0.
-
Recommended:
McConnell, Steve. Dokonalý kód : umění programování a techniky tvorby software. Vyd. 1. Brno : Computer Press, 2005. ISBN 80-251-0849-X.
-
Recommended:
Skiena, Steven S. The algorithm design manual. 2nd ed. New York : Springer, 2008. ISBN 978-1-848-00-069-.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
65
|
Preparation for an examination (30-60)
|
40
|
Undergraduate study programme term essay (20-40)
|
30
|
Total
|
135
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
algorithmize simple problems |
programming in one of the basic programming languages (Java,C,Pascal) |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
analyze a simple task |
create a simple program in a basic programming language |
write and debug a simple program in the development environment for given language
|
create user and programmer documentation for that program |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
analyze the problem and choose appropriate data structures and algorithms |
use and implement basic data structures used in informatics (stack, queue, search trees, dictionaries, hash tables, sets, graphs) |
use and implement basic sorting and searching algorithms and graph algorithms (shortest path, minimum spanning tree, network flows) |
use and implement text processing algorithms, combinatorial algorithms, and data compression algorithms |
to enumerate and explain the basic cryptographic algorithms |
Skills - skills resulting from the course: |
analyze the problem and choose appropriate data structures and algorithms |
create a program in one of the basic programming languages |
create user and programmer documentation for the problem |
evaluate the solution of the problem, eventually, suggest possible modifications of the solved problem that could not be realized |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Written exam |
Seminar work |
Skills - skills achieved by taking this course are verified by the following means: |
Written exam |
Skills demonstration during practicum |
Seminar work |
Competences - competence achieved by taking this course are verified by the following means: |
Skills demonstration during practicum |
Seminar work |
Individual presentation at a seminar |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Practicum |
Skills - the following training methods are used to achieve the required skills: |
Practicum |
Individual study |
Competences - the following training methods are used to achieve the required competences: |
Practicum |
Individual study |
|
|
|
|