inf030 - Programming, Algorithms and Data Structures (Complete module description)

No specialised prior knowledge required.

Programming is one of the basic activities of computer scientists and a prerequisite for many other courses on the computer science degree programme. The aim of the ‘Programming, Algorithms and Data Structures’ module is to learn the basic concepts of imperative, procedural and object-oriented programming using the Java programming language and to present known, efficient algorithms and data structures for various frequently occurring problems.

After completing the module, students should be able to independently develop imperative and simple object-oriented programmes based on Java to solve small problems and assess the efficiency of their programmes. They should also be able to apply important algorithms and select them based on their complexity.

Subject-related competences

The students

• describe basic concepts of imperative programming with Java
• recognise the terminology of imperative programming and use the corresponding terms precisely in discussions
• recognise basic terminology of object-oriented programming
• describe what programmes presented to them do
• develop programmes independently to solve small problems
• systematically examine their own and other people's programmes for errors
• use modern programme development environments to develop and test programmes
• create algorithms with general design concepts (e.g. greedy method, divide-and-conquer method)
• name algorithms and data structures for solving frequently occurring problems and evaluate their applicability
• name problems of the efficiency of algorithmic solutions to specific problems and evaluate them
• select an algorithm and a data structure to solve a specific problem in a well-founded manner
• apply the algorithms and data structures they have learnt in a meaningful way to given and concrete problems

Methodological competences

The students

• solve given problems from the point of view of imperative or object-orientated programming
• transfer practical experience in programme development to new tasks

Social competences

The students

• communicate the structure and mode of operation of self-developed programmes to others
• present independently developed solutions to small tasks to groups

Self-competences

The students

• organise themselves when finding algorithmic solutions for small and medium-sized problems in computer science
• incorporate the concepts of general programme design into their work

In the first part, general basic concepts of programming are introduced:

• Algorithm, programming languages, computer
• development tools, development phases
• compilers
• grammars
• Logic

The second part deals with basic programming concepts:

• data types
• variables
• expressions, statements
• control structures
• methods, parameters
• recursion
• reference data types, arrays
• classes, objects
• documentation
• testing

The third part contains an introduction to data structures and algorithms as well as a discussion of their efficiency, i.e. the computational effort and memory requirements depending on the amount of data to be processed. The module presents known, efficient algorithms and data structures for various frequently occurring problems. These include in particular

• methods for searching for keys, as well as insertion and deletion in dynamic data sets, e.g. lists, trees, AVL trees or hash methods,
• methods for searching for text patterns,
• methods for sorting data according to key values, e.g. QuickSort and HeapSort,
• graph-based applications, e.g. for determining the shortest paths in graphs.

The lecture section is supplemented by a comprehensive exercise section in which the programming content taught is implemented using practical examples.

Essential

• Lecture Notes (made available via Stud.IP during the course of the lecture)

Recommended secondary literature

• Dietmar Ratz, Jens Scheffler, Detlev Seese, Jan Wiesenberger: Grundkurs Programmieren in Java, Carl Hanser Verlag.
• Joachim Goll, Cornelia Heinisch: Java als erste Programmiersprache, Springer Vieweg Verlag
• Ottmann, Widmayer: Algorithmen und Datenstrukturen. Spektrum Verlag, 5. Auflage, 2012
• Segdewick, Wayne: Algorithms. Addison Wesley, 4th ed., 2011
• Siege: Einführung in die Informatik. Shaker Verlag, 2013

At the end of the Semester

written exam / portfolio (short written exams) / oral exam