# Analysis and Design of Algorithms (ADA)

Credits Dept. Type Requirements
7.5 (6.0 ECTS) CS
• Compulsory for DIE
• Compulsory for DCSFW
PRAP - Prerequisite for DIE , DCSYS
PRED - Prerequisite for DIE , DCSYS
PS - Prerequisite for DCSFW

## Instructors

 Person in charge: (-) Others: (-)

## General goals

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.

## Specific goals

### 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.

## Contents

Estimated time (hours):

 T P L Alt Ext. L Stu A. time Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Analysis of algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
5,0 5,0 0 0 0 10,0 0 20,0
Time and space costs.

Worst case, best case, and middle case.

Asymptotic notation.

Calculating the cost of iterative and recursive algorithms.

2. Divide and Conquer algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
3,0 2,0 0 0 0 5,0 0 10,0
Mergesort

Quicksort

Karatsuba

Strassen

Other examples

3. More Data Structures
T      P      L      Alt    Ext. L Stu    A. time Total
7,0 8,0 0 0 0 15,0 0 30,0
Heaps
Heapsort
Extended priority queues
Hash tables
Binary search trees
Balanced binary search trees

4. Graphs
T      P      L      Alt    Ext. L Stu    A. time Total
3,0 2,0 0 0 0 7,0 0 12,0
Representations

Paths

Basic algorithms

5. Greedy algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
5,0 5,0 0 0 0 12,0 0 22,0
The principles underlying greedy algorithms
Minimum spanning trees: Kruskal, Prim
Shortest paths: Dijkstra
Optimal prefix codes: Huffman
Other examples

6. Exhaustive search algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
5,0 5,0 0 0 0 12,0 0 22,0
The principles underlying exhaustive search algorithms

Backtracking and branch and bound

Examples

Notions of complexity

7. Dynamic programming algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
5,0 5,0 0 0 0 12,0 0 22,0
The principles underlying dynamic programming algorithms
The optimality principle
Recursive solutions featuring memoization and iterative algorithms
Shortest paths: Floyd
Edit distance
Other examples

 Total per kind T P L Alt Ext. L Stu A. time Total 33,0 32,0 0 0 0 73,0 0 138,0 Avaluation additional hours 9,0 Total work hours for student 147,0

## Docent Methodolgy

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.

## Evaluation Methodgy

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
subject.

## Basic Bibliography

• 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.

## Complementary Bibliography

• 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.

(no available informacion)

## Previous capacities

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.

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

Use and internal implementation of sequential 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.

Compartir