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ó    

    Algorithms and Complexity

    A tantárgy neve magyarul / Name of the subject in Hungarian: Algoritmusok és bonyolultságuk

    Last updated: 2016. július 29.

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

    Engineering Information Technology, MsC

    Theory of Computation, minor specialization
    Course ID Semester Assessment Credit Tantárgyfélév
    VISZMA00 1 2/1/0/f 4  
    3. Course coordinator and department Dr. Friedl Katalin,
    Web page of the course cs.bme.hu/algbony
    4. Instructors

    Dr Csima Judit associate professor Department of Computer Science and Information Theory

    Dr Friedl Katalin  associate professor Department of Computer Science and Information Theory

    Dr Katona Gyula associate professor Department of Computer Science and Information Theory

    5. Required knowledge Basics of algorithms and complexity theory
    6. Pre-requisites
    Kötelező:
    NEM ( TárgyEredmény( "BMEVISZM143" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZM143", "FELVETEL", AktualisFelev()) > 0
    VAGY
    TárgyEredmény( "BMEVISZMA14" , "jegy" , _ ) >= 2
    VAGY
    TárgyEredmény("BMEVISZMA14", "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  In order to improve algorithmical thinking  to learn advanced algorithmical techniques, to see modern techniques, learn the limits of new models (e.g. parallel, ditributed and quantum computation computation). 
    8. Synopsis

    Introduction of selected topics.

    Interactive proofs -- a possible generalization of NP. Strong and weak players,  the AM and IP classes. Probabilistically checkable proofs.

     Communication complexity : computation with minimal information exchange. Connection to the matrix of the function. Nondeterministic complexity and its relation to deterministic complexity. Randomized protcols and their efficiency.

     Geometrical algorithms: computations without division, closest pair of points, efficient convex hull computation .

    Advanced search techniques: k-th element in linear time, computation of rank. How to store intervals

    Pattern matching: KMP and Boyer-Moore algorithms. Pattern matching by finite automaton. Matching with errors, approximate solutions, and the efficient computation of edit distanc.

     Parallel algorithms: variants of the PRAM model. Comparisons for simple cases.  Computations organized in binary trees. The effect of changing the numer of processors (Brent's theorem)

     Parallel algorithms for sorting (Batcher). Prefix sum computation and its applications. Computation of ranks.

    Distributed algorithms: theoretical model. Leader selection algorithms on rings and on general graphs.

    Distributed algorithms whith failers: fails in lines, when processors stop, and byzantine errors.

     Network topologies from graph theoretical point of view: grid, cube, cube connected cycel, butterfly, Benes(shortest paths, diameter, cuts). Embeddings,algorithmical aspects.

     Random graphs: different models, their basic properties (degrees, paths, connectedness). Random graphs as models of networks.

    Parametric complexity: NP-hard problems with efficient solution for small values of a parameter.  Bounding the depth of a search tree.Grpah minor theorem and consequences. The kernel method. W[1] complexity.

    On-line algorithms: measure of effifiency. Examples. Scheduling algorithms.

    Quantum computation:  tools from linear algebra, simple algorithms (teleporting, Deusch-Jozsa). Qunatum Fourier transformation, the idea of prime factorization. Quantum cryptography.

     

    9. Method of instruction Large part is like a seminar, the students present the topic of their own choice. The possibel topics and their order is changing from year to year, depending on interest. We discuss the details on the first class.
    10. Assessment Paticipation in the discussions and giving a presentation.
    12. Consultations by appointment
    13. References, textbooks and resources

    T. Corman, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms

    H. Attiya: Distributed Computing lecture notes

     J. Flum, M. Grohe: Parameterized Complexity Theory, Springer 2006.

    A. Gibbons, W. Rytter: Efficient Parallel Algorithms, Cambridge University Press, 1988.

    14. Required learning hours and assignment
    In class
    		42
    Preparation for classes
    		28
    Preparation for midterm
    		 
    Homework  
    Reading assignment
    		50
    Final
    		 
    Total
    		 120
    15. Syllabus prepared by Dr Friedl Katalin  associate professor Department of Computer Science and Information Theory