BME VIK - Algoritmuselmélet

A tantárgy neve magyarul / Name of the subject in Hungarian: Algoritmuselmélet

3. Course coordinator and department Dr. Friedl Katalin,

Web page of the course www.cs.bme.hu/thalg

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

6. Pre-requisites

Kötelező:

(TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1
VAGY TárgyEredmény( "BMEVISZAA04" , "aláírás" , _ ) = -1)

ÉS
NEM ( TárgyEredmény( "BMEVISZA213" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZA213", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAB03" , "jegy" , _ ) >= 2
VAGY
TárgyEredmény("BMEVISZAB03", "FELVETEL", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAB03" , "aláírás" , _ ) = -1)

A fenti forma a Neptun sajátja, ezen technikai okokból nem változtattunk.

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

7. Objectives, learning outcomes and obtained knowledge To learn the basic methods and skills in the design and analysis of algorithms. To study the most important models of computations.

8. Synopsis

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.

9. Method of instruction 2 hours lecture, 2 hours problem solving

10. Assessment

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%.

11. Recaps There are 2 possibilities to retake the midterm and also the final.

12. Consultations By appointment.

13. References, textbooks and resources

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

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

14. Required learning hours and assignment

In class	56
Preparation for classes	28
Preparation for midterm	10
Homework
Reading assignment
Preparation for final	26
Total	120

15. Syllabus prepared by

Dr. Katalin Friedl, associate professor

Department of Computer Science and Information Theory