Content:

* Algorithms: definition, algorithms vs. programs, representing algorithms, abstraction layers and characteristics of algorithms

* Specifications: objectives, Interface descriptions, requirements, representing specifications

* Step-wise refinement: "divide & conquer", systematic problem solving, examples

* Algorithms with a memory: term and definition, ways to implement algorithms with a memory

* Complexity: terms and definitions, runtime analysis, runtime measurements, asymptotic complexity, minimal complexity of problems

* Dynamic data structures: classes and references, linear lists, unsorted lists, sorted lists, ring lists, double-connected lists, stacks, queues, sets

* Recursion: term and definition, classification, termination, applications, transforming recursive into iterative algorithms

* Sorting: selection sort, insertion sort, shell sort, quick sort, merge sort, sorting lists, heap sort, topological sort, complexity of sorting algorithms

* Trees: term and definition, binary search trees, balanced trees, topdown-234-trees, black-red-trees, B-trees

* Graphs: term and definition, depth-first-search, breadth-first-search, smallest spanning tree, shortest path, transitive hull, serialization of graphs

* Exhaustion: n-queens problem, schema to search a solution, using exhaustion to find a solution, optimization, representing solution vectors, approximation, non-deterministic algorithms

* Classification of algorithms

Methods:

The lecture mostly is based on algorithms in pseudo code. This allows learning algorithms independent of a concrete programming language.

Some parts of the lecture are supported by demo videos. Some algorithms are constructed on the blackboard or whiteboard step by step.

The exercises are meant to detail and deepen what is learnt in the lecture. Exercises are thus defined based on the contents of the lecture. Students shall use a recent object-oriented programming language (e.g., Java) to practice designing and implementing the algorithms that are presented in the lecture, using simple yet realistic examples. In the exercise units, students and lecturers discuss exercises including example solutions.

Course work:

VO: lecture exam at the end ot the semester

UE:  evaluation of elaborated sentences

Documents:

The lecture is mainly based on slides. Slides and additional material will be made available for download in PDF format.

Literature:

• Aho A.V., Hopcroft J.E., Ullman J.D.: Data Structures and Algorithms.  Addison-Wesley 1983.
• Goodrich, M. T., Tamassia, R., and Goldwasser, M. H.: Data structures and algorithms in Java. John Wiley & Sons. 2014.
• Knuth D.E.: The Art of Computer Programming. Addison-Wesley 1973.

              --> Band 1: Fundamental Algorithms.

              --> Band 2: Seminumerical Algorithms.

              --> Band 3: Sorting and Searching.

• Pomberger G., Dobler H.: Algorithmen und Datenstrukturen. Pearson 2008.
• Saake G., Sattler K.: Algorithmen und Datenstrukturen. dpunkt 2006.
• Sedgewick R.: Algorithmen in Java. Pearson 2014.
• Wirth N.: Algorithmen und Datenstrukturen. Teubner Studienbücher Informatik 1986.

Links

Visualization und animation of different Algorithmen: here, opens an external URL in a new window and here, opens an external URL in a new window.

.

Exercise mode

• Discussion of open questions/sample solutions
• Illustration of the exercises by examples
• Presentation of the current task
• No compulsory attendance

Tutorium

A virtual Tutorium with the tutors is held every Tuesday 4:15pm – 5:00pm. The Zoom link is provided in  Moodle.

Exercise submission

• Electronic submission of exercises in the Moodle course
• Each exercise has at least a 7 day processing period. Hard deadline at 23:59:00!.
• Only ZIP archives and/or PDF are accepted as submission formats.
• PDF for (hand-)written assignments; ZIP for programming assignments.
• The files to be submitted must follow a naming convention:
  • algo1_ue<nr>_<matrNr>.zip (example: algo1_ue02 _01255105.zip).
• All classes relevant for the solution are to be stored in a Java package.
• Only individual work will be accepted. Detected plagiarism will be penalized. At minimum ALL involved parties get 0 points WITHOUT exception. Further actions will be determined. Changing variable names or similar does not prevent plagiarism.

Grading

• A total of 9 exercise sheets, each with different tasks related to the lecture.
• 3 of the first 4 exercises and 3 of the second 4 exercises must be submitted. Exercise 9 is for preparation of the exam.
• A maximum of 24 points can be achieved in each exercise.
• The 8 best exercises of the 9 exercises will be included in the grade.
• The sum of the achieved points of 8 best graded exercises determines the grade.
• Exercises not handed in will be graded with 0 points.

Grades

Material

The exercise details and supplementary material for the course are available for download in the Moodle course.