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

Others

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)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Partial Exam


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

    Final Exam


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

    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.8 * Theory + 0.2 * Practice
    where:
    Theory: MAX(T2, 0.5 * T1 + 0.5 * T2)

    Reassessment: Only those who have failed the theory part, after taking the final exam, may take the reassessment. The maximum grade that can be obtained in the reassessment is 7.

    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