COURSE INFORMATION Course Title: ADVANCED ALGORITHMS & DATASTRUCTURES

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

Language:	English
Compulsory/Elective:	Elective
Classroom and Meeting Time:	E-012
Course Description:	An exploration of advanced algorithms in data structures using object-oriented design. An introduction to databases using Java. Course reviews main-memory data structures such as hash tables and trees. Disk-based structures such as persistent hash tables and indexed files. Architectural foundations for files, large scale sorting and serialization.
Course Objectives:	This course builds on the first-year Design and Analysis of Algorithms course. It introduces students to a number of highly efficient algorithms and data structures for fundamental computational problems across a variety of areas. Students are also introduced to techniques such as amortised complexity analysis. As in the first-year course, the style of the presentation is rigorous but not formal.

COURSE OUTLINE

Week	Topics
1	Intro. to Course and Review
2	Amortised analysis
3	Disjoint sets / union-find
4	Binary search trees
5	Mergeable heaps
6	Number theoretic algorithms + RSA
7	Fast Fourier transform
8	MIDTERM EXAM
9	Linear programming
10	Max flow in networks
11	String matching
12	Approximation algorithms
13	Stable matching
14	Stable matching cont

Prerequisite(s):	Analysis of Algorithms Data Structures
Textbook:	Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2009 (third edition).
Other References:	S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, Mcgraw-Hill, 2006. J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 2006.
Laboratory Work:	Yes
Computer Usage:	YES
Others:	No

COURSE LEARNING OUTCOMES

1	Be able to understand and apply amortised analysis on data structures, including binary search trees, mergable heaps, and disjoint sets.
2	Understand the implementation and complexity analysis of fundamental algorithms such as RSA, primality testing, max flow, discrete Fourier transform.
3	Have an idea of applications of algorithms in a variety of areas, including linear programming and duality, string matching, game-theory

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
Homework	5	5
Midterm Exam(s)	1	20
Project	1	20
Final Exam	1	35
	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	6	96
Hours for off-the-classroom study (Pre-study, practice)	4	7	28
Mid-terms	1	6.5	6.5
Assignments	5	7	35
Final examination	1	7	7
Other	3	5	15
Total Work Load:			187.5
Total Work Load/25(h):			7.5
ECTS Credit of the Course:			7.5