Programming and Algorithms I

You are here

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

  • Jordi Delgado Pin ( )

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


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
Type: theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Final Exam


Objectives: 5 6 7
Week: 15 (Outside class hours)
Type: theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

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)

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.