Programming and Algorithms II

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Artificial Intelligence » Curriculum » Syllabus » Programming and Algorithms II
Credits
6
Types
Compulsory
Requirements
This subject has not requirements, but it has got previous capacities
Department
CS
Second part of the Introduction to Programming course for students of the degree of AI (the complete course is PA1 + PA2). In this course we will focus essentially on data abstraction, defining new data structures (stacks, queues, lists, trees, graphs, heaps) or seeing how known data structures (sets and dictionaries) are implemented. At the end of the course we will see the continuation of the topic of complexity, which began at the end of PA1

Teachers

Person in charge

  • Jordi Delgado Pin ( )
  • Jose Luis Balcázar Navarro ( )

Others

  • Caroline König ( )

Weekly hours

Theory
2
Problems
0
Laboratory
2
Guided learning
0
Autonomous learning
6

Competences

Transversal Competences

Transversals

  • CT4 [Avaluable] - 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.
  • CT6 [Avaluable] - 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.

Technical Competences

Especifics

  • CE02 - To master the basic concepts of discrete mathematics, logic, algorithmic and computational complexity, and its application to the automatic processing of information through computer systems . To be able to apply all these for solving problems.
  • CE03 - To identify and apply the basic algorithmic procedures of computer technologies to design solutions to problems by analyzing the suitability and complexity of the proposed algorithms.
  • CE04 - To design and use efficiently the most appropriate data types and structures to solve a problem.
  • CE10 - To analyze, design, build and maintain applications in a robust, secure and efficient way, choosing the most appropriate paradigm and programming languages.
  • CE12 - To master the fundamental principles and models of computing and to know how to apply them in order to interpret, select, assess, model, and create new concepts, theories, uses and technological developments related to artificial intelligence.
  • CE13 - To evaluate the computational complexity of a problem, identify algorithmic strategies that can lead to its resolution and recommend, develop and implement the one that guarantees the best performance in accordance with the established requirements.

Generic Technical Competences

Generic

  • CG2 - To use the fundamental knowledge and solid work methodologies acquired during the studies to adapt to the new technological scenarios of the future.
  • CG4 - Reasoning, analyzing reality and designing algorithms and formulations that model it. To identify problems and construct valid algorithmic or mathematical solutions, eventually new, integrating the necessary multidisciplinary knowledge, evaluating different alternatives with a critical spirit, justifying the decisions taken, interpreting and synthesizing the results in the context of the application domain and establishing methodological generalizations based on specific applications.
  • CG8 - Perform an ethical exercise of the profession in all its facets, applying ethical criteria in the design of systems, algorithms, experiments, use of data, in accordance with the ethical systems recommended by national and international organizations, with special emphasis on security, robustness , privacy, transparency, traceability, prevention of bias (race, gender, religion, territory, etc.) and respect for human rights.

Objectives

  1. Learn new data structures: Stacks, Queues, Lists, Trees and Graphs and the algorithms associated with the necessary operations on these structures.
    Related competences: CG2, CG4, CT6, CE03, CE04, CE12,
  2. Learn different implementations of data structures: Implementations using simpler data structures provided by the programming language, and dynamic implementations.
    Related competences: CG2, CG4, CE02, CE03, CE04, CE12,
  3. Learn the basics of object oriented programming: Concepts of class, instance, method, inheritance (single and multiple), etc.
    Related competences: CG2, CG4, CT6, CE03, CE04, CE10,
  4. Extension of Computational Complexity: Big O, Big Omega, Master Theorems
    Related competences: CG2, CG4, CT6, CE02, CE12, CE13,
  5. Solve a small/medium-sized problem in group, applying what they have learned about object orientation
    Related competences: CG2, CG4, CG8, CT4, CE03, CE04, CE10,

Contents

  1. Trees and Graphs
    We will start the course using the data structures that the programming language provides us to implement Trees and Graphs. We will look at path algorithms for both structures, and other important algorithms related to these, such as Dijkstra's algorithm.
  2. Objects and Classes
    The fundamental concepts of object orientation are introduced: Class, object, instance, delegation, inheritance, etc. and other particularities of the implementation of object orientation specific to the programming language we work with.
  3. Dynamic data structures
    We will learn how to implement known data structures using the concept of reference to an object. We will re-implement data structures that the programming language provides by default, and new data structures that we have already seen implemented more easily.
  4. Sets and Dictionaries: Implementation
    We will look at different ways to implement sets and dictionaries: Hash Tables and Binary Search Trees (BSTs). The properties, advantages and disadvantages of these structures will be studied.
  5. Algorithm Complexity (II)
    In PA1 we started the study of the concept of complexity of a program, an algorithm and a problem, and we introduced the asymptotic notation, though only the definition of Theta (f). This topic is a continuation, where we will see the Big O, the Big Omega, etc., and the Master Theorems.

Activities

Activity Evaluation act


Building Abstractions with Data: Trees and Graphs

The student should pay attention to the lecture and he/she should work through the exercises suggested by the lecturer.
Objectives: 1 2
Contents:
Theory
4h
Problems
0h
Laboratory
5h
Guided learning
0h
Autonomous learning
10h

Building Abstractions with Functions: Objects and Classes

The student should pay attention to the lecture and he/she should work through the exercises suggested by the lecturer.
Objectives: 2 3
Contents:
Theory
8h
Problems
0h
Laboratory
8h
Guided learning
0h
Autonomous learning
16h

Building Abstractions with Data: Dynamic Data Structures

The student should pay attention to the lecture and he/she should work through the exercises suggested by the lecturer.
Objectives: 1 2
Contents:
Theory
6h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
10h

Sets and Dictionaries: Implementation

The student should pay attention to the lecture and he/she should work through the exercises suggested by the lecturer.
Objectives: 2 3
Contents:
Theory
4h
Problems
0h
Laboratory
4h
Guided learning
0h
Autonomous learning
8h

Algorithmic Complexity (II)

The student should pay attention to the lecture and he/she should work through the exercises suggested by the lecturer.
Objectives: 4
Contents:
Theory
6h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
8h

Practical Work

Students will do a pair practice related to a small-medium size problem.
Objectives: 1 2 3 5
Week: 15 (Outside class hours)
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
12h

Partial Exam


Objectives: 1 2 3
Week: 8 (Outside class hours)
Type: theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
12h

Final Exam


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

Teaching methodology

Teaching the course is structured in lectures and laboratory sessions.

Teachers will use lectures to introduce the essential contents of the course. In the laboratory sessions the contents of the course will be brought to the computer by carrying out practical problems. The laboratory classes will be a continuation of the lectures, where new concepts will be implemented as they appear in lectures.

Evaluation methodology

Grading the course will consist of two theoretical tests (T1 and T2), one mid-course and the other at the end, and one medium-sized practical work (Practice).

Then, the evaluation method would be:
0.6 * Theory + 0.4 * Practice
where:
Theory: MAX(T2, 0.5 * T1 + 0.5 * T2)

Teamwork:

Evaluated using a simple rubric that each group tutor group uses
to rank different aspects of teamwork of every member of the group.

Bibliography

Basic:

Complementary:

  • Python pocket reference - Lutz, Mark, O'Reilly Media , 2014. ISBN: 9781449356941

Web links

  • Aquest és el text PRINCIPAL de l'assignatura, la font d'informació primària per a tot allò que expliquem a classe. Tot i això, a PA2 hi ha temes que no apareixen en aquest text. http://composingprograms.com/
  • La principal referència del llenguatge de programació que fem servir: Python. No és un lloc on aprendre a programar, és un lloc on consultar detalls de les construccions i llibreries del llenguatge https://docs.python.org/3/reference/index.html

Previous capacities

PA1 course, or equivalent