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

    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: 2022. augusztus 24.

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

    Course ID Semester Assessment Credit Tantárgyfélév
    VISZAA08 2 2/2/0/f 5  
    3. Course coordinator and department Dr. Katona Gyula,
    Web page of the course
    4. Instructors Dr Attila Sali, associate professor, Department of Computer Science and Information Theory
    5. Required knowledge graph theory, high school mathematics
    6. Pre-requisites

    (TárgyTeljesítve_Képzésen("BMEVISZAA04") VAGY
    TárgyTeljesítve_Képzésen("BMEVISZAA01") VAGY
    Felvetel("BMEVISZAA04") )


    NEM ( TárgyTeljesítve_Képzésen("BMEVISZAB03") )


    ( Kepzes("5N-A8") VAGY

    VAGY EgyenCsoportTagja("Kreditpótlás_2023/24/2 ")

    TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
    TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
    (TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
    TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))


    TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
    TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
    (TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
    TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))

    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
    (K1) Knowledge level:
    recalling, listing and superficially presenting the concepts of the topic.

    (K2) Level of understanding:
    knowledge of explanations, connections, recognition and classification of cases.

    (K3) Application level:
    applying knowledge of problem solving, solving examples and tasks independently.

    (K4) Construction level:
    problem analysis, setting up alternative solutions, comparison, choice, justification.
    8. Synopsis
    1. Minimum and maximum search in n-1 steps, selection sort, order of magnitude of functions, Ordo notation, solving simple recursion equations, merge sort.
    2. Comparison based sorting and their analysis (bubble, insertion, merge, quick sort). Lower bounds for the number of comparisons needed. Non-comparison-based sorts and their analysis: bin sort, radix sort.
    3. Representation of graphs with a matrix or edge list, the number of steps of basic operations in graphs, depth-first search, directed-acyclic graphs (DAG), their recognition.
    4. Finding a topological order, shortest and longest path in DAG
    5. Dynamic programming, knapsack problem, maximum sum interval
    6. The Dijkstra algorithm and proof of its correctness
    7. Data structures: binary tree and its traversals, heap, Dijsktra algorithm with heap

    8. Binary search tree, red-black tree, 2-3-tree, B-tree
    9. Bucket hashing, hash with open addressing
    10. Kruskal implementation details, number of steps, Prim algorithm
    11. Decision problems, efficient witness, definitions of problem classes P, NP, coNP and their relationship

    12. The Karp reduction and its properties, NP-completeness, examples of NP-complete problems
    13. Approximation algorithms, epsilon approximation, bin packing, FirstFit algorithm, FirstFitDecreasing algorithm, traveling salesman problem: in general and the Euclidean version, branch-and-bound
    9. Method of instruction 2 hours lecture, 2 hours problem solving
    10. Assessment During the semester, we have 2 midterms. For completing the semester: at least 40% performance in both midterms. The final grade (if completed) is determined by the average of the mindterm results.
    11. Recaps
    During the semester, there will be a possibility to retake both midterms.
    During the make-up week, there will be only one time when one of the midterms can retaken again.
    13. References, textbooks and resources By appointment.
    14. Required learning hours and assignment
    In class56
    Preparation for classes28
    Preparation for midterm24
    Reading assignment14
    Preparation for final
    15. Syllabus prepared by
    dr. Judit Csima  associate professor SZIT 
    dr. Katalin Friedl  associate professor SZIT
    dr. Gyula Katona  associate professor SZIT