Algorithm Design

Code:

L.EIC016

Acronym:

DA

Keywords
Classification	Keyword
OFICIAL	Informatics Engineering and Computing

Instance: 2022/2023 - 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	422	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.

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

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

The following are the minimum grade rules regarding the various grading elements:

• All graded components have a minimum grade of 8.0 (no rounding). A component with a grade below 8.0 will have to be subject to a Make-Up (“recurso”).
• The two projects cannot be retaken or improved. Failing to meet the minimum project grade automatically implies failing the class.

Exceptionally, this year of 2023 previous year students (2021/22) may elect to use the grades of the two projects towards this year’s final class grade and will only need to retake the two mini-tests (T1 and T2).

This policy will not be followed in the coming years.

Calculation formula of final grade

The final class grade is based on the following components:

• 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 each 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.There is alo a simple demo session for each group when all the elements of the group must be present.

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

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

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

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 term, may still petition to improve their class grade enrolling in a special term (”Melhoria”) for which there is an administrative fee.

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.