Building on the knowledge of the "Introduction to Structured and Object-Oriented Programming" (ISOP), the handling of data structures and algorithms of greater structural complexity is to be trained. Students gain knowledge of cost estimation, complexity measures, basics of advanced data structures, search and sorting methods, and basic graph and optimization algorithms. This will enable them to design or select algorithms and suitable data structures for given problems and to evaluate the performance behavior.The accompanying exercises (UE) deepen the lecture material (VO) and should help to perform the construction and analysis of algorithms. Some of the presented data structures or algorithms are to be implemented exemplarily in Java. In addition to this basic goal of the course, selected implementation examples serve to consolidate the programming knowledge acquired in ISOP. 

Lecture and discussion (live & via Moodle)

Introduction: Algorithm, (un)decidability, efficiency, complexityElementary data structuresElementary algorithmsDivide & conquerSorting and searchingHashingGraphs and advanced treesString matchingData communication: Compression, error detection & correction, encryptionOutlook: Classes P & NP

Programming at ISOP level

Any textbook on Algorithms & Data Structures, e.g.,T.H. Cormen, C.E. Leiserson, C. Stein, R.L. Rivest: Introduction to Algorithms, MIT Press, 3rd ed. (2009) or 4th ed. (2022).S. Dasgupta, C. Papadimitrou, U. Vazirani: Algorithms, McGraw-Hill (2008).R. Sedgewick, K. Wayne: Algorithms, Addison-Wesley, 4th ed. (2011).M.T. Goodrich, R. Tamassia, M.H. Goldwasser: Data Structures and Algorithms in Java, Wiley, 6th ed. (2014). 

Written exam with theoretical questions (mostly free text answers, possibly some MC questions) and programming tasks (paper & pencil, no IDE; possibly SPU or ROPE); if necessary, supplementary oral examination in borderline cases. If no more than 12 persons are registered for an exam, it may also be held completely orally.Merit  points earned during the course can be redeemed the first time the exam is attempted

See "Inhalt(e) / Contents" above.

The theory questions must be answered in such a way that it can be inferred from the answer that the topic from which the question is taken is sufficiently mastered.The programming tasks must be solved essentially correctly, whereby "venial sins" in syntactic terms are tolerated.Grading key:Grade  from50 %450 %363 %276 %189 %