Algorithms, Data Structures and Databases

You are here

Credits
6
Types
Elective
Requirements
This subject has not requirements, but it has got previous capacities
Department
CS-ESSI
This is a reinforcement course that covers basic concepts on algorithms, data structures and databases.

Teachers

Person in charge

  • Jordi Delgado Pin ( )
  • Oscar Romero Moral ( )

Weekly hours

Theory
1.8
Problems
0
Laboratory
1.8
Guided learning
0.214
Autonomous learning
6.85

Competences

Generic Technical Competences

Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG2 - Capability to lead, plan and supervise multidisciplinary teams.

Transversal Competences

Teamwork

  • CTR3 - Capacity of being able to work as a team member, either as a regular member or performing directive activities, in order to help the development of projects in a pragmatic manner and with sense of responsibility; capability to take into account the available resources.

Information literacy

  • CTR4 - Capability to manage the acquisition, structuring, analysis and visualization of data and information in the area of informatics engineering, and critically assess the results of this effort.

Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

Basic

  • CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous.

Objectives

  1. Calculate the efficiency of iterative and recursive algorithms
    Related competences: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Compare the efficiency of different algorithms for solving the same problem and select the most appropriate one.
    • Understand the definitions of the Big-O, Omega and Theta asymptotic notations and their usefulness in characterising the efficiency of algorithms in time and space.
    • Compute the cost of an algorithm in the worst, best and average cases.
  2. Review of simple data structures and its implementation: lists, stacks, queues, trees.
    Related competences: CG1, CB9, CTR4, CTR6,
  3. Understand, explain, design, analyse, compare and implement the main data structures that can be used to implement priority queues (trees, heaps).
    Related competences: CG1, CB9, CTR4, CTR6,
  4. Understand, explain, design, analyse, compare and implement the main data structures that can be used to implement dictionaries (tables, sorted tables, lists, sorted lists, hash tables, binary search trees, AVL trees).
    Related competences: CG1, CB9, CTR4, CTR6,
  5. Understand, explain, design, analyse, compare and implement algorithms that solve classic graph problems such as traversals, topological sorts, shortest paths, etc.
    Related competences: CG1, CB9, CTR4, CTR6,
  6. Understand, explain, design, analyse, compare and implement algorithmic schemes using diverse techniques (divide and conquer, greedy, backtracking, etc)
    Related competences: CG1, CB9, CTR4, CTR6,
  7. Identify computational limits: understand the implications of the question "P = NP?", understand the statement of Cook-Levin's Theorem, and recognise and identify several classic NP-complete problems.
    Related competences: CG1, CB9, CTR4, CTR6,
  8. Describe what is a database and a database management system
    Related competences: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Distinguish the objectives of a database management system from a file system
    • Enumerate the objectives of a database management system
  9. Effectively use the standard Structured Query Language (SQL) to query relational databases
    Related competences: CG1, CB9, CTR4, CTR6,
  10. Explain the relational data model, including its data structures, the relational algebra and integrity constraints
    Related competences: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Express any SQL query in terms of a relational algebra expression
  11. Identify the main objectives of a database management system query optimizer
    Related competences: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Explain what is a cost model and how to automatically generate physical access plans
    • Evaluate the main pros and cons of the most popular data structures used by database management systems given a workload characterized in terms of database cardinality, size and the operations expected and their selectivity factor
  12. Given a set of informational requirements, model the logic schema of a relational database
    Related competences: CG1, CB9, CTR4, CTR6,
  13. Put in practice the course content on algorithmics, data structures and databases to solve real-life problems
    Related competences: CG1, CG2, CB9, CTR3, CTR4, CTR6,

Contents

  1. Basics of Analysis of Algorithms
    Cost in time and space. Worst case, best case and average case. Asymptotic notation. Analysis of the cost of iterative and recursive algorithms. Recurrences
  2. Simple Data Structures: Review
    Operations. Lists, Stacks, Queues, Trees
  3. Priority Queues
    Operations of priority queues. Implementations with heaps. Heapsort.
  4. Dictionaries
    Operations of dictionaries and ordered dictionaries. Basic implementations: tables and lists. Advanced implementations: hash tables, binary search trees, AVL trees
  5. Graphs
    Representations: adjacency matrices, adjacency lists and implicit representation. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Dijkstra's algorithm for shortest paths. Prim's algorithm for minimum spanning trees.
  6. Algorithmic schemes
    Divide and conquer, Greedy algorithms, Dynamic Programming, Exhaustive search, Backtracking.
  7. Notions of Intractability
    Basic introduction to P and NP classes. NP-completeness.
  8. Introduction to databases and database management systems
    Main concepts on databases and database management systems. Relational database management systems.
  9. SQL: Data-definition language and data-manipulation language
    Introduction to the SQL language
  10. The relational model
    Data structures and integrity constraints. Views.
  11. The relational algebra
    The relational algebra operators and how to build data pipes with them. Notion of semantic and syntactic optimization.
  12. Logical design of relational databases
    Normalization theory. Translating conceptual schemas into relational schemas.
  13. Notions of physical design and physical database optimization
    Notions of query optimizer, access plan and cost model

Activities

Activity Evaluation act


Basics of Analysis of Algorithms

Cost in time and space. Worst case, best case and average case. Asymptotic notation. Analysis of the cost of iterative and recursive algorithms. Recurrences
Objectives: 1
Contents:
Theory
2h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
4h

Review of simple data structures

Operations. Lists, Stacks, Queues, Trees
Objectives: 2
Contents:
Theory
1.5h
Problems
0h
Laboratory
1.5h
Guided learning
0h
Autonomous learning
8h

Priority Queues

Operations of priority queues. Implementations with heaps. Heapsort.
Objectives: 3
Contents:
Theory
2h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
8h

Dictionaries

Operations of dictionaries and ordered dictionaries. Basic implementations: tables and lists. Advanced implementations: hash tables, binary search trees, AVL trees
Objectives: 4
Contents:
Theory
2h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
8h

Graphs

Representations: adjacency matrices, adjacency lists and implicit representation. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Dijkstra's algorithm for shortest paths. Prim's algorithm for minimum spanning trees.
Objectives: 5
Contents:
Theory
3h
Problems
0h
Laboratory
3h
Guided learning
2h
Autonomous learning
8h

Algorithmic schemes

Divide and conquer, Greedy algorithms, Dynamic Programming, Exhaustive search, Backtracking.
Objectives: 6
Contents:
Theory
5h
Problems
0h
Laboratory
5h
Guided learning
0h
Autonomous learning
11h

Notions of Intractability

Basic introduction to P and NP classes. NP-completeness.
Objectives: 7
Contents:
Theory
1h
Problems
0h
Laboratory
1h
Guided learning
0h
Autonomous learning
8h

First Partial Exam

This exam will assess the first 2/3 of the total content of the course
Objectives: 1 2 4 5 6 7 3
Week: 9
Type: theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Introduction to databases and database management systems

The student attends the lecture, takes notes and participates in the session exercises
Objectives: 8
Contents:
Theory
1h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2h

SQL

The student attends the lecture, takes notes and participates in the session exercises
Objectives: 9
Contents:
Theory
1h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
8h

The Relational Model

The student attends the lecture, takes notes and participates in the session exercises
Objectives: 10 12
Contents:
Theory
2h
Problems
0h
Laboratory
2h
Guided learning
1h
Autonomous learning
6h

Logical Design of Relational Databases

The student attends the lecture, takes notes and participates in the session exercises
Objectives: 10 12
Contents:
Theory
1h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
4h

Physical Optimization

The student attends the lecture, takes notes and participates in the session exercises
Objectives: 11
Contents:
Theory
4h
Problems
0h
Laboratory
1h
Guided learning
0h
Autonomous learning
8h

Second Partial Exam

Closed book exam on databases and database management systems
Objectives: 8 9 10 12 13 11
Week: 15
Type: theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Teaching methodology

During the master classes the lecturer provides material related to the topic and proposes exercises. During the labs the lecturer proposes material and exercises to be solved with the computer. For the algorithms and data structures part, the "Jutge" tool will be used. For the database part, the "Learn-SQL" tool will be used.

Due to the heterogeneous background of the students taking the course, and also due to the fact this is a reinforcement course on basic Computer Science concepts, the autonomous learning is extremely important in this course. The student will be provided with several exercise to be done at home (whenever possible, through "Jutge" or "Learn-SQL"). It is the student responsibility to adapt the autonomous workload to his / her background needs.

Evaluation methodology

Let P1 be the score of the first partial exam.
P2 the score of the second partial exam
EF the score of the final exam
Pr1 the score of the first practical work
Pr2 the score of the second practical work
Then,
NT = MAX(EF, P1*2/3 + P2*1/3)
NP = Pr1*2/3 + Pr2*1/3
So the final score will be 0.6*NT + 0.4*NP
Transversal competences will weight a 0% in the final score.

Bibliography

Basic:

Complementary:

Web links

Previous capacities

This course assumes basic competences in algorithms, data structures and databases. The course is structured to cope with different backgrounds and learning needs but basic knowledge on Computer Science principles is assumed: notions of computer architecture, basic programming constructs and data structures.