Skip to content

Latest commit

 

History

History

Advanced Algorithms and Parallel Programming

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

Advanced Algorithms and Parallel Programming

Main lectures topics:

Part I

  • Course Objectives and Introduction

  • Randomized algorithms: Las Vegas and Monte Carlo algorithms. Analyzing Randomized algorithms.

  • Hiring Problem and Generating Random Permutations.

  • Randomized Quicksort. Worst-case analysis. Average-case analysis.

  • Karger’s Min-Cut Algorithm. Faster version by Karger and Stein.

  • Randomized data structures: Skip Lists, Treaps.

  • Dynamic Programming: Memoization. Examples of Dynamic Programming: String Matching, BDDs, etc.

  • Amortized Analysis: Dynamic tables, Aggregate method, Accounting method and Potential method.

  • Approximate programming.

  • Competitive Analysis Self-organizing lists Move-to-front heuristic.

Part II

  • Design of Parallel Algorithms - Parallel Algorithms and Parallel Programming.

  • Parallel patterns: Map, Reduce, Scan, Mapreduce, Kernel Fusion, etc.

  • Tools and languages for parallel programming: Posix Threads, OpenMP, Message Passing Interface, CUDA.

  • Comparison of Parallel Programing Technologies.

  • Optimizing and analyzing parallel performance.

  • Examples of Parallel Algorithms.