Advanced Algorithms

Academic Year 2017/2018 - Spring semester

Prof.ssa Rossella Petreschi

News

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

First lesson:
Tuesday March 6 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.

Program

* Program_AA_2017-2018.docx

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

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

Lessons

Tuesday, March 6, 2018
  • Amortized Analysis.
  • Aggregation, accounting and potential method.
  • Operations on stack.
  • The increment of a binary counter.
  • Table insertion: amortized analysis with aggregation and accounting method.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17

Wednesday, March 7, 2018

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

Tuesday, March 13, 2018

  • Avarage analysis of a sequence of insertion operations.
  • Balanced search trees.
  • AVL trees.
  • The height of an AVL tree is logarithmic.
  • Rotations on a AVL tree.
  • Insertion and deletion in an AVL tree.
  • Self-adjiusting trees.
  • Splay operation.
Reference: Levitin A., "The design and analysis of algorithms", Chap.6.3
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7

Wednesday, March 14, 2018

  • Amortized analysis of a single splay step.
  • Amortized analysis of a sequence of operations on a splay tree.
  • 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: Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7
Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19

Tuesday, March 20, 2018

  • Amortized analysis of a single splay step.
  • Bounding the maximum degree in a FT.
  • Dijkstra's algorithm for single source shortest paths.
  • Definition of B-trees.
  • B-tree's height.
  • Insertion on a B-tree.
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.
  • Data structure for disjoint sets.
  • Quickunion trees.
  • Quickfind trees.
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.
  • Balanced Quickfind trees.
  • Euristics to improve running times.
  • How to augment a data structures.
  • Management of the rank 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,21

Tuesday, March 27, 2018, afternoon

  • First partial examination.

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 .

Tuesday, April 10, 2018

  • Transportation networks.
  • Flow on a network.
  • Pushing flow on forward and backward edges.
  • Augmenting path and bottleneck edges.
  • Residual networks method.
  • Ford and Fulkerson' algorithm.
    Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16.

Wednesday, April 11, 2018

  • Complexity of Ford and Fulkerson' algorithm.
  • Max-flow and min-cut.
  • Networks with multiple sources and tails.
  • Bipartite graphs:matching and flow nwetwork.
  • Planar Graphs.
  • Euler's formula.
  • Kuratowski's theorem.
Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16, 17.3
Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.1.1-1.5

Tuesday, April 17, 2018

  • st-numbering.
  • Functions DFN, FATHER and LOW.
  • Function PATH.
  • Algorithm for st-numbering.
Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.3.

Wednesday, April 18, 2018

  • Bush form.
  • PQ-tree.
  • Concurrent system vs sequential system.
  • Distributed system vs parallel system.
  • Synchronous and asynchronous systems .
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1
Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.3

Thursday, April 19, 2018, afternoon

  • Second partial examination.

Wednesday, May 2, 2018

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

Tuesday, May 8, 2018

  • Accelerated Cascading.
  • Interconnection Networks: Mesh, Binary Tree, Hypercube.
  • Broadcast on Mesh, Binary Tree and Hypercube.
  • Prefix Sums on P-RAM shared memory.
  • Prefix Sums on Mesh and Binary Tree.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2.
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.

Wednesday, May 9, 2018

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

Tuesday, May 15, 2018

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

Wednesday, May 16, 2018

  • Parallel implementation of Sollin's algorithm.
  • Communication in distributed networks.
  • General scheme of a distributed algorithm.
  • Broadcast on a distributed ring.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.5.
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.

Tuesday, May 21, 2018

  • Broadcast on a general network.
  • Broadcast with ECO.
  • Leader election on a ring: n initializers.
  • Leader election on a ring: one initializer.
  • Leader election on a ring: k-neighbourly.
Reference: Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.
Attiya H.,Welch J."Distributed Computing"Chap.3.

Wednesday, May 23, 2018

  • Minimum Spanning Tree on a distributed system.
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.

Tuesday, May 29, 2018

  • Closing of the Course.


This topic: AA > WebHome > AdvancedAlgorithms_2017_18
Topic revision: r30 - 2018-05-29 - RossellaPetreschi
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback