Advanced Topics in Algorithms

Code:

CC445

Acronym:

CC445

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2010/2011 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~ap/taa/1011/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master's Degree in Network and Information Systems Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	13	PE do Mestrado em Ciência de Computadores	1	-	7,5	67	202,5
MI:ERS	2	Plano de Estudos a partir de 2007	4	-	7,5	67	202,5

Teaching language

Portuguese

Objectives

Understanding the relationships among the design, correctness proof and runtime analysis of algorithms.

Learning generic techniques useful to implement new algorithms.

Knowing the major algorithms in some specific domains.

Experiencing in practice how to apply generic algorithms to specific problems.

Program

Fundamentals of runtime analysis of algorithms, amortized analysis
Divide and conquer, recurrences
Randomized algorithms
Linear sorting and selection
Universal and perfect hashing
Dynamic programming and greedy algorithms
Multithreaded algorithms
String matching

Mandatory literature

000102107. ISBN: 9780262033848

Teaching methods and learning activities

There is a weekly lecture exposing the course material.

Each week a few exercises and problems are proposed, whose solutions by the students are presented and discussed in the following weekly discussion class.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	67,50
1st Test	Exame	1,50		2011-03-30
2nd Test	Exame	1,50		2011-04-27
3ed Test	Exame	1,50		2011-05-25
Exam	Exame	2,50
	Total:	-	0,00

Eligibility for exams

A minimum global grade of 8 in the training (see below) is mandatory.

Calculation formula of final grade

There are two evaluation components: training and submission.

The final grade is ( 80% training + 20% submission ).

Training:
- consists in the individual resolution of the weekly proposed exercises/problems (12 weeks);
- is individually evaluated, in each discussion class, with 0 (null), 1 (weak), 2 (satisfactory) or 3 (good).
- results in a global average grade of the 8 best (of the maximum 12) elements, normalized to 20 (the minimum of 8 is mandatory for approval in the course).

Submissions:
- there are 3 tests and one exam;
- the provisional grade takes the average of the 3 tests as the submission grade;
- positive (>= 10) provisional grade allows the waiving of the exam;
- going to exam, the submission grade is that of the exam if better than the test average, otherwise the two are averaged (with approval guaranteed if so did the provisional grade).

Special assessment (TE, DA, ...)

A working student may decide, at the start of the semester, to be evaluated just by exam, without training and its minimum grade.

In that case the final grade is just that of the exam.

Classification improvement

Raising a previously obtained grade is obtained solely and directly through exam.

After approval in the regular exam period, the final grade can be raised with the recourse exam, its grade replacing that of the regular exam in the formula.