|
|
Main menu for Browse IS/STAG
Course info
KIV / PPA2E
:
Course description
Department/Unit / Abbreviation
|
KIV
/
PPA2E
|
Academic Year
|
2024/2025
|
Academic Year
|
2024/2025
|
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
|
English
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
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
|
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/DB2 and KIV/PPA2
|
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 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 |
to understand primitive data types used in Java |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
to perform basic mathematical derivations and calculations |
to construct simple programs in Java
|
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: |
to interpret statements on problem complexity, to understand statements on complexity classes P, NP and NP-C |
to describe the means of performing a Java program, in particular regarding the memory allocation on the heap and construction of stack frames |
to determine the complexity of operations on particular implementations of abstract data structures, in particular of the standard implementations in the Java class libraries |
to interpret statements on algorithm complexity and complexity classes O, Theta and Omega
|
to name and describe the most commonly used data types, their possible implementations and their implied properties |
to name and describe the most commonly used sorting algorithms and to analyze their properties |
Skills - skills resulting from the course: |
to analyze and to compare algorithms in terms of their computational and memory complexity |
to construct advanced data structures according for particular problems, with focus on choosing a proper and efficient abstract data structure and its implementation |
to implement advanced algorithms to process dynamic data structures |
to implement basic graph processing algorithms, i.e. breadth first search, depth first search and topological ordering |
to implement basic tree data structure processing algorithms, i.e. preorder, inorder and postorder traversal |
to implement programs in Java using basic principles of object oriented programming |
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 |
|
|
|
|