This course is the usual follow-up to the introduction to programming courses for studying the basic data structures and algorithms that allow an efficient solution to computational problems. The constant improvements in hardware are not enough to cope with the requirements of current software applications. In fact, advances in hardware are more fruitful when they are designed to process efficient algorithms. On the contrary, those advances in hardware are irrelevant if the algorithms and data structures are not fit to the purpose of the software application.



Research on data structures and algorithms has been a non-stop activity in recent decades. That research has set up a body of knowledge that is a basic requirement for a computer professional. Mastering that knowledge will allow the professional to assess the algorithmic solutions proposed in the context of the specific software that he/she has to build (especially with reference to the running time of the programs).



This course is an introduction to data structures and algorithms that provides the elements for other more advanced courses that are taught in later courses in degrees of Informatics Engineering and Artificial Intelligence.



It is recommended that the student has previously acquired knowledge of basic programming and object-oriented programming in Java.

Learning outcomes



1. To know the fundamental concepts of data structures and algorithms for solving common computer science problems and to apply them correctly.

2. To be able to design algorithms of medium complexity and translate them into a computer program, using the appropriate language primitives, including object orientation, when appropriate.

3. To know how to implement the most appropriate algorithms and data structures in a programming language to effectively solve the problems addressed. To know how to identify the sources of inefficiency in a program.

4. To know and to use, among others, access, insertion and ordering algorithms for the data structures used. To use the recursive design in problem solving with the appropriate data structures.

5. To know how to evaluate the cost in time and memory of the solutions proposed and developed by the student himself/herself. To use skilfully some software development tools and environments.

Topic 1. Analysis of algorithms.

1.1. Asymptotic notation. Cost function.

1.2. Comparing Growth Functions.

Topic 2. Linear Structures. Implementation and characteristics.

2.1. Stacks and Queues

2.2. Sorting and searching

2.3. Lists.

2.4. Iterators.

Topic 3. Recursive design.

3.1. Recursion in program design

3.2. Sorting and searching with recursion

Topic 4. Trees.

4.1. Non-linear data structures.

4.2. Recursion design

4.3. Binary Search Trees.

4.4. Other types of trees.

Topic 5. Hashing. Hash tables and Maps.

Topic 6. Graphs. Graph traversal algorithms. Backtracking algorithms.

6.1. Definitions. Directed and Undirected graphs

6.2. Graph traversals.

The topics will be presented in classroom lectures and in laboratory sessions. There are other not on-site activities.

The classroom sessions will be devoted to presenting the topics. Other sessions will further elaborate and discuss the answers to the proposed exercises. Laboratory sessions will be used to work in the practical aspects. The methodology assumes continuous attendance to lectures, working on the solutions to the proposed problems and the active participation in the class sessions.



This course follows a problem-solving approach in both individual and group settings, where the student(s) are confronted with different problem descriptions that they have to solve. Students should be able to work autonomously with the teaching material and references provided. There is the possibility of developing a small programming project as part of the learning process.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • Written test to be taken (%): 70
  • Realization of Practical Work (exercises, cases or problems) (%): 30

There are two alternative types of assessment for this course: the continuous assessment (1) or the global assessment (2).



(1) Continuous assessment (out of 10 points)



The final grade of the course is computed by adding the points obtained in

(a) Programming Activities (a maximum of 3 points)

(b) Individual assessments (a maximum of 7 points).



The student must get 50% of the maximum points in each part (a) and (b).



For the assessment purposes, the content of the course is divided into three parts that will be assessed in three or two individual exams, with a weight of 25%-25%-20% or 50%-20%, respectively. The exam dates will be the days assigned to the course in the special weeks and the day assigned by the Junta de Facultad for the first global assessment. The final grade of the individual assessments is the sum of those intermediate assessments.



The programming assignments will consist of, either or both, individual and group exercises that will be carried out throughout all weeks of the course.



The continuous assessment is available to those students who can follow the course in a regular way, attending classroom lectures and laboratories, and handing in the proposed exercises on time. Otherwise, the student may be excluded from the continuous assessment. The provisional enrolment will become final once both the request by the student at the specified dates (around week 11) has been verified and the student performances have been assessed by the professor. The student will go under the global assessment if he/she renounces the Continuous Assessment.



(2) Global assessment (out of 10 points).



This assessment will consist of two parts: a final exam and a programming practice problem.

(a) The final written exam will be graded in 7 out of 10 points. The student will have to get 3.5 points, at least, to pass the course.

(b) The programming practice problem will be graded in 3 out of 10 points, and the student will have to get 1.5 points, at least.



It is assumed that the student renounces the global assessment if he/she does not show up at the exam classroom.



The use of books, notes, as well as telephone, electronic, computer or any other device by students will be prohibited during the development of the exams, unless stated otherwise.

The extra exam or supplemental session will be assessed in the same way as the regular exam session.

- eGela platform.
- Eclipse programming environment.
- Java programming language.

Basic bibliography

- "Algorithms", 4th edition. Robert Sedgewick and Kevin Wayne. Addison Wesley, (2011).

- "Java software structures : designing and using data structures" John

Lewis, Joseph Chase. 4th edition. Addison Wesley (2014).

In-depth bibliography

- "Introduction to Algorithms" (3rd edition) Cormen, Leiserson, Rivest & Stein. MIT press (2009).
- "Data Structures and Algorithm Analysis in Java" (Third edition). Mark Allen Weiss. Pearson (2012).

Web addresses

- Algorithms, 4th edition (R. Sedgewick):
http://algs4.cs.princeton.edu
- Dictionary of Algorithms and Data Structures:
http://xlinux.nist.gov/dads/
- JavaTM Platform, Standard Edition:
https://www.java.com/en/download/
- Eclipse.org