Logo UAB
2021/2022

Graphs, Topology and Discrete Geometry

Code: 104349 ECTS Credits: 6
Degree Type Year Semester
2503758 Data Engineering OB 1 2
The proposed teaching and assessment methodology that appear in the guide may be subject to changes as a result of the restrictions to face-to-face class attendance imposed by the health authorities.

Contact

Name:
César Pablo Corcoles Briongos
Email:
Cesar.Corcoles@uab.cat

Use of Languages

Principal working language:
english (eng)
Some groups entirely in English:
No
Some groups entirely in Catalan:
No
Some groups entirely in Spanish:
No

Teachers

Joan Serra Sagristà
Miguel Hernández Cabronero
David Marín Pérez

Prerequisites

 There are no prerequisites. However, students should be familiar with the most basic concepts of programming, fundamental algebra, such as set theory and applications. It is also recommended for students to have taken the courses “Fundamentals of Mathematics” and "Fundamentals of Programming".

 

Objectives and Contextualisation

 The course deals with topics included in the area of Discrete Mathematics focussing on the study of discrete objects. It begins with basic graph theory, path optimisation, algorithms in graphs and complexity of algorithms and problems. Following this, it contemplates basic concepts related to topology and discrete topology, as well as basic concepts on the geometry of curves and surfaces.

 

Competences

  • Develop critical thinking and reasoning and know how to communicate it effectively in both your own language and in English.
  • Make adequate representations of information both from a computational and a mathematical viewpoint.
  • Search, select and manage information and knowledge responsibly.
  • Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.
  • Work cooperatively in complex and uncertain environments and with limited resources in a multidisciplinary context, assuming and respecting the role of the different members of the group.

Learning Outcomes

  1. Develop critical thinking and reasoning and know how to communicate it effectively in both your own language and in English.
  2. Identify and interpret the fundamental descriptors and properties of representations based on the geometry of the data.
  3. Identify and recognise the basic graph-traversing algorithms and demonstrate the capacity to optimise them.
  4. Interpret and apply the basic properties of directed and non-directed graphs.
  5. Search, select and manage information and knowledge responsibly.
  6. Students must be capable of collecting and interpreting relevant data (usually within their area of study) in order to make statements that reflect social, scientific or ethical relevant issues.
  7. Work cooperatively in complex and uncertain environments and with limited resources in a multidisciplinary context, assuming and respecting the role of the different members of the group.

Content

Part I

  1. Previous concepts: sets, functions and complexity of algorithms

    1. Sets and operations with sets

    2. Cartesian product and binary relations

    3. Combinatorial elements

    4. Finite sets, infinite and numerable

    5. Complexity of algorithms and problems

    6. Functions of complexity. Polynomial and non-polynomial complexity

  1. Fundamentals of graphs

    1. Definitions. Variants of graphs

    2. Paths, circuits and distances

    3. Degrees and handshaking lemma

    4. Subgraphs and important types of graphs

    5. Graphic sequences (Havel-Hakimi)

    6. Graph representation

  1. Walk, trail, paths and optimal generating trees

    1. Exploration of graphs (DFS and BFS)

    2. Minimum cost paths (Dijkstra, Floyd)

    3. Characterization of trees

    4. Optimal generating trees (Kruskal)

  1. Planarity and colouring

    1. Basic results
    2. Characterization of planar graphs
    3. Colouring of planar graphs
     
  2. Algorithmic complexity

Part II

  1. Topology

    1. Topological space and basic properties

    2. Isomorphisms

    3. Simplexes, meshes and graphs as encoders of a discrete topology

  1. Geometry of curves and surfaces

    1. Parametric curves

    2. Parameter arc, implicit parametrization and level curves

    3. Basic descriptors of a curve in space: Triedre de Frenet, torsion and curvature

  1. Surface geometry

    1. Parametric surfaces

    2. Tangent space

    3. First and second fundamental forms

    4. Difeomorphisms

    5. Geodesic and minimal cost paths

Methodology

Theoretical course contents will be discussed in lectures. Regular, autonomous Personal Work will be expected from the students; lectures will not be based on reading available and required materials. These should be worked individually prior to sessions to maximize learning outcome.

During problem sessions, problems from a predefined list will be discussed, related to the course goals. Consistently with theory lectures, regular independent Personal Work will be required to maximize learning. In particular, individual solutions to a selection of problems will be expected prior to each session, and discussed in class.

Lab sessions will be held to assist the students in acquiring hands-on experience in topics related to the Syllabus. Microprojects will be completed by the students, who will be required to produce some deliverables.

Teaching will be predominantly in English.

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.

Activities

Title Hours ECTS Learning Outcomes
Type: Directed      
Labs 12 0.48 5, 1, 2, 3, 4, 6, 7
Problem sessions 12 0.48 5, 1, 2, 3, 4, 6
Theory lectures 26 1.04 5, 1, 2, 3, 4, 6
Type: Supervised      
Office hours 5 0.2 5, 1, 2, 3, 4, 6
Preparation of problems and lab submissions 12.5 0.5 5, 1, 2, 3, 4, 6, 7
Type: Autonomous      
Personal work 50 2 5, 1, 2, 3, 4, 6
Preparation for final exam 25 1 5, 1, 2, 3, 4, 6

Assessment

Continuous-assessment dates (and any change to them) will be published on the Campus Virtual.

Subject assessment (out of 10 points) will be carried out as follows:

Theory (6 points total):

Two individual partial tests, 6 points (3 points each). The first partial test will be given at the end of the first three chapters of the course; the second partial test will be given on finishing all the chapters of the course. These individual tests will consist mostly of exercises in the style of those worked on during the course; a smaller part will consist of more theoretical questions.

Final exam, 6 points. Those who have not passed the subject through the individual partial tests will have the option to take a single final exam as a re-assessment grade to compensate for both individual partial tests.

Problems (1.5 points):

As part of continuous assessment, activities must be carried out or exercises must be solved by applying the given algorithms (via online quizzes, for example). The non-online activities or exercises will take place during the exercise sessions.

Labs (2.5 points):

As part of continuous assessment, certain deliverables must be submitted, which will be anounced with appropriate anticipation. The final score of this part will be calculated as the average score of these submissions.

An overall grade of 5 or higher is required to pass the subject. A "non-assessable" grade cannot be assigned to students who have participated in any of the individual partial tests or the final exam. No special treatment will be given to students who have completed the course in previous academic years, except that the lab lab/seminar previously obtained can be assigned to this course gradebook. In order to pass the course with honours, the final grade must be a 9.0 or higher. Because the number of students with this distinction cannot exceed 5% of the number of students enrolled in the course, this distinction will be awarded to whoever has the highest final grade. In case of a tie, partial-test results will be taken into consideration.

It is important to bear in mind that no assessment activities will be permitted for any student at a different date or time to that established, unless for justified causes duly advised before the activity and with the lecturer’s previous consent. In all other cases, if an activity has not been carried out, this cannot be re-assessed.

In the case of exercise resolution, a review may be requested after the date of the activity or the date of closure of the quiz. For all other assessment activities, a place, date and time of review will be indicated allowing students to review the activity with the lecturer. In this context, students may discuss the activity grade awarded by the lecturers responsible for the subject. If students do not take part in this review, no further opportunity will be made available.

Plagiarism and other academic irregularities

Notwithstanding other disciplinary measures deemed appropriate, and in accordance with the academic regulations in force, assessment activities will receive a zero whenever a student commits academic irregularities that may alter such assessment. Assessment activities graded in this way and by this procedure will not be re-assessable. If passing the assessment activity or activities in question is required to pass the subject, the awarding of a zero for disciplinary measures will also entail a direct fail for the subject, with no opportunity to re-assess this in the same academic year. Irregularities contemplated in this procedure include, among others: the total or partial copying of a practical exercise, report, or any other evaluation activity; allowing others to copy; presenting group work that has not been done entirely by the members of the group; presenting any materials prepared by a third party as one’s own work, even if these materials are translations or adaptations, including work that is not original or exclusively that of the student; having communication devices (such as mobile phones, smart watches, etc.) accessible during theoretical-practical assessment tests (individual exams).

To consult the academic regulations approved by the Governing Council of the UAB, please follow this link: http://webs2002.uab.es/afers_academics/info_ac/0041.htm

Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Submission of lab deliveries 25% 3 0.12 5, 1, 2, 3, 4, 6, 7
Tests based on exercises from the problems class 15% 1.5 0.06 5, 1, 2, 3, 4
Two partial exams 60% 3 0.12 5, 2, 3, 4, 6

Bibliography

  • J.M. Basart. Grafs: fonaments i algorismes. Manuals de la UAB, 13. Servei de publicacions de la UAB, 1994.
  • C. Berge. Graphs. North-Holland, 1991.
  • N.L. Biggs. Matemàtica discreta. Vicens-Vives, 1994.
  • N. Christofides. Graph theory, an algorithmic approach. Academic Press, 1975.
  • J. Gimbert, R. Moreno, J.M. Ribó, M. Valls. Apropament a la teoria de grafs i als seus algorismes. Eines 23, edicions de la UdL, 1998.
  • F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
  • M. P. do Carmo. Geometría diferencial de curvas y superficies. Alianza Editorial, 1995.
  • J. R. Munkres, Topología, Prentice-Hall, 2a edición, 2002.
  • M. Spivak. Cálculo en variedades. Editorial Reverté, 2a edición, 1970.
  • W. A. Sutherland, Introduction to metric and topological spaces, 2nd edition, Oxford University Press, 2009.

Software

The projects for lab assessment will be programmed in Python.