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: 2015. december 4.

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

    Software Engineering

    BSc

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAB01 4 2/2/0/v 4  
    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