Main Page

<!DOCTYPE html> <html lang="en" data-bs-theme=""> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title> Main Page </title> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <meta name="author" content="Markus Bauer, Marc Jose, Sigurd Schneider"> <meta name="commit" content="68a829ca75de920005cb4a9fea469531bf66b624@develop"> <style> html[data-bs-theme=dark] .site-logo > img { content: url("/system/theme/Sic/img/logo-dark.png"); } </style> <link rel="stylesheet" type="text/css" href="/system/css/cakecms.css" course="system"/><link rel="stylesheet" type="text/css" href="/system/css/fontawesome.min.css" course="system"/><link rel="stylesheet" type="text/css" href="/system/css/theme.css" course="system"/><link rel="stylesheet" type="text/css" href="/system/css/theme-custom.css" course="system"/><script type="text/javascript" src="/system/js/modern/bootstrap.bundle.min.js" course="system"></script><script type="text/javascript" src="/system/js/modern/tempus-dominus.min.js" course="system"></script><script type="text/javascript" src="/system/js/modern/popper.min.js" course="system"></script><script type="text/javascript" src="/system/js/modern/custom.js" course="system"></script> <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/system/theme/Sic/img/apple-touch-icon-144-precomposed.png"> <link rel="apple-touch-icon-precomposed" sizes="114x114" href="/system/theme/Sic/img/apple-touch-icon-114-precomposed.png"> <link rel="apple-touch-icon-precomposed" sizes="72x72" href="/system/theme/Sic/img/apple-touch-icon-72-precomposed.png"> <link rel="apple-touch-icon-precomposed" sizes="57x57" href="/system/theme/Sic/img/apple-touch-icon-57-precomposed.png"> <link rel="shortcut icon" type="image/x-icon" href="/system/theme/Sic/img/favicon.png"> <link rel="icon" type="image/x-icon" href="/system/theme/Sic/img/favicon.png">  </head> <body class="bg-body-tertiary d-flex flex-column py-0" style="min-height: 100vh;"> <nav class="navbar navbar-dark border-bottom navbar-expand-lg fixed-top"> <div class="container-lg"> <a href="/algodat23/../system" class="navbar-brand">Courses</a> <div class="navbar-expand flex-grow-1 flex-s d-lg-none overflow-none"> <ul class="navbar-nav d-lg-none flex-wrap" id="navbar-overflow"></ul> </div> <button class="navbar-toggler ms-2" type="button" data-bs-toggle="collapse" data-bs-target="#navbar-course" aria-controls="navbar-system" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbar-course"> <ul class="navbar-nav me-auto mb-2 mb-md-0" id="navbar-main"> <li class="nav-item"><a class="nav-link active" href="/algodat23/">Main Page</a></li><li class="nav-item dropdown"><button class="nav-link dropdown-toggle" type="button" data-bs-toggle="dropdown">Information</button><ul class="dropdown-menu"><li><a class="dropdown-item" href="/algodat23/termine/calendar/index">Timetable</a></li><li><a class="dropdown-item" href="/algodat23/tutors">Team</a></li></ul></li><li class="nav-item"><a class="nav-link" href="/algodat23/students/register">Registration</a></li><li class="nav-item"><a class="nav-link" href="/algodat23/landing">Personal Status</a></li> </ul> <div class="navbar-nav"> <div class="dropdown"> <button class="dropdown-toggle nav-link user-menu-toggle" data-bs-toggle="dropdown" data-bs-auto-close="outside"> <i class="fa fa-user fa-fw"></i> Login <b class="caret"></b> </button> <ul class="dropdown-menu dropdown-menu-end"> <form action="/algodat23/users/login" class="p-2 dropdown-item-text d-grid gap-2" style="min-width: 240px" id="UserLoginMenuForm" method="post" accept-charset="utf-8"><div style="display:none;"><input type="hidden" name="_method" value="POST"/><input type="hidden" name="data[_Token][key]" value="755a97769b17d06e25171dd37467e0d905bd48837b7dd37c0311cb41208bb88baacc77dde1a7c1b59b948ae3e3c5c09f46b39b8beb94855a7499cad5337d4e93" id="Token1350077907" autocomplete="off"/></div> <input name="data[User][username]" placeholder="Username" id="MenuUserUsername" maxlength="100" class="form-control" type="text" required="required"/> <input name="data[User][password]" placeholder="Password" id="MenuUserPassword" class="form-control" type="password" required="required"/> <div class="my-2"><input type="hidden" name="data[Auth][remember_me]" id="MenuAuthRememberMe_" value="0"/><input type="checkbox" name="data[Auth][remember_me]" id="MenuAuthRememberMe" class="form-check-input" value="1"/><label for="MenuAuthRememberMe" class="mx-2 form-check-label">Remember me</label></div> <input type="hidden" name="data[User][redirect]" value="https://cms.sic.saarland/algodat23/landing" id="MenuRedirect" class="form-control"/> <li class="d-grid"> <button type="submit" class="btn btn-primary"><i class="fa fa-right-to-bracket"></i> Login</button> </li> <div style="display:none;"><input type="hidden" name="data[_Token][fields]" value="10d30f5dc23345ff66000b4d1df633937e280ca0%3AUser.redirect" id="TokenFields145856066" autocomplete="off"/><input type="hidden" name="data[_Token][unlocked]" value="" id="TokenUnlocked596191663" autocomplete="off"/></div></form> <li class="dropdown-divider"></li> <li> <a href="/algodat23/students/register" class="dropdown-item"><i class="fa fa-user-plus fa-fw"></i> Registration</a> </li> <li> <a href="/algodat23/Users/lost" class="dropdown-item"><i class="fa fa-lock-open fa-fw"></i> Forgot Password?</a> </li> <li><hr class="dropdown-divider"></li> <li style="min-width: 270px;"> <button class="dropdown-item lightmode-only" data-toggle="theme" data-bs-theme="dark"> <i class="fa fa-moon fa-fw"></i> Enable dark mode </button> <button class="dropdown-item darkmode-only" data-toggle="theme" data-bs-theme="light"> <i class="fa fa-sun fa-fw"></i> Enable light mode </button> </li> </ul> </div> </div> </div> </div> </nav>  <div class="border-bottom flex-shrink-0">  <div class="navbar bg-body-tertiary"> <div class="container-lg"> <a class="navbar-brand" href="#"> </a> </div> </div> <div class="container-lg py-3"> <div class="page-header"> <div class="page-logo"> <a href="/algodat23/../system" class="site-logo" title="Front Page"><img src="/system/theme/Sic/img/logo.png" course="system" alt=""/></a> </div> <div class="page-title"> <h1 class="mt-1"> Algorithms and Data Structures (block course) </h1> <div> <small class="text-muted"> Karl Bringmann, Evangelos Kipouridis, Philip Wellnitz </small> </div> <div class="mt-2"><small class="text-muted fs-6">Core Lecture 9CP</small></div> </div> </div> </div> </div>   <div class="bg-body py-3 flex-shrink-0 flex-grow-1"> <div class="container-lg main-layout"> <div class="row"> <main class="col-12"> <div id="content" class="content"> <section> <h2>News</h2> <div class="action-row"> </div> <table class="table"> <colgroup> <col span="1" style="width: auto;" /> </colgroup> <tbody> <tr> <td class="align-top"> <a id="newsElement5"></a> <h4 class="fs-5"><a href="/algodat23/news/view/5">Grades and Inspection II</a></h4> <p> <small class="text-muted"><i> Written on <span data-bs-toggle="tooltip" data-bs-title="12.04.2024 16:37:45">12.04.24</span> by Karl Bringmann </i></small> </p> <p>Dear students,</p> <p>You can now see your grade for the re-exam by logging into the course website.</p> <p>On Monday from 14:00-15:00 you can inspect your exam in room 415, E1 3.</p> </td> </tr> </tbody> </table> </section> <section> <div class="action-row"> </div> <div class="page overflow-auto"> <h2>Algorithms and Data Structures (block course)</h2> <p>The course will cover basic and advanced data structures and algorithms, as well as their analysis. Examples of data structures are perfect hashing, splay trees, randomized search trees, union-find structures. In terms of problem domains, we cover graphs, strings, polynomials, and geometry. Furthermore, we discuss algorithm analysis techniques such as amortization and randomization, and general algorithm design principles.</p> <h3>Time, Date, and Format</h3> <p>This core course will be offered in an intensive block version <strong>between February 28 and March 26</strong>. The course can be taken only in presence.</p> <p>The format of the course will be as follows: A "unit" consists of a 70 minute lecture, followed by 2 hours of group work on an exercise sheet, followed by a short discussion section with a tutor (tutorial). Typically we will have two units a day, the first starting at 9am, the second at 2pm, Monday through Friday, except for Wednesdays, which will have only the morning unit. As an exception, the <strong>first lecture happens on February 28 at 14:00</strong>. See Information→Timetable for details.</p> <p>The lecture will take place in room <strong>HS003 in building E1 3</strong>.</p> <p>The tutorial will take place at 12:00 and at 17:00 in seminar room <strong>106 in building E1 1</strong>. The room 016 in building E1 3 is also reserved throughout the lecture period as working space.</p> <p>This will be a very intensive course. Do not plan on doing anything else serious beside it.</p> <h3>Registration</h3> <p>You need to register on this webpage to get access to exercise sheets and other course material.</p> <h3>Exams</h3> <p>You grade will be determined by a written exam. Admittance to the exams requires active participation in the course.</p> <p>Endterm:  28.03. 2pm-4pm, HS I in E2 5</p> <p>Re-Exam:  11.04. 2pm-4pm, HS 002 in E1 3</p> <h3>Prerequisites</h3> <p>The course requires basic knowledge in algorithms and data structures as covered for example by the course “Introduction to Algorithms and Data Structures” (“Grundzüge von Algorithmen und Datenstrukturen”). In particular, you should be familiar with correctness proofs of algorithms. Specific concepts that you should have basic familiarity with and should be able to apply include:</p> <ul> <li>pseudocode notation</li> <li>O-notation, running time analysis</li> <li>binary search</li> <li>basic sorting algorithms, mergesort</li> <li>arrays, linked lists</li> <li>stacks, queues</li> <li>heaps / priority queues</li> <li>binary search trees, balanced binary search trees (e.g. AVL trees)</li> <li>definition of a graph</li> <li>graph traversal (e.g. depth first search / breadth first search)</li> </ul> <p>In case you want to read up on these topics we recommend the videos of the course “Introduction to Algorithms and Data Structures”, see Information→Materials.</p> <h3>Tentative List of Topics</h3> <ul> <li>greedy algorithms</li> <li>dynamic programming</li> <li>divide and conquer (e.g. master theorem, integer multiplication, FFT)</li> <li>randomized algorithms (e.g. quicksort, randomized search trees, hashing)</li> <li>amortization (e.g. Fibonacci heaps, union find)</li> <li>strings (e.g. pattern matching, suffix arrays)</li> <li>graphs (e.g. shortest paths, maxflow, matching)</li> <li>computational geometry</li> </ul> <table border="1" cellpadding="1" cellspacing="1" style="width:800px"> <thead> <tr> <th scope="col">Date</th> <th scope="col">Lecturer</th> <th scope="col">Topic</th> <th scope="col">Comment</th> </tr> </thead> <tbody> <tr> <td>28.2. 2pm</td> <td>PW</td> <td>Intro: machine model, O-notation</td> <td> </td> </tr> <tr> <td>29.2. 9am</td> <td>PW</td> <td>Strings I: string matching</td> <td>Morris-Pratt (see [CR])</td> </tr> <tr> <td>29.2. 2pm</td> <td>PW</td> <td>Strings II: edit distance and approximate string matching</td> <td>Needleman-Wunsch</td> </tr> <tr> <td>1.3. 9am</td> <td>PW</td> <td>Strings III: approximate string matching (cont), suffix array</td> <td><a href="https://doi.org/10.1016/0022-0000(88)90045-1">Landau-Vishkin</a></td> </tr> <tr> <td>1.3. 2pm</td> <td>PW</td> <td>Strings IV: suffix array construction, lcp array construction</td> <td> <p><a href="https://doi.org/10.1007/3-540-45061-0_73">Kärkkäinen-Sanders</a>,<br /> <a href="https://doi.org/10.1007/3-540-48194-X_17">Kasai et al.</a></p> </td> </tr> <tr> <td>4.3. 9am</td> <td>PW</td> <td>Strings V: lcp array construction (cont), range minimum queries</td> <td>Kasai et al. (cont)</td> </tr> <tr> <td>4.3. 2pm</td> <td>PW</td> <td>Advanced Dynamic Programming: LIS, segment trees</td> <td> </td> </tr> <tr> <td>5.3. 9am</td> <td>EK</td> <td>Amortization I: intro</td> <td> </td> </tr> <tr> <td>5.3. 2pm</td> <td>EK</td> <td>Amortization II: Fibonacci heaps</td> <td> </td> </tr> <tr> <td>6.3. 9am</td> <td>EK</td> <td>Amortization III: splay trees</td> <td> </td> </tr> <tr> <td>7.3. 9am</td> <td>EK</td> <td>Amortization IV: union find</td> <td> </td> </tr> <tr> <td>7.3. 2pm</td> <td>KB</td> <td>Randomized I: model, rank select</td> <td> </td> </tr> <tr> <td>8.3. 9am</td> <td>KB</td> <td>Randomized II: randomized search trees</td> <td> </td> </tr> <tr> <td>8.3. 2pm</td> <td>KB</td> <td>Randomized III: hashing</td> <td> </td> </tr> <tr> <td>11.3. 9am</td> <td>KB</td> <td>Randomized IV: more on hashing</td> <td> </td> </tr> <tr> <td>11.3. 2pm</td> <td>KB</td> <td>Randomized V: Monte Carlo algorithms</td> <td> </td> </tr> <tr> <td>12.3. 9am</td> <td>PW</td> <td>Divide and Conquer I: Recurrences (I), Karatsuba</td> <td> </td> </tr> <tr> <td>12.3. 2pm</td> <td>PW</td> <td>Divide and Conquer II: Recurrences(II), Master Theorem, Strassen</td> <td> </td> </tr> <tr> <td>13.3. 9am</td> <td>PW</td> <td>Polynomials I: Introduction</td> <td> </td> </tr> <tr> <td>14.3. 9am</td> <td>PW</td> <td>Polynomials II: FFT</td> <td> </td> </tr> <tr> <td>14.3. 2pm</td> <td>PW</td> <td>Polynomials III: Polynomial division, Schönhage-Strassen</td> <td> </td> </tr> <tr> <td>15.3. 9am</td> <td>EK</td> <td>Graphs I: intro, BFS+DFS, Dijkstra</td> <td> </td> </tr> <tr> <td>15.3. 2pm</td> <td>EK</td> <td>Graphs II: shortest path: Bellman-Ford, Floyd-Warshall, Johnson, ...</td> <td> </td> </tr> <tr> <td>18.3. 9am</td> <td>EK</td> <td>Graphs III: minimum spanning tree</td> <td> </td> </tr> <tr> <td>18.3. 2pm</td> <td>EK</td> <td>Graphs IV: maxflow: intro, maxflow mincut</td> <td> </td> </tr> <tr> <td>19.3. 9am</td> <td>EK</td> <td>Graphs V: maxflow: Ford-Fulkerson</td> <td> </td> </tr> <tr> <td>19.3. 2pm</td> <td>EK</td> <td>Graphs VI: maxflow: blocking flows</td> <td> </td> </tr> <tr> <td>20.3. 9am</td> <td>EK</td> <td>Graphs VII: maximum matching</td> <td> </td> </tr> <tr> <td>21.3. 9am</td> <td>EK</td> <td>Graphs VIII: global mincut</td> <td> </td> </tr> <tr> <td>21.3. 2pm</td> <td>KB</td> <td>Geometry I: intro, convex hull</td> <td> </td> </tr> <tr> <td>22.3. 9am</td> <td>KB</td> <td>Geometry II: convex hull ctd., linear programming</td> <td> </td> </tr> <tr> <td>22.3. 2pm</td> <td>KB</td> <td>Geometry III: orthogonal range searching</td> <td> </td> </tr> <tr> <td>25.3. 9am</td> <td>KB</td> <td>Geometry IV: sweep line, Voronoi diagrams</td> <td> </td> </tr> <tr> <td>25.3. 2pm</td> <td>KB</td> <td>Geometry V: Voronoi diagrams ctd. + intro to models of computation</td> <td> </td> </tr> <tr> <td>26.3. 9am</td> <td>KB</td> <td>Models of Computation: cache hierarchy, IO model</td> <td> </td> </tr> <tr> <td>26.3. 2pm</td> <td>KB</td> <td>Models of Computation: IO model ctd.</td> <td> </td> </tr> </tbody> </table> <div> </div> <h3>Literature</h3> <div> <p>The course will not follow a particular book. The following is a list of literature that could be useful.</p> <ul> <li>[MS] K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox, Springer, 2008 (ISBN: 9783540779773)</li> <li>[CLRS] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms - Second Edition, McGraw-Hill, 2001 (ISBN: 0262531968)</li> <li>[KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005 (ISBN: 0-321-29535-8)</li> <li>[Meh] K. Mehlhorn, Data Structures and Algorithms, Vols. 1-3, Springer Verlag, 1984</li> <li>[Koz] D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, 1991</li> <li>[GKP] R. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley, 1994</li> <li>[Sch] A. Schrijver, <a href="http://homepages.cwi.nl/~lex/files/dict.pdf">A Course in Combinatorial Optimization</a>, 2013</li> <li>[BKOS] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry, Springer Verlag, 2000</li> <li>[Eri] J. Erickson, <a href="https://jeffe.cs.illinois.edu/teaching/algorithms/">Algorithms</a>, 2019 (Free electronic version)</li> <li>[CR] M. Chrochemore, W. Rytter, <a href="https://www.worldscientific.com/worldscibooks/10.1142/4838#t=aboutBook">Jewels of Stringology</a>, World Scientific 2002</li> </ul> </div> </div> </section> </div> </main>  </div>  </div>  </div>    <div class="border-top flex-shrink-0"> <div class="container text-center py-4"> <small class="page-footer text-muted"> <a href="https://www.uni-saarland.de/en/privacy.html" target="_blank">Privacy Policy</a> | <a href="https://www.uni-saarland.de/en/legal-notice.html" target="_blank">Legal Notice</a><br/> If you encounter technical problems, please contact <a href="mailto:cakecms@cs.uni-saarland.de?subject=[]&body=Please%20provide%20sufficient%20informations%20as%3A%20Name%2C%20Date%2C%20Role%2C%20Which%20System%2C%20What%20Error%21">the administrators</a>.</small> </div> </div>  </body> </html>

CINXE.COM

Main Page