| Data Structures | Code: 22.610 : 6 |
Data structures are an abstraction used in the world of computer science to represent information like that used in nature. Let’s make an analogy on means of transport. In this context, we have different alternatives for moving people or objects. A very sustainable bicycle is designed for very short journeys and only allows one person to be transported. A car has a greater range but the ability to carry people or objects remains limited. A bus significantly increases the ability to transport people and their autonomy. A truck significantly increases the ability to carry objects but not people. An airplane increases the ability to carry people, their autonomy and at the same time increases their costs. River transport further increases storage capacity. There are many more options than those presented, but with these, we get an idea of ¿¿which, with the tools available, and given a need would be the most "efficient" option.
There exist also many other approaches in the nature that can inspire us, for instance, how traditional paper dictionaries are organized, the queues that form at the entrance of a certain event, the pile of dishes in the sink, a mound of stones or fruits that we can collect from a fruit tree, among many others.
This course studies the several structures for representing data on a computer. At the same time, design tools and criteria are provided to make a good choice and determine the efficiency (in time and space) of the structures. All these concepts are put into practice and deepened through the development of a previously designed case study.
Data Structures is a compulsory course that builds on the knowledge already acquired in the previous programming courses. For instance, previous courses introduced some basic data structures, such as lists, stacks or queues. This course, expands this knowledge and introduces the concept of abstract data type (ADT), as a general model to describe a data structure and study its efficiency. Finally, the central core of the course consists of learning how to properly use each data structure and knowing how to select the most appropriate data structure for each situation.
The different data structures introduced in this course will be used in later courses, especially when there is the need to develop software where efficiency is a critical factor.
The design of data structures is a fundamental skill in the field of software development, especially in systems where efficiency is a critical factor.
This course requires fundamental notions of algorithms (assignments, conditionals, loops) and programming using the imperative paradigm (use of compilers and debuggers, use of an integrated development environment -IDE-, etc.). In addition, this course requires good knowledge of object-oriented programming, specifically using Java.
Before enrolling in this course, it is highly recommended to have passed the following courses:
- Fundamentals of Programming
- Programming in Practice
- Object-Oriented Programming.
This course has the following objectives:
To know in depth the most common data structures to represent the information of an application in memory.
Know how to calculate the spatial and temporal efficiency of a data structure and compare different alternatives.
Being able to identify the data structures used in a program and understand how they work.
Know the most common component libraries to represent data structures.
Know how to implement a program that uses data structures using the possibilities offered by object-oriented programming and the available libraries.
Know how to propose the most appropriate data structure for a specific application taking into account its characteristics.
This course addresses the following competences of the Bachelor's Degree in Techniques for Software Development:
CE3: Understand and use the scientific bases of software development to analyse each problem at the appropriate level of abstraction and apply the skills and knowledge acquired in order to solve them.
CE6: Design and build computer applications using development, integration and reuse techniques.
CE9: Propose and evaluate different technological alternatives for solving a specific software development problem.
- Abstract Data Types
- Algorithmic complexity
- Sequential containers (stacks, queues, lists, …)
- Trees
- Priority queues
- Tables
- Searches
- Graphs
- Collections
| Developer Mozilla. Resources for developers, by developers | Web |
| Data Structures Library | Web |
| Data Structures. Study Guide 3: Non-linear Data Structures | |
| Data Structures. Study Guide 2: ADT and Sequential Data Structures | |
| Data Structures. Study Guide 0: Weekly Guide | |
| Data Structures. Study Guide 1: Tooling | |
| Abstract data types (ADT) specifications |
The assessment process is based on the student's personal work and presupposes authenticity of authorship and originality of the exercises completed.
Lack of authenticity of authorship or originality of assessment tests, copying or plagiarism, the fraudulent attempt to obtain a better academic result, collusion to copy or concealing or abetting copying, use of unauthorized material or devices during assessment, inter alia, are offences that may lead to serious academic or other sanctions.
Firstly, you will fail the course (D/0) if you commit any of these offences when completing activities defined as assessable in the course plan, including the final tests. Offences considered to be misconduct include, among others, the use of unauthorized material or devices during the tests, such as social media or internet search engines, or the copying of text from external sources (internet, class notes, books, articles, other students' essays or tests, etc.) without including the corresponding reference.
And secondly, the UOC's academic regulations state that any misconduct during assessment, in addition to leading to the student failing the course, may also lead to disciplinary procedures and sanctions.
The UOC reserves the right to request that students identify themselves and/or provide evidence of the authorship of their work, throughout the assessment process, and by the means the UOC specifies (synchronous or asynchronous). For this purpose, the UOC may require students to use a microphone, webcam or other devices during the assessment process, and to make sure that they are working correctly.
The checking of students' knowledge to verify authorship of their work will under no circumstances constitute a second assessment.
|
This course can only be passed through continuous assessment (CA), the mark for which is combined with a practical (Pr) mark to give the final course mark. It is not planned to have any final test.The formula for accrediting the course is as follows: CA + Pr. |