Logo UAB
2022/2023

Algorithm Design

Code: 104359 ECTS Credits: 6
Degree Type Year Semester
2503758 Data Engineering OB 2 2

Contact

Name:
Jorge Bernal del Nozal
Email:
jorge.bernal@uab.cat

Use of Languages

Principal working language:
catalan (cat)
Some groups entirely in English:
No
Some groups entirely in Catalan:
Yes
Some groups entirely in Spanish:
No

Teachers

Jorge Bernal del Nozal

Prerequisites

Although it is not compulsory, it is highly advisable to have studied the following subjects:

·     Fonaments de Programació

·         Programació Avançada

·         Estructures de Dades

·         Anàlisi de Grafs i prop d'Informació

·         Enginyeria l'Rendiment

The teaching team will assume that the student has previously acquired the knowledge taught in these subjects.

 

Objectives and Contextualisation

On the basis that students have some basic knowledge about programming and data structures acquired in previous subjects, the student is expected to be able to analyze, design and implement algorithms based on algorithm design techniques existing ones To meet this goal, the student will acquire the knowledge about:

·         Formal specification of problems. How to move from a description of a problem to a valid specification for the development of an algorithm that resolves it.

·         Formal tests to validate programs. Design based on contracts. Preconditions, postconditions and invariants.

·         Paradigms for the design of algorithms. Search algorithms, greedy recursion, backtracking, branch & bound, dynamic programming, probabilistic algorithms, etc.

The development of an algorithm begins to formalize the statement of a problem. From this statement, an algorithm is designed to solve the problem, but this is not enough, it is also important to consider how long the algorithm will take when giving us the solution. So we are interested in creating algorithms as fast as possible. In this way we can create programs that solve problems as large as possible in acceptable times. This rapidity is achieved by designing algorithms that minimize the number of operations to be performed to solve a problem and develop an efficient implementation of the operations of the algorithm. This will mean that in this subject the student will acquire knowledge about algorithmics and efficient implementation of algorithms.

 

Competences

  • Design efficient algorithmic solutions to computational problems, implement them in the form of robust software developments which are structured and easy to maintain, and verify their validity.
  • Make a critical evaluation of work carried out.
  • Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.

Learning Outcomes

  1. Decide on the most suitable data-learning method depending on the characteristics of the data to be analysed.
  2. Make a critical evaluation of work carried out.
  3. Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.

Content

The subjects covered in the course will be:

  1. Topic 1. Revision of basic concepts (Pre-conditions, post-conditions, invariants)
  2. Topic 2. Computational complexity
  3. Topic 3. Search algorithms: Taxonomy and strategies.
  4. Topic 4. Greedy.
  5. Topic 5. Recursion.
  6. Topic 6. Divide and conquer.
  7. Topic 7. Backtracking.
  8. Topic 8. Branch & Bound.
  9. Topic 9. Dynamic programming.
  10. Topic 10. Stochastic Algorithms

 

 

 

 

 

 

Methodology

Taking into account that the final objective of the subject is that the students are able to analyze and design algorithms efficiently according to a given problem, the personal work of the students should be the main part to obtain the Learning objectives, always accompanied and guided by the teaching staff. For this reason, face-to-face classes will be highly practical and will focus on which students consolidate the knowledge that is objective of learning this subject.

The general methodology of the subject can be divided into three phases:

Preparation of the class: the objective of this phase is that the students can learn the concepts that will be worked on in the following session through various activities offered by teachers how can be the viewing of videos, reading texts, etc.

Class attendance: the objective of this phase is to consolidate the concepts seen and put them in value within the context of the subject. The teaching staff will ensure that students delve into these concepts through exercises (more or less) guided during the session. Thus the class will begin with a brief explanation of the concepts that the student will have studied in the preparation of the class. This summary will give a general overview of the concepts under study and will give rise to the students being able to solve their doubts. Then the problem or practical work will be explained during the second part of the class. These problems or practices will be carried out with a computer, since in many cases they will be able to implement algorithms.

Autonomous work: in order for the students to take the opportunity to program the algorithms seen, they will have to do a part of the work on their own, whether they are loose exercises or within a project.

The proposed teaching methodology and evaluation may undergo some modification depending on the restrictions on attendance imposed by the health authorities

 

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.

Activities

Title Hours ECTS Learning Outcomes
Type: Directed      
Theoretical Class 22 0.88 1
Type: Supervised      
Practicum 14 0.56 2, 1, 3
Seminaries 14 0.56 2, 1
Type: Autonomous      
Practicum solving 25 1 2, 1, 3
Problem solving 25.5 1.02 2, 1, 3
Study of the theory material 40 1.6 1

Assessment

Criteria and indicators:

·         Understanding the theoretical concepts of the subject.

·         Correct and efficient implementation of algorithms.

Activities and evaluation instruments:

·         Theory Marks: it corresponds to two intermediate exams of the theoretical content on the subject. If intermediate exams are passed, the student should not exam him/herself in the final exam.

·         Problems Marks: It corresponds to the mark obtained by a series of problems that the student will be assigned. There is no recovery for the delivery of problems.

·         Follow-up of the learning progress Marks: it corresponds to the mark obtained during the different activities of follow-up of the learning that will be realized during the course (questionnaires in Caronte, Kahoots) and that will done always during the face-to-face classes. There is no recovery for these activities.

·         Practicum Marks: In this section there is a group and an individual mark:

