The only requirement to take this subject is a general knowledge of computer science and basic programming skills, such as those provided by the subject "Introduction to Computer Science" during the first semester. The student should be also familiar with basic mathematical concepts on linear algebra, geometry and analysis. The subject introduces basic and more advanced search and sorting algorithms and studies their computational efficiency (especially, time complexity), by applying algorithm analysis techniques and using asymptotic notation. Then, the concept of abstract data type (ADT) is introduced and several ADTs are studied in increasing order of complexity, as well as some algorithm design techniques. The examples and exercises are supported by a high level programming language used in the current scientific-technological environment. The subject provides the knowledge and skills needed to solve algorithmic problems of medium complexity that will allow the students to undertake modeling and simulation tasks in other subjects of the degree.

SPECIFIC COMPETENCES

- To know the basics of current programming techniques: data structures, structured programming and object-oriented programming.

- To know and apply methods to study and compare the computational complexity of algorithms.

- To be able to apply a rigorous programming methodology based on the knowledge of data structures and computing methods for the development of software projects.

- To master a general-purpose programming language which is commonly used in today's scientific-technological environments, being able to use it for the implementation of basic algorithms.

- To be able to present a programming project clearly and concisely, and to explain the design decisions made during its development.



LEARNING OUTCOMES

- To know the main features and the most common implementations of basic data structures: linear (list, stacks and queues) and non-linear structures (hash tables, trees and graphs), and to be able to identify the most suitable structures depending on the application and how to integrate them in more general designs.

- To know and apply computational complexity analysis techniques, in order to compare two or more algorithms with each other and choose the best one (in terms of efficiency) for some given problem and context.

- To design new ADTs, exploit existing ADTs and apply basic algorithm design techniques to solve problems in a structured, clear and efficient manner.

- To be a productive part of a team in a real programming environment, using a high level programming language to solve algorithmic problems, analyzing alternative solutions, identifying the ADTs that are required, exploiting those that are already available, designing and implementing those that are not, and using running time profiles to make a decision about the most suitable approach.

CONTENTS



1. Search and sorting algorithms

- Basic search schemes: sequential search and binary search

- Basic sorting schemes: insertion, selection and bubble sort

- Partition sort (quicksort)

- Merge sort



2. Analysis of the computational efficiency of algorithms

- Asymptotic notation versus running time profiles

- Analysis of control structures

- Analysis of recursive algorithms

- Divide and Conquer algorithms



3. Abstract Data Types (ADT)

- ADT-based design

- Object Oriented Programming (OOP)

- Study of cases



4. Linear ADT

- Stacks

- Queues

- Priority queues



5. Non-linear ADT

- Hash tables

- Heaps

- Trees

- Binary search trees



6. Graphs (advanced topic)

- Definitions, operations and representations

- Paths and connectivity

- Minimum spanning trees

- Greedy algorithms

- Shortest paths

- Dynamic programming algorithms



HANDS-ON LEARNING ACTIVITIES



Three open problems (of increasing complexity) are proposed, related to the topics developed in lectures. For each of them, students must develop one or several algorithmic solutions and, depending on the case, write a brief report (results, running time profiles, etc.), which will be uploaded to the e-gela (Moodle-based LMS) platform. The proposed problems will change every year, but their general objectives will be: (1) to strengthen the knowledge about data structures and the programming skills acquired during the first semester in the subject "Introduction to Computer Science"; (2) to study the computational efficiency of algorithms from a practical point of view (that is, by obtaining running time profiles); and (3) to design, develop and apply one or several ADTs in a realistic situation.

The teaching team employs five different teaching/learning modalities:



(1) Lectures, in which the instructor exposes a topic based on a slide presentation, with notes on the board and often with the development of code examples on the computer. Lectures are fundamentally unidirectional, though students are invited to ask any questions that may arise. Lecture notes, code examples, exercises, and even relevant links for those interested, are provided through the e-gela platform.



(2) Problem-solving sessions, in which the students, with the help of the instructor, present and discuss their solutions to the exercises. This modality is essentially interactive. Eventually, these sessions are also used to solve doubts about the contents exposed in lectures or about the hands-on (programming) sessions. Commented solutions to the exercises are also provided through the e-gela platform.



(3) Hands-on (programming) sessions, in which the students, with the support of the teaching team, write and debug code in a programming environment. Each student goes through seven highly interactive sessions that take place in a computer lab. As noted above, three different problems (of increasing complexity) are proposed, each supplied with the necessary datasets, designed specifically to develop aspects discussed in lectures. Students must encode algorithmic solutions in a programming language and write a brief report with the obtained results. These sessions aim to provide the students with confidence in the application of the acquired knowledge and to develop creative skills through the interaction with the teaching team and other students.



(4) Seminars, in which advanced topics about the programming language are exposed and discussed. Each student attend to five one-hour seminars in a computer lab, just before the first five hands-on sessions, so that they can check and explore the discussed topics by themselves in a programming environment.



(5) Tutorials, in which instructors deal with students at their office, to answer questions about the contents, the proposed exercises or the hands-on sessions. This teaching modality allows for a more direct and personal interaction. Though there is an official time slot for tutorials, students can set an appointment at any time, as long as the instructors are available. Finally, students can also raise questions through e-mail, the instructors placing their answers usually within two days.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Written test to be taken (%): 60
  • Individual works (%): 20
  • Team projects (problem solving, project design)) (%): 20

In the First Call, there will be two possible assessment paths. In the CONTINUOUS ASSESSMENT path (which is the default path), the final grade is computed as follows:



- Written exam: 60%.

- Hands-on sessions (delivery of reports in term, and where appropriate, explanation or defense): 20%

- Individual / group work (delivery of exercises in term, and if applicable, explanation or defense): 20%



Those students who wish to follow the FINAL ASSESSMENT path should apply for their resignation to the continuous assessment path BEFORE THE WEEK 10 OF THE SEMESTER.



The final grade in the final assessment path will be computed as follows:



- Written exam: 60%.

- Computer programming test: 40%.



The time, place and other conditions of the computer programming test will be announced at least ONE MONTH in advance.



In any case, it will be required a grade of 4 (out of 10) in the written exam to pass the subject.

In the Second Call, as established by the University of the Basque Country regulations, only the FINAL ASSESSMENT path will be applied. Two possible modalities are observed:



* MODALITY A (default): The grades of hands-on sessions and individual / group work are kept, so that the student just takes the written exam. Under this modality, the final grade will be computed as follows:



- Written exam: 60%.

- Hands-on sessions (delivery of reports in term, and where appropriate, explanation or defense): 20%

- Individual / group work (delivery of exercises in term, and if applicable, explanation or defense): 20%



* MODALITY B: This modality establishes the same conditions as for the FINAL ASSESMENT path defined in the First Call. The final grade will be computed as follows:



- Written exam: 60%.

- Computer programming test: 40%.



The time, place and other conditions of the computer programming test will be announced at least TEN (10) DAYS in advance.



Those students who wish to choose MODALITY B should apply for it at least FOURTEEN (14) DAYS BEFORE the date established for the written exam. If no communication is received, it will be understood that the student chooses MODALITY A.



In any case, it will be required a grade of 4 (out of 10) in the written exam to pass the subject.

Basic bibliography

1. Bradley N. Miller, David L. Ranum. Problem Solving with Algorithms and Data Structures Using Python (Second Edition). Franklin, Beedle & Associates, 2011.

2. Rance D. Necaise. Data Structures and Algorithms Using Python. John Wiley & Sons, 2011.

3. John V. Guttag. Introduction to Computation and Programming Using Python (Third Edition). The MIT Press, 2021.

4. Gilles Brassard, Paul Bratley. Fundamentals of Algorithmics. Pearson, 1996.

5. Mark Summerfield. Programming in Python 3. A Complete Introduction to the Python Language (Second Edition). Addison-Wesley Professional, 2010.

In-depth bibliography

6. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (Third Edition). The MIT Press, 2009.
7. Steven S. Skiena. The Algorithm Design Manual (Second Edition). Springer, 2008.
8. Naomi Ceder. The Quick Python Book (Third Edition). Manning Publications, 2018.
9. David M. Beazley. Python Essential Reference (4th Edition). Addison-Wesley Professional, 2009.
10. Mark Lutz. Learning Python (Fifth Edition). O'Reilly Media, 2013.

Web addresses

Problem Solving with Algorithms and Data Structures Using Python - Official Website
https://runestone.academy/runestone/books/published/pythonds/index.html

MIT OCW Introduction to Computer Science and Programming in Python
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/

Python Programming Language - Official Website
http://python.org/

Python 3 documentation
https://docs.python.org/3/

The Python 3 Tutorial
https://docs.python.org/3/tutorial/