AdvancedAlgorithms_2017_18 < 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">7</font>/201<font color="990000">8</font> - Spring semester</font>
</center>
<center>

---+++ <font color="990000" size="+2"> Prof.ssa Rossella Petreschi</font>
</center>

---+++ <font color="990000" size="+2"> *News* </font>

No classes will be held on these days: 24th and 25th of April, May the first.<br />
From 2nd of May, classes will start again as usual.<br />

*First lesson*: <br />
Tuesday March 6 at 8.00 in Aula Alfa - Via Salaria,113.<br />

---+++ <font color="990000" size="+2"> *Timetable* </font>

*When*: <br />
Tuesday  08.00 - 10.30 <br />
                  Wednesday 08.00 - 10.30. <br />

*Where*: <br />
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_2017-2018.docx][Program_AA_2017-2018.docx]]


---+++ <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 27 , April 19, May 25 , Room: "Seminari", Via Salaria,third floor<br />

2)   by taking an examination on the whole program from the end of the course on.<br />
Dates of option 2:<br />
                             2018 June 8, Room: "Seminari", Via Salaria,third floor;<br />
                             2018 July 11,  Room: "Riunioni", Via Salaria,third floor;<br /> 
                             2018 September                       , Room:        <br />
                             2019 January                            , Room:        <br />
                             2019 February                           , Room:        <br />


 
 



---+++ <font color="990000" size="+2"> *Lessons* </font> 
Tuesday, March 6, 2018<br/>
   * Amortized Analysis.<br/>
   * Aggregation, accounting and potential method.<br/>
   * Operations on stack.<br/>
   * The increment of a binary counter.<br/>
   * Table insertion: amortized analysis with aggregation and accounting method.<br/>
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17<br/>

Wednesday, March 7, 2018<br/>
   * Dynamic tables.<br/>
   * How to expand a table.<br/>
   * Tables expansion and contraction.<br/>
   * Binary search tree.<br/>
   * Visit a binary search tree.<br/>
   * Insertion and deletion in a binary search tree.<br/>
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17<br/>
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/>

Tuesday, March 13, 2018<br/>
   *  Avarage analysis of a sequence of insertion operations.<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/>
   *  Self-adjiusting trees.<br/>
   *  Splay operation.<br/>
Reference: 
Levitin A., "The design and analysis of algorithms", Chap.6.3<br/>
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/>
  
Wednesday, March 14, 2018
   *  Amortized analysis of a single splay step.<br/>
   *  Amortized analysis of a sequence of operations on a splay tree.<br/>
   *  Fibonacci Heaps (FH).<br/>
   *  Representation of Fibonacci Heaps.<br/>
   *  Comparing Heaps and Fibonacci Heaps.<br/>
   *  Insertion and deletion operations.<br/>
   *  Extracting the minimum.<br/>
   *  Decreasing a key  and deleting a node.<br/>
   *  Mergeable-heap operations.<br/>
   * Computing the amortized analysis of all the operations on a FH.<br/>
Reference: 
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/>
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19 <br/>

Tuesday, March 20, 2018
   *  Amortized analysis of a single splay step.<br/>
   *  Bounding the maximum degree in a FT.<br/>
   *  Dijkstra's algorithm for single source shortest paths.<br/>
   *  Definition of B-trees.<br/>
   *  B-tree's height.<br/>
   *  Insertion on a B-tree.<br/>
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.18, 19, 24.3

Wednesday, March 21, 2018
   *  Deleting a key from a B-tree.<br/>
   *  Data structure for disjoint sets.<br/>
   *  Quickunion trees.<br/>
   *  Quickfind trees.<br/>
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.18,21


Tuesday, March 27, 2018
   *  Balanced Quickunion trees.<br/>
   *  Balanced Quickfind trees.<br/>
   *  Euristics to improve running times. <br/>
   *  How to augment a data structures. <br/> 
   *  Management of the rank of an element on a AVL tree.<br/>
   *  Intervals and Interval trees.<br/>
   *  Search, insert and delete on an Interval tree.<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,21

Tuesday, March 27, 2018, afternoon 
   *  First partial examination.<br/>
    
 
Wednesday, March 28, 2018
   *  Maximal, maximum and perfect matching.
   *  Alternating and augmenting paths.
   *  XOR operator and its properties.
   *  The hungarian tree method for bipartite graphs.
   *  Blossom's contraction and expansion in general graphs.
   *  Algorithm fo finding maximum matching in a bipartite graph.
   *  Algorithm fo finding maximum matching in a general graph.
Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17

Wednesday, April 4, 2018 
   *  Exercizes .<br/>
    
Tuesday, April 10, 2018 
   *  Transportation networks. <br/>
   *   Flow on a  network. <br/>  
   *   Pushing flow on forward and backward edges.<br/>
   *   Augmenting path and bottleneck edges.<br/>
   *   Residual networks method.<br/>    
   *   Ford and Fulkerson' algorithm.<br/>    
 Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16.

Wednesday, April 11, 2018
   *  Complexity of 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/>
   *  Planar Graphs.<br/>
   *  Euler's formula.<br/>
   *  Kuratowski's theorem.<br/>
Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16, 17.3<br/>
Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.1.1-1.5<br/> 

Tuesday, April 17, 2018
   *  st-numbering.<br/> 
   *  Functions DFN, FATHER and LOW.<br/> 
   *  Function PATH.<br/> 
   *  Algorithm for st-numbering.<br/> 
Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.3.<br/>  

Wednesday, April 18, 2018
   *  Bush form.<br/>  
   *  PQ-tree.<br/>  
   *  Concurrent system vs sequential system.<br/>  
   *  Distributed system vs parallel system.<br/>  
   *  Synchronous and asynchronous systems .<br/>  
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1<br/>  
Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.3<br/>  

Thursday, April 19, 2018, afternoon 
   *  Second partial examination.<br/>

Wednesday, May 2, 2018
   *  P-RAM model.<br/> 
   *  Shared memory and concurrent write and read.<br/> 
   *  Speed up and Efficiency.<br/> 
   *  First half tecnique: compute the sum and find maximum.<br/>   
   *  EREW vs CREW: Broadcast on P-RAM.<br/>   
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1.<br/>   
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/>   

Tuesday, May 8, 2018
   *  Accelerated Cascading.<br/> 
   *  Interconnection Networks: Mesh, Binary Tree, Hypercube.<br/> 
   *  Broadcast on Mesh, Binary Tree and Hypercube.<br/>
   *  Prefix Sums on P-RAM shared memory.<br/>
   *  Prefix Sums on Mesh and Binary Tree. <br/> 
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2.<br/>   
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/>   

    
Wednesday, May 9, 2018
   *  Combinatorial Networks.<br/>
   *  Zero-One Principle.<br/>
   *  Bitonic Sequences.<br/>
   *  Bitonic Merge.<br/>
   *  Bitonic Sorting Networks.<br/>
   *  Brent's theorem on CREW and on EREW.<br/>
   *  Decreasing the number of processors.<br/>
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2,4.<br/>
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/> 

Tuesday, May 15, 2018
   *  Pointer jumping technique.<br/>
   *  List ranking.<br/>
   *  The Euler tour technique.<br/>
   *  Tree computations: rooting a tree, finding the root.<br/>
   *  Postorder and preorder numbering.<br/>
   *  Computing the vertex level.<br/>
   *  Different strategies for computing minimum spanning tree.<br/>
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.3,5.<br/>
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/> 


Wednesday, May 16, 2018
   *  Parallel implementation of Sollin's algorithm.<br/>
   *  Communication in distributed networks.<br/>
   *  General scheme of a distributed algorithm.<br/>  
   *  Broadcast on a distributed ring.<br/> 
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.5.<br/> 
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/> 

Tuesday, May 21, 2018
   *  Broadcast on a general network.<br/> 
   *  Broadcast with ECO.<br/>
   *  Leader election on a ring: n initializers.<br/> 
   *  Leader election on a ring: one initializer.<br/> 
   *  Leader election on a ring: k-neighbourly.<br/> 
Reference: Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/> 
Attiya H.,Welch J."Distributed Computing"Chap.3.<br/>    
    
Wednesday, May 23, 2018
   *  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" gallager.....pdf
 
Friday, May 25, 2018 
   *  Third partial examination.<br/> 

Tuesday, May 29, 2018 
   *  Closing of the Course.<br/>