<table border="0"> <tbody> <tr valign="top"> <td style="padding-right: 5px;" width="90%"> <center> ---+++ <font color="990000" size="+3"> Advanced Algorithms</font> ---+++ <font color="990000" size="+2"> Academic Year 201<font color="990000">6</font>/201<font color="990000">7</font> - Spring semester</font> </center> <center> ---+++ <font color="990000" size="+2"> Prof.ssa Rossella Petreschi</font> </center> ---+++ <font color="990000" size="+2"> *News* </font> *Next exam:* September 19th, Via Salaria 113 , Aula seminari, third floor, 9 a.m.<br/> *The last lesson will take place on May 18th* and the *last written partial examination will be conducted on next May 19th* at 'Aula Oriana', via Salaria 113, ground floar.<br/> Prof. Petreschi will communicate the results of the partial examination on *Monday May 29th, from 9 a.m. to 12 a.m.,* in her office (via Salaria 113, third floar). Together with the results of the partial examination, Prof. Petreschi will propose to each student who has participated at the interim tests either a final evaluation or the request for a final partial examination on some specific topics.<br/> For all the other students who did not take part to the interim tests, the written exams remain fixed for <br/> *Thursday June 8th* Aula seminari, 9-13. <br/> *Monday July 3rd* Aula seminari, 9-13. <br/> *Wednesday April 26* the lesson will not take place.<br/> *Wednsday March 15* the lessons will not take place due to the event "Open DI".<br/> *Thursday March 16 and Thursday March 23* the lessons will be at 14.00 in Aula Seminari,Via Salaria 113, third floor.<br/> *First lesson*: Wednesday February 22 at 14.00 in Aula Alfa - Via Salaria,113.<br/> ---+++ <font color="990000" size="+2"> *Timetable* </font> _When_: Wednesday 14.00 - 16.00 and Thursday 14.00 - 16.00. <br/> _Where_: Aula Alfa - Via Salaria,113, ground floor.<br/> ---+++ <font color="990000" size="+2"> *Office Hours* </font> _By appointment_.<br />Office: Via Salaria, room 341/a, third floor. Phone: 06 - 4991 8511. <br />E-mail: petreschi AT di.uniroma1.it<br /> ---+++ <font color="990000" size="+2"> *Aim of the course* </font> The course presents algorithms and data structures that are used in the efficient resolution of important applied problems. <br /> Particular interest is focused on the design of algorithms that operate on parallel architectures.<br /> ---+++ <font color="990000" size="+2"> *Prerequisites* </font> It is assumed that students have knowledge of all topics covered during the bachelor program about algorithms.<br /> ---+++ <font color="990000" size="+2"> *Program* </font> * [[%ATTACHURL%/Program_AA_2016-2017.docx][Program_AA_2016-2017.docx]]: Program 2016-2017 ---+++ <font color="990000" size="+2"> *Exams* </font> The exam consists of a written test regarding themes covering the full course program.<br/> The exam can be taken in two ways: <br/> 1) by taking partial examinations at the end of each course section; <br/> Dates of option 1: March 10, April 7, April 28, May 19, Room: Aula seminari, third floor.<br/> 2) by taking an examination on the whole program from the end of the course on.<br/> Dates of option 2: June 8th, July 3rd, September 19th, Room: Aula seminari, third floor, 9 a.m.<br/> ---+++ <font color="990000" size="+2"> *Lessons* </font> Wednesday, February 22, 2017<br/> * Amortized Analysis.<br/> * Aggregation, accounting and potential methods.<br/> * Operations on stack.<br/> * The increement of a binary counter Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17<br/> Thursday, February 23, 2017<br/> * Dynamic tables.<br/> * How to expand a table.<br/> * Tables expansion and contraction.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17<br/> Wednesday, March 1, 2017<br/> * Binary search tree.<br/> * Visit a binary search tree.<br/> * Insertion and deletion in a binary search tree.<br/> * Analysis of a binary search tree insertions.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.12<br/> Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/> Thursday, March 2, 2017<br/> * Balanced search trees.<br/> * AVL trees.<br/> * The height of an AVL tree is logarithmic.<br/> * Rotations on a AVL tree.<br/> * Insertion and deletion in an AVL tree.<br/> Reference: Levitin A., "The design and analysis of algorithms", Chap.6.3<br/> Wednesday, March 8, 2017<br/> * Self-adjiusting trees.<br/> * Splay operation.<br/> * Make a binary search tree a splay tree.<br/> * Amortized analysis of a single splay step.<br/> * Amortized analysis of a sequence of operations on a splay tree.<br/> Reference: Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/> Thursday, March 9, 2017<br/> * Structure of Fibonacci heaps (FH).<br/> * Inserting an element in a FH.<br/> * Decreasing a key in a FH.<br/> * Deleting a node in a FH.<br/> * Mergeable-heap operations.<br/> * Computing the amortized analysis of all the operations on a FH.<br/> * Comparing heaps and Fibonacci heaps.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19 <br/> Friday, March 10, 2017<br/> * First partial examination:[[%ATTACHURL%/Testo_Esonero_1032017.docx][Testo_Esonero_1032017.docx]]<br/> Thursday, March 16, 2017<br/> * Bounding the maximum degree in a FT.<br/> * Dijkstra's algorithm for single source shortest paths.<br/> * Answers to the questions in the first partial examination.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19, 24.3 <br/> Wednesday, March 22, 2017<br/> * Definition of B-trees.<br/> * Basic operationson B-trees.<br/> * Deleting a key from a B-tree.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.18<br/> Wednesday, March 29, 2017<br/> * Data structure for disjoint sets.<br/> * Quickunion and Balanced Quickunion trees.<br/> * Quickfind and Balanced Quickfind trees.<br/> * Euristics to improve running times.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.21<br/> Thursday, March 30, 2017 * Augmenting data structures.<br/> * Managment of the rank of an element.<br/> * How to augment a data structure.<br/> * Correctness of the interval search procedure.<br/> Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.14<br/> Wednesday, April 05, 2017<br/> * Maximal, maximum and perfect matching.<br/> * Aletrnating and augmenting paths.<br/> * Maximum matching in general graphs.<br/> Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17<br/> Thursday, April 06, 2017<br/> * XOR operator and its properties.<br/> * The hungarian tree method for bipartite graphs.<br/> * Blossom's contraction in general graphs.<br/> Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17<br/> Friday, April 7, 2017<br/> * Second partial examination:[[%ATTACHURL%/Testo_Esonero_7_4_2017.docx][Testo_Esonero_7_4_2017.docx]] <br/> Wednesday, April 12, 2017<br/> * Flow networks.<br/> * Residual networks method.<br/> * Augmenting path method.<br/> * Ford and Fulkerson' algorithm.<br/> * Max-flow and min-cut.<br/> * Networks with multiple sources and tails.<br/> * Bipartite graphs:matching and flow nwetwork.<br/> Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16, 17.3<br/> Wednesday, April 19, 2017<br/> * Planar Graphs.<br/> * Euler's formula.<br/> * Kuratowski's theorem.<br/> * st-numbering.<br/> * Functions DFN, FATHER and LOW.<br/> Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.1.1-1.5, Chap.3.2 <br/> Thursday, April 20, 2017<br/> * Function PATH.<br/> * Algorithm for st-numbering.<br/> * Bush form.<br/> * PQ-tree.<br/> Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.1.1-1.5, Chap.3.2 <br/> Thursday, April 27, 2017<br/> * Concurrent system vs sequential system.<br/> * Distributed system vs parallel system.<br/> * Synchronous and asynchronous systems .<br/> * Shared memory and concurrent write and read.<br/> * General scheme of a distributed algorithm.<br/> * Broadcast on a distributed ring.<br/> Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1.1-1.2<br/> Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.1,2; 12.5.1-5.4<br/> Friday, April 28, 2017<br/> * Third partial examination: [[%ATTACHURL%/Testo_Esonero_2842017.docx][Testo_Esonero_2842017.docx]]<br/> Wednesday, May 3, 2017<br/> * Interconnection networks.<br/> * Broadcast on P-RAM, Mesh and Binary Tree.<br/> * EREW vs CREW .<br/> * Sum on P-RAM, Mesh and Binary Tree.<br/> Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1.3<br/> Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.4<br/> Thursday, May 4, 2017<br/> * Accelerated Cascading.<br/> * Broadcast with Echo.<br/> Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2.6<br/> Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.2-12.5<br/> Wednesday, May 10, 2017<br/> * Pointer Jumping Tecnique. * List ranking.<br/> * Prefix Sums.<br/> * Sorting Networks.<br/> * Bitonic Sequences.<br/> * Zero-One Principle.<br/> Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2.2,3.1<br/> Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.2,3<br/> Thursday, May 11, 2017<br/> * Bitonic Merge. * Bitonic Sorting Networks. * Brent's theorem on CREW and on EREW.<br/> * Decreasing the number of processors.<br/> * Leader election on a ring: n initializers.<br/> * Leader election on a ring: one initializer.<br/> Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.4.4<br/> Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.3, 12.5<br/> Wednesday, May 17, 2017<br/> * Parallel Minimum Spanning Tree.<br/> Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.5.1-2<br/> Thursday, May 18, 2017<br/> * Minimum Spanning Tree on a distributed system.<br/> Reference: Gallager R.G., Humblet P.A., Spira P.M., "A Distributed Algorithm for Minimum-Weight Spanning Trees" [[%ATTACHURL%/gallager.....pdf][gallager.....pdf]]<br/> Zomaya A.Y.H., "Parallel and distributed computing handbook" Chap. 5.3.3.2. Friday, May 19, 2017<br/> * Fourth partial examination:[[%ATTACHURL%/Testo_Esonero_19_5_20171.docx][Testo_Esonero_19_5_20171.docx]] <br/>
This topic: AA
>
WebHome
>
AdvancedAlgorithms_2016_17
Topic revision: r41 - 2018-02-05 - RossellaPetreschi
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback