Analysis of Algorithms

Year
3
Academic year
2018-2019
Code
01001387
Subject Area
Computation
Language of Instruction
Portuguese
Mode of Delivery
Face-to-face
Duration
SEMESTRIAL
ECTS Credits
6.0
Type
Elective
Level
1st Cycle Studies

Recommended Prerequisites

Programming methods I, II and Logic.

Teaching Methods

Traditional classes with chalkboard. Every once in a while, an implementation will be presented due to the effort of a particular student who shows special interest in the practical accomplishment of the knowledge transmitted.

Further influence that can still be exerted by commitment in classroom: problem solution (homework) proposed and suggested but not compulsory.

Learning Outcomes

Learn different computational abstract models, such as RAM, RASP, and k-tape Turing Machine, and translate programs between these models.

Study complexities, mainly time complexities but also space and algorithm complexities.

Learn how to use data structures suitable for an efficient implementation of algorithms.

Learn the importance of the relative efficiency of a program.

Informal study of programs correction.

Ability to develop estimates for recursive formulae.

Polynomial and intractable problems.

Many algorithms for ordering lists and whole numbers following different criteria and specifications.

Algorithms for finding shortest paths, generating trees, performing the union of lists, etc.

 

Furthermore, we will expect a further development of certain generic competences that are essential to the study of Mathematics, such as:

Capacity for generalization and abstraction;

Capacity for formulating and solving problems;

Logical argumentation;

Critical thinking.

Work Placement(s)

No

Syllabus

The syllabus was already mentioned in p, since the syllabus is a subset of the objectives of the curricular unit and the competences that must be developed. A more comprehensive list of the syllabus can be found in the curricular unit summary.

Assessment Methods

Final Assessment
Exam 20 points: 100.0%

Continuous Assessment
2 4-points Mini-tests. 12-points Test: 100.0%

Bibliography

Aho, Hopcroft, Ullman, Design and Analysis of Algorithms, Addison Wesley 1974.

 

BAASE, S. and GELDER,A.Van.(2000). Computer Algorithms: Introduction to Design and Analysis.3rd Ed. Addison-Wesley.

 

WEISS, C, M.A. (1997). Data Structures and Algorithm Analysis. 2nd Ed.Addison-Wesley.