Y'all,

So a minap kellett nekem egy Szamelm tetelsor, amit angolul nem talaltam, ezert keszitettem magamnak egyet a CS tanszek honlapjan karbantartott alapjan. Ugy gondoltam kozkincse tesztem, tovabb utan a LaTeX text belinkelve simple as that; lehet kikezdeni. Amugy az eredmeny az, hogy reszemrol a Computability and Algorithms class requirement waived :)

\documentclass[a4paper,10pt]{report}

% Title Page
\title{Computability and Algorithms Syllabus}
\author{Daniel Komaromy}

\begin{document}
\maketitle

\begin{abstract}
\end{abstract}

\begin{enumerate}
 \item \textbf{Set theory:} binary operations on sets, Cantor-Bernstein-Schroeder Theorem; Cardinality of infinite sets, countably infinite and uncountable sets, cardinality of natural, rational and real numbers, cardinality of power sets, Cantor Theorem, continuum-hypothesis.

\item \textbf{Linear algebra:} Definition, properties and calculation of determinants, Laplace expansion, Multiplication Theorem. Matrices, basic operations. Invertible Matrices, existence criterion, inverse calculation. Rank of a matrix, adjacency and incidence matrices of graphs and their ranks.

\item Systems of linear equations, properties (equivalence, independence, consistency), Gaussian elimination. Coordinate geometry, equation of a plane, equation system of a line, finding the solution sets for intersections.

\item Vector spaces: definition, examples. Linear combinations, Subspaces, generated subspaces. Linear independence. Definition of base and dimension of vector spaces.

\item Linear transformations: examples, matrix representations. Product of linear mappings. Kernel, Image subspaces, rank-nullity theorem. Eigenvector, eigenvalue and eigensubspace, calculation.

\item \textbf{Graph Theory:} definitions, types of graphs, isomorphism, subgraphs, spanning subgraph, walk path, cycle, strongly connnected compomnents, trees, spanning trees. Cayley's Theorem.

\item Algorithms for finding minimum spanning-trees. Red-blue algorithm, Prim's algorithm, Kruskal's algorithm, Boruvka's algorithm. Implementation and complexity.

\item Graph search algorithms and their complexities. Breadth-first, depth-first search. Finding shortest paths: Dijkstra's algorithm, Bellman-Ford's algorithm, Floyd's algorithm. Directed and undirected graphs, DAGs, PERT method.

\item Planar graphs, Euler Theorem. Kuratowski Graphs and Kuratowski's Theorem on forbidden graphs, Fary-Wagner Theorem. Dual graphs, Whitney's planarity criterion.

\item Hamilton path and cycle, Euler path and cycle. Complexity of finding Hamilton cycles. Existence criteria, Ore's Theorem, Dirac's Theorem.

\item Graph coloring. $ \chi(G)$, $ \omega(G)$, $ \Delta(G)$, $ \chi_e(G)$ and their relationships. Brook's Theorem. Mycielski construction, coloring interval graphs. Perfect graphs. Chromatic number, edge chromatic number. Complexity of the 3-coloring problem. Vizing's Theorem.

\item Bipartite graphs and matching problems. Hungarian method and its complexity. Konig's Theorem, Hall's Theorem, Frobenius' Theorem.  $ \nu$, $ \tau$ and their relationships, Tutte's Theorem, Gallai's Theorems.

\item Flow networks. Computing maximum  ow and minimal cut: Ford-Fulkerson method. Edmonds-Karp algorithm. Connectivity, Menger's Theorem. Dirac's Theorem.

\item \textbf{Number Theory:} Divisibility, composite and prime numbers. Number of divisors. The infinitude or prime numbers. Congruence, basic operations. Linear congruence equations. Wilson's Theorem. Remainder systems. Euler-Fermat Theorem, Fermat's Little Theorem. Euclidean algorithm.

\item Basic operations and exponentiation modulo m. Primality testing: Fermat-test, Carmichael numbers. Public key cryptography, RSA algorithm.

\item Abstract algebra: operations, groups, abelian groups, subgroups, cyclic groups, dieder groups, symmetric groups. Group isomorphism. Lagrange's Theorem. Rings, fields. Examples. Complex numbers, algebraic and trigonometric form, basic operations, exponentiation, $\sqrt[n]{X}$. Galois Theory.

\item \textbf{Algorithms:} Sorting algorithms and their complexity. Bubble sort, insertion sort, shell short, merge sort. Lower bound for complexity of comparison-based sorting algorithms. Quicksort, bucket sort, radix sort.

\item Data structures: constructions, operations and their complexity. Heaps, heap sort: algorithm and complexity. Binary Search Trees. AVL-trees, red-black trees, 2-3 trees, B-trees: number of levels, operations and their complexity.

\item Hash tables, complexity of operations. Double hashing. Applicability of hash algorithms, in comparison to BSTs.

\item Dynamic Programming: idea, examples from earlier algorithms. Solution for the bounded knapsack problem. Basic approximation algorithms.

\item \textbf{Computability:} Turing Machines (TM). Multi-tape TM definitions. Simulation of multi-tape TM with single-tape TM. Relationship of variations of TMs and the Chomsky-hierarchy. Universtal TM. Church-Turing Theorem.

\item Space and time bound TMs. Space-time Theorem. P, PSPACE, EXPTIME.

\item Non-deterministic TMs, their space and time complexity. NP and coNP, their relationship with P and R. Witness Theorem. Examples of NP and
coNP languages.

\item Reducability. Karp Reduction. NP-Completeness. Cook-Levin Theorem. NP-Completeness of languagues: 3-SAT, 3-Coloring, MAXFTLEN, X3C, H, RH.

\item Recursive and recursively enumerable languages. Relationships of R, RE, coR, coRE classes. Famous problems and their complexity: diagonal language, universal language, halting problem, domino problem. Undecidable problems in the context of CF grammars.

\item Kolmogorov complexity. Definition, invariance theorem, compression, incompressible strings.

\item \textbf{Formal Languages:} Finite automatons, minimal automatons, constructions.

\item Generative grammars and their cardiality, Chomsky hierarchy. Regular languages, closure properties under operations (complement, Kleene star,
concatenation, union, intersection, difference), pumping lemma.

\item CF languages, Chomsky normal form, Greibach normal form, recursions and left recursions. Closure properties of CF languages. Pushdown automatons, their relationship with CF grammars, constructing a pushdown automaton from a CF grammar.

\item Translators. Finite translators, pushdown translators. Closure properties of regular and CF languages for finite translations. Syntax-oriented translators.

\item Lexical analyzers. Top-down parsing, LL(k) parsers, LL(k) grammars and languages.

\item Bottom-up parsing, LR(k) parsers, LR(k) grammars and languages, prefix property languages, their relationship with LR(k) parsers.

\item Precedence parsing: algorithm, precedence grammars, weak precedence grammars. Operator-presedence parsers.
\end{enumerate}

\end{document}