Data Structures and Algorithmics

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Informatics Engineering » Curriculum » Syllabus » Data Structures and Algorithmics
Credits
6
Types
Compulsory
Requirements
Department
CS
Web
http://www.cs.upc.edu/~eda
This course begins by introducing the concepts of efficiency and cost of an algorithm and the basic mathematical tools to analyze them. These tools are then used to study and analyze the design and the different implementations of classic and fundamental algorithms and data structures.

Teachers

Person in charge

  • Albert Oliveras Llunell ( )

Others

  • Amalia Duch Brown ( )
  • Antoni Lozano Boixadors ( )
  • Conrado Martínez Parra ( )
  • Daniel Benedí García ( )
  • Elisabet Burjons Pujol ( )
  • Ilario Bonacina ( )
  • Irene Simó Muñoz ( )
  • Salvador Roura Ferret ( )

Weekly hours

Theory
2
Problems
1
Laboratory
1
Guided learning
0.4
Autonomous learning
5.6

Competences

Technical Competences

Common technical competencies

  • CT2 - To use properly theories, procedures and tools in the professional development of the informatics engineering in all its fields (specification, design, implementation, deployment and products evaluation) demonstrating the comprehension of the adopted compromises in the design decisions.
    • CT2.3 - To design, develop, select and evaluate computer applications, systems and services and, at the same time, ensure its reliability, security and quality in function of ethical principles and the current legislation and normative.
    • CT2.4 - To demonstrate knowledge and capacity to apply the needed tools for storage, processing and access to the information system, even if they are web-based systems.
  • CT4 - To demonstrate knowledge and capacity to apply the basic algorithmic procedures of the computer science technologies to design solutions for problems, analysing the suitability and complexity of the algorithms.
    • CT4.1 - To identify the most adequate algorithmic solutions to solve medium difficulty problems.
    • CT4.2 - To reason about the correction and efficiency of an algorithmic solution.
    • CT4.3 - To demonstrate knowledge and capacity to apply the fundamental principles and the basic techniques of the intelligent systems and its practical application.
  • CT5 - To analyse, design, build and maintain applications in a robust, secure and efficient way, choosing the most adequate paradigm and programming languages.
    • CT5.1 - To choose, combine and exploit different programming paradigms, at the moment of building software, taking into account criteria like ease of development, efficiency, portability and maintainability.
    • CT5.2 - To know, design and use efficiently the most adequate data types and data structures to solve a problem.
    • CT5.3 - To design, write, test, refine, document and maintain code in an high level programming language to solve programming problems applying algorithmic schemas and using data structures.
    • CT5.4 - To design the programs¿ architecture using techniques of object orientation, modularization and specification and implementation of abstract data types.
    • CT5.5 - To use the tools of a software development environment to create and develop applications.
  • CT8 - To plan, conceive, deploy and manage computer projects, services and systems in every field, to lead the start-up, the continuous improvement and to value the economical and social impact.
    • CT8.6 - To demonstrate the comprehension of the importance of the negotiation, effective working habits, leadership and communication skills in all the software development environments.
    • CT8.7 - To control project versions and configurations.

Transversal Competences

Information literacy

  • G6 [Avaluable] - To manage the acquisition, structuring, analysis and visualization of data and information of the field of the informatics engineering, and value in a critical way the results of this management.
    • G6.2 - After identifying the parts of an academic document and organizing the bibliographic references, to design and execute a good strategy to make an advanced search with specialized information resources, selecting the pertinent information taking into account relevance and quality criteria.

Objectives

  1. 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.
    Related competences: CT4.2,
  2. Calculate the efficiency of iterative algorithms using appropriate calculation rules.
    Related competences: CT4.2,
  3. Describe the efficiency of recursive algorithms using recurrence relations and understand and apply master theorems to solve them.
    Related competences: CT4.2,
  4. Design algorithms for solving various problems of medium difficulty with time and space constraints.
    Related competences: CT4.1, CT4.2,
  5. Compare the efficiency of different algorithms for solving the same problem and select the most appropriate one.
    Related competences: CT4.1, CT4.2,
  6. Understand, explain, design, analyse, compare and implement algorithms (such as mergesort, quicksort, Karatsuba, Strassen, etc.) using divide and conquer.
    Related competences: CT4.1, CT4.2, CT5.3,
  7. 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: CT4.1, CT4.2, CT5.2, CT2.4,
  8. Understand, explain, design, analyse, compare and implement the main data structures that can be used to implement priority queues (trees, heaps).
    Related competences: CT4.1, CT4.2, CT5.2, CT2.4,
  9. Understand, explain, design, analyse, compare and implement algorithms that solve classic graph problems such as traversals, topological sorts, shortest paths, etc.
    Related competences: CT4.1, CT4.2, CT5.2, CT2.4,
  10. Understand, explain, design, analyse, compare and implement exhaustive search algorithms using the backtracking technique.
    Related competences: CT4.1, CT4.2, CT2.4, CT4.3,
  11. 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: CT4.2,
  12. Complete and modify C++ programming language implementations of several algorithms to solve medium-difficulty problems
    Related competences: CT4.2, CT5.2, CT5.1,
  13. Identify and propose solutions to efficiency problems in algorithms and programs written in the C++ programming language.
    Related competences: CT4.1, CT4.2, CT5.2, CT2.4, CT2.3,
  14. Analyse a strategy game for designing and programming an effective, efficient, collaborative and competitive player that maximises the chances of winning the game and is capable of establishing partnerships and coordinating with other players.
    Related competences: CT8.6, CT8.7, CT4.1, CT4.2, CT5.2, CT5.4, CT5.5, G6.2, CT2.4, CT4.3, CT5.1, CT5.3, CT2.3,
  15. Apply information search strategies (for bibliographic references, scientific articles, patents, credible web resources, etc.) and, making an ethical use of the compiled information and properly citing sources, produce a well-structured document describing a well-known algorithm that solves a given problem.
    Related competences: G6.2,
  16. Compute the cost of an algorithm in the worst, best and average cases.
    Related competences: CT4.2,

Contents

  1. 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.
  2. Divide and conquer
    Principles: partition into subproblems, recombination of solutions. Examples: mergesort, quicksort, Karatsuba's algorithm for multiplying large numbers, Strassen's algorithm for matrix multiplication.
  3. Dictionaries
    Operations of dictionaries and ordered dictionaries. Basic implementations: tables and lists. Advanced implementations: hash tables, binary search trees, AVL trees.
  4. Priority Queues
    Operations of priority queues. Implementations with heaps. Heapsort.
  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. Exhaustive Search and Generation
    Principles: solution space, partial solutions, pruning. Generation of subsets and permutations. Examples: knapsack, travelling salesman.
  7. Notions of Intractability
    Basic introduction to P and NP classes, Cook-Levin's Theorem, reductions and NP-completeness.

Activities

Activity Evaluation act


Analysis of Algorithms

Topic 1 development.
Objectives: 1 2 3 5 4 16
Contents:
Theory
4h
Problems
2h
Laboratory
2h
Guided learning
0h
Autonomous learning
8h

Divide and conquer

Topic 2 development.
Objectives: 3 5 4 6 12 13
Contents:
Theory
4h
Problems
2h
Laboratory
2h
Guided learning
0h
Autonomous learning
8h

Dictionaries

Topic 3 development.
Objectives: 5 4 7 12 13
Contents:
Theory
3.5h
Problems
2h
Laboratory
2h
Guided learning
0h
Autonomous learning
8h

Priority Queues

Topic 4 development.
Objectives: 5 4 8 12 13
Contents:
Theory
1.5h
Problems
2h
Laboratory
1h
Guided learning
0h
Autonomous learning
4h

Mid-semester written exam

Learning objectives corresponding to topics 1 and 2 will be assessed.
Objectives: 1 2 3 5 4 6 12
Week: 6 (Outside class hours)
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Graphs

Topic 5 development.
Objectives: 5 4 9 12 13
Contents:
Theory
4h
Problems
2h
Laboratory
2h
Guided learning
0h
Autonomous learning
8h

Game Presentation

Becoming familiar with the Game: first matches, visualizations and debugging.
Objectives: 14
Contents:
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
0.5h

Game

Goals corresponding to learning objective 15 will be assessed. A statement describing a strategy game will be published. Students will have to program a player for this game (i.e. implement a strategy aimed at winning). A competition will be carried out in which students will play against each other, from which a ranking will be obtained. To participate in the competition, the players of the students will have to pass a qualification test. The grade corresponding to this part will be computed from the position in the ranking in a proportional way, ensuring that the winner gets a 10 and that all students with a qualified player get a minimum of 5. Those students who have not been able to qualify a player will get a 0.
Objectives: 14
Week: 9 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Game development

Learning the most appropriate strategies for the Game. Learning the solution to the most common questions about the Game.
Objectives: 14
Contents:
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
2.5h

Exhaustive Search and Generation

Topic 6 development.
Objectives: 5 4 10 12 13
Contents:
Theory
4h
Problems
2h
Laboratory
4h
Guided learning
0h
Autonomous learning
8h

Notions of Intractability and Undecidibility

Topic 7 development.
Objectives: 11
Contents:
Theory
4h
Problems
3h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Grand Final of the Game

Attending the Game Grand Final. Learning the strategies used by the winners.
Objectives: 14
Contents:
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
2h
Autonomous learning
1.5h

RGF library science tutorials.

Self-learning through the BRGF library science tutorials on: intellectual property, the ethical use of information and the use of reference management software.
Objectives: 15
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
2.5h

Practical on sound use of computer resources.

Goals corresponding to learning objective 16 will be assessed. A statement will be published consisting in the description of a computational problem and the name of an algorithm to solve it. Students will conduct research (in the library, on the web, etc.) into the problem and the algorithm and will write a brief, well-structured document that properly lists sources. The document should be handed in on the day of the final exam. Students' generic competences will be assessed on the basis of this document.
Objectives: 15
Week: 14 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Computer-based exam

Laboratory aspects, i.e. implementation aspects, of the topics covered up to the date will be assessed. Students will be issued two or three problems in front of their computer. These problems will have a statement, one or more public test suites and, possibly, an already implemented code. When students are ready to submit programs for particular problems, they upload them to an automatic judge which returns a verdict on program behaviour. Students can submit up to 10 solutions for the same problem. The lecturer will correct the last solution submitted for each problem.
Objectives: 7 8 9 10
Week: 15 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
4h

Final Exam

Learning objectives for content corresponding to topics 1 to 7 will be assessed.
Objectives: 1 2 3 5 4 6 7 8 9 10 12 13 11
Week: 15 (Outside class hours)
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Teaching methodology

Topics are explained in a practical way through the use of numerous examples.

Theory classes cover the required concepts and techniques, which are put into practice in the problem-solving and laboratory classes by means of a collection of problems and exercises from an automatic judge.

The two-hour theory class will take place once a week. The two-hour laboratory class will take place once a fortnight. The two-hour problem-solving class will take place once a fortnight.

Programming for the game integrates knowledge and skills of the entire course.

The C++ programming language is used for this course.

Evaluation methodology

NPP = written mid-semester exam grade (0 to 10)
NO = computer-based exam grade (0 to 10)
NF = final exam grade (0 to 10)
NJ = game grade (0 to 10)


GRADE = mín(10, màx (22.5%NPP + 22.5%NF + 45%NO + 20%NJ , 45%NF + 45%NO + 20%NJ))

Bibliography

Basic:

Complementary:

Web links

  • MIT OpenCourseWare: és una publicació gratuïta dels materials dels cursos del Massachusets Institute of Technology (MIT) que mostra la majoria de temes que s'ensenyen en el MIT. Conté apunts, exercicis, exercicis resolts, exàmens i videos de classes. MIT OpenCourseWare: es una publicación gratuita de los materiales de los cursos del Massachusets Institute of Technology (MIT) que muestra la mayoría de temas que se enseñan en el MIT. Contiene apuntes, ejercicios, ejercicios resueltos, exámenes y vídeos de clases. MIT OpenCourseWare: it is a free publication of the materials of the courses of the Massachusets Institute of Technology (MIT) that shows most of the topics that are taught in MIT. Contains notes, exercises, solved exercises, exams and videos of classes. http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science
  • UVa Online Judge http://uva.onlinejudge.org/
  • Algorithms Courses on the WWW: és un llistat exhaustiu d'enllaços a portals web relacionats amb algorísmia i complexitat: cursos de diverses universitats, software, aplicacions gràfiques, pàgines personals d'investigadors coneguts, entre d'altres coses. Algorithms Courses on the WWW: es un listado exhaustivo de enlaces a portales web relacionados con la algoritmia y complejidad: cursos de varias universidades, software, aplicaciones gráficas, páginas personales de investigadores conocidos, entre otras cosas. Algorithms Courses on the WWW: it is an exhaustive listing of links to web sites related to algorithms and complexity: courses of several universities, software, graphic applications, personal pages of well-known researchers, among other things. http://www.cs.pitt.edu/~kirk/algorithmcourses/index.html
  • The Stony Brook Algorithm Repository: és un portal web amb una col·lecció d'implementacions de més de setanta algorismes fonamentals d'optimització combinatòria. The Stony Brook Algorithm Repository: es un portal web con una colección de implementaciones de más de setenta algoritmos fundamentales de optimitzación combinatoria. The Stony Brook Algorithm Repository: it is a web site with a collection of implementations of more than seventy fundamental algorithms of combinatorial optimitzation. http://www.cs.sunysb.edu/~algorith/
  • TopCoder http://www.topcoder.com
  • Transparències de K. Wayne per al curs "Algorithms and Data Structures" de la Princeton University https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php
  • Jutge https://www.jutge.org/

Previous capacities

Students are expected to be familiar with imperative object-based programming techniques:
- parameter passing
- classes,
- objects,
- methods,
- pointers,
- dynamic memory,
- genericity,
- recurrence,
- standard classes usage,
- iterators

They are also expected to know at least one imperative object-oriented language, preferably C++.

Critical thinking capacity and mathematical maturity are required too.