Algorithms and Data Structures

Algorithms and data structures (218 - 13873)
Study: Bachelor in Informatics Engineering
Semester 2/Spring Semester
1st Year Course/Lower Division

Students are expected to have completed:

- Programming
- Calculus

Compentences and Skills that will be Acquired and Learning Results:

Competences
CECRI1 (1 ECTS) Evidence Assessment: PRACTICE LABORATORY, WORK TEAM (CASE)
CECRI6 (Algorithms) (1.5 ECTS) Evidence Assessment: TESTING, LABORATORY PRACTICE, GROUP AND INDIVIDUAL WORK
CECRI7 (TYPES AND DATA STRUCTURES) (2.5 ECTS) Evidence Assessment: TESTING, LABORATORY PRACTICE, GROUP AND INDIVIDUAL WORK
CGB4 (0.50 ECTS) Evidence Assessment: PRACTICE LABORATORY TEAM WORK
CGB% (0.50 ECTS) Evidence Assessment: LABORATORY PRACTICE, GROUP WORK

1. Generic/Transversal Competences.
- Capacity to analyze and synthesize (PO e).
- Capacity to organize and plan the work (PO d).
- Resolution of problems (PO e).
- Working as a team (PO d).
- Capacity to put in practice theory knowledge (PO e).
2. Specific Competences.
a. Cognitive (to know).
- General knowledge about algorithms (PO a).
- Understanding of basic data structures (PO k).
- Familiarity with advanced data structures (PO k).
b. Procedural/instrumental (to be able to do).
- To be able to design and analyze the algorithms complexity (PO a).
- To be able to understand and use different data structures (PO k).
- To be able to implement program solutions to specific problems using these tools (PO e).

c. Attitude (Being)
- Ability to solve problems through algorithms (PO e).
- Ability to clarify, simplify and efficiency of solving problems (PO e and k).
- Ability to question and conclude various solutions to any problem (PO e and k).

The learning outcomes are:

Individual work:
Resolution by students of problems that must prove they have the ability to combine theory and practice.

Group work:
Case Study on design and implementation of data structures.

Description of Contents: Course Description

1. Introduction
a. Abstract Data Type and Data Structure
b. ADT Specification and Implementation

2. Linear Abstract Data Types
a. Definition Linear ADT
b. Stacks
c. Queues..
d. Lists.

3. Algorithms I: recursion.
a. Recursion
b. Divide and Conquer
c. BackTracking

4. Algorithms II: Complexity
a. Analysis of Algorithms
b. Types of complexity
c. Function Time.
d. Notation Big-O.
e. Worst and best cases.
5. Hierarchic Abstract Data types: Trees
a. General Trees
b. Binary Trees
c. Tree Trasverse: preorder, inorder, postorder
d. Search Binary Trees.
e. Balanced BST.

6. Graphs
a. Definition Graph ADT. Applications
b. Implementation based on adjacency matrix.
c. Implementation based on adjacency list.
d. Graph trasversal: Depth-first search and breadth-first search.

Learning Activities and Methodology:

1. Theory Lectures with the objective of acquire the cognitive specific competences (PO a and k).
2. Academic activities guided by the teacher:
2.1. With the teacher: to solve exercises devoted to analyze, design and implement cases with different level of complexity in collaboration with students (PO a and k). Some of the exercises will be carried out in computer laboratories (PO k).
2.2. Student work: Homework, individually or cooperatively, with exercises, implementation cases and basic readings from bibliography proposed by the teacher (PO k and e).
Moreover, these activities can be performed as:
a. Individual work consisting on developing solutions to the problems and exercises posed by the teacher.
b. Working cooperatively developing solutions to the problems proposed by the teacher (PO d).
3. Mid-term partial exam and final exam (PO a, e, k).
4. There will be a group tutorship for each small group to solve the queries and doubts of students.

Assessment System:

In addition to serve as formative activity, the exercises and examinations serve to be used as evaluation measure.
During the course, two worksheets will be published at "Aula Global" site. Students should also try to solve a practical case study using the concepts learned during the course.
The evaluation includes the assessment of the guided academic activities and practical work according to the following weighting:
Mid- term partial exam : 20 % (Po a, e, k)
Practical case study: 15% (Po a, e, d, k)
Deliver of exercises (at least 80%): 5% (Po a, e, k)
Final exam: 60 % (Po a, e, k). This exam is mandatory for all students. Students must earn a grade of at least 4 (4/10) in order to pass the subject. The final grade must be higher than 5.

If a student chooses not to follow the continuous evaluation, he/she must take the final exam. In this case, the grade obtained in the exam is 60% of the final grade.

---
In the extraordinary exam, its grade will be the 100% of the final grade.

Basic Bibliography:

Isabel Segura Bedmar, Harith Al-Jumaily, Julian Moreno Schneider, Juan Perea. A friendly notebook on Data Structures and Algorithms. Reprografia/Univerisdad Carlos III. 2011
Isabel Segura Bedmar, Harith AlJumaily, Julian Moreno Schneider, Juan Perea & Nathan D. Ryan. Algorithms and Data Structures. OCW-UC3M: http://ocw.uc3m.es/ingenieria-informatica/algorithms-and-data-structures. 2011
Isabel Segura Bedmar, Harith AlJumaily, Julian Moreno Schneider, Juan Perea & Nathan D. Ryan. Algorithms and Data Structures. OCW-UC3M: http://ocw.uc3m.es/ingenieria-informatica/algorithms-and-data-structures. 2011
Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in JAVA, 4th edition, 2006. John Wiley & Sons.

Additional Bibliography:

Mark Allen Weiss. Data Structures and Algorithms analysis in Java, 2nd edition, 2007. Pearson Addison Wesley.
Rowe G. W.. An introduction to Data Structures and Algorithms with Java. Prentice Hall.