• Description

When designing a program it is very important to take efficiency into account, that is to say, let it consume the minimum quantity of resources in order to carry out its goal. Therefore, computational time and memory space to store the data is to be minimized, as well as the number of messages to be sent through the network, the amount of consumed energy, etc.

There exist two fundamental tools to achieve this: data structures and algorithmic schemes:

• The data structures focus on how information is managed: they consist of strategies to organise data and reduce the access and manipulation time, as well as the storage space required.
• Algorithmic schemes focus on the computational process: they are general patterns that describe the necessary steps to reach a solution and they have to be particularized for the specific problem to solve.

This course presents the concepts on data structures and algorithms necessary for research. In particular, the subject reviews fundamental concepts of algorithmic complexity (space and temporary costs, calculation of the cost of an algorithm, typical orders of magnitude) as well as basic concepts of data structures (abstract data types, management of pointers and memory, etc). From this base, the subject deepens in usual data structures (stacks, queues, lists, trees, heaps, hash tables) and presents an introduction to algorithms on graphs (paths, shortest paths, tree generators, etc.).

• The subject within the syllabus as a whole

Data structures and algorithms is an optional course of the Interuniversity Master in Computational and Mathematical Engineering.

The knowledge acquired in this course will be useful in the development of practical activities in other courses of the master. In particular, it is recommended to enroll this course before enrolling Combinatorial optimisation.

• Professional fields to which it applies

The concepts acquired in this course are essential to develop software that efficiently uses any available computational resources. For this reason, this course is relevant to any work related to the design and implementation of software, especially in the field of R&D or applied mathematics.

• Prior knowledge

This course requires basic knowledges of algorithmics: knowing the basics of programming (loops, conditionals, etc.) and understanding algorithms described in pseudocode. Also it requires a previous knowledge of the Java object-oriented programming language sufficient to write, execute and test programs.

On the other hand, the central materials of the course are in English. By this reason, having a good level of written comprehension of technical English is recommended.

• Information prior to enrolment

Before enrolling this subject, it is necessary to have previous knowledge about algorithmics and Java programming and have a good level of technical English for written comprehension.

• Learning objectives and results

The general competences of the master taught in this course are:

• Understanding and applying advanced knowledge about computing and numerical or computational methods to engineering problems.
• Applying the mathematical and computational methods to the resolution of technological and engineering problems, particularly in tasks of research, development and innovation.
• Design, implement and validate algorithms using the most convenient structures.

The specific competences of this course are:

• Knowing the concept of abstract data type and knowing how to define an abstract data type for a concrete problem.
• Knowing the sequential abstract data types (stacks, queues, lists) and their operations, and knowing how to use them to resolve problems.
• Knowing the concept of asymptotic complexity, knowing how to calculate it for a given algorithm and being able to use it to compare two different algorithms from efficienncy point of view.
• Knowing different sorting algorithms, their advantages and disadvantages and how to choose the most appropriate in a concrete context.
• Knowing different strategies of information search (hashing, search trees), their advantages and disadvantages and know how to choose the most appropriate in a specific context.
• Knowing the main algorithms on graphs, their complexity and being able to use them to resolve concrete problems.
• Being able to choose the most appropriate data structure for a problem according to efficiency criteria and justify the decision.

• Content

The course is structured in four thematic blocks:

• View the UOC learning resources used in the subject

• Additional information on support tools and learning resources

The central material of the course is a book of reference in this field: "Algorithms, 4th Edition", by Robert Sedgewick and Kevin Wayne. The contents of the book go further of what we will study in the course and will be useful as a reference during your professional career.

To guide the study of the book and highlight the important contents of the book within the course, there will be a study guide in the classroom every week with advice on how to review the contents of the book.

As complementary material, there are some didactic UOC modules titled "Design of data structures". These materials can be used to solve any doubts that you may have when reviewing the book of the course. However, these materials mainly focus on how the data structures are implemented, whereas in this course we will focus more in knowing how to use them and the criteria to choose the most appropriate.

• Guidelines on assessment at the UOC

Assessment at the UOC is, in general, online, structured around the continuous assessment activities, the final assessment tests and exams, and the programme's final project.

Assessment activities and tests can be written texts and/or video recordings, use random questions, and synchronous or asynchronous oral tests, etc., as decided by each teaching team. The final project marks the end of the learning process and consists of an original and tutored piece of work to demonstrate that students have acquired the competencies worked on during the programme.

To verify students' identity and authorship in the assessment tests, the UOC reserves the right to use identity recognition and plagiarism detection systems. For these purposes, the UOC may make video recordings or use supervision methods or techniques while students carry out any of their academic activities.

The UOC may also require students to use electronic devices (microphones, webcams or other tools) or specific software during assessments. It is the student's responsibility to ensure that these devices work properly.

The assessment process is based on students' individual efforts, and the assumption that the student is the author of the work submitted for academic activities and that this work is original. The UOC's website on academic integrity and plagiarism has more information on this.

Submitting work that is not one's own or not original for assessment tests; copying or plagiarism; impersonation; accepting or obtaining any assignments, whether for compensation or otherwise; collaboration, cover-up or encouragement to copy; and using materials, software or devices not authorized in the course plan or instructions for the activity, including artificial intelligence and machine translation, among others, are examples of misconduct in assessments that may have serious academic and disciplinary consequences.

If students are found to be engaging in any such misconduct, they may receive a Fail (D/0) for the graded activities in the course plan (including final tests) or for the final grade for the course. This could be because they have used unauthorized materials, software or devices (such as artificial intelligence when it is not permitted, social media or internet search engines) during the tests; copied fragments of text from an external source (the internet, notes, books, articles, other students' work or tests, etc.) without the corresponding citation; purchased or sold assignments, or undertaken any other form of misconduct.

Likewise and in accordance with the UOC's academic regulations, misconduct during assessment may also be grounds for disciplinary proceedings and, where appropriate, the corresponding disciplinary measures, as established in the regulations governing the UOC community (Normativa de convivència).

In its assessment process, the UOC reserves the right to:

• Ask students to provide proof of their identity as established in the UOC's academic regulations.
• Ask students to prove the authorship of their work throughout the assessment process, in both continuous and final assessments, through a synchronous oral interview, of which a video recording or any other type of recording established by the UOC may be made. These methods seek to ensure verification of the student's identity, and their knowledge and competencies. If it is not possible to ensure the student's authorship, they may receive a D grade in the case of continuous assessment or a Fail grade in the case of the final assessment.

Artificial intelligence in assessments

The UOC understands the value and potential of artificial intelligence (AI) in education, but it also understands the risks involved if it is not used ethically, critically and responsibly. So, in each assessment activity, students will be told which AI tools and resources can be used and under what conditions. In turn, students must agree to follow the guidelines set by the UOC when it comes to completing the assessment activities and citing the tools used. Specifically, they must identify any texts or images generated by AI systems and they must not present them as their own work.

In terms of using AI, or not, to complete an activity, the instructions for assessment activities indicate the restrictions on the use of these tools. Bear in mind that using them inappropriately, such as using them in activities where they are not allowed or not citing them in activities where they are, may be considered misconduct. If in doubt, we recommend getting in touch with the course instructor and asking them before you submit your work.

• View the assessment model