Algorithm Design and Analysis

Code:

EIC0110

Acronym:

CAL

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2014/2015 - 2S

Active?	Yes
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MIEIC	159	Syllabus since 2009/2010	2	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

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 tecquniques to conceive and devise a wide range of algorithm classes;
• 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. 

Learning outcomes and competences

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.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

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 

Program

1. Algorithm techniques: divide and conquer; greedy algorithms; dynamicy programming; backtracking algorithms; probabilistic and stochastic algorithms.


2. Algorithm representation and formalisation, complexity analysis (temporal and spatial); verficiation and correctness of algorithms.


3. Advanced data structures: priority queues with dynamic positioning of elements; disjunct sets.


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


5. String algorithms: exact string matching; approximate string matching (fuzzy string searching); longest common substring problem; text/file compression.


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

Mandatory literature

Thomas H. Cormen... [et al.]; Introduction to algorithms. ISBN: 978-0-262-53305-8
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

Comments from the literature

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

Teaching methods and learning activities

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 (at a maximum of two 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.

Software

Eclipse C++
Cute C++ Unit Testing Framework (plug-in p/ Eclipse)

keywords

Physical sciences > Mathematics > Algorithms
Technological sciences > Technology > Computer technology > Software technology

Evaluation Type

Distributed evaluation with final exam

Assessment Components

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

Amount of time allocated to each course unit

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

Eligibility for exams

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.

Calculation formula of final grade

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)

Examinations or Special Assignments

N/A

Internship work/project

N/A

Special assessment (TE, DA, ...)

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.

Classification improvement

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.

Observations

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.