Algorithmics

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Informatics Engineering » Curriculum » Syllabus » Algorithmics
Credits
6
Types
Specialization compulsory (Computing)
Requirements
  • Prerequisite: EDA
  • Precorequisite: PE
  • Corequisite: PROP
Department
CS;BSC;ENTEL
Web
http://www.cs.upc.edu/~mjserna/docencia/grauA/alg-GEI.html
Mail
Algorithmics is the science that studies algorithms, their properties and their efficiency. Algorithmics aims at developing methods and techniques for designing efficient algorithms and data structures (DS) and for their analysis; another goal is the development of algorithms and DS that solve specific problems. After a brief review of basic concepts and known algorithmic techniques, we will study new techniques such as the greedy method, dynamic programming, network flows, linear programming and randomization. Each of the studied design and analysis techniques is illustrated with specific examples, many of which are fundamental algorithms and DS with significant practical impact such as Dijkstra's algorithm to compute the shortest paths in a graph, the algorithm to compute the edit distance between two strings, Rabin's primality test or Ford-Fulkerson algorithm to find the optimal flow in a network.

Teachers

Person in charge

  • Maria Jose Serna Iglesias ( )

Others

  • Amalia Duch Brown ( )
  • Conrado Martínez Parra ( )
  • Maria Josep Blesa Aguilera ( )
  • Santiago Marco Sola ( )

Weekly hours

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

Competences

Technical Competences

Common technical competencies

  • CT1 - To demonstrate knowledge and comprehension of essential facts, concepts, principles and theories related to informatics and their disciplines of reference.
    • CT1.2C - 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.
  • 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.
  • CT5 - To analyse, design, build and maintain applications in a robust, secure and efficient way, choosing the most adequate paradigm and programming languages.
    • 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.

Transversal Competences

Autonomous learning

  • G7 [Avaluable] - To detect deficiencies in the own knowledge and overcome them through critical reflection and choosing the best actuation to extend this knowledge. Capacity for learning new methods and technologies, and versatility to adapt oneself to new situations.
    • G7.3 - Autonomous learning: capacity to plan and organize personal work. To apply the acquired knowledge when performing a task, in function of its suitability and importance, decide how to perform it and the needed time, and select the most adequate information sources. To identify the importance of establishing and maintaining contacts with students, teacher staff and professionals (networking). To identify information forums about ICT engineering, its advances and its impact in the society (IEEE, associations, etc.).

Technical Competences of each Specialization

Computer science specialization

  • CCO1 - To have an in-depth knowledge about the fundamental principles and computations models and be able to apply them to interpret, select, value, model and create new concepts, theories, uses and technological developments, related to informatics.
    • CCO1.1 - To evaluate the computational complexity of a problem, know the algorithmic strategies which can solve it and recommend, develop and implement the solution which guarantees the best performance according to the established requirements.
  • CCO2 - To develop effectively and efficiently the adequate algorithms and software to solve complex computation problems.
    • CCO2.5 - To implement information retrieval software.
  • CCO3 - To develop computer solutions that, taking into account the execution environment and the computer architecture where they are executed, achieve the best performance.
    • CCO3.1 - To implement critical code following criteria like execution time, efficiency and security.
    • CCO3.2 - To program taking into account the hardware architecture, using assembly language as well as high-level programming languages.

Objectives

  1. Knowing greedy algorithms, to identify when and how you can apply them, knowing the most common techniques to prove correctness and becoming familiar with some basic greedy algorithms, e.g, Dijkstra's algorithm, Kruskal's and Prim's algorithms.
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, G7.3,
  2. Understanding the dynamic programming scheme, to identify when and how you can apply it and become familiar with some fundamental dynamic programming algorithms, eg, Floyd's algorithm or calculating the edit distance
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, G7.3,
  3. Knowing the basic problem of optimal flows on networks, to become familiar with a basic algorithm (Ford-Fulkerson), to understand the maxflow-mincut theorem, to recognize when a problem can be formulated in terms of a flow problem
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, G7.3,
  4. To understand the importance of randomization in the design of algorithms and data structures, to become familiar with some basic techniques of probabilistic analysis needed to study the efficiency of randomized algorithms and with some classic examples.
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, G7.3,
  5. To know about some computational problems that arise in specific areas of CS as diverse as search in document databases,
    protein and genomic databases, geographic information systems, content-based information retrieval, data compression, etc. and to know some advanced data structures to respond to these needs
    Related competences: CT1.2C, CCO2.5, CCO1.1, CT4.1, CT4.2, CT5.2, CCO3.1, G7.3,
  6. Becoming familiar with the use of algorithmic design principles for the design of data structures and to learn some essential techniques to obtain implementations which yield maximum efficiency and take advantage of the specific hardware features supporting the execution
    Related competences: CT1.2C, CCO1.1, CT4.1, CT4.2, CT5.2, CCO3.1, CCO3.2, G7.3,
  7. To develop the necessary habits, attitudes and skills to be able to study, alone or in a team, a specific subject, making use of available sources of information (bibliography, web, ...) and to achieve the level of knowledge and compression of the subject which is enough to explain it to others, writing a summary and preparing a supplementary visual material
    Related competences: G7.3,
  8. To understand some basic principles for the design of computational experiments and to learn basic techniques of data collection, validation and statistical analysis of the collected data, and how to draw conclusions, recognizing the need, usefulness and limitations of experimental studies in design and implementation of algorithms and data structures
    Related competences: CT4.1, CT4.2, CT5.2, CT5.4, CCO3.1, CCO3.2, G7.3, CT5.3,

Contents

  1. Basic Algorithmic Concepts
    Worst case analysis. Asymptotic Notation. Divide and conquer. Analysis of recursive algorithms. Linear sorting. Graph algorithms. Randomization.
  2. Greedy algorithms
    The scheme for greedy algorithms. Task scheduling. Bellman-Ford' and Johnson's algorithms for shortest paths. Kruskal's and Prim's algorithms for minimum spanning trees. Union-find. Huffman codes.
  3. Dynamic Programming
    Principle of optimality. Memoization. Floyd-Warshall algorithm for all-shortest paths. Traveling salesman problem. Knapsack problem. Other examples.
  4. Network Flows
    Basic concepts. Maxflow-mincut theorem. The Ford-Fulkerson algorithm. Applications: Matching and Edge disjoint paths. Duality.
  5. Advanced Data Structures and Algorithms
    A selection of some of the following algorithms and/or data structures (or others). Linear Programming. Fibonacci heaps. Hashing. Bloom Filters. Blockchains. Map Reduce. Random graphs. Page Rank.

Activities

Activity Evaluation act


Basic Algorithmic Concepts

To remind the basic concepts learnt in previous courses, and to become familiar with the terminology and notation that will be used throughout the course. Learn other basic algorithmic techniques.
  • Autonomous learning: - Study of theory and problems seen in class - Resolution of the exercises in advance

Contents:
Theory
4h
Problems
4h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Greedy algorithms

Attend lectures and problem sessions where this subject is exposed, do the exercises proposed by the teacher to do at home or in class
  • Autonomous learning: - Study of theory and problems seen in class - Resolution of the exercises in advance
Objectives: 1
Contents:
Theory
5h
Problems
4h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Dynamic Programming

Attend lectures and problem sessions where this subject is exposed, do the exercises proposed by the teacher to do at home or in class
  • Autonomous learning: - Study of theory and problems seen in class - Resolution of the exercises in advance
Objectives: 2
Contents:
Theory
7h
Problems
10h
Laboratory
0h
Guided learning
0h
Autonomous learning
15h

Network Flows

Attend lectures and problem sessions where this subject is exposed, do the exercises proposed by the teacher to do at home or in class
  • Autonomous learning: - Study of theory and problems seen in class - Resolution of the exercises in advance
Objectives: 3
Contents:
Theory
7h
Problems
10h
Laboratory
0h
Guided learning
0h
Autonomous learning
15h

Advanced Data Structures

Attend lectures and problem sessions where this subject is exposed, do the exercises proposed by the teacher to do at home or in class
  • Autonomous learning: - Study of theory and problems seen in class - Resolution of the exercises in advance
Objectives: 5 6
Contents:
Theory
2h
Problems
2h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Autonomous Learning Project

The teacher makes a brief interview with each of the student teams to discuss the written documentation and audiovisual material delivered, find out how the activity has been developed over the course, finding out about planning issues, if there was any, finding out what mechanisms have been used to coordinate the parts of the work carried out by the team, etc.. The teacher assesses the degree of learning of the proposed subject by the students by means of short specific questions and the achievement of the activity goals
Objectives: 1 2 3 4 5 6 7 8
Week: 6 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
15h

Final Exam/Second partial


Objectives: 1 2 3 4 5 7
Week: 15 (Outside class hours)
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Mid term exam

Partial examination outside teaching hours.
Objectives: 1 2 5 6 7
Week: 8
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Project supervision

Solve doubts, follow up of the activity, etc.
Objectives: 6 7 8
Contents:
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
6h
Autonomous learning
0h

Teaching methodology

Theory lectures will be magistral, with theoretical explanations from the teacher, interspersed with numerous examples. Students should actively participate with their questions and comments along these classes. Each week there will be two hours of lectures and two hours devoted to problems. In problem sessions, there will be discussion of the solutions proposed by the students to the exercises posed by the teacher in advance (more complex assignments, with which the student has been able to work during the week, autonomously) or of the short exercises posed during the class to be worked by teams of two-four students or individually. Occasionally, the students could be required to expose their solutions to the rest of their mates. During the course, written handouts of the solution of 3-4 problems will be required, these solutions will be corrected by other students.

To complement personal study and practical problem solving in paper, a programming project will be proposed. In the project, the student must design and encode programs in C++ that solve the proposed problems, for instance, to implement two (or more) algorithms that solve the same problem and to carry out experiments that allow to compare the performance of the algorithms, and at the same time, to compare these performances with the predictions of the theoretical analysis. Each student will have to develop the project in a team of two or three people.
This project will be used to assess the autonomous learning skills, as it will require the study of a particular subject, related with those in the course, but no exposed in any lecture.

Evaluation methodology

The final grade (NF) is calculated from the mark of the resolution of algorithmic problems (A), the mark of the handout and corrections of problems (P), that of the mid term exam (M) (subject corresponding to the 6 -7 first weeks of the course), the final exam (F) and the project note associated with autonomous learning (P).

The final mark is obtained by the formula

Si (M+F)/2 < 3.5, NF = (M+F)/2

Si (M+F)/2 >= 3.5, NF = 0.5 max(0.5 M + 0.5 F, F) + 0.2 P + 0.2 E + 0.1 A


The teacher will assess the degree of acquisition of the "Autonomous learning" skill from the score earned in a programming project that involves autonomous learning on the part of the students. The score P will be graded in a numerical scale from 0 to 10.

The qualitative grade for "Autonomous learning" is given according to the range in which the numerical grade falls: [0,5) => D, [5,6.5) => C, [6.5, 8.5) => B, [8.5, 10] => A

Bibliography

Basic:

Complementary:

Previous capacities

- Familiarity with the basic programming techniques and the programming language C + +: iterations, alternative, recursive functions, parameter passing, pointers, references, dynamic memory, classes, objects, methods, ...

- Knowledge of basic algorithmic concepts: efficiency of algorithms, asymptotic notation, graphs, graph traversals, data structures (lists, search trees, hashing, heaps, ...)

- Basic knowledge of discrete mathematics, linear algebra and calculus

- Basic knowledge of probability theory and statistics

- Basic knowledge of computer architecture and memory hierarchy