Go to:

Site map

Code: | EIC0110 | Acronym: | CAL |

Keywords | |
---|---|

Classification | Keyword |

OFICIAL | Programming |

Active? | Yes |

Responsible unit: | Department of Informatics Engineering |

Course/CS Responsible: | Master in Informatics and Computing Engineering |

Acronym | No. of Students | Study Plan | Curricular Years | Credits UCN | Credits ECTS | Contact hours | Total Time |
---|---|---|---|---|---|---|---|

MIEIC | 190 | Syllabus since 2009/2010 | 2 | - | 6 | 56 | 162 |

Teacher | Responsibility |
---|---|

Rosaldo José Fernandes Rossetti |

Lectures: | 2,00 |

Recitations: | 2,00 |

Type | Teacher | Classes | Hour |
---|---|---|---|

Lectures | Totals | 1 | 2,00 |

Rosaldo José Fernandes Rossetti | 2,00 | ||

Recitations | Totals | 7 | 14,00 |

Liliana da Silva Ferreira | 2,00 | ||

Rosaldo José Fernandes Rossetti | 4,00 | ||

Henrique Daniel de Avelar Lopes Cardoso | 4,00 | ||

Francisco Xavier Richardson Rebello de Andrade | 4,00 |

This course unit aims to follow up and deepen the knowledge acquired in previous modules such as “Programming” and “Algorithms and Data Structures”, namely by introducing techniques for devising and implementing efficient algorithms to solve different classes of problems, as well as for analysing and assessing them.

More specifically, it is intended to allow students to:

- be acquainted with and know how to apply efficient algorithms in graph problems, sets and strings;
- be acquainted with and know how to apply generic algorithm design and analysis techniques;
- be acquainted with some classes of intractable problems and know how to conceive and devise algorithms to produce approximate solutions to some of those problems.

In the end of this course unit, it is expectable that students will be able to:

- characterise a given problem;
- formalise the problem, identifying input data, constraints and boundary conditions;
- conceive and devise efficient algorithms to solve the problem;
- assess and evaluate the devised solution regarding its efficiency and correctness.

It is desirable and necessary that students have fundamental knowledge on object-oriented programming, data structures and abstract data types. It is recommended that students had attended the following modules: EIC0012 - Programming; EIC0013 - Algorithms and Data Structures

- Algorithm techniques: divide and conquer; greedy algorithms; dynamicy programming; backtracking algorithms; probabilistic and stochastic algorithms.
- Problem formalisation; algorithm representation; complexity analysis (temporal and spatial); verficiation of algorithm correctness.
- Advanced data structures: priority queues with dynamic positioning of elements; disjunct sets.
- Efficient algorithms in graphs: depth-first and breadth-first search; topological sort/ordering; biconnex components; strongly connected components; shortest path; minimum spanning tree; maximum flow and minimum cost flow in transport networks; Euler circuit and the Chinese Postman problem; matching and stable marriage problems.
- String algorithms: exact string matching; approximate string matching (fuzzy string searching); longest common substring problem; text/file compression.
- Solving intractable problems: problem reduction techniques; NP-complete problems theory; examples of intractable problems in graphs; algorithms to produce approximate solutions to some intractable problems in polynomial time.

Steven S. Skiena; The algorithm design manual. ISBN: 0-387-94860-0

Sedgewick, Robert; Algorithms in C++ Part 5: Graph Algorithms, 3/E, Addison-Wesley Professional, 2001. ISBN: 0201361183

Other links and support material will be made available on the Web site of this course unit.

PERCENTUAL DISTRIBUTION 60% Theory: to introduce the various concepts and application examples of algorithms design techniques, graphs, strings and file algorithms, NP-completeness and related problems 40% Practice: laboratory hands-on practice, in which students are expected to do practical exercises on topics presented in theory classes.

Theory classes are structured so as to give students a formal exposition of the subject, together with discussions on examples and their solutions. Lab classes are intended to provide students with tools and hands-on practice exercises to practice algorithms development and their implementation in C++ to test the devised solutions. Students will also be assigned course works to be carried out in groups of 3 (three) students. Although these projects are meant to be carried out in groups, assessment and marks will account for individual performance of students within their groups.

Eclipse C++

Technological sciences > Technology > Computer technology > Software technology

Designation | Weight (%) |
---|---|

Defesa pública de dissertação, de relatório de projeto ou estágio, ou de tese | 40,00 |

Exame | 60,00 |

Total: |
100,00 |

Designation | Time (hours) |
---|---|

Elaboração de projeto | 50,00 |

Estudo autónomo | 56,00 |

Frequência das aulas | 28,00 |

Trabalho laboratorial | 28,00 |

Total: |
162,00 |

To succeed in this course unit throughout the term:

- The student is expected to meet the requirements of minimum attendance to lab classes;
- In each of the assignment components, as well as in the final exam, the student is expected to have a minimum mark of 40% (>= 8 out of 20).

Students that have attended this course unit of "Algorithms Design and Analysis" during the previous academic year and have succeed in the course unit’s assignments, are eligible not to attend lab classes, needing only to do the final exam (FE) to be assessed. However, if the student is willing to improve his/her mark of course assignments, then he/she is required to attend lab classes again.

The final assessment of this course unit includes the following partial assessments:

- Final Exam (FE), for which the access of course material is restricted (only books and handouts of theory classes are permitted) and whose expected duration is 2 hours
- Distributed component (DC) to be carried out throughout the term, composed by two assignments:
- Course assignment 1 (A1) – graphs
- Course assignment 2 (A2) – strings/files

The DC mark related to the distributed component is evaluated in the following way:

- DC = 0,60 * A1 + 0,4 * A2, where A1 >= 8 (out of 20) and A2 >= 8 (out of 20)

The final mark (FM) is evaluated in the following way:

- FM = 0,6 * FE + 0,4 * DC, where FE >= 8 (out of 20)

N/A

N/A

Students attending this course unit under special statuses and privileges are expected to meet the same assessment requirements as to ordinary students, and must perform the course assignments as expected. Nevertheless, the student may schedule with his/her lecturer of lab classes when to hand in and present the course assignments as appropriate, out of normal class hours.

The course assignments part of the assessment system can be improved if the student attends the lab classes during the following edition of this course unit. Exam marks in the first call can be improved during the exame in the second call, in the same term.

It is recommended that students had attended the "Programming" and the "Algorithms and Data Structures" course units prior to attending this course unit of "Algorithms Design and Analysis" to improve potential of success.

The deadline for the submission of the first course assinment (A1) is april, 8.

The deadline for the submission of the second course assinment (A2) is may, 20.

Copyright 1996-2023 © Faculdade de Engenharia da Universidade do Porto
I Terms and Conditions
I Accessibility
I Index A-Z
I Guest Book

Page generated on: 2023-09-27 at 06:30:01 | Acceptable Use Policy | Data Protection Policy | Complaint Portal

Page generated on: 2023-09-27 at 06:30:01 | Acceptable Use Policy | Data Protection Policy | Complaint Portal