Algorithmics and Programming II

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Data Science and Engineering » Curriculum » Syllabus » 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

  • Jordi Cortadella Fortuny ( )

Others

  • Jordi Petit Silvestre ( )
  • Pau Fernandez Duran ( )

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, CE2, CG1, CG2, CG5,

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
8h

Partial examination (with computer)


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

Final examination (on paper)



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

Final examination (with computer)



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

Project delivery



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

Development of content 2


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

Development of content 3


Objectives: 1
Contents:
Theory
9h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
20h

Development of content 4


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

Development of content 5


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

Development of content 6


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

Development of content 7



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

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

Bibliography

Basic:

Complementary:

Web links

Previous capacities

Those acquired at the course AP1-GCED.