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

    Belépés
    címtáras azonosítással

    vissza a tantárgylistához   nyomtatható verzió    

    Theory of Algorithms

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

    Last updated: 2017. június 22.

    Budapest University of Technology and Economics
    Faculty of Electrical Engineering and Informatics
    Software Engineering, BSc
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAB03   2/2/0/v 5  
    3. Course coordinator and department Dr. Friedl Katalin,
    Web page of the course 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( "BMEVISZAB01" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZAB01", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZAB01" , "aláírás" , _ ) = -1)

    ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))

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

    A kötelező előtanulmányi rendek grafikus formában itt láthatók.

    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.

    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
    Kontakt óra56
    Félévközi készülés órákra28
    Felkészülés zárthelyire18
    Házi feladat elkészítése 
    Kijelölt írásos tananyag elsajátítása0
    Vizsgafelkészülés48
    Összesen150
    15. Syllabus prepared by

    Dr. Katalin Friedl, associate professor

    Department of Computer Science and Information Theory