BME VIK - Algoritmuselmélet

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

3. Course coordinator and department Dr. Katona Gyula,

Web page of the course http://cs.bme.hu/thalg/

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

Kötelező:

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

ÉS

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

ÉS

( Kepzes("5N-A8") VAGY
Kepzes("5NAA8"))

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

VAGY
(Kepzes("9N-AM06")ÉS
TargyEredmeny("BMEVISZA025" , "jegy" , _ ) >= 2 ÉS
TargyEredmeny("BMETE91AM43" , "jegy" , _ ) >= 2 ÉS
(TargyEredmeny("BMETE91AM57" , "jegy" , _ ) >= 2 VAGY
TargyEredmeny("BMETE91AM57", "FELVETEL", AktualisFelev()) > 0))

VAGY

(Kepzes("9NAAM17")ÉS
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 class	56
Preparation for classes	28
Preparation for midterm	24
Homework	28
Reading assignment	14
Preparation for final
Total	150

15. Syllabus prepared by

dr. Judit Csima associate professor SZIT

dr. Katalin Friedl associate professor SZIT

dr. Gyula Katona associate professor SZIT