Course: 587SM-2 - ALGORITHMIC DESIGN 2022

Section outline

Select section General

General

Collapse all Expand all
- Select activity Annunci
  
  Annunci Forum
Select section Introduction

Introduction
Basic info about the course, the study material, and the examination.
Recording on Teams, link: https://teams.microsoft.com/l/channel/19%3aTmj2Q_zNhYm_cOGzd3fm_RLH-SU8RzJw-EaY7v7vPpA1%40thread.tacv2/General?groupId=bfd0affb-649e-4559-9b73-b2a1114b6120&tenantId=a54b3635-128c-460f-b967-6ded8df82e75
You find the recordings in Files>Recordings>Solo visualizzazione.
Link to the document to choose the paper for your presentation: Paper_choice.xlsx
Link to the document to book a date for the examination AFTER YOU BOOKED AN OFFICIAL DATE IN ESSE3: Exam_Dates_Booking
The exam on the 13th of September will take place in room 4C of H2bis.
- Select activity Slides Introduction
  
  Slides Introduction File PDF
Select section Basics

Basics
Basic notions about algorithms and pseudocodes. Asymptotic complexity. Asymptotic notation.

Recording on Teams (team CD2022 587SM-2 ALGORITHMIC DESIGN ) or below:
- Select activity Slides Basics
  
  Slides Basics File PDF
- Select activity Exercises for Lecture 1
  
  Exercises for Lecture 1 File PDF
Select section Sorting: Insertion Sort, Merge Sort, Heap Sort

Sorting: Insertion Sort, Merge Sort, Heap Sort
- Select activity Insertion, Merge and Heap Sort
  
  Insertion, Merge and Heap Sort File PDF
- Select activity Exercises for Lecture 2
  
  Exercises for Lecture 2 File PDF
Select section Quicksort, Lower bounds on sorting, Counting Sort, Radix Sort

Quicksort, Lower bounds on sorting, Counting Sort, Radix Sort
- Select activity Sorting2
  
  Sorting2 File PDF
- Select activity Exercises for Lecture 3
  
  Exercises for Lecture 3 File PDF
- Select activity Exercises for Lecture 5
  
  Exercises for Lecture 5 File PDF
Select section Binary Search Trees, BST Sort, RB trees

Binary Search Trees, BST Sort, RB trees
- Select activity Exercises
  
  Exercises File PDF
- Select activity BTS_RBtrees
  
  BTS_RBtrees File PDF
Select section Matrix Multiplication and Hashing

Matrix Multiplication and Hashing
- Select activity 05_Strassen-Hashing
  
  05_Strassen-Hashing File PDF
- Select activity Strassen's original paper
  
  Strassen's original paper File PDF
Select section Amortised analysis and graph traversals

Amortised analysis and graph traversals
- Select activity Amortised analysis and graph traversals updated
  
  Amortised analysis and graph traversals updated File PDF
Select section Weighted graphs

Weighted graphs
- Select activity 07_weighted_graphs
  
  07_weighted_graphs File PDF
Select section Exam papers

Exam papers
This is a partial list of papers that are eligible for the presentation you have to prepare for the exam. You can either pick a paper from this list (I will set up a tool to associate people to papers in the next few days) or propose a paper yourself or ask me to find a paper on your preferred topic, as long as it is related to the topics of the course.
- Select activity 1.Cuckoo Hashing
  
  1.Cuckoo Hashing File PDF
- Select activity 2.Cuckoo Filter
  
  2.Cuckoo Filter File PDF
- Select activity 3.Simplified Cuckoo Filter
  
  3.Simplified Cuckoo Filter File PDF
- Select activity 4.Count min sketch
  
  4.Count min sketch File PDF
- Select activity 5.Set Sketching
  
  5.Set Sketching File PDF
- Select activity 6.Bloom Filter Replacement
  
  6.Bloom Filter Replacement File PDF
- Select activity 7.Resizable arrays until page12
  
  7.Resizable arrays until page12 File PDF
- Select activity 8.Soft Heaps
  
  8.Soft Heaps File PDF
- Select activity 9.Soft Heap Construction
  
  9.Soft Heap Construction File PDF
- Select activity 10.Soft Heaps Application until page16
  
  10.Soft Heaps Application until page16 File PDF
- Select activity 11.Antiperiods
  
  11.Antiperiods File PDF
- Select activity 12.Exact and Approximate Pattern Matching in the Streaming Model
  
  12.Exact and Approximate Pattern Matching in the Streaming Model File PDF
- Select activity 13.LCA revisited
  
  13.LCA revisited File PDF
- Select activity 14.Streaming Pattern-Matching
  
  14.Streaming Pattern-Matching File PDF
- Select activity 15.Weight Ancestors Suffix Tree
  
  15.Weight Ancestors Suffix Tree File PDF
- Select activity 16.FM Index
  
  16.FM Index File PDF
- Select activity 17.FM index revisited
  
  17.FM index revisited File PDF
- Select activity 18.DP RNA folding
  
  18.DP RNA folding File PDF
- Select activity 19.Omnitigs
  
  19.Omnitigs File PDF
- Select activity 20.Safely Filling Gaps
  
  20.Safely Filling Gaps File PDF
- Select activity 21.Dynamic APSP until page14
  
  21.Dynamic APSP until page14 File PDF
- Select activity 22.Fully dynamic APSP
  
  22.Fully dynamic APSP File PDF
- Select activity 23.Dynamic Shortest Path Algorithms for Hypergraphs
  
  23.Dynamic Shortest Path Algorithms for Hypergraphs File PDF
- Select activity 24.K Shortest Paths until page16
  
  24.K Shortest Paths until page16 File PDF
- Select activity 25.QuickHeapSort
  
  25.QuickHeapSort File PDF
- Select activity 26.QuickXsort
  
  26.QuickXsort File PDF
- Select activity 28.Path-length Distance
  
  28.Path-length Distance File PDF
- Select activity 29.Chromatic binary search trees
  
  29.Chromatic binary search trees File PDF
- Select activity 30.Red-Black trees constant update
  
  30.Red-Black trees constant update File PDF
- Select activity 31.AVL trees relaxed
  
  31.AVL trees relaxed File PDF
- Select activity 32.Suffix BST until page 13
  
  32.Suffix BST until page 13 File PDF
- Select activity 33.Suffix Trays
  
  33.Suffix Trays File PDF
- Select activity 34.Property matching
  
  34.Property matching File PDF
- Select activity 36.Bloomier filters
  
  36.Bloomier filters File PDF
- Select activity 37.Bloomier filters second look
  
  37.Bloomier filters second look File PDF
- Select activity 38.WhatsHap
  
  38.WhatsHap File PDF
- Select activity 39.RNA assembly
  
  39.RNA assembly File PDF
Select section Instructions and tips for the examination

Instructions and tips for the examination
- Select activity EXAM
  
  EXAM File PDF
Select section Exact pattern marching

Exact pattern marching
- Select activity 08 Exact Pattern Matching1
  
  08 Exact Pattern Matching1 File PDF
- Select activity Boyer-Moore
  
  Boyer-Moore File PDF
- Select activity 09 Exact Pattern Matching2
  
  09 Exact Pattern Matching2 File PDF
- Select activity Gusfield suffix array
  
  Gusfield suffix array File PDF
- Select activity Gusfield suffix tree definition
  
  Gusfield suffix tree definition File PDF
- Select activity 10 SuffixTree
  
  10 SuffixTree File PDF
Select section Sample Presentation

Sample Presentation
- Select activity Sample paper
  
  Sample paper File PDF
- Select activity Sample presentation
  
  Sample presentation File PDF