o   Group mark: Corresponds to the grade obtained for group deliveries of the practice. Deliveries of failed practices can be recovered in subsequent installments.

o   Individual note: This is the score obtained in the practice exam. There will be recovery of the practice exam.

The final grade of the subject is obtained by combining the evaluation ofthese four activities in the following way:

A.  Note Theory

IF First intermediate exam score> = 5 and Second intermediate exam note = = 5 THEN

Theory Mark= 0.5 * First intermediate exam + 0.5 * Second intermediate exam

ELSE Theory Mark= MIN (First intermediate exam, Note intermediate exam)

B.  Problems Mark

Mark = Weighted average of the one obtained for each assignment.

C.   Follow-up Mark

Mark = Accumulated note from the collection of the different assessment systems in person.

D.  Note Practices

IF Individual Mark> = 5 and Group Mark> = 5 THEN

Practicum Mark= 0.2 * Individual Mark+ 0.8 * Group Mark

ELSE Practicum Mark = MIN (Individual Mark, Group Mark)

 

Where:

·         Individual Mark= Examination of practicum.

·         Group Mark = Weighted average of the delivery of practices if all are passed. If it is not the case, the mark will be the minimum of the notes of the deliveries. In case the student makes the practicum individually, there will be no practicum exam.

·         Practicum recovery: In the case of having suspended a group delivery, it will be possible to recover in the following deliveries of the practice. The note will be 0.75 * (max (note recovery, note suspended delivery) Note delivery suspended) + note delivery suspended. In the case of suspending the practice exam, the student will have to submit to a practice recovery exam on the same day as the final recovery exam.

 

Final Mark

IF Theory> = 5 and Practicum > = 5 THEN

Final Mark= 0.35 * Theory + 0.2 * Problems + 0.1 * Follow-up + 0.35 * Practicum

THEN Final Mark = MIN (Theory, Practicum)

 

Conditions to pass the subject:

To pass the subject, it must have been approved (note greater or equal to 5):

·         Final mark

·         Theory mark

·         Practical mark

·         Marks delivery practices.

·         Exams

Conditions for non-evaluable:

·         Not having any part of the subject suspended and not fulfilling the conditions to approve.

Conditions for failing the subject:

·         Do not reach a mark equal to or greater than 5.

·         Suspend some of the subject's evaluation activities, although the average exceeds 5. In this case, the mark will be the minimum markobtained from one of the parties (exams or practices).

Conditions for honor grade:

Honors can be obtained with an average grade of 9.0 or higher.

Due to the fact that there is a limited number of honor grades that can be given by group, they will be awarded in order of note from more to less.

Practices, work or exams copied:

Without prejudice to other disciplinary measures that are deemed appropriate, and in accordance with the current academic regulations, irregularities committed by a student that can lead to a variation of the qualification will be classified by zero (0). Assessment activities qualified in this way and by this procedure will not be recoverable. If it is necessary to pass any of these assessment activities to pass the subject, this subject will be suspended directly, without opportunity to recover it in the same course. These irregularities include, among others:

- the total or partial copy of a practice, report, or any other evaluation activity;

- let copy;

- present a group work not done entirely by the members of the group;

- present as own materials prepared by a third party, although they are translations or adaptations, and generally works with non-original and exclusive elements of the student;

- Have communication devices (such as mobile phones, smart watches, etc.) accessible during individual theoretical and practical evaluation tests (exams).

In case the student has committed irregularities in an evaluation act, the numerical note of the file will be the lowest value between 3.0 and the corresponding grade according to the method of evaluation of the subject (and therefore not the approved one will be possible for compensation).

Short and short: copying, copying, or plagiarizing in any of the assessment activities is equivalent to a SUSPENS with a score of less than 3.0.

Publication of notes, dates of examinations, etc.:

The dates of continuous evaluation and delivery of works will be published in the virtual campus and may be subject to changes of programming for reasons of adaptation to possible incidents. The virtual campus will always be informed about these changes as it is understood to be the usual mechanism for exchanging information between teacher and students.

Procedure for reviewing the qualifications

For each evaluation activity, a place, date and time of review will be indicated in which the student can review the activity with the teacher. In this context, claims can be made about the activity note, which will be evaluated by the teachers responsible for the subject. If the student does not appear in this review, this activity will not be reviewed later.

 

Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Final exam See evaluation activities and instruments 2.5 0.1 1
First intermediate exam See activities and evaluation instruments 2 0.08 2, 1
Practicum evaluation See evaluation activities and instruments 2 0.08 2, 1, 3
Practicum exam See evaluation activities and instruments 1 0.04 2, 3
Second intermediate exam See evaluation activities and instruments 2 0.08 2, 1

Bibliography

·         Fundamentos de Algorítmia, G Brassard P. Bratley. Prentice Hall.

·         Técnicas de Diseño de Algoritmos, Rosa Guerequeta y Antonio Vallecillo.

·         Técnicas de diseño de algoritmos, F. Perales, M. Mascaró. Universitat de les Illes Balears

·         Karumanchi, Narasimha. "Algorithm Design Techniques: Recursion, Backtracking, Greedy, Divide and Conquer, and Dynamic Programming." (2018).

·         Chun, Wesley. Core python programming. Vol. 1. Prentice Hall Professional, 2001.

Software

Python programming language (version 3.4 onwards) will be used during this course. We do not impose any restrictions on the IDE to be used (Anaconda, PyCharm, Visual Studio)