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.







There will be three kinds of classes: theory sessions and problem sessions. On average, the number of contact hours a week will be split evenly between theory and practice classes.







The theory sessions take the form of lectures in which the teacher introduces new concepts or techniques, and examples illustrating them.







Practical classes focus on exercises and case studies



. Teachers set the problems to be solved



. The purpose of the exercises is to present and discuss fairly straightforward problems requiring little theory or technical knowledge



. As a rule, they cover exercises that illustrate the concepts introduced in the most recent theory sessions



. The problems posed in case studies are more complex than those put forward in exercises, and moreover cover various theoretical concepts that need to be drawn together to come up with a good solution.

Note: NP means that the student has not taken the corresponding exam

There are two mid-term exams (PAR1 and PAR2) and a final exam (FINAL). The final exam is for those students who don't want to take mid-term examinations or who obtain a grade less than 4 in the first mid-term exam (PAR1). The final exam covers all the syllabus of the course.

Additionally, students may get from 0 to 1 point for voluntary works (TV) under their professor's supervision; those works consist in small programming projects.

The first mid-term exam usually covers the first four chapters of the course.
For those not wanting to take mid-term examinations or who get a grade less than 4 in the first mid-term exam must take the final exam.
Those students with a grade greater or equal to 4 in the first mid-term exam may take
the final exam if they wish so, but in that case their PAR1 grade will be discarded.
The final grade of the course is computed as follows in those cases:

[if PAR1 < 4 or PAR1 = NP ] NF = min(FINAL + TV, 10)

Those with a grade greater or equal to 4 in the first mid-term exam, may choose to take
the second mid-term exam (PAR2) or the final exam.
The second mid-term exam typically covers chapters 5 to 7 of the course.
The final grade is in that case, according to whether they take PAR2 or FINAL,

[if PAR1 >= 4 and PAR2 != NP] NF = min((PAR1 + PAR2) / 2 + TV, 10)
[if PAR1 >= 4 and PAR2 = NP and FINAL != NP] NF = min(FINAL + TV, 10)

The second mid-term exam PAR2 is in the same day and time as the final exam, although its duration is shorter since it does only cover part of the syllabus.

All exams consist of problem solving exercices which allow to evaluate the level of acomplishment of the specific goals of the course. At least an 80% of the mark in all exams
comes from problems directly based upon those in the problem collection of the course, which is at the disposal of the students. There will be two editions of the problem collection each term, one at the beginning of the term (for PAR1) and the other around the middle of the term (for PAR2 and FINAL). There won't be any other changes in the collection during the term.

• R. Sedgewick Bundle of Algorithms in CPP, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition), Addison-Wesley, 2001.
• M.A. Weiss Data Structures and Algorithm Analysis in CPP (2nd Edition), Addison-Wesley, 1999.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, Second Edition, MIT Press, 2001.
• Brassard, Bratley Fundamentos de Algoritmia, Prentice Hall, 1997.

• M.A. Weiss Data Structures and Problem Solving Using CPP (Second Edition), Addison-Wesley,, 2000.
• Ian Parberry and William Gasarch Problems on Algorithms, 2a edició disponible online a http://hercule.csci.unt.edu/ian/books/poa.html, 2002.
• N. Martí, Y. Ortega, J.A. Verdejo Estructuras de datos y métodos algorítmicos - Ejercicios resueltos, Prentice Práctica, 2003.

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.