Algorithm Design

Code:

L.EIC016

Acronym:

DA

Keywords
Classification	Keyword
OFICIAL	Informatics Engineering and Computing

Instance: 2021/2022 - 2S

Active?	Yes
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Bachelor 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
L.EIC	365	Syllabus	2	-	6	52	162

Teaching language

Suitable for English-speaking students

Objectives

This course complements and deepens the knowledge acquired in the previous curricular unit of Algorithms and Data Structures, by introducing techniques for devising and implementing algorithms to solve different classes of problems.

Learning outcomes and competences

At the end of the course, the student is expected to be able to::

• be acquainted with and know how to apply generic algorithm design techniques;
• be acquainted with and know how to apply advanced algorithms in graphs;
• be acquainted with and know how to apply algorithms in strings;
• be able to identify intractable problems and to devise algorithms to produce approximate solutions;
• be able to identify mathematical optimization problems and know how and be able to apply algorithms for solving some types of linear and non-linear optimization problems.

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: L.EIC009 - Programming; L.EIC011 - Algorithms and Data Structures 

Program

1. Algorithm design techniques: divide and conquer; greedy algorithms; dynamic programming; backtracking algorithms; application examples.


2. Linear programming: constrained optimization problems; solution by the simplex algorithm.


3. Advanced graph algorithms: maximum flow and minimum cost flow in transport networks; Euler circuit and the Chinese postman problem; matching and stable marriage problems.


4. String algorithms: exact string matching; approximate string matching; text/file compression.


5. Intractable problems: NP-complete problems theory; problem reduction techniques; examples of intractable problems; approximate polynomial algorithms.


6. Numerical algorithms: root finding; solving systems of linear and non-linear equations; finding local minima by the gradient descent method; error analysis; applications.

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

The teaching methodology of this course is characterized by the adoption of theoretical and practical components in an integrated manner, both in classes and in the various assessment components. The lectures are used for the formal exposition of the subject, accompanied by the presentation of examples and their discussion. Practical classes are used for solving exercises and developing small programs to test the algorithms developed with tutorial follow-up.

The practical consolidation of the acquired theoretical knowledge, in a "learning-by-doing" perspective, allows the student to acquire skills in: i) characterizing a given problem; ii) formalizing the problem precisely; and iii) identifying the most appropriate algorithm design technique to solve the problem at hand. In a rather integrated and holistic perspective of all the acquired knowledge, the implementation of a complete project as the main support of the practical evaluation of this course allows the student to consolidate the aforementioned competences, and iv) to evaluate, both analytically and empirically, the quality of the conceived solution, in terms of both efficiency and correction. Upon the final exam, the student must demonstrate autonomously the knowledge acquired, at both practical and theoretical levels. Thus, the proposed teaching and assessment methods support the effective consolidation of the four competences listed above.

Software

GoogleTest, Google's C++ test framework
The CLion cross-platform IDE for C and C++ by JetBrains

keywords

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

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Designation	Weight (%)
Exame	70,00
Trabalho prático ou de projeto	30,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 in 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 to the practical part (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);
• Course assignment 2 (A2);

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

• DC = 0,40 * A1 + 0,60 * 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,7 * FE + 0,3 * 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 exam resit, 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 so as to improve potential of success.