Advanced Algorithms

Academic Year 2016/2017 - Spring semester

Prof.ssa Rossella Petreschi

News

Next exam: September 19th, Via Salaria 113 , Aula seminari, third floor, 9 a.m.
The last lesson will take place on May 18th and the last written partial examination will be conducted on next May 19th at 'Aula Oriana', via Salaria 113, ground floar.

Prof. Petreschi will communicate the results of the partial examination on Monday May 29th, from 9 a.m. to 12 a.m., in her office (via Salaria 113, third floar). Together with the results of the partial examination, Prof. Petreschi will propose to each student who has participated at the interim tests either a final evaluation or the request for a final partial examination on some specific topics.

For all the other students who did not take part to the interim tests, the written exams remain fixed for
Thursday June 8th Aula seminari, 9-13.
Monday July 3rd Aula seminari, 9-13.

Wednesday April 26 the lesson will not take place.

Wednsday March 15 the lessons will not take place due to the event "Open DI".

Thursday March 16 and Thursday March 23 the lessons will be at 14.00 in Aula Seminari,Via Salaria 113, third floor.

First lesson: Wednesday February 22 at 14.00 in Aula Alfa - Via Salaria,113.

Timetable

When: Wednesday 14.00 - 16.00 and Thursday 14.00 - 16.00.
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_2016-2017.docx: Program 2016-2017

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 10, April 7, April 28, May 19, Room: Aula seminari, third floor.
2) by taking an examination on the whole program from the end of the course on.
Dates of option 2: June 8th, July 3rd, September 19th, Room: Aula seminari, third floor, 9 a.m.

Lessons

Wednesday, February 22, 2017
  • Amortized Analysis.
  • Aggregation, accounting and potential methods.
  • Operations on stack.
  • The increement of a binary counter
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17

Thursday, February 23, 2017

  • Dynamic tables.
  • How to expand a table.
  • Tables expansion and contraction.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.17

Wednesday, March 1, 2017

  • Binary search tree.
  • Visit a binary search tree.
  • Insertion and deletion in a binary search tree.
  • Analysis of a binary search tree insertions.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.12
Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7

Thursday, March 2, 2017

  • 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.
Reference: Levitin A., "The design and analysis of algorithms", Chap.6.3

Wednesday, March 8, 2017

  • Self-adjiusting trees.
  • Splay operation.
  • Make a binary search tree a splay tree.
  • Amortized analysis of a single splay step.
  • Amortized analysis of a sequence of operations on a splay tree.
Reference: Kingston J.K., "Algorithms and data Structures: Design, Correctness, Analysis", Chap.7

Thursday, March 9, 2017

  • Structure of Fibonacci heaps (FH).
  • Inserting an element in a FH.
  • Decreasing a key in a FH.
  • Deleting a node in a FH.
  • Mergeable-heap operations.
  • Computing the amortized analysis of all the operations on a FH.
  • Comparing heaps and Fibonacci heaps.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19

Friday, March 10, 2017

Thursday, March 16, 2017

  • Bounding the maximum degree in a FT.
  • Dijkstra's algorithm for single source shortest paths.
  • Answers to the questions in the first partial examination.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.19, 24.3

Wednesday, March 22, 2017

  • Definition of B-trees.
  • Basic operationson B-trees.
  • Deleting a key from a B-tree.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.18

Wednesday, March 29, 2017

  • Data structure for disjoint sets.
  • Quickunion and Balanced Quickunion trees.
  • Quickfind and Balanced Quickfind trees.
  • Euristics to improve running times.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.21

Thursday, March 30, 2017

  • Augmenting data structures.
  • Managment of the rank of an element.
  • How to augment a data structure.
  • Correctness of the interval search procedure.
Reference: Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., "Introduction to algorithms", Chap.14

Wednesday, April 05, 2017

  • Maximal, maximum and perfect matching.
  • Aletrnating and augmenting paths.
  • Maximum matching in general graphs.
Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17

Thursday, April 06, 2017

  • XOR operator and its properties.
  • The hungarian tree method for bipartite graphs.
  • Blossom's contraction in general graphs.
Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.17

Friday, April 7, 2017

Wednesday, April 12, 2017

  • Flow networks.
  • Residual networks method.
  • Augmenting path method.
  • Ford and Fulkerson' algorithm.
  • Max-flow and min-cut.
  • Networks with multiple sources and tails.
  • Bipartite graphs:matching and flow nwetwork.
Reference: Alsuwaiyel M.H. "Algorithms. Design Techniques and Analysis", Chap.16, 17.3

Wednesday, April 19, 2017

  • Planar Graphs.
  • Euler's formula.
  • Kuratowski's theorem.
  • st-numbering.
  • Functions DFN, FATHER and LOW.
Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.1.1-1.5, Chap.3.2

Thursday, April 20, 2017

  • Function PATH.
  • Algorithm for st-numbering.
  • Bush form.
  • PQ-tree.
Reference: Nishizeki T., Chiba N., "Planar graphs:theory and algorithms" Chap.1.1-1.5, Chap.3.2

Thursday, April 27, 2017

  • Concurrent system vs sequential system.
  • Distributed system vs parallel system.
  • Synchronous and asynchronous systems .
  • Shared memory and concurrent write and read.
  • General scheme of a distributed algorithm.
  • Broadcast on a distributed ring.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1.1-1.2
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.1,2; 12.5.1-5.4

Friday, April 28, 2017

Wednesday, May 3, 2017

  • Interconnection networks.
  • Broadcast on P-RAM, Mesh and Binary Tree.
  • EREW vs CREW .
  • Sum on P-RAM, Mesh and Binary Tree.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.1.3
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.4

Thursday, May 4, 2017

  • Accelerated Cascading.
  • Broadcast with Echo.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2.6
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.2-12.5

Wednesday, May 10, 2017

  • Pointer Jumping Tecnique.
  • List ranking.
  • Prefix Sums.
  • Sorting Networks.
  • Bitonic Sequences.
  • Zero-One Principle.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.2.2,3.1
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.2,3

Thursday, May 11, 2017

  • Bitonic Merge.
  • Bitonic Sorting Networks.
  • Brent's theorem on CREW and on EREW.
  • Decreasing the number of processors.
  • Leader election on a ring: n initializers.
  • Leader election on a ring: one initializer.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.4.4
Johnsonbaugh R.,Schaefer M. "Algorithms" Chap.12.3, 12.5

Wednesday, May 17, 2017

  • Parallel Minimum Spanning Tree.
Reference: Jaja J., "An Introduction to Parallel Algorithms" Chap.5.1-2

Thursday, May 18, 2017

  • 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
Zomaya A.Y.H., "Parallel and distributed computing handbook" Chap. 5.3.3.2.

Friday, May 19, 2017

This topic: AA > WebHome > AdvancedAlgorithms_2016_17
Topic revision: r41 - 2018-02-05 - 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