Building on the knowledge gained in the Introduction to Structured and Object-Oriented Programming (ISOP) course, students will learn to deal with data structures and algorithms of greater structural complexity.Students will gain knowledge of cost estimation, complexity measures, fundamentals of advanced data structures, search and sorting methods, and basic graph and optimization algorithms. This will enable them to design or select algorithms and appropriate data structures for given problems and to evaluate their performance.Based on the material presented in the lecture (VO), the exercises (UE) will deepen the material presented in the lecture and will help to construct and analyze algorithms. Some of the presented data structures or algorithms will have to be implemented in Java and submitted to Moodle. In addition to this basic goal of the course, selected implementation examples serve to consolidate the programming knowledge acquired in ISOP.Skills to be acquiredTogether with the associated lecture, this course should enable the successful students toexplain the properties of algorithms;perform and empirically validate performance estimates;explain and apply the concept of asymptotic complexity (Landau and Tilde notation, complexity classes);explain and apply or compare properties of sequential data structures (arrays, lists, stacks, queues);understand and implement sorting algorithms (insertion sort, mergesort, quicksort, heapsort, countsort, bucket sort);explain and differentiate design paradigms (divide & conquer - focus, dynamic programming, greedy approaches);map graphs and trees in data structures;implement basic graph algorithms (BFS, DFS, LNR family, SSSP, Floyd-Warshall, A*, minimal spanning trees - Prim & Kruskal);deal with search trees (binary search tree, balanced binary search trees - AVL);understand the principle of hashing and implement or evaluate hashing methods (linear or quadratic probing, double hashing, linear hashing);explain cryptographic hashing;explain or implement and evaluate pattern searches (Boyer-Moore, KMP, Karp & Rabin, Tries, finite automata);understand and implement compression algorithms (RLE, Huffman code, LZW);explain the principle of error-detecting and error-correcting codes (parity codes, Hamming code);name aspects of complexity theory (NP, NPC, undecidability, Turing machines).

Discussion of the exercise tasks, presentation including discussion of solutions by the students.Exchange & peer walk-through of programming solutions.

Introduction: Algorithm and their performanceSearching in linear data structuresSortingSome algorithm design paradigms: Divide & Conquer, Dynamic Programming, Greedy AlgorithmsGraphs and treesHashingText processing: Pattern matchingCompression, error detection & correction, encryptionOutlook: Classes P & NP, Turing Machines

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). 

This is an examination-immanent course. If you earn ≥ 50 % of the possible scores stemming from the following two sources, you will pass the course:"Crossing lists" (see below):(Σ "crossed points" of prepared tasks) / (Σ "crossing points" of all tasks) × 30Presentation of solutions (and other bonus points):min((Σ points earned) / (median points of all students of your class) × 70, 70)

For each week, up to 10 exercise items can be prepared as homework. Depending on the associated workload, each item yields a number of points. You need to submit your solution in the corresponding Moodle quiz and enter a check mark (“cross”) in the corresponding overview in the Campus systembefore the deadline for the homework (typically, Thursday at 18:00).A “crossed exercise item” means that you are willing to present your solution in class. Crossings are counted only if you a present in the class in which the homework is discussed (typically the one after the deadline of the homework). 

When you present your solution, you will earn a score between zero and the number of points assigned to the respective exercise item (“crossing points”).Note that if you crossed an exercise item and it turns out that you have not at all understood the presented solution (➝ “ChatGPT solution”, plagiarism, etc.), all “crossing points” of that week are voided. Thus, only “cross” exercises that you have actually done and understood.

Handed-in solution for exercise tasks (30 % weight)Presentation of solutions to exercise tasks and ad-hoc contributions (70 % weight)

Handed-in solutions of exercise tasks must be genuine work and understood (no unreflected “copy & paste”)Handed-in solutions for exercise tasks must be correct (on the whole)The presentation of solutions must be understandable by the audienceQuestions related to the theory pertinent to the exercise item presented must be answered correctly (on the whole)Grading key:Grade  from50 %450 %362,5 %275 %187,5 %