Computation II

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

General characterization

Code

100027

Credits

7.0

Responsible teacher

Mauro Castelli

Hours

Weekly - Available soon

Total - Available soon

Teaching language

Portuguese. If there are Erasmus students, classes will be taught in English

Prerequisites

  • Computer programming skills
  • Knowledge of probability
  • Basic knowledge in discrete mathematics

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: 70% test and 30% project (the same of the first epoch).

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.

Programs

Programs where the course is taught: