|
|
Main menu for Browse IS/STAG
Course info
KIV / PPA2
:
Course description
Department/Unit / Abbreviation
|
KIV
/
PPA2
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Computers and Programming 2
|
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
|
Czech
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
16 / -
|
0 / -
|
4 / -
|
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
|
10
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
Czech
|
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 |
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
|
KIV/DB2 and KIV/PPA2E
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
KIV/PPA1 and KIV/PPA or KIV/PPA-E
|
Courses depending on this Course
|
KSO/SBZIM
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
To provide students knowledge of fundamentals of data structures and algorithms.
|
Requirements on student
|
Homework assignments, midterm, seminar work and its on-line application.
Deadline for course credit is end of june.
|
Content
|
1. Problem, algorithms, program. Program and programming language. Program execution. Object, class.
2. Linked data structured. Program correctness. Program analysis.
3. Abstract data type. Stack and queue.
4. Linked list. Examples of recursion. Recursive programs.
5. Recursion and stack. Tree, basic concepts. Binary tree. Binary search tree.
6. Graphs and their implementation. Graph search. Topological sort.
7. Direct-address tables. Hash tables. Hash function.
8. Priority queue. Heap. Sort using priority queue.
9. Sorting problem. Heap sort. Shell sort. Quicksort. Mergesort.
10.Generic programming. Inheritance. Interface.
11.Abstract problem. Algorithmically unsolvable problems. Lower bound for sorting.
Classification of problems.
12.NP-complete problems. Satisfiability of logical circuit. Proof of NP-completeness.
13. Examples of practical application of algorithms.
|
Activities
|
|
Fields of study
|
Pro předmět existuje systém opor v LMS Courseware se všemi podstatnými informacemi a materiály
|
Guarantors and lecturers
|
|
Literature
|
-
Basic:
Šafařík, Jiří. Počítače a programování 2. ZČU, 2005.
-
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:
Lafore, Robert. Data structures & algorithms in Java. Corte Madera : Waite Group Press, 1998. ISBN 1-57169-095-6.
-
Recommended:
Cormen, Thomas H. Introduction to algorithms. Cambridge : MIT Press, 2001. ISBN 0-262-03293-7.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Preparation for formative assessments (2-20)
|
8
|
Preparation for an examination (30-60)
|
30
|
Contact hours
|
65
|
Individual project (40)
|
40
|
Total
|
143
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
to understand primitive data types used in Java |
to demonstrate knowledge of basic math terminology and methods |
to describe basic means of data representation in a computer |
to describe programming principles in imperative programming language, with focus on control flow |
to understand basic imperative control flow in Java |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
to construct simple programs in Java |
to perform basic mathematical derivations and calculations |
to use some common integrated development environment for Java on user level |
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: |
interpretovat výroky o složitosti algoritmů a složitostních třídách O, Theta a Omega |
interpretovat výroky o složitosti problémů, porozumět výrokům o třídách složitosti P, NP a NP-C |
popsat způsob vykonání programu v jazyce Java, zejména z hlediska alokace paměti v zásobníku a na hromadě a vytváření zásobníkových rámců |
určit výpočetní složitost operací nad konkrétními implementacemi abstraktních datových struktur, zejména u standardních implementací v knihovně jazyka Java |
vyjmenovat a popsat nejpoužívanější algoritmy řazení a analyzovat jejich vlastnosti |
vyjmenovat a popsat nejrozšířenější abstraktní datové typy, možnosti jejich implementace a z toho plynoucí vlastnosti |
Skills - skills resulting from the course: |
analyzovat a provnávat algoritmy z hlediska třídy výpočetní a paměťové složitosti |
implementovat programy využívající základní principy objektového programování v jazyce Java |
implementovat složitější algoritmy zpracovávající dynamické datové struktury |
implementovat základní algoritmy zpracování grafů, tj. prohledávání do šířky a do hloubky a topologické řazení |
implementovat základní algoritmy zpracování stromových datových struktur, tj. preorder, inorder a postorder procházení |
vytvářet složitější datové struktury podle konkrétních zadání, zejména s ohledem na volbu vhodné a efektivní abstraktní datové struktury a její implementace |
Competences - competences resulting from the course: |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Continuous assessment |
Written exam |
Test |
Seminar work |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Individual study |
Lecture with visual aids |
Lecture supplemented with a discussion |
Practicum |
E-learning |
|
|
|
|