Advanced Algorithms

Academic Year 2018/2019 - Spring semester

Prof.ssa Rossella Petreschi

News

No classes will be held from April 18 to May 6.
From May 7, classes will start again as usual.

Third partial examination:
May 9 at 11 in Aula Seminari - Via Salaria,113, third floor.

Second partial examination:
April 11 at 10.00 in Aula Riunioni - Via Salaria,113, third floor.

Extra classes:

  • April 4 at 11.00 in Aula Seminari - Via Salaria,113, third floor.
  • May 9 at 11.00 in Aula Riunioni - Via Salaria,113, third floor.

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)

No classes will be held on these days: March 5 and 6.
From March 12, classes will start again as usual.

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 , 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
2020 January
2020 February

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.

Edit | Attach | Watch | Print version | History: r25 < r24 < r23 < r22 < r21 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r25 - 2019-04-17 - RossellaPetreschi





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
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