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