Introduction to the Theory of Computing 2

A tantárgy neve magyarul / Name of the subject in Hungarian: Bevezetés a számításelméletbe 2

Last updated: 2022. október 12.

Budapest University of Technology and Economics
Faculty of Electrical Engineering and Informatics
Course ID Semester Assessment Credit Tantárgyfélév
VISZAA04 2 2/2/0/v 5  
3. Course coordinator and department Dr. Wiener Gábor,
Web page of the course http://cs.bme.hu/bsz2
4. Instructors

Dr. Rita Csákány, associate professor, Department of Computer Science and Information Theory

Dr. Tamás Fleiner, associate professor, Department of Computer Science and Information Theory

Dr. Péter Pál Pach, associate professor, Department of Computer Science and Information Theory

Dr. András Recski, professor, Department of Computer Science and Information Theory

Dr. Dávid Szeszlér, associate professor, Department of Computer Science and Information Theory

Dr. Gábor Wiener, associate professor, Department of Computer Science and Information Theory
5. Required knowledge High school level mathematics.
6. Pre-requisites
Kötelező:
((TárgyEredmény( "BMEVISZAA00" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVISZAA03" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVISZA103" , "aláírás" , _ ) = -1
VAGY
TárgyEredmény( "BMEVISZAA06" , "aláírás" , _ ) = -1 )

ÉS NEM

(TargyEredmeny("BMEVISZA110", "jegy", _) >= 2
VAGY
TárgyEredmény("BMEVISZA110", "felvétel", AktualisFelev()) > 0
VAGY
TargyEredmeny("BMEVISZAA01", "jegy", _) >= 2
VAGY
TárgyEredmény("BMEVISZAA01", "felvétel", AktualisFelev()) > 0
VAGY
TárgyEredmény( "BMEVISZAA01" , "aláírás" , _ ) = -1) )

VAGY

(EgyenCsoportTagja("INFO - 2022 - MINTATANTERV HALLGATÓI") VAGY
EgyenCsoportTagja("INFO - 2022ENG - MINTATANTERV HALLGATÓI"))

ÉS (Training.Code=("5N-A8") VAGY Training.Code=("5NAA8"))

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

The goal of the subject is to acquire the fundamental mathematical knowledge (in the area of linear algebra and number theory) necessary for software engineering studies. 

Students successfully completing the course will be able to:

  • (K3) understand and apply the notions and the knowledge covered by the course;
  • (K3) individually solve practical problems related to the material of the course;
  • (K2) apply the algorithms covered by the course;
  • (K2) prove certain theorems covered by the course;
  • (K3) during their further studies, identify situations where fields of knowledge covered by the course are applicable and apply them successfully.
8. Synopsis

1) Basic notions of graph theory: graph, simple graph, degree of a vertex, subgraph, induced subgraph, walk, trail, tour, path, cycle, isomorphism.

2) Connected graph, connected component, tree, spanning tree. Existence of a spanning tree.

3) Storing graphs: adjacency list, adjacency matrix. Directed graphs. Efficiency of graph algorithms. Deciding connectivity, finding a shortest path (with unit edge lengths): Breadth First Search.

4) Computing a minimum weight spanning tree: Kruskal's algorithm.

5) Euleri trails and tours, necessary and sufficient conditions on their existence. Hamiltonian paths and cycles. Necessary conditions on their existence: the maximum number of components after deleting k nodes. Sufficient conditions: theorems of Dirac and Ore.

6) Bipartite graphs, their characterization with odd cycles. Chromatic number. Greedy coloring, upper bound on the chromatic number in terms of the maximum degree. Maximum clique size, its relation to the chromatic number, Zykov's construction.

7) Optimal coloring of interval graphs. Matching, vertex cover, independent set, edge cover. Relation between the sizes of the maximum matching and the minimum vertex cover. Gallai's theorems.

8) Computing a maximum matching in a bipartite graph, the augmenting path algorithm, its optimality. Kőnig's theorem on the equality between the sizes of a maximum matching and a minimum vertex cover.

9) Edge-chromatic number, its relation to the maximum degree, Vizing's theorem.Kőnig's theorem on the edge coloring of bipartite graphs.

10) The maximum flow problem: the notions of network, flow, overall value of a flow. The augmenting path algorithm for computing a maximum flow. The notion of an st-cut of a network, and its capacity.

11) Ford-Fulkerson theorem, Edmonds- Karp theorem. The integer valued maximum flow problem. The problem of edge-disjoint s-t paths, Menger's corresponding theorem.

12) The problem of edge-disjoint paths in undirected graphs, the problems of vertex-disjoint paths in directed and undirected graphs, Menger's corresponding theorems. The notions of k-connectivity and k-edge-connectivity, Menger's corresponding theorems.

13) The shortest path problem with real edge length in directed graphs, the Bellman-Ford algorithm.

14) Summary and review.

9. Method of instruction

2 hours of lecture and 2 hours of problem solving each week.

The lecture introduces new theory and the role of practice classes is to deepen the acquired knowledge by applying it on problems. Since practice classes closely follow the material of corresponding lectures, a thorough knowledge of the material covered by the lectures is expected from the students. The common work done on practice classes (including homeworks) is an inherent part of the learning process. Lectures in most cases build on the material of previous weeks, it is typically impossible to follow the new material without the preliminary knowledge provided by them.

10. Assessment

Signature:

There will be 1 midterm during the semester. In order to acquire the signature, the result of the midterm must be at least 24 points out of 60.

Final exam:

In order to take the final exam students must have a valid signature.

The final exam is oral.

The final score is based on the score of the midterm (40%) and the score of the oral exam (60%). 

The final grade based on the final score is as follows. 0-39,9: fail (1), 40-54,9: pass (2), 55-69,9: satisfactory (3), 70-84,9: good (4), 85-100: excellent (5).

 

Pre-exam is not allowed.

11. Recaps One retake of the midterm is possible free of charge in order to acquire the signature or to improve on the score of a succesful midterm. One further retake is possible in order to acquire the signature for an official fee.
13. References, textbooks and resources

Online course book: http://cs.bme.hu/bsz2/jegyzet/. (in Hungarian)

The midterms and scoring guides of the last decade can also be found on the website of the course. 

14. Required learning hours and assignment
In class 56
Preparation for lectures8
Preparation for practice classes21
Preparation for midterms15
Preparation for the final50
  
Total150
15. Syllabus prepared by Dr. Gábor Wiener, associate professor, Department of Computer Science and Information Theory