Computation II
Code
100027
Academic unit
NOVA Information Management School
Credits
7.0
Teacher in charge
Mauro Castelli
Teaching language
Portuguese. If there are Erasmus students, classes will be taught in English
Objectives
The main goal of this course is to study the fundamental techniques to design efficient algorithms and analyze their running time. After a brief review of prerequisite material (search, asymptotic notation), we will solve various problems through divide and conquer algorithms and greedy algorithms.
Upon completion of this course, students will be able to do the following:
- Analyze the asymptotic performance of algorithms.
- Demonstrate a familiarity with major algorithms and data structures.
- Apply important algorithmic design paradigms and methods of analysis.
- Synthesize efficient algorithms in common engineering design situations
Prerequisites
- Computer programming skills
- Knowledge of probability
- Basic knowledge in discrete mathematics
Subject matter
Basic strategies of algorithm design: top-down design, divide and conquer, average and worst-case criteria, asymptotic costs.
Simple recurrence relations for asymptotic costs.
Choice of appropriate data structures: arrays, lists, stacks, queues, trees, heaps, priority queues,trees.
Applications to sorting and searching, and spanning tree problems.
Introduction to discrete optimisation algorithms: dynamic programming, greedy algorithms.
Bibliography
Cormen, Thomas, Charles Leiserson, et al. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848
Teaching method
- Theoretical class where the professor will present the formal methods needed to analyze and build efficient algorithms.
- Practical classes where students will have the opportunity to test the performance of different algorithms for solving a set of tasks.
Evaluation method
First epoch: 70% test and 30% project.
Second epoch: 100% exam.