2014 - 2015

0510-6401-01
  Design and Analysis of Algorithms                                                                    
FACULTY OF ENGINEERING
Prof. Dana Ron-GoldreichEngineering Studies - Classrooms205Mon1600-1900 Sem  2
 
 
University credit hours:  3.0

Course description
Credits: 3
Prerequisites: Data Structures and Algorithms
 
This course aims at two targets. One is to get the students acquainted with a selection of advanced techniques in algorithmic theory, and the other is to let the students experience what is the spirit in contemporary algorithmic research. Namely, what problems are considered interesting, and how to evaluate possible solutions
 
The course will include topics from the following list: (1) Approximation background: Decision and optimization problems, NP Hardness, approximation algorithm, approximation scheme. (2) Basic approximation algorithms: load balancing, vertex and set cover, traveling salesman, subset sum, knapsack. (3) Randomized algorithms: the probabilistic method with applications to max-cut and max-SAT; randomized rounding; random sampling. (4) Online problems: ski rentals, self-organizing lists, best-expert and bandit, paging, load balancing, call admission in communication networks. (5) Distributed and parallel computation: models and algorithms. Algorithms include Bellman-Ford, maximal independent set, prefix sums, minimum spanning tree.

accessibility declaration


tel aviv university