Algorithmics

Credits
6
Types
Specialization compulsory (Computing)
Requirements
Department
CS;BSC;ENTEL
Web
http://www.cs.upc.edu/~mjserna/docencia/grauA/alg-GEI.html
Mail
alg@cs.upc.edu
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

Others

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.

    • 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,

    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
    6h
    Problems
    6h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    16h

    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
    8h
    Problems
    9h
    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
    8h
    Problems
    8h
    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
    1h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    4h

    Mid term exam

    Partial examination outside teaching hours. It covers the firs part of the syllabus and the topic assigned as autonomous learning work.
    Objectives: 1 2 5 6 7
    Week: 8 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final Exam

    Final exam on all the course topics
    Objectives: 1 2 3 4 5 7
    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Learning a topic outside the contents of the course

    At the beginning of the course, a topic of study will be proposed; this topic will form part of the syllabus for the midterm exam.

    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    10h

    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.

    In order to assess the autonomous learning skills, we will require the study of a particular subject, related with those in the course, but no exposed in any lecture. The subject will be proposed at the beginning of the course and evaluated inside the partial exam.

    Evaluation methodology

    The final grade 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 together with the topic associated to the autonomous learning) and the final exam (F).

    The final mark is obtained by the formula: 0.75 max(0.5 M + 0.5 F, F) + 0.15 E + 0.1 A

    The degree of acquisition of the "Autonomous learning" skill will be obtained from the corresponding question in the partial exam that contributes to te exam mark by 1 point. The qualitative grade for "Autonomous learning" is given according to the range in which the numerical grade falls: [0,0.25) => D, [0.25,0.5) => C, [0.5,0.75) => B, [0.75,1] => 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