# 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 three specializations starting in the second year of study:

**–**General Computer Science**–**Databases and Web**–**Artificial Intelligence.

Students select their specialization during the second year of their study in accordance with the study regulations.

#### 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 three 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 | |

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

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

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

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

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

NMAI059 | 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. Real functions of one variable.
Continuity, limit of a function. Derivatives: definition and basic rules, behaviour of
functions, Taylor polynomial with remainder. Primitive functions: definition, uniqueness,
existence, methods of calculation.

#### Relevant courses:

**–**Mathematical Analysis 1 (NMAI054)

**2. Algebra and Linear Algebra**

Groups and subgroups, fields. Vector spaces and subspaces. Scalar product, norm.
Orthogonality, othonormal basis. Systems of linear equations, Gauss and Gauss–Jordan elimination.
Matrices, operations with matrices, matrix rank. Eigenvalues and eigenvectors of a matrix.
Characteristic polynomial, relationship between eigenvalues and roots of polynomials.

#### Relevant courses:

**–**Linear Algebra 1 (NMAI057)**–**Linear Algebra 2 (NMAI058)

**3. Discrete Mathematics**

Relations, properties of binary relations. Equivalence relation, equivalence classes.
Partial orders. Functions, types of functions. Permutations and their basic properties.
Binomial coefficients, binomial theorem. Principle of inclusion and exclusion. Hall's theorem
on systems of distinct representatives, matchings in a bipartite graph.

#### Relevant courses:

**–**Discrete Mathematics (NDMI002)**–**Combinatorics and Graph Theory 1 (NDMI011)

**4. Graph Theory**

Basic concepts, basic examples of graphs. Connected graphs, connected components.
Trees, their properties, equivalent characterizations of trees. Planar graphs, Euler's
formula and the maximum number of edges in a planar graph. Graph colourings, chromatic
number and clique number. Edge- and vertex-connectivity, Menger's theorem. Directed
graphs, weak and strong connectivity. Network flows.

#### Relevant courses:

**–**Discrete Mathematics (NDMI002)**–**Combinatorics and Graph Theory 1 (NDMI011)

**5. Probability and Statistics**

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

#### Relevant courses:

**–**Discrete Mathematics (NDMI002)**–**Probability and Statistics 1 (NMAI059)

**6. Logic**

Syntax – language, open and closed formulas. Normal forms of propositional formulas,
prenex forms of predicate logic formulas, 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.

#### Relevant courses:

**–**Propositional and Predicate Logic (NAIL062)

#### Computer Science

**1. Automata and Languages**

Regular languages, finite automaton (deterministic, nondeterministic), Kleene's
theorem, iteration lemma, regular grammars. Context-free languages, push-down automaton,
context-free grammar. Turing machine, type 0 grammar, diagonal language, universal language.
Chomsky hierarchy.

#### Relevant courses:

**–**Automata and Grammars (NTIN071)

** 2. Algorithms and Data Structures **

Time and space complexity of algorithms, asymptotic notation. Complexity classes
P and NP, NP-hardness and NP-completeness. ``Divide and conquer" algorithms, complexity
computation for these algorithms, examples. Binary search trees, AVL trees. Binary heaps.
Hashing with buckets and open addressing. Sorting algorithms. DFS, BFS and their applications.
Shortest paths. Minimum spanning trees. Network flows. Euclid's algorithm.

#### Relevant courses:

**–**Algorithms and Data Structures 1 (NTIN060)**–**Algorithms and Data Structures 2 (NTIN061)

**3. Programming Languages**

Concepts for abstraction, encapsulation, and polymorphism. Primitive and object
types and their representation. Generic types and functional elements. Working
with resources and mechanisms for error handling. Object lifecycle and memory
management. Threads and support for synchronization. Implementation of basic
elements of object-oriented languages. Native and interpreted execution,
compilation and linking.

#### Relevant courses:

**–**Programming 1 (NPRG030)**–**Programming 2 (NPRG031)**–**Principles of Computers (NSWI120)**–**Based on the choice of the programming language: Programming in C# Language (NPRG035) or Programming in C++ (NPRG041) or Programming in Java Language (NPRG013)

**4. Computer Architecture and Operating Systems**

Computer organization, data and program representation. Instruction set architecture
as a hardware/software interface, connection to elements of high-level programming
languages. Support for operating system execution. Peripheral device interface and
handling. Fundamental OS abstractions, interfaces, and mechanisms for program execution,
resource sharing, and input/output. Parallelism, threads and interfaces for thread
management, thread synchronization.

#### Relevant courses:

**–**Principles of Computers (NSWI120)**–**Computer Systems (NSWI170)**–**Introduction to Networking (NSWI141)**–**Introduction to Linux (NSWI177)**–**Based on the choice of the programming language: Programming in C# Language (NPRG035) or Programming in C++ (NPRG041) or Programming in Java Language (NPRG013)