AdvancedAlgorithms_2016_17 < AA

Tags: view all tags
<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/>