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

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






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

The lesson on next May 14th will be the last of the course.<br />
On June 11th, from 9 a.m. to 1 p.m. OR on July 5th, from 2 p.m. to 6 p.m.,  in Room Riunioni, Via Salaria 113, final written exams will take place.<br /> 
Students will have the choice to either complete the partial tests (total number of partial tests is 4) or to present the whole program.<br />
It is required to pre-inform via e-mail on which date and which type of proof it is intended to take part.<br />  
Instead, for students who will register for the exams scheduled from September to February, the final written exam will be only on the whole program.<br />
The program consists in all the arguments discussed during the lessons (see all the details on the twiki page of the Course).<br />
The topics of each partial tests are the following:<br />

   * Test 1: From amortized analysis to fibonacci trees. (from February 26 to March 19)<br />
   * Test 2: From union-find algorithms to B-tree (from March 19 to April 3)<br />
   * Test 3: From matching to planar graphs( from April 3 to April 17) <br />
   * Test 4: Parallel and Distributed algorithms ( from May 7 to May 14)<br />





*Third partial examination*:<br /> 
May 9 at 11 in Aula Seminari - Via Salaria,113, third floor. <br />
*Results*:<br /> 	
1667647:	   40 (10+10+10+10) <br /> 
1772138:	   27 (10+2+10+5) <br /> 
1772090:	   16 (0+10+4+2) <br />


*Second partial examination*:<br /> 
April 11 at 10.00 in Aula Riunioni - Via Salaria,113, third floor. <br />
*Results*:<br /> 				
1667647:	   40 (10+10+10+10) <br /> 
1619664:	   37 (10+8+10+9) <br /> 
1350084:	   17 (7+3+0+7) <br /> 
1772487:	   19 (5+5+2+7) <br /> 
1772138:	   32 (10+7+5+10) <br /> 
1772848:	   37 (10+7+10+10) <br /> 
1772090:	   23 (10+5+5+3) <br /> 






*First partial examination*:<br /> 
March 21 at 11.00 in Aula Seminari - Via Salaria,113, third floor. <br />
*Results*:<br /> 				
1667647:	   37 (10+7+10+10) <br /> 
1619664:	   29 (10+10+7+2) <br /> 
1516792:	   22 (5+2+5+10) <br /> 
1350084:	   20 (5+0+5+10) <br /> 
1772487:	   19 (10+0+5+4) <br /> 
1772138:	   17 (2+4+1+10) <br /> 



*First lesson*: <br />
Tuesday February 26 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"> *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 21, April 11, May 9, May 21,   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 />

                             2019 June  11,   9-12, Aula riunioni, Via Salaria,third floor;<br />
                             2019 July     5, 14-17, Aula riunioni, Via Salaria,third floor;<br />  
                             2019 September  19, 9-12, Aula riunioni, Via Salaria,third floor;<br />  
                             
                             2020 January: by appointment. <br />  
                             2020 February: by appointment. <br />     


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

*Wednesday*, *February 27 2019* <br/>
   * Dynamic tables.<br/>
   * Table insertion: amortized analysis with aggregation and accounting method.<br/>
   * Load factor and potential function.<br/>
   * How to expand a table: amortized analysis with potential method.<br/>
   * How to contract a table: amortized analysis with potential method.
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17<br/>

*Tuesday*, *March 12 2019* <br/>
   * Binary search tree.<br/>
   * Visit a binary search tree.<br/>
   * Insertion and deletion in a binary search tree.<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.
Reference:      
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/>
Levitin A., "The design and analysis of algorithms", Chap.6.3<br/>
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.6<br/> 
    
*Wednesday*, *March 13 2019* <br/>
   * Rotations on a AVL tree.
   * Insertion and deletion in an AVL tree.
   * Self-adjiusting trees.
   * Splay operation.
   * Amortized analysis of a single splay step.
   * Amortized analysis of a sequence of operations on a splay tree.
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/>
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.6<br/>

*Thursday*, *March 14 2019* <br/>
   * Fibonacci Heaps (FH).
   * Representation of Fibonacci Heaps.
   * Comparing Heaps and Fibonacci Heaps.
   * Insertion and deletion operations.
   * Extracting the minimum.
   * Decreasing a key and deleting a node.
   * Mergeable-heap operations.
   * Computing the amortized analysis of all the operations on a FH.
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19<br/> 
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.8<br/>

*Tuesday*, *March 19 2019* <br/>
   * Bounding the maximum degree in a FT.
   * Dijkstra's algorithm for single source shortest paths.
   * QuickUnion trees.
   * QuickFind trees.
   * Balanced QuickUnion trees.
   * Balanced QuickFind trees.
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19,21<br/> 
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.8,9<br/>

*Wednesday*, *March 20 2019* <br/>
   * Euristics to improve running times. 
   * Union for compressed ranks in amortized time O(m+nlogn). 
   * Union for compressed ranks in amortized time O((n+m)log*n). 
   * Exercizes. 
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.21<br/> 
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.9<br/>

*Thursday*, *March 21 2019* <br/>
   * First partial examination.

*Tuesday*, *March 26 2019* <br/>
   * Randomized array-partition.
   * Randomized quick-sort.
   * Randomized selection.
   * Selection in worst case linear time.
   * Rank of an element on a AVL tree.
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.9, 14<br/> 
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.5<br/>

*Wednesday*, *March 27 2019* <br/>
   * Management of the size of an element on a AVL tree.
   * Intervals and Interval trees.
   * Search, insert and delete on an Interval tree.
   * Correctness of the interval search procedure.
Reference:
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.14<br/> 

*Tuesday*, *April 2  2019* <br/>
   * Definition of 2/3-trees.
   * 2/3-tree's height.
   * Insertion on a 2/3-tree.
   * Deletion on a 2/3-tree.
   * Definition of B-trees.
   * B-tree's height.
   * Extremal B-trees.    
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.18<br/>
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/>

*Wednesday*, *April 3  2019* <br/> 
   * Insertion on a B-tree.
   * Deleting a key from a B-tree.
   * Maximal, maximum and perfect matching.
   * Alternating and augmenting paths.
   * XOR operator and its properties. 
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.18<br/>
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7<br/>
Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17<br/>  
 
*Thursday*, *April 4 2019* <br/> 
   * 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 


*Tuesday*, *April 9 2019* <br/> 
   * Transportation networks.
   * Flow on a network.
   * Pushing flow on forward and backward edges.
   * Augmenting path and critical edges.
   * Residual networks method is correct.
   * Complexity of Ford and Fulkerson' algorithm.
   * Max-flow and min-cut.
Reference: 
Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16.

        
*Wednesday*, *April 10, 2019* <br/>
   * Ford and Fulkerson' algorithm.
   * Distances Lemma.
   * Complexity of Ford and Fulkerson' algorithm.
   * Networks with multiple sources and tails.
   * Bipartite graphs:matching and flow nwetwork.
   * Exercizes.   
Reference: 
Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16,17.    

*Thursday*, *April 11 2019* <br/>
   * Second partial examination. 

*Tuesday*, *April 16 2019* <br/> 
   * Relations and Graphs. 
   * Properties of relations. 
   * Partial order on a digraph. 
   * Topological sort.
   * Strongly connected components. 
   * Biconnected components.
Reference: 
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.22<br/>
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.11<br/>

 *Wednesday*, *April 17 2019* <br/> 
   * Planar Graphs.    
   * Euler's formula.
   * Kuratowski's theorem.
   * st-numbering.
   * Functions DFN, FATHER and LOW.
   * Function PATH.
   * Algorithm for st-numbering.
   * Bush form.
   * PQ-tree.

Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.3.

 *Tuesday*, *May 7 2019* <br/> 
   * Concurrent system vs sequential system.
   * Distributed system vs parallel system.
   * Synchronous and asynchronous systems .
   * P-RAM model.
   * Shared memory and concurrent write and read.
   * Communication in distributed networks.
   * The importance of the number of messages.
   * Speed up and Efficiency of a parallel algorithm. 
   * EREW vs CREW: Broadcast on P-RAM.
   * Interconnection Networks: Mesh, Binary Tree, Hypercube.
   * Broadcast on Mesh, Binary Tree and Hypercube.
     
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1,2.<br/>
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/>

 
  *Wednesday*, *May 8 2019* <br/>
   * General scheme of a distributed algorithm.
   * Broadcast on a distributed ring.
   * Broadcast on a general network.
   * Broadcast with ECO. 
   * First half tecnique: compute the sum  
   * Accelerated Cascading.
   
    
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1,2.<br/>
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.<br/>

   *Thursday*, *May 9 2019* <br/>
   * Third partial examination 

 *Tuesday*, *May 14 2019* <br/> 
   * Leader election on a ring: n initializers.
   * Leader election on a ring: one initializer.
   * Leader election on a ring: k-neighbourly.  
   * Combinatorial Networks.
   * Zero-One Principle.
   * Bitonic Sequences.
   * Bitonic Merge.
   * Bitonic Sorting Networks.
   * Brent's theorem on CREW and on EREW.
    

Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2,4, 3.5.<br/>
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.

*Tuesday*, *May 21 2019* <br/> 
   * Pointer jumping: Prefix Sums on P-RAM .
   * Prefix Sums on Mesh  
   * The Euler tour technique.
   * Tree computations: rooting a tree, finding the root.
   * Postorder numbering.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2,4, 3.5.<br/>