Algorithm Design

Code:

L.EIC016

Acronym:

DA

Keywords
Classification	Keyword
OFICIAL	Informatics Engineering and Computing

Instance: 2023/2024 - 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	425	Syllabus	2	-	6	52	162

Teaching language

Suitable for English-speaking students

Objectives

This course on Design of Algorithms (DA) aims at complementing and further develop the implementation skills regarding the analysis and synthesis of computer algorithms, previously explored (in an introductory fashion) in the algorithms and data structures (AED course. This DA class introduces various algorithmic techniques of wide applicability, such as brute-force, backtracking, divide-and-conquer, greedy and dynamic programming, ubiquitous in real life algorithmic implementation solutions. We will also introduce the complexity classes of P and NP and the concept of polynomial-time reduction. As a practical application, we will also introduce the notion of approximation algorithms. Lastly, we will also cover the algorithmic techniques used in optimization problems via linear (real and integer) programming.

Learning outcomes and competences

At the end of this course, students, should be able to:

• Identify and understand how to apply generic algorithmic development technics;
• Identify and understand how to apply advanced graph and tree algorithms;
• Identify intractable problems and optimization problems that are suitable to have approximate solutions
• Identify classes of optimization problems for which generic technics such as back-tracking and linear optimization are feasible.

Working method

Presencial

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

It is highly desirable that students have solid knowledge of imperative programming (including object-oriented), data structures and abstract data types. The successful completion of L.EIC009 (Prog) and L.EIC011 (AED) is highly recommended.

Program

1. Review of asymptotic complexity notation and basic data structuers and algorithms in arrays and trees.


2. 
   

   Brute-force approach and simple applications for small scale (size) optimization problems.

   
   


3. 
   

   greedy algorithms and example application problems.

   
   


4. 
   

   Divide-and-Conquer algorithms and its applications including numérical methods.

   
   


5. 
   

   Dynamic programming algorithms.

   
   


6. 
   

   Linear programming (LP) optimization and introduction to integer linear programming (ILP).

   
   


7. 
   

   Backtracking and Brach-and-Bound and its use in optimization problems.

   
   


8. 
   

   Intractable problems and polynomial-time and space reduction between problems. Approximation algorithms for selected problems.

   
   

Mandatory literature

Thomas H. Cormen... [et al.]; Introduction to algorithms. ISBN: 978-0-262-53305-8

Comments from the literature

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

Teaching methods and learning activities

Lectures are used to present the concepts alongside the discussion and presentation of specific application examples. In the practical classes, these examples are further expanded the techniques revisited. Practical classes are also used in support of the two programming projects the students are expected to develop as they consolidate, in a very practical and pragramatic fashion, the algorithmic concepts described in this class. 

The consolidation of the theoretic knowledge in this class, in a pragmatic implementation approach, allows each student to acquire a broad component in i) problem characterization ii) formalization in a precise fashion of the problem and corresponding solutions iii) identification of the various plausible algorithmic techniques that can be pursued as a feasible solution. In the context of an integrated and holistic learning approach, the students are asked to develop two programming projects (leveraging techniques and components acquired in this course and in previous courses), and in a staged fashion, where various algorithmic approaches are pursed in search for feasible engineering solutions for complex real-life problems.

Software

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

keywords

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

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Trabalho prático ou de projeto	40,00
Teste	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

For the purposes of being eligible for grading, the only requirement is that students have a grade of at least 8.0 for both group programming projects. Failure to meet this requirement results in a Fail grade in the class with RFF as you cannot make-up the grade of a programming project.

There is no attendance requirement for the TP classes except for the demo of the programming project which all the elements of each group must attend, in person.

No grades from the previous years for any of the grading elements are accepted towards this year’s final grade credit.

Calculation formula of final grade

The final class grade is based on the following components on a scale from 0.0 to 20.0 points:

• Two individual written mini-testes (T1 and T2), lasting 1.5 hours (30 mins max. extra) and without access to support materials
• Two group programming projects (P1 and P2) with 3 students (maximum) and 2 students (minimum).

 The student’s individual grade in the Project has two components. One group component with a 75% weight reflecting the overall performance of the project solution and a 25% individual grade reflecting the level of effort of the student. Each group, besides of the program submission and corresponding sample inputs and outputs, shall also submit a simple report describing the features of their solution highlighting any potential innovative aspects.

The final class grade (NF) is computed as follows:

NF = (0.30 *(T1 + T2)) + (0.20 * (P1+P2))

where T1, T2, P1 and P2 will have to be greater or equal than 8.0, which only after this will be rounded up to the units.

In case the students does not meet the minimum grade of 8.0 in one of the grading components, he/she will be automatically enrolled in the “make-up” (“recurso”) term in which he/she will have to make-up for that component.

Examinations or Special Assignments

N/A

Internship work/project

This component includes the development of 2 programming projets (P1 e P2), leveraging the techniques and competences acquired in the Algorithms and Data Structures (AED) course, and in a staged fashion, making use of the design and implementation techniques learned in this design of algorithms (DA) course. These programming projects will be carried out in groups of 3 students (maximum) and 2 students (minimum) and will focus on specific problems that elicit the application of the techniques studied in this design of algorithms (DA) class. These projects should be developed and demonstrated in the programming environments used in the previous course of AED. However, it is at the discretion of the responsible instructor to allow the students to use an alternative programming and development environment.

Special assessment (TE, DA, ...)

Students with special needs or under the provision of special status (e.g., student worker, athletic status), must complete the same grading components as the regular students (albeit with different time limits). These students, may, nevertheless, agree with the instructor specific arrangement regarding turning in their work.

Classification improvement

Only the mini-test grades can be made up during the make-up term (“Recurso”). Students who have passed the class during the regular session, may still petition to improve the grade enrolling in a special “Make-up” term session (”Melhoria”) and for which there is fee. Students, may choose which of the two, or both, mini-test grades they want to make up, but this only applies to mini-tests whose grades do not meet the minimum grade requirement of 8.0 out of 20.0. If, however, the student wishes to improve one of the mini-test grades, he/she needs not enroll in the special administrative “Melhoria” term and instead needs to inform the instructor that wishes to make-up one of the two mini-terms while making up the other mini-test grade that is below the minimum grade.

Observations

It is highly desirable that students have solid knowledge of imperative programming (including object-oriented), data structures and abstract data types. The successful completion of L.EIC009 (Prog) and L.EIC011 (AED) is highly recommended.