Analysis and Design of Algorithms (ADA)

This subject provides students with basic algorithmic techniques in order for them to be able to develop correct and efficient programs for solving advanced problems. These basic techniques encompass theoretical and practical knowledge, skills, experience and a critical mindset, all of which are based on solid theories and techniques that have been proven and are well-established.

Knowledges

1. Analysis of algorithms: efficiency, costs, cases, asymptotic notation, solution of simple recurrences.
2. Data structures: Priority queues, dictionaries, graphs.
3. Algorithm schemes: Divide and conquer algorithms, greedy algorithms, exhaustive search algorithms, dynamic programming.
4. Basic algorithms: Ordering, shortest paths, tree expansion.

Abilities

1. Familiarisation with some of the basic techniques for designing and analyzing algorithms and data structures.
2. Acquire the methodology for drawing up a specification and identifying ADT use, design and ADT implementation.
3. Know-how in the use of various efficient data-structuring techniques.
4. Knowledge of generic ADT techniques, and how to use and modify them to yield the solutions required.
5. Know-how in checking the correctness and efficiency of ADT implementations and the algorithms which they employ.
6. Criteria for choosing the most appropriate design and implementation options during the specification stage, and the ability to set forth a reasoned argument for the choices made.
7. Knowledge of some of the classic algorithms for dealing with basic problems.
8. Knowing how to adapt general algorithmic schemes to solve problems.

Competences

1. Critical, logical-mathematical reasoning.
2. Ability to solve problems through the application of scientific and engineering methods.
3. Ability to design systems, components and processes meeting certain needs, using the most appropriate methods, techniques and tools in each case.
4. Ability to think in abstract terms. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.
5. Know-how to apply the solution cycle to common scientific and engineering problems: specification, coming with ideas and alternatives, design solution strategies, carrying out the strategy, validation, interpretation and evaluation of results. Ability to analyse the process on completion.
6. Ability to study various sources, recognise that the information obtained in class is insufficient, and to seek the supplementary information required.
7. Ability to relate and structure information from various sources and thus integrate ideas and knowledge.

The subject will be set forth in a highly practical fashion and will be illustrated with many examples.

Theory and examples of application will be presented in an intertwined fashion along the course.

The average five hours per week of this course are distributed into
two blocks per week of two hours
each and a block of two hours every two weeks.

The partial exam (P) evaluates items 1 through 4.

The computer exam (M) asks to solve two problems on
from items 2, 4, 5 and 6.

The final exam (F) evaluates all the items.

The practical work volunteer (A) consists of
implementation of a player for one game.

The grade for the course is calculated as follows:

GRADE = min (10, max (P + 25% 25% 50% M + F 100% F) + 20% A)


The timing is as follows:

P is a mid course exam, M is at the end of the course
and F fater its end. A should delivered by the end of the course.

The review mechanism before the machine is
follows:

In front of the computer, students receive two
problems. A problem is defined with a
utterance, one or more sets of evidence and public,
maybe some code already implemented. When a study
If your solution to deliver one of
problems, the machine sends a judge in
short seconds, he returned the verdict on
behavior of your program. Students can
forward up to 10 solutions for the same
trouble. The teachers corrected the last
submission for each problem.


The mechanism of practical work is voluntary
follows:

After partial shipment of the sentence
practical volunteer work, which consist of
description of a game. Students seeking
carry out practical work must be voluntary
program a player for this game (ie,
implement a strategy to try to win the
game). Along with the statement, teachers
Also given the code for a simple player:
the "silly."

At the end of course, there will be a public confrontation
through a system of rounds that will include all
The players delivered by students and the fool.
In this confrontation will be deducted from a classification
and appoint a champion.

The notice of voluntary practical work is calculated
automatically from the position where
classification of linearly and ensuring that the
Champion has a 10 and all participants
earning the silly to have a minimum grade 5.
The players who will not win the stupid one
note 0.

The voluntary submission of practical work
implicitly accepts that if it finds that
been fraud in its execution, shall be the
points (instead of adding them) of the
subject.

• R. Sedgewick Bundle of Algorithms in CPP, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Addison-Wesley, 2001.
• Mark Allen Weiss Data structures and algorithm analysis in C++, Pearson Education, 2006.
• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.
• G. Brassard, T. Bratley Fundamentos de algoritmia, Prentice Hall,, 1996.

• Mark Allen Weiss Data structures and problem solving using C++, Pearson Education International, 2003.
• Ian Parberry Problems on algorithms, Prentice Hall, 1995.
• Narciso Martí Oliet, Yolanda Ortega Mallén, José Alberto Verdejo López. Estructuras de datos y métodos algorítmicos : ejercicios resueltos, Pearson Educación, 2001.

Mastery of object-oriented programming techniques:
- passing parameters,
- classes,
- objects,
- methods,
- pointers,
- dynamic memory,
- genericity,
- use of standard classes.

Mastery of at least one object-oriented language, preferably C++.
Recursiveness.
The ADT concept.

Sequential ADTs:
- stacks,
- queues,
- lists with Points of Interest (POI),
- lists with iterators.

Use and internal implementation of sequential ADTs.

branched ADTs:
- binary tree,
- n-ary tree,
- general tree,
- paths.

Use and internal implementation of branched ADTs (Abstract Data Types).

Mathematical knowledge of graphs, sums, and limits. Discrete mathematics. Ability to reason mathematically and to follow mathematical reasoning.

Rudimentary knowledge of statistics and probability: probability space, events, distribution functions, random variables, expectation.