Programming and Algorithms I

Credits
6
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
This course is the introduction to programming for new students of the AI degree. The course will revolve around the concept of Abstraction, emphasizing the process by which one is able to solve problems using function-based abstraction.

Teachers

Person in charge

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 the most basic concepts of programming with functions (simple and high-order) and their use as tools to adapt a programming language to the domain of the problem to be solved
      Related competences: CG2, CT6, CE03, CE10, CE12,
    2. Learn the concept of recursion and how to distinguish iterative and recursive processes defined with recursive functions
      Related competences: CG4, CT6, CE03, CE10, CE12,
    3. Initiate the student in the understanding of the concept of software design
      Related competences: CG4, CT6, CE03, CE10,
    4. Being able to deal with the idea of an error in a program and using exceptions to cope with these errors
      Related competences: CG4, CE10,
    5. Learn the concept of container and the situations in which it is relevant to use them. Know the cost of its use (informally)
      Related competences: CG4, CT6, CE02, CE04,
    6. Introduce the student to the computation of the complexity of algorithms
      Related competences: CE13,
    7. Involve the student in the design and implementation of a simple problem collaborating with other students
      Related competences: CG2, CG4, CG8, CT4, CE03, CE10,

    Contents

    1. Building Abstractions with Functions: Functions (simple and high-order). Environments. Execution flow control.
      The student is introduced to the main problem-solving mechanism, from a bottom-up point of view, of designing functions that bring the programming language closer to the domain of the problem. The mechanisms of function definition, parameter passing, environment and scope, and the main control structures of the execution flow (conditional, iterative) are studied.
    2. Building Abstractions with Functions: Recursion and examples.
      The fact that a function is able to call itself is introduced, and how this leads to recursion as a conceptual mechanism for solving problems, and the idea of process. Recursive functions may define iterative and recursive processes.
    3. Building Abstractions with Functions: Design. Error handling with exceptions.
      The concept of designing a program to solve a problem is introduced. The idea of error in a program and how to deal with them by means of the exception mechanism is introduced.
    4. Building Abstraccions with Functions: Examples of solving problems
      The concepts introduced so far are reinforced with numerous problems of low and medium difficulty.
    5. Building Abstractions with Functions: Containers
      We start working with containers provided by the programming language: Sequences, Lists, Dictionaries and others implemented within the course, such as Matrices or Trees.
    6. Building Abstractions with Functions: Mutability. Iterators and Generators.
      The concept of mutability is first seen in relation to lists, and the advantages and disadvantages of having immutable data structures are discussed. Iterators and generators are introduced as new control structures.
    7. Introduction to Algorithm Complexity
      A short introduction is made to asymptotic notation and to the complexity in the worst case of some notable algorithms seen during the course.

    Activities

    Activity Evaluation act


    Building Abstractions with Functions: Functions and Control Structures

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

    Building Abstractions with Functions: Containers, Iterators, Generators.

    The student should pay attention to the lecture and he/she should work through the exercises suggested by the lecturer.
    Objectives: 5 7
    Contents:
    Theory
    12h
    Problems
    0h
    Laboratory
    14h
    Guided learning
    0h
    Autonomous learning
    30h

    Algorithm Complexity

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

    Midterm Exam


    Objectives: 1 2 3 4
    Week: 7
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final Exam


    Objectives: 5 6 7
    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

    Web links

    • Aquest és el text PRINCIPAL de l'assignatura, la font d'informació primària per a tot allò que expliquem a classe. http://www.composingprograms.com/
    • Aquest és el curs CS 61A: Structure and Interpretation of Computer Programs, de l'Universitat de Berkeley, en el que aquest curs està basat https://cs61a.org/
    • 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

    Students are expected to have acquired the knowledge and skills defined for the scientific-technical branch of upper secondary school education or equivalent.