1. General information
Course:
DATA STRUCTURES
Code:
42312
Type:
CORE COURSE
ECTS credits:
6
Degree:
406 - UNDERGRADUATE DEGREE IN COMPUTER SCIENCE AND ENGINEERING (AB)
Academic year:
2022-23
Center:
604 - SCHOOL OF COMPUTER SCIENCE AND ENGINEERING (AB)
Group(s):
10
11
12
Year:
2
Duration:
First semester
Main language:
Spanish
Second language:
English
Use of additional languages:
English Friendly:
N
Web site:
Bilingual:
Y
Lecturer:
JUAN ANTONIO GUERRERO ABENZA
- Group(s):
10
11
Building/Office
Department
Phone number
Email
Office hours
Infante D. Juan Manuel/1A4
SISTEMAS INFORMÁTICOS
926053299
juan.guerrero@uclm.es
Available at the beginning of the academic year. See
http://www.esiiab.uclm.es
Lecturer:
GINES MORENO VALVERDE
- Group(s):
12
Building/Office
Department
Phone number
Email
Office hours
Infante D. Juan Manuel/1.C.9
SISTEMAS INFORMÁTICOS
2471
gines.moreno@uclm.es
Available at the beginning of the academic year. See
http://www.esiiab.uclm.es
2. Pre-Requisites
Students are expected to have already acquired (in previous subjects like Algebra and Calculus, first year) a basic mathematical background in logic, functions theory, algebraic structures and abstraction, as well as some experience in basic programming environments and the Java language (such concepts have been previously taught in the subjects Programming Foundations -I and II- and Information Systems).
3. Justification in the curriculum, relation to other subjects and to the profession
Data Structure belongs to the Programming block and it is included in the common module of Computer Science within de degree programme.
The subject can be seen as the natural continuation of Programming Foundations II, but here we study new data structures under several points of view which include, apart from its use, how they are formally defined and implemented, also allowing the possibility of being incorporated as a library into a programming environment.
The subject is also strongly connected with Programming Methodology, where several algorithmic patterns admit an immediate application on the new data structures (for instance, sorting linear ADTs, greedy/dynamic traversing of trees, optimal path searching on graphs, ...) as well as with Declarative Programming (speciality on Computation), where it is mandatory to have been acquired some basic notions on lists, recursion, etc. in order to reinforce some data structures after introducing new expressive resources like higher order, infinite data structures, and so on.
During the rest of the degree (and even furthermore, on their professional careers), students will be concerned with the implementation and manipulation of software applications using complex data structures. Modern languages usually provide some of them by default (lists, queues, ...), but they must be studied with some detail in order to be used correctly. Anyway, other more intrincate data structures (trees, graphs, ...), which are not directly available on typical programming environments, must be designed and incorporated into such tools. Furthermore, the use of data structures, from the point of view of their design and analysis, provide a good level of abstraction and programming skills (recursion, modularity ...) very useful in most tasks related to the development of software applications.
4. Degree competences achieved in this course
| Course competences | |
|---|---|
| Code | Description |
| BA04 | Basic knowledge about the uses and programming of computers, operating systems, data bases, and digital programmes with applications in engineering. |
| CO06 | Knowledge and application of basic algorithms in digital technologies for the development of solutions, analysing their appropriateness and complexity. |
| CO07 | Knowledge, design, and efficient use of types of data and structures which arise as most appropriate in problem solving. |
| CO08 | Ability to analyse, design, build and maintain applications in a strong, safe, and efficient manner by selecting the most appropriate paradigms and programming languages. |
| PER01 | Team work abilities. |
| PER04 | Interpersonal relationship skills. |
5. Objectives or Learning Outcomes
| Course learning outcomes | |
|---|---|
| Description | |
| Ability to manage types of data, data structures, and abstract tupes of data in an appropriate manner regarding their problems, as well as their formal specifications, implementations, and use of abstract types of lineal and non-lineal data | |
| Application of basic principles of structured design, led to objects for problem solving. | |
| Additional outcomes | |
| Not established. |
6. Units / Contents
-
Unit 1: Unit 1. Introduction.
-
Unit 1.1: Topic 1.1. Presentation and preliminary concepts.
-
Unit 1.2: Topic 1.2. Data structures and efficiency.
-
-
Unit 2: Unit 2. Formal description of ADTs.
-
Unit 2.1: Topic 2.1. Formal specification with Haskell.
-
Unit 2.2: Topic 2.2. Example: sets.
-
Unit 2.3: Topic 2.3. Implementing an ADT.
-
-
Unit 3: Unit 3. Linear ADTs.
-
Unit 3.1: Topic 3.1. Lists. Specification and examples.
-
Unit 3.2: Topic 3.2. Implementing lists.
-
Unit 3.3: Topic 3.3. Stacks and Queues. Specification and implementation.
-
-
Unit 4: Unit 4. Non linear ADTs. Trees.
-
Unit 4.1: Topic 4.1. General trees. Specification.
-
Unit 4.2: Topic 4.2. Binary trees. Specification and implementation.
-
Unit 4.3: Topic 4.3. Search trees. Implementation.
-
Unit 4.4: Topic 4.4. Balance and efficiency. AVL trees.
-
-
Unit 5: Unit 5. Graphs.
-
Unit 5.1: Topic 5.1. Introduction.
-
Unit 5.2: Topic 5.2. Specification of undirected graphs.
-
Unit 5.3: Topic 5.3. Static implementation of graphs.
-
7. Activities, Units/Modules and Methodology
| Training Activity | Methodology | Related Competences (only degrees before RD 822/2021) | ECTS | Hours | As | Com | Description | |
| Class Attendance (theory) [ON-SITE] | Lectures | BA04 CO06 CO07 CO08 | 0.68 | 17 | Y | N | ||
| Problem solving and/or case studies [ON-SITE] | Problem solving and exercises | BA04 CO06 CO07 CO08 PER01 PER04 | 0.68 | 17 | Y | N | ||
| Computer room practice [ON-SITE] | Problem solving and exercises | BA04 CO06 CO07 CO08 PER01 PER04 | 0.28 | 7 | Y | N | ||
| Computer room practice [ON-SITE] | Practical or hands-on activities | BA04 CO06 CO07 CO08 PER01 PER04 | 0.28 | 7 | Y | N | ||
| Progress test [ON-SITE] | Assessment tests | BA04 CO06 CO07 CO08 | 0.48 | 12 | Y | N | ||
| Final test [ON-SITE] | Assessment tests | BA04 CO06 CO07 CO08 | 0.24 | 6 | Y | N | ||
| Practicum and practical activities report writing or preparation [OFF-SITE] | Project/Problem Based Learning (PBL) | BA04 CO06 CO07 CO08 PER01 PER04 | 0.8 | 20 | Y | N | ||
| Study and Exam Preparation [OFF-SITE] | Self-study | BA04 CO06 CO07 CO08 PER01 PER04 | 2.56 | 64 | Y | N | ||
| Total: | 6 | 150 | ||||||
| Total credits of in-class work: 2.64 | Total class time hours: 66 | |||||||
| Total credits of out of class work: 3.36 | Total hours of out of class work: 84 | |||||||
As: Assessable training activity Com: Training activity of compulsory overcoming (It will be essential to overcome both continuous and non-continuous assessment).
8. Evaluation criteria and Grading System
| Evaluation System | Continuous assessment | Non-continuous evaluation * | Description |
| Progress Tests | 70.00% | 0.00% | Progress tests related to knowledge acquired in the classroom and/or laboratory ([ESC]50%, [LAB]20%) |
| Practicum and practical activities reports assessment | 20.00% | 20.00% | Practices and/or tasks submitted via Moodle ([INF]20%) |
| Assessment of active participation | 10.00% | 0.00% | Oral presentations in the classroom and/or laboratory ([PRES]10%) |
| Final test | 0.00% | 80.00% | Exam on the complete syllabus of the subject ([ESC]80%) |
| Total: | 100.00% | 100.00% |
According to art. 4 of the UCLM Student Evaluation Regulations, it must be provided to students who cannot regularly attend face-to-face training activities the passing of the subject, having the right (art. 12.2) to be globally graded, in 2 annual calls per subject , an ordinary and an extraordinary one (evaluating 100% of the competences).
Evaluation criteria for the final exam:
-
Continuous assessment:There is not a final term exam. Each student's final grade in the regular assessment will be based on the results from her/his work developed throughout the course. In order to achieve a passing grade in this subject, the total score of the sum (weighted sum according to the previous table, without requiring minimum marks on each item) of all the assignments to be assessed cannot be less than 50% of the maximum possible score.
By default, all students are enrolled in the continuous assessment mode. Those who wish to change to non-continuous evaluation must indicate it through the following link https://www.esiiab.uclm.es/alumnos/evaluacion.php before the end of the corresponding academic term, as long as 50% of the subject has not been evaluated, as established in the Student Evaluation Regulations. -
Non-continuous evaluation:Students are considered enrolled in the non-continuous evaluation trail whenever they develop less than 50% of the activities scheduled in continuous evaluation (tests + assignments/practices + participation).
By default, all students are enrolled in the continuous assessment mode. Those who wish to change to non-continuous evaluation must indicate it through the following link https://www.esiiab.uclm.es/alumnos/evaluacion.php before the end of the corresponding academic term, as long as 50% of the subject has not been evaluated, as established in the Student Evaluation Regulations.
There are two final tests exclusively for those who do not follow the continuous assessment: one on the complete syllabus of the subject (80%), and another on the practical activities reports (20%). These reports are the same than the ones offered in continuous assessment, although their presentation will be done in just one session.
To pass the subject, the sum of the marks from the previous tests (complete syllabus of the subject and practical activities reports) cannot be less than 50% of the maximum achievable mark.
Specifications for the resit/retake exam:
Same criteria as in the non continuous evaluation.
Specifications for the second resit / retake exam:
Same criteria as in the non continuous evaluation (and resit/retake exam).
9. Assignments, course calendar and important dates
| Not related to the syllabus/contents | |
|---|---|
| Hours | hours |
| Final test [PRESENCIAL][Assessment tests] | 6 |
| Unit 1 (de 5): Unit 1. Introduction. | |
|---|---|
| Activities | Hours |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Study and Exam Preparation [AUTÓNOMA][Self-study] | 6 |
| Unit 2 (de 5): Unit 2. Formal description of ADTs. | |
|---|---|
| Activities | Hours |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 3 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 1 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 1 |
| Practicum and practical activities report writing or preparation [AUTÓNOMA][Project/Problem Based Learning (PBL)] | 2 |
| Study and Exam Preparation [AUTÓNOMA][Self-study] | 10 |
| Unit 3 (de 5): Unit 3. Linear ADTs. | |
|---|---|
| Activities | Hours |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 4 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Progress test [PRESENCIAL][Assessment tests] | 4 |
| Practicum and practical activities report writing or preparation [AUTÓNOMA][Project/Problem Based Learning (PBL)] | 6 |
| Study and Exam Preparation [AUTÓNOMA][Self-study] | 16 |
| Unit 4 (de 5): Unit 4. Non linear ADTs. Trees. | |
|---|---|
| Activities | Hours |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 4 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Progress test [PRESENCIAL][Assessment tests] | 4 |
| Practicum and practical activities report writing or preparation [AUTÓNOMA][Project/Problem Based Learning (PBL)] | 6 |
| Study and Exam Preparation [AUTÓNOMA][Self-study] | 16 |
| Unit 5 (de 5): Unit 5. Graphs. | |
|---|---|
| Activities | Hours |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 4 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Problem solving and/or case studies [PRESENCIAL][Problem solving and exercises] | 2 |
| Progress test [PRESENCIAL][Assessment tests] | 4 |
| Practicum and practical activities report writing or preparation [AUTÓNOMA][Project/Problem Based Learning (PBL)] | 6 |
| Study and Exam Preparation [AUTÓNOMA][Self-study] | 16 |
| Global activity | |
|---|---|
| Activities | hours |
| General comments about the planning: | This course schedule is APPROXIMATE. It could vary throughout the academic course due to teaching needs, bank holidays, etc. A weekly schedule will be properly detailed and updated on the online platform (Virtual Campus). Note that all the lectures, practice sessions, exams and related activities performed in the bilingual groups will be entirely taught and assessed in English. Classes will be scheduled in 3 sessions of one hour and a half per week. |
10. Bibliography and Sources
| Author(s) | Title | Book/Journal | Citv | Publishing house | ISBN | Year | Description | Link | Catálogo biblioteca |
|---|---|---|---|---|---|---|---|---|---|
| Java ES con NetBeans + Documentación | http://java.sun.com/javase/downloads/index.jsp | ||||||||
| Java. Tutorial online | http://java.sun.com/docs/books/tutorial/java/TOC.html | ||||||||
| Página oficial de Haskell | http://haskell.org | ||||||||
| Tutorial de Haskell | http://www.haskell.org/tutorial/ | ||||||||
| Bird, R.; Walder, P. | Introducción a la Programación Funcional en Haskell | Prentice-Hall | 84-8322-176-4 | 2000 | http://books.google.es/books?id=xIlyOiGOC6EC&printsec=frontcover&dq=haskell+bird&hl=es&ei=-ACQTLa9IIHxOe6WqOkM&sa=X&oi=book_result&ct=result&resnum=1&ved=0CC4Q6AEwAA#v=onepage&q&f=false |
|
|||
| Ehrig, H., Mahr, B. | Fundamentals of Algebraic Specifications | Springer-Verlag | 3-540-51799-5 | 1990 | http://books.google.es/books?id=sq1Ktr9W3RgC&lpg=PA41&dq=abstract%20data%20types&pg=PP1#v=onepage&q=abstract%20data%20types&f=false | ||||
| Goodrich, Michael T. | Data structures and algorithms in Java | Wiley & Sons | 978-0-470-39880-7 | 2011 |
|
||||
| Lafore, R. | Data Structures and algorithms in Java | Sams Publishing | 2002 | ||||||
| Lewis, John | Estructuras de datos con Java : diseño de estructuras y algo | Pearson Educación | 84-205-5034-5 | 2006 |
|
||||
| Nell, Dale | Abstract data types : specifications, implementations and ap | D. C. Heath and Company | 978-0-669-40000-7 | 1996 | http://books.google.es/books?id=hJ6IOaiHVYUC&printsec=frontcover&dq=Dale+Walker+Abstract+data+types |
|