# General Information

#### Programme Coordinator: doc. RNDr. Ondřej Čepek, Ph.D.

#### Study specializations

The Bachelor of Computer Science programme has a common first year of study and is divided into six specializations starting in the second year of study:

**–**General Computer Science**–**Programming and Software Development**–**Systems Programming**–**Databases and Web**–**Artificial Intelligence**–**Computer Graphics, Vision and Game Development.

Students select their specialization during the second year of their study in accordance with the study regulations. Please note that some specializations might not be offered; in 2020/2021 we currently plan to offer General Computer Science, Databases and Web, and Artificial Intelligence.

#### Degree plans

The course of study in the individual specializations is regulated by the relevant degree plan, which specifies the obligatory and elective courses, the requirements for the State Final Exam, and a recommended course of study. The elective courses are in each specialization divided into several groups. A minimum number of credits should be obtained from elective courses overall; in addition, a minimum total number of credits is also required for certain groups of elective courses. Besides obligatory courses and the required number of elective courses, each student may sign up for additional courses taught at our faculty or at other faculties of Charles University (these are called ``optional courses").

All six specializations share a large part in common, containing obligatory courses that cover the foundations of mathematics, theoretical computer science, programming, and software systems. Most of these subjects are recommended for the first year in the entire Computer Science programme. The recommended course of study for the first year specified below consists of obligatory courses (in boldface) and several optional courses (in italics). Of course, other optional courses may be selected instead of those that are recommended, provided that a total of at least 60 credits is achieved within the first academic year.

#### Recommended course of study for the first year

Code | Subject | Credits | Winter | Summer | |

NPRG062 | Introduction to Algorithms | 4 | 2/1 C+Ex | — | |

NPRG030 | Programming 1 | 5 | 2/2 C | — | |

NSWI120 | Principles of Computers | 3 | 2/0 Ex | — | |

NSWI141 | Introduction to Networking | 3 | 2/0 MC | — | |

NDMI002 | Discrete Mathematics | 5 | 2/2 C+Ex | — | |

NMAI057 | Linear Algebra 1 | 5 | 2/2 C+Ex | — | |

NMAI069 | Mathematical skills | ^{1} | 2 | 0/2 C | — |

NTVY014 | Physical Education I | ^{2} | 1 | 0/2 C | — |

ASE500129 | Czech Language Course 1 | ^{3} | 3 | 0/2 C | — |

NTIN060 | Algorithms and Data Structures 1 | 5 | — | 2/2 C+Ex | |

NPRG031 | Programming 2 | 5 | — | 2/2 C+Ex | |

NSWI170 | Computer Systems | 5 | — | 2/2 C+Ex | |

NSWI177 | Introduction to Linux | 4 | — | 1/2 MC | |

NMAI054 | Mathematical Analysis 1 | 5 | — | 2/2 C+Ex | |

NMAI058 | Linear Algebra 2 | 5 | — | 2/2 C+Ex | |

NTVY015 | Physical Education II | ^{2} | 1 | — | 0/2 C |

ASE500130 | Czech Language Course 2 | ^{3} | 3 | — | 0/2 C |

^{1} The course NMAI069 Mathematical Skills is designed for students who
wish to gain and practice the fundamental mathematical skills needed for the more mathematically oriented courses given at our faculty. Emphasis is put on the ability to use
precise and correct mathematical formulations and on basic proof techniques.

^{2} The Physical Education courses are obligatory for students on
the programme taught in Czech, while they are elective for students on
the programme taught in English. If you like sports, this may be a course
for you, but there is no obligation to take it.

^{3} The Czech Language Courses are optional, offered as a counterpart
to the elective English Language Courses recommended for students studying in the programme taught in Czech. Since these courses are elective, they may naturally be replaced by any
other course while maintaining the minimum of 30 credits per semester.

Some obligatory courses common to all specializations are taught in the second and third year of study. They are listed below.

#### Common obligatory courses in the second and third year of study

Code | Subject | Credits | Winter | Summer | |

NTIX061 | Algorithms and Data Structures 2 | 5 | 2/2 C+Ex | — | |

NDBX025 | Database Systems | 5 | 2/2 C+Ex | — | |

NDMX011 | Combinatorics and Graph Theory 1 | 5 | 2/2 C+Ex | — | |

NAIX062 | Propositional and Predicate Logic | 5 | 2/2 C+Ex | — | |

NTIX071 | Automata and Grammars | 5 | — | 2/2 C+Ex | |

NMAX059 | Probability and Statistics 1 | 5 | — | 2/2 C+Ex | |

NPRG045 | Individual Software Project | ^{4} | 4 | — | 0/1 C |

NSZZ031 | Bachelor Thesis | 6 | — | 0/4 C |

^{4} It is possible to sign up for the course NPRG045 both in the winter semester
and in the summer semester; the standard period is the summer semester.

Each individual specialization requires additional obligatory courses and groups of elective courses. A detailed degree plan for each specialization is given later in this text.

#### Recommended course of study for the second and third year

The recommended course of study is prepared for each specialization in such a way that the obligatory courses are scheduled in the required order, the student obtains in time the credits needed for enrolment in the next year of study, and the student fulfils in time all the prerequisites needed in order to take the State Final Exam. A recommended course of study for each specialization is given later in this text.

#### Branches within specializations

Some specializations are further divided into branches. Individual branches within the same specialization differ only in one area of prerequisites for the State Final Exam. Students should adjust their choice of elective and optional courses according to the branch in which they intend to take the State Final Exam. The choice of a particular branch within the student's specialization is declared only when signing up for the State Final Exam.

#### State Final Exam

The State Final Exam consists of two parts:

**–**Defence of Bachelor Thesis**–**Exam in Mathematics and Computer Science

Each part of the State Final Exam is graded. The final grade for the State Final Exam is determined by the grades obtained for each part. The student can sign up for each part of the State Final Exam separately. Bachelor studies are successfully concluded only upon passing both parts of the State Final Exam. In case of failure, the student retakes those parts of the State Final Exam which he or she failed. Each part of the State Final Exam can be retaken at most twice.

Necessary conditions for signing up for either part of the State Final Exam are the following:**–**passing all the obligatory courses of a given specialization,**–**obtaining the required number of credits for elective courses,**–**submitting a completed bachelor thesis by the specified deadline (necessary for signing up for the bachelor thesis defence),**–**obtaining at least 180 credits (necessary for signing up for the last part of the State Final Exam).

A bachelor thesis topic is typically assigned at the beginning of the third year. The bachelor thesis usually consists of either a software package, which may be a continuation of the Individual Software Project (see degree plans above), or a piece of theoretical work. We recommend choosing a topic offered by the department which is connected with the selected specialization. In case another topic (offered by another department or suggested by the student) is to be selected, we strongly recommend consulting the relevant Specialization Coordinator before doing so.

The prerequisites for the State Final Exam are divided into two parts, one common to all specializations and the other specific to the given specialization. The list of common prerequisites is given below this paragraph; the prerequisites specific to the various specializations are listed after their degree plans given further below.

*Knowledge requirements for the State Final Exam common to all specializations*

#### Mathematics

**1. Fundamentals of Differential and Integral Calculus**

Sequences and series of numbers and their properties (properties of limits and sums,
convergence criteria). Real functions of one variable. Continuity, limit of a function
(ordinary, infinite). Derivatives: definition and basic rules. Applications
(examination of behaviour of functions, Taylor polynomial with remainder). Antiderivatives (primitive
functions): definition, uniqueness, existence, methods of calculation.

**2. Algebra and Linear Algebra**

Groups and subgroups, definitions, examples, commutativity. Fields – definition,
characterization of a field, finite fields. Vector spaces and subspaces, properties,
basic notions (linear combination, linear span/ hull, generators, linear dependence and
independence, basis, dimension, coordinates) and uses. Practical ability in testing
for linear dependence and independence, finding a basis, determining the dimension etc.
Scalar product and its properties. Norm and its relation to scalar product, examples.
Orthogonality, othonormal basis, properties and uses (e.g. finding coordinates, projection). Systems of linear equations and sets of solutions. Solution
methods, Gauss and Gauss–Jordan elimination, reduced row echelon form of a matrix and uniqueness
(without proof). Matrices, operations with matrices (addition, multiplication,
transposition, etc.), interpretation of matrix multiplication as composition of linear
mappings. Matrix rank, rank of a transposition. Eigenvalues and eigenvectors of a matrix,
geometric meaning and properties, spectral radius. Characteristic polynomial,
relationship between eigenvalues and roots of polynomials.

**3. Discrete Mathematics**

Relations, properties of binary relations (reflexivity, symmetry, antisymmetry,
transitivity). Equivalence relations and partition into equivalence classes. Partial orders, basic concepts
(minimal and maximal elements, minimum and maximum elements, chains, antichains),
height and width of a partially ordered set and their mutual relationship.
Functions, types of functions (injective, surjective, bijective) and the number of
functions between two finite sets of a given type. Permutations and their basic
properties (number of permutations, fixed points, etc.). Binomial coefficients and relationships between them, binomial theorem and its applications. Principle of inclusion and exclusion, general formulation (and proof), applications (Euler's totient function, number of surjections, etc.).
Hall's theorem on systems of
distinct representatives (SDR) and its relation to matchings in a bipartite graph, principle of proof and algorithmic consequences (polynomial-time algorithm for finding an SDR).

**4. Graph Theory**

Basic concepts (graph, vertices and edges, graph isomorphism, subgraph, vertex
neighbourhood and vertex degree, graph complement, bipartite graph), basic examples of graphs
(complete graph, complete bipartite graph, paths, cycles). Connected graphs, connected
components, distance in a graph. Trees: definition and basic properties (existence of
leaves, number of edges), equivalent characterizations of trees. Planar graphs:
definition and basic concepts (planar graph and plane drawing of a graph, faces), Euler's
formula and the maximum number of edges in a planar graph (proof and applications).
Graph colourings: definition of a proper colouring, relation between chromatic number and clique
number. Edge- and vertex-connectivity, edge and vertex version of Menger's
theorem. Directed graphs: weak and strong connectivity. Network flows: definition of
a network and of a flow, existence of a maximum flow (without proof), basic principle
of finding a maximum flow in a network with integer-valued capacities (e.g. using the
Ford–Fulkerson algorithm).

**5. Probability and Statistics**

Random events, conditional probability, independence of random events – definitions
of these terms, Bayes' formula, applications. Random variables, mean (expectation),
distribution of random variables, geometric, binomial and normal distribution.
Linear combination of random variables – linearity of expectation, applications.
Point estimates, confidence intervals, hypothesis testing.

**6. Logic**

Syntax – knowledge of and working with the basic syntax of propositional and predicate logic
(language, open and closed formulas, etc.). Normal forms of propositional formulas,
prenex normal forms of predicate logic formulas – knowledge of basic normal forms (CNF, DNF, PNF),
converting to normal form, applications in algorithms (SAT, resolution). Semantics,
truth, falsity, independence of a formula with respect to a theory,
satisfiability, tautologies, logical consequence, the notion of a model of a theory,
extensions of theories.

#### Computer Science

**1. Automata and Languages**

Regular languages: finite automaton, language accepted by a finite automaton,
deterministic, nondeterministic, epsilon transitions, regular expressions, Kleene's
theorem, iteration (pumping) lemma for finite automata, regular grammars. Context-free
languages: context-free grammar, language generated by a grammar, push-down automaton,
class of languages accepted by push-down automata. Turing machine: type 0 grammar,
diagonal language, universal language. Chomsky hierarchy: determination of equivalence
or inclusion between classes of languages generated by the automata and
grammars mentioned above. Classifying a given language in the Chomsky hierarchy
(typically by constructing an appropriate automaton or grammar and proving that the
language does not belong to a lower class using an iteration lemma).

** 2. Algorithms and Data Structures **

Time complexity of algorithms: time and space needed for computation on a given input,
time and space complexity of an algorithm, data size measurement, complexity in the worst,
best and average case, asymptotic notation. Complexity classes: P and NP,
problem reducibility, NP-hardness and NP-completeness, examples of NP-complete problems
and reductions among them. ``Divide and conquer" technique: recursive division of
a problem into subproblems, complexity computation using recursive equations, master
theorem, applications (Merge sort, multiplication of long numbers, Strassen's algorithm).
Binary search trees: definition of a search tree, operations with non-balanced trees,
AVL trees (definition only). Heaps: binary heap. Hashing: hashing with buckets, open
addressing. Sorting: primitive sorting algorithm (Bubble sort, Insertion sort etc.), Heapsort,
Quicksort, lower bound for sorting based on pairwise comparisons, bucket sorting for
numbers and strings. Graph algorithms: depth-first search and breadth-first search,
connected component detection, topological sorting of directed graphs, shortest paths
in weighted graphs (Dijkstra's algorithm, Bellman–Ford algorithm), minimum spanning trees
(Jarník's algorithm, Borůvka's algorithm), network flows (Ford–Fulkerson algorithm). Algebraic
algorithms: Euclid's algorithm.

**3. Programming Languages**

Concepts and principles of object-oriented design: classes, interfaces, methods,
attributes, inheritance (visibility of members, namespaces, separation into
packages/modules), multiple inheritance and its problems (language-specific methods for
resolving problems, multiple and virtual inheritance in C++, single inheritance and
default methods in Java), implementing interfaces, polymorphism (static vs. dynamic
polymorphism), functional elements of object-oriented languages (function objects,
lambdas, support in standard libraries). Implementation of object-oriented languages:
basic object-oriented concepts in a concrete language (Java, C++, C#), primitive types
vs. objects (implementation of primitive types, memory representation of compound types
and objects), implementation of virtual methods (virtual method tables), lifetime of
objects (allocating and initializing objects (statically, on the stack, on the heap),
constructors, calling inherited constructors, freeing objects, explicit delete/dispose,
garbage collection, automatically freeing objects, shared_ptr/unique_ptr, destructors,
finalizers), threads and synchronization (implementing threads, basic synchronization
constructs, data types with atomic operations), debugging, exceptions (throwing and
catching exceptions (try-catch-finally), working with resources: try-with-resources
(Java), RAII (C++), using (C#)). Separate compilation, linking, compiler directives:
compilation vs. interpreting, role of linking, JIT.

**4. Computer Architecture and Operating Systems**

Data representation: encoding and layout in memory, bitwise operations and their
usage. Computer organization: von Neumann and Harvard architectures, computer
memory, secondary storage, address spaces, input/output devices. Instruction set
architectures: computer instructions, high-level programming-language constructs
and their representation using computer instructions, basic notion of a shared-memory
multi-processor. Operating systems: computer and OS initialization, OS kernel, device
drivers, privileged and non-privileged code execution, programming interfaces, OS shell
environment, user management. Hardware/software interface: device drivers and driver
stack, interrupt and exceptions at CPU, OS, and programming language level. Processes
and threads: process and thread contexts, process hierarchy, cooperative and preemptive
multitasking, scheduling, thread states, active and passive waiting. Race conditions,
critical section, mutual exclusion, synchronization primitives, the notions of deadlock
and livelock. File and socket APIs, file descriptors, accessing devices as files,
standard input and output and their redirection, interprocess communication via pipes.