Advanced Algorithms

Academic Year 2018/2019 - Spring semester

Prof.ssa Rossella Petreschi

News

IMPORTANT:

The lesson on next May 14th will be the last of the course.
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.
Students will have the choice to either complete the partial tests (total number of partial tests is 4) or to present the whole program.
It is required to pre-inform via e-mail on which date and which type of proof it is intended to take part.
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.
The program consists in all the arguments discussed during the lessons (see all the details on the twiki page of the Course).
The topics of each partial tests are the following:

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

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

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

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

First lesson:
Tuesday February 26 at 8.00 in Aula Alfa - Via Salaria,113.

Timetable

When:
Tuesday 08.00 - 10.30
Wednesday 08.00 - 10.30.

Where:
Aula Alfa - Via Salaria,113, ground floor.

Office Hours

By appointment
Office: Via Salaria, room 341/a, third floor. Phone: 06 - 4991 8511.
E-mail: petreschi AT di.uniroma1.it

Aim of the course

The course presents algorithms and data structures that are used in the efficient resolution of important applied problems.
Particular interest is focused on the design of algorithms that operate on parallel architectures.

Prerequisites

It is assumed that students have knowledge of all topics covered during the bachelor program about algorithms.

Exams

The exam consists of a written test regarding themes covering the full course program.
The exam can be taken in two ways:

1) by taking partial examinations at the end of each course section;
Dates of option 1: March 21, April 11, May 9, May 21, Via Salaria, third floor

2) by taking an examination on the whole program from the end of the course on.
Dates of option 2:

2019 June 11, 9-12, Aula riunioni, Via Salaria,third floor;
2019 July 5, 14-17, Aula riunioni, Via Salaria,third floor;
2019 September 15, 9-12, Aula riunioni, Via Salaria,third floor;

2020 January: by appointment.
2020 February: by appointment.

Lessons

Tuesday, February 26 2019
  • Amortized Analysis.
  • Aggregation, accounting and potential method.
  • Operations on stack.
  • The increment of a binary counter.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17

Wednesday, February 27 2019

  • Dynamic tables.
  • Table insertion: amortized analysis with aggregation and accounting method.
  • Load factor and potential function.
  • How to expand a table: amortized analysis with potential method.
  • 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

Tuesday, March 12 2019

  • Binary search tree.
  • Visit a binary search tree.
  • Insertion and deletion in a binary search tree.
  • Avarage analysis of a sequence of insertion operations.
  • Balanced search trees.
  • AVL trees.
  • The height of an AVL tree is logarithmic.
Reference: Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7
Levitin A., "The design and analysis of algorithms", Chap.6.3
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.6

Wednesday, March 13 2019

  • 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
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.6

Thursday, March 14 2019

  • 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
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.8

Tuesday, March 19 2019

Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19,21
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.8,9

Wednesday, March 20 2019

  • 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
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.9

Thursday, March 21 2019

  • First partial examination.

Tuesday, March 26 2019

  • 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
Demetrescu C., Finocchi I.,Italiano G.F., "Algoritmi e Strutture Dati",Chap.5

Wednesday, March 27 2019

  • 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

Tuesday, April 2 2019

  • 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
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7

Wednesday, April 3 2019

  • 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
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7
Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17

Thursday, April 4 2019

  • 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

  • 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

  • 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

  • Second partial examination.

Tuesday, April 16 2019

  • 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
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.11

Wednesday, April 17 2019

  • 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

  • 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.
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.

Wednesday, May 8 2019

  • 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.
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.

Thursday, May 9 2019

  • Third partial examination

Tuesday, May 14 2019

  • 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.
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.

Tuesday, May 21 2019

  • 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.

Edit | Attach | Watch | Print version | History: r36 < r35 < r34 < r33 < r32 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r36 - 2019-07-09 - RossellaPetreschi





 
ATTENZIONE: per lavori ACEA sulla cabina elettrica il server resterā spento
nei giorni 19-22 agosto.
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback