Profile of the Department of Computer Science

The first comprehensive computer science curriculum in (Czecho)Slovakia was introduced at the Faculty in 1973. The department, established in 1974, continues to be responsible for organizing the major part of the undergraduate and graduate computer science education to this date. The distinguishing feature of the curriculum has been a balanced coverage of the mathematical foundations, theoretical computer science, and practical computer science. The part of the curriculum covered by the department at present includes courses on computer architecture, system software, networks, databases, software design, design and analysis of algorithms, formal languages, computational complexity, discrete mathematics, cryptology, data security and others.

The quality of the computer science education has been repeatedly testified by publications of our best students and by high ranking of our student team in the ACM Collegiate Programming Contest Finals. Inclusion of the more abstract, foundational courses proved to be the key factor in educating flexible professionals who have been well received and successful in industry, commerce, research, and education. Most typically they serve as system and/or network administrators, software engineers and programmers. More recently, our graduates have been successful in newly established software firms, both as managers and programmers. Several well-known theoretical computer scientists (Hromkovič, Szelepcsényi, Geffert, etc.) are graduates or obtained their degrees at the Department.

The department succeeded several times in project applications within the TEMPUS Programme of the EU. The projects CIPRO and "Neumann Network" helped to build the departmental hardware infrastructure and to establish the expertise in Unix workstation technology, networking, and structured document processing. The CUSTU PARLAB parallel computing laboratory run jointly with the Department of Informatics of the Faculty of Electrical Engineering and Informatics of the Slovak Technical University also resulted from one of these projects. Furthermore, the department participated in project LEARN-ED under the COPERNICUS Programme and built a multimedia laboratory.

The department has been involved in the organization of one of the top European conferences in theoretical computer science - MFCS - each time it took place in Slovakia. Besides, the department houses the secretariat of the European Association for Theoretical Computer Science, of the Slovak Society for Computer Science and of the Association for Security of Information Technologies (ASIT).

Research in theoretical computer science and discrete mathematics has the longest tradition in the department. The results in formal languages, complexity theory, learning theory, graph theory and combinatorics were published in leading international journals and were presented at renowned international conferences. Most notably, the result of R. Szelepcsényi on the closure of nondeterministic space under complement, independently obtained also by N. Immerman, brought the prestigious Gödel Prize of ACM and EATCS to both of them in 1995. More recently research in parallel and distibuted computing, cryptology and information security, and in software development has been initiated. The department is involved in international cooperation on the development of the structured document editor within the Euromath Project.

The department has many international contacts, succeeded in research project application (project ALTEC - "Algorithms for Future Technologies") with partners from EU, and also has two research grants from the Slovak Grant Agency.

1. Ďuriš, P., Galil, Z.: On the power of multiple reads in a chip, Information and Computation 104 (1993), 277-287.
2. Ďuriš, P., Galil, Z., Schnitger, G.: Lower bounds on communication complexity, Information and Computation 73 (1987), 1-22.
3. Ďuriš, P., Rolim, J., D., P.: A note on the density of oracle decreasing time-space complexity, Theoretical Computer Science 132 (1994), 435-444.
4. Ďuriš, P., Rolim, J., D., P.: Optimal lower bounds on the multiparty communication complexity, Lecture Notes in Computer Science 900, Springer-Verlag (1995), 350-360.
5. Jendroľ, S., Nedela, R., Škoviera M.: Constructing regular maps and graphs from planar quotients, Math. Slovaca 47 (1997), 155-170.
6. Hromkovič, J., Karhumäki, J., Rovan, B., Slobodová, A.: On the power of synchronization in parallel computations, Discrete Appl. Math. 32 (1991), 155-182.
7. Hromkovič, J., Rovan, B., Slobodová, A.: Deterministic versus nondeterministic space in terms of synchronized alternating machines, Theoretical Computer Science 132 (1994), 319-336.
8. Nedela, R., Škoviera M.: Which generalized Petersen graphs are Cayley graphs ?, J. Graph Theory 19 (1995), 1-11.
9. Nedela, R., Škoviera, M.: Decompositions and reductions of snarks, J. Graph Theory 22 (1996), 253-279.
10. Nedela, R., Škoviera, M.: Regular Embeddings of Canonical Double Coverings of Graphs, J. Comb. Theory Ser. B 67, (1996), 249-277.
11. Nedela, R., Škoviera, M.: Exponents of orientable maps, Proc. London Math. Soc. (3) 75 (1997), 1-31.
12. Nedela, R., Škoviera, M.: Regular Maps from Voltage Assignments and Exponent Groups, Europ. J. Combinatorics 18, (1997), 807-823.
13. Olejár, D., Stanek, M.: Design of Substitution Blocks Satisfying Strict Avalanche Criterion, SAC '97, 2-12.
14. Szelepcsényi, R.: The method of forced enumeration for nondeterministic automata, Acta Informatica 26 (1988), 279-284.
15. Škoviera, M.: The maximum genus of graphs of diameter two, Discrete Math. 87 (1991), 175-180.
16. Škoviera, M., Širáň, J.: Characterization of the maximum genus of a signed graph, J. Comb. Theory Ser. B 52 (1991), 124-146.

(From Faculty Report '97)