Algorithmics and Programming II

Credits
7.5
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
Web
http://www.cs.upc.edu/~jordicf/Teaching/AP2
The mathematical analysis of the algorithms is introduced and the tools are presented to calculate its cost. These foundations are used to study and analyse the design and the different implementations of several algorithms and fundamental data structures (stacks, queues, lists, priority queues, trees, binary search trees, balanced trees, hash tables and graphs) . The necessary tools are introduced to implement these data structures and their associated algorithms. Moreover, object orientation and the use of external libraries are examined in detail.

Teachers

Person in charge

Others

Weekly hours

Theory
3
Problems
0
Laboratory
2
Guided learning
0
Autonomous learning
7.5

Competences

Technical Competences

Technical competencies

  • CE2 - To be able to program solutions to engineering problems: Design efficient algorithmic solutions to a given computational problem, implement them in the form of a robust, structured and maintainable program, and check the validity of the solution.

    • Transversal Competences

    Transversals

  • CT4 - Teamwork. Be able to work as a member of an interdisciplinary team, either as a member or conducting management tasks, with the aim of contributing to develop projects with pragmatism and a sense of responsibility, taking commitments taking into account available resources.
  • CT5 [Avaluable] - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
  • CT6 - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.
  • CT7 - Third language. Know a third language, preferably English, with an adequate oral and written level and in line with the needs of graduates.

    • Basic

  • CB5 - That the students have developed those learning skills necessary to undertake later studies with a high degree of autonomy

    • Generic Technical Competences

    Generic

  • CG1 - To design computer systems that integrate data of provenances and very diverse forms, create with them mathematical models, reason on these models and act accordingly, learning from experience.
  • CG2 - Choose and apply the most appropriate methods and techniques to a problem defined by data that represents a challenge for its volume, speed, variety or heterogeneity, including computer, mathematical, statistical and signal processing methods.
  • CG5 - To be able to draw on fundamental knowledge and sound work methodologies acquired during the studies to adapt to the new technological scenarios of the future.

    • Objectives

    1. Being able to design, analyze, implement algorithms that solve problems using algorithmic and programming techniques.
      Related competences: CB5, CT4, CT5, CT6, CT7, CG1, CG2, CG5, CE2,

    Contents

    1. Abstract Data Types.
      Specification and implementation. Abstraction, functional and data decomposition, information hiding and encapsulation. Object-oriented languages: classes and objects, private and public methods, constructors and destructors. Genericity. Examples: point, rectangle, rational numbers.
    2. Algorithm analysis.
      Cost in time and space. Worst, best and average case. Asymptotic notation. Analysis of the cost of iterative and recursive algorithms. Examples: insertion and selection sort, maximum subsequence sum, convex hull.
    3. Divide and conquer.
      Principles: partition into subproblems, recombination of solutions. Master theorem. Examples: binary search, merge sort, quick sort, quick select, finding the two closest points in a plane. Fast Fourier Transform (FFT).
    4. Memory management.
      Representation of data in memory. Pointers and references. Dynamic memory management (vector class). Memory layout of a program (code, stack, heap).
    5. Basic containers.
      Operations, usage and implementations of stacks, queues, priority queues and lists.
    6. Graphs.
      Representations: adjacency matrices, adjacency lists and implicit representations. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Algorithms for shortest paths (Dijsktra, Bellman-Ford). Algorithms for minimum spanning trees (Prim and Kruskal). Algorithms for the maximum flow problem (Ford-Fulkerson).
    7. Sets and dictionaries.
      Trees and their representation. Binary trees and traversals (pre-order, post-order, in-order and level-order). Binary search trees and balanced trees: operations and implementation. Hashing.

    Activities

    Activity Evaluation act


    Development of content 1


    Objectives: 1
    Contents:
    Theory
    5h
    Problems
    0h
    Laboratory
    3h
    Guided learning
    0h
    Autonomous learning
    9h

    Partial examination (with computer)


    Objectives: 1
    Week: 7 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final examination (on paper)



    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final examination (with computer)



    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Project delivery



    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Development of content 2


    Objectives: 1
    Contents:
    Theory
    5h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    12h

    Development of content 3


    Objectives: 1
    Contents:
    Theory
    7h
    Problems
    0h
    Laboratory
    5h
    Guided learning
    0h
    Autonomous learning
    20h

    Development of content 4


    Objectives: 1
    Contents:
    Theory
    3h
    Problems
    0h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    7.5h

    Development of content 5


    Objectives: 1
    Contents:
    Theory
    7h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    16h

    Development of content 6


    Objectives: 1
    Contents:
    Theory
    9h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    21h

    Development of content 7



    Contents:
    Theory
    7h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    16h

    Teaching methodology

    The syllabus is presented in a very practical way, through the presentation of many examples.

    The theory classes introduce all the necessary concepts and techniques, which are put into practice in the classes of problems and laboratory through a collection of problems and exercises in an automatic judge.

    Every week, there are two hours of theory classes, one hour of problems and two hours of laboratory.

    The course uses C++ and Python as programming languages.

    Evaluation methodology

    The final grade of the course takes into account the following evaluation acts:
    * P1: individual programming project to be delivered in mid-course
    * P2: programming project (in pairs) to be delivered in at the end of the course
    * PL: partial laboratory exam (with computer)
    * FL: final laboratory exam (with computer)
    * FT: final theory exam (with paper)

    The project grade is calculated as: P = (P1 + P2)/2
    The exams grade is calculated as: X = max (0.3 PL + 0.4 FT + 0.3 FL, 0.5 FT + 0.5 FL)

    The final grade N is calculated as:
    * N = max(0.3 P + 0.7 X, 0.15 P + 0.85 X), if X >= 4
    * N = 0.15 P + 0.85 X, if X < 4

    Students who fail the subject can take the reevaluation exams RL (laboratory) and RT (theory). The grades of these exams will substitute FL and FT, respectively, in the formula of the computation of the final grade.

    Bibliography

    Basic

    Complementary

    Web links

    Previous capacities

    Those acquired at the course AP1-GCED.