COURSE INFORMATION Course Title: RANDOMIZED ALGORITHM

Code	Course Type	Regular Semester	Theory	Practice	Lab	Credits	ECTS
CEN 514	B	99	3	2	0	4	7.5

Language:	English
Compulsory/Elective:	Elective
Classroom and Meeting Time:
Course Description:	The course has two main themes. The first theme is basic tools from probabilisticanalysis that are recurrent in algorithmic applications. The second theme is specific areas ofapplication. Tools will be interleaved with applications that illustrate them in concrete settings.
Course Objectives:	The course has two main themes. The first theme is basic tools from probabilistic analysis that are recurrent in algorithmic applications. The second theme is specific areas of application. Tools will be interleaved with applications that illustrate them in concrete settings. This course aims to confer: (1) some familiarity with several of the main thrusts of work in randomized algorithms—giving you context for formulating and seeking known solutions to an algorithmic problem; (2) background and facility to read current research publications in the area of algorithms; and (3) a set of tools for design and analysis of new algorithms for new problems that you encounter.

COURSE OUTLINE

Week	Topics
1	Introduction and administrivia
2	Game tree evaluation. The minimax principle. Randomness and non-uniformity.
3	Moments and deviations.
4	Tail inequalities
5	The probabilistic method
6	Markov chains and random walks
7	Data structures
8	Midterm
9	Geometric algorithms
10	Graph algorithms
11	Approximate counting
12	Online algorithms
13	Information theory
14	Course overview

Prerequisite(s):
Textbook:	Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
Other References:
Laboratory Work:	Yes
Computer Usage:	Yes
Others:	No

COURSE LEARNING OUTCOMES

1	Analyze and develop an ability to develop and implement appropriate algorithms
2	Understand the strengths and requirements of probabilistic approach

COURSE CONTRIBUTION TO... PROGRAM COMPETENCIES (Blank : no contribution, 1: least contribution ... 5: highest contribution)

No	Program Competencies	Cont.
Professional Master in Computer Engineering Program

COURSE EVALUATION METHOD

Method	Quantity	Percentage
Midterm Exam(s)	1	40
Quiz	2	10
Final Exam	1	40
	Total Percent:	100%

ECTS (ALLOCATED BASED ON STUDENT WORKLOAD)

Activities	Quantity	Duration(Hours)	Total Workload(Hours)
Course Duration (Including the exam week: 16x Total course hours)	16	5	80
Hours for off-the-classroom study (Pre-study, practice)	16	5	80
Mid-terms	1	12	12
Assignments			0
Final examination	1	15.5	15.5
Other			0
Total Work Load:			187.5
Total Work Load/25(h):			7.5
ECTS Credit of the Course:			7.5