Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

Dr Attila Sali, associate professor, Department of Computer Science and Information Theory

A kötelező előtanulmányi rend az adott szak honlapján és képzési programjában található.

To learn the basic methods and skills in the design and analysis of algorithms. To study the most important models of computations.

Pattern matching: naive algorithm, the fingerprinting method of Rabin and Karp, solution by finite automata.

Deterministic and non-deterministic finite automata and their equivalence. Regular expressions, regular languages, and their connections to finite automata. Finite automaton as lexical analyser.

Context free grammars. Parse tree, left and right derivation. Ambiguous words, grammars, languages. The importance of unambiguous grammars for algorithms.

Pushdown automaton. Connection between pushdown automata and context free grammars, how to get a PDA from a CF grammar. The main task of a parser.

The general automaton: Turing machine.  Church-Turing thesis. The classes  P, NP, coNP, their relations. Karp reduction and the notion of NP completeness.

Theorem of Cook and Levin. 3SAT, 3COLOR are NP complete languages.

Further NP complete languages: MAXSTABLE, HAM-CYCLE, HAM-PATH, TSP,  3DH, SUBSETSUM, PARTITION, KNAPSACK, SUBGRAPHISO. The problem of GRAPHISO.

 Linear and integer programming. LP is in P (without proof), IP is in NP. LP and IP as algorithmic tools, translation of combinatorial problems to integer programming. Another tool: branch and bound.

Dynamical programming (example: knapsack, longest common substring).

 The objective in approximation algorithms. Bin packing has fast and good approximations (FF, FFD, theorem of Ibarra and Kim). Fro the TSP even the approximation s hard in general but there is efficient 2-approximation in the euclidean case.

Comparison based sorting: bubble sort, insertion sort, merge sort, quick sort. Lower bound for the number of comparisons. Other sorting methods: counting sort, bin sort, radix sort.

 Linear and binary search. The binary search is optimal in the number of comparisons. Notion of search tree, their properties and analysis.

Red-black tree as a balanced search tree. The 2-3 tree, and its generalization, the B tree. Comparisons of the different data structures.

2 hours lecture, 2 hours problem solving

There is a midterm and a final. Both must be at least 40%.

In the final grade the midterm counts as 40% and the final as 60%

There are 2 possibilities to retake the midterm.

By appointment.

T.Corman, C.Leiserson, R.Rivest, C.Stein: Introduction to Algorithms (MIT Press)

M.Sipser: Introduction to the Theory of Computing (Thomson)

Dr. Katalin Friedl, associate professor

Department of Computer Science and Information Theory