General Schedule of Academic Year

The following table summarizes the main administrative issues you have to cope with (When and Where you are supposed to do What).

Winter Term

when	what	where
September	enrollment (as soon as you come to Prague)	Student Office
October - mid January	winter term
mid October	registration of courses for winter term	Student information System (SIS) and Student Office
mid October	enrollment ceremony	Karolinum
mid November	2nd year students - registration for master topic	SIS
December	Christmas Holidays (cca 2 weeks)
mid January - mid February	winter exam session

Summer Term

when	what	where
end of February - end of May	summer term
mid March	registration of courses for summer term	SIS and Student Office
mid April	2nd year students - submission of the thesis (regular term)	department secretariat
end of April	2nd year students who have submitted their theses - completion of courses (all the study requirements must be fulfilled)
	final checking of passed courses	Student Office
	registration for state exams	SIS
mid May - mid June	2nd year students - thesis defense + final stat exams (regular term)
end of May - June	1st year students and those 2nd year students who have not submitted their theses - summer exam session
beginning of July	Closing ceremony (regular term)	Karolinum
July - August	summer holidays
beginning of August	2nd year students - submission of the thesis (2nd regular term)	department secretariat
	completion of courses for those who have submitted their theses (all the study requirements must be fulfilled)
	final checking of passed courses	Student Office
	registration for state exams	SIS
September	thesis defense + final stat exams (2nd regular term)
end of September	1st year students - completion of courses final checking of passed courses	Student Office
end of September	end of academic year
beginning of December	Closing ceremony (2nd regular term)	Karolinum

Late term for the thesis submission and defense

when	what	where
beginning of December	2nd year students - submission of the thesis (2nd regular term)	department secretariat
	completion of courses for those who have submitted their theses (all the study requirements must be fulfilled)
	final checking of passed courses	Student Office
	registration for state exams	SIS
end of January - mid February	thesis defense + final stat exams (late term)

Ph.D. application

when	what	where
end of April	Ph.D. application	SIS
mid June	Ph.D entrance examination

---

Requirements for Final State Exams

There are three obligatory areas (1-3) for Final State Exams ; in addition, students choose two areas from 4-6:

1. Complexity and computability
2. Data Structures
3. Fundamentals of Natural Language Processing
4. Statistical Methods and Machine Learning in Computational Linguistics
5. Applications in Natural Language Processing
6. Linguistic Theories and Formalisms

Requirements for Final State Exams in Detail

1. Complexity and Computability

Algorithm design methods: divide and conquer, dynamic programming, greedy algorithm. Lower bound for complexity of sorting algorithms (decision trees). Amortized complexity. Complete problems for the NP class. Cook-Levin theorem. Pseudopolynomial algorithms, strong NP-completeness. Approximation algorithms and schemes. Algorithmically enumerable functions, their properties, equivalence of their various mathematical definitions. Partially recursive functions. Recursive and recursively enumerable sets and their properties. Algorithmically undecidable problems (halting problem). Recursion theorems and their applications: examples, Rice's theorem.

Covered by courses: NTIN090 Introduction to Complexity and Computability Theory

2. Data Structures

Tree search structures: binary search trees and their balancing, heaps, trie, B-trees and their variants. Hashing: collision handling, universal hashing, perfect hashing. Possibilities of dynamization of the individual data structures. Mapping data structures into pages of the computer's external memory, time complexity of algorithms expressed as number of I/O operations. Sorting in internal and external memory.

Covered by courses: NTIN066 Data Structures I, NTIN067 Data Structures II

3. Fundamentals of Natural Language Processing

Fundamentals of general linguistics (basic linguistic terms and concepts, structural linguistics, language typology, function and form). System of layers in language description (phonetics, phonology, morphology, surface/deep syntax, semantics, pragmatics). Dependency syntax, formal definition of dependency trees, their characteristics (dependency relation, coordination, projectivity). Chomsky hierarchy of languages, context free languages, phrase grammars for a natural language. Design and evaluation of linguistics experiments, evaluation metrics (precision, recall, f-measure, statistical significance etc.) Basic stochastic methods (generative, discriminative; source-channel model; HMM). Language modeling, basic methods for training stochastic models (maximal likehood, EM). Basic algorithms (Trellis, Viterbi, Baum-Welch).

Covered by courses: NPFL063 Introduction to general linguistics, NPFL067 Statistical methods in Natural Language Processing I

4. Statistical Methods and Machine Learning in Computational Linguistics

Generative and discriminative models. Language data for machine learning. Language models. Smoothing of models. Noisy channel models, decoding. Model parameters, space of hypotheses. Theoretical aspects of machine learning (PAC). Supervised machine learning (Naive Bayes, Maximal Entropy, SVN, perceptron, decision trees, logistic regression, Bayesian Networks). Unsupervised machine learning methods (clustering, expectation-maximization). HMM, Viterbi. Tests of significance, intervals for reliability. Statistical parsing algorithms (PCFG, MST).

Covered by courses: NPFL067 Statistical methods in Natural Language Processing I, NPFL068 Statistical methods in Natural Language Processing II, NPFL054 Introduction to Machine Learning (in Computational Linguistics), NPFL070 Language Data Resources

5. Applications in Natural Language Processing

Processing morphology (morphological categories, tagset; analysis, tagging, lemmatization, segmentation, generating, algorithms). Syntactic analysis (surface, deep, dependency, phrase-based syntax, algorithms). Natural language generation. Speech analysis and synthesis. Information retrieval, summarization. Spell-checking and grammar-checking. Machine translation (direct translation, transfer, interlingua; systems for Czech, machine aided translation, statistical methods: IBM models, phrase-based models, hierarchical models, syntactic models).

Covered by courses: NPFL093 NLP Applications, NPFL094 Morphological and Syntactic Analysis, NPFL087 Statistical Machine Translation, NPFL038 Fundamentals of Speech Recognition

6. Linguistic Theories and Formalisms

Functional Generative Description (basic characteristics, system of layers, theory of valency, language meaning), comparison with other dependency-based theories (e.g., MTT). Government and binding (nativism, X-bar, movement, trace, binding). Other basic grammar formalisms (unification-based grammars, feature structures, HPSG, LFG, categorial grammars, TAG). Formal semantics. Language corpora and linguistic annotation (data resources, corpus typology). Computer lexicography (types of lexicons, wordnets, ontologies). Topic-focus articulation. Anaphora. Discourse.

Covered by courses: NPFL063 Introduction to General Linguistics, NPFL083Linguistic Theories and Grammar Formalisms, NPFL075 Prague Dependency Treebank, NPFL070 Language Data Resources, NPFL082 Information Structure of Sentence and Discourse Structure