COURSE INFORMATION Course Title: DESIGN AND ANALYSIS OF ALGORITHMS

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

Academic staff member responsible for the design of the course syllabus (name, surname, academic title/scientific degree, email address and signature)	NA
Lecturer (name, surname, academic title/scientific degree, email address and signature) and Office Hours:	Enea Mançellari , 09:00 - 11:00
Second Lecturer(s) (name, surname, academic title/scientific degree, email address and signature) and Office Hours:	NA
Teaching Assistant(s) and Office Hours:	NA
Language:	English
Compulsory/Elective:	Elective
Classroom and Meeting Time:	E-012
Course Description:	-
Course Objectives:	This course explores the analysis of algorithms and the relevance of analysis to the design of efficient computer algorithms.

COURSE OUTLINE

Week	Topics
1	Asymptotic notation Recurrences
2	Recurrences (con't.) Recursion tree method Master method Divide and Conquer: Mergesort
3	Divide and Conquer (con't.): Strassen's Matrix Mult. Alg. Polynomial Multiplication
4	Fast Fourier Transforms Introduction to Dynamic Programming
5	Dynamic Programming (con't.): Assembly-line scheduling Matrix-chain multiplication Elements of dynamic programming
6	Dynamic Programming (con't.): Memoization Longest common subsequence Optimal binary search trees
7	Dynamic Programming (con't.): All-pairs shortest path
8	MIDTERM EXAM
9	Greedy Algorithms: Overview Activity Selection Huffman Codes
10	Greedy Algs (con't.): Single-Source Shortest Paths Dijkstra's Alg.
11	Background for complexity Complexity class NP
12	Polynomial-time Polynomial-time verification
13	NP-completeness proofs and NP-complete problems SAT, 3-CNF
14	NP-completeness (con't.): Ham-Cycle, Traveling Salesman, Subset-Sum

Prerequisite(s):	Students should have a solid background in fundamental algorithms and data structures and discrete mathematics . This background should include a working knowledge of sorting techniques, stacks, queues, lists, hash tables, heaps, B-trees, binary search trees, red-black trees, recursion, set theory, graph theory, counting and probability theory, basic calculus, and proofs by mathematical induction.
Textbook:	Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest, and Stein, published by McGraw-Hill.
Other References:
Laboratory Work:	Yes
Computer Usage:	YES
Others:	No

COURSE LEARNING OUTCOMES

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

No	Program Competencies	Cont.
Doctorate (PhD) in Computer Engineering Program
1	Engineering graduates with sufficient theoretical and practical background for a successful profession and with application skills of fundamental scientific knowledge in the engineering practice.	5
2	Engineering graduates with skills and professional background in describing, formulating, modeling and analyzing the engineering problem, with a consideration for appropriate analytical solutions in all necessary situations	5
3	Engineering graduates with the necessary technical, academic and practical knowledge and application confidence in the design and assessment of machines or mechanical systems or industrial processes with considerations of productivity, feasibility and environmental and social aspects.	5
4	Engineering graduates with the practice of selecting and using appropriate technical and engineering tools in engineering problems, and ability of effective usage of information science technologies.	5
5	Ability of designing and conducting experiments, conduction data acquisition and analysis and making conclusions.	5
6	Ability of identifying the potential resources for information or knowledge regarding a given engineering issue.	5
7	The abilities and performance to participate multi-disciplinary groups together with the effective oral and official communication skills and personal confidence.	5
8	Ability for effective oral and official communication skills in foreign language.	5
9	Engineering graduates with motivation to life-long learning and having known significance of continuous education beyond undergraduate studies for science and technology.	5
10	Engineering graduates with well-structured responsibilities in profession and ethics.	5
11	Engineering graduates who are aware of the importance of safety and healthiness in the project management, workshop environment as well as related legal issues.	5
12	Consciousness for the results and effects of engineering solutions on the society and universe, awareness for the developmental considerations with contemporary problems of humanity.	5

COURSE EVALUATION METHOD

Method	Quantity	Percentage
Homework	6	5
Midterm Exam(s)	1	20
Project	1	20
Final Exam	1	30
	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	4	16
Mid-terms	1	7.5	7.5
Assignments	6	6	36
Final examination	1	8	8
Other	3	8	24
Total Work Load:			187.5
Total Work Load/25(h):			7.5
ECTS Credit of the Course:			7.5