Degree | Type | Year | Semester |
---|---|---|---|
2500149 Mathematics | OB | 2 | 1 |
BMath first year courses Linear Algebra-100088 and Fundamental Mathematics-100089.
Discrete Mathematics is a field of mathematics that studies finite mathematical objects. It covers topics such as combinatorics, graph theory, cryptography, error-correcting codes, combinatorial design theory, game theory, logic, optimization, or algorithm design and analysis that can be applied to solve problems in any of the above-mentioned branches. Most of discrete mathematics has evolved relatively recently, motivated by the challenges mainly in computer science and operations research. The chapters of this introductory course are quite independent from one another. A prior knowledge of linear algebra, modular arithmetic, basic combinatorics, and -fundamentally- mathematical language and reasoning should be adequate to understand the subject matter of each chapter.
The first chapter addresses the topic of generating functions and recurrent sequences, this being a natural next step following the elementary combinatorics studied in the first year course Fundamental Mathematics. Once again, problems in combinatorics require training the skill of formulating a problem in terms of a mathematical statement. The second chapter deals with graphs, which are a fundamental tool for problem solving in quite different settings, ranging from the most abstract mathematics up to operations research. In some cases, a graph-theoretical formulation of the problem turns out to be, in itself, illuminating and a highly efficient step towards the solution.
The last chapter tackles the topic of linear programming, whose goal is to optimize linear functions of several variables subject to linear constraints. Although the subject shows a hybrid continous/discrete nature, it is often taught along with other discrete math disciplines. The theory behind linear programming involves basic linear algebra techniques. While appearing simple, the methods explained in class apply to a wide collection of complex real world problems. Some of them require integer and binary variables and are among the most interesting.
In summary, throughout this course in discrete mathematics, a variety of examples and applications will be explained, where by means of relatively simple tools and a clever approach, we get to solve interesting and difficult problems. Moreover, by their work on problem sets, students will be able to practice the first step in the process of mathematical modeling, namely, understanding a problem and finding a suitable mathematical formulation that leads to the solution.
1. Generating functions and recurrent sequences.
- Generating function definition. Computation techniques. Solving combinatorial problems using generating functions.
- Recurrent sequences. First and second order linear recurrence relations.
- Solving recurrence relations with generating functions.
2. Graph Theory.
- Definition and examples of mathematical modeling using graph theory.
- Basic concepts. Some graph families.
- Graph representation, graph isomorphism.
- Paths and cycles.
- Trees.
3. Linear Programming.
- Introduction. Some examples.
- Mathematical model. Basic concepts and main results.
- The simplex method.
4. Brief Introduction to other topics in Discrete Mathematics(Student-presented Seminar).
Topics may include combinatorial designs, cryptography, planar graphs, Hamiltonian graphs, Random graphs, Coding theory, Ramsey theory, Game theory, etc...
Classroom activities change over the course:
-Lectures and Problem Sets are planned for the first two chapters. In order to benefit from the class discussion, students should come to Problem-Set class meetings after having prepared the corresponding assignments.
- Lectures, Problem Sets, and Computer Labs are scheduled for chapter 3.
-One month after the course begins, students start working on their presentations. The class is divided into teams of four students each. A presentation topic approved by the instructor is assigned to each team. Teams work on their own and prepare a short study guide including a table of contents, definitions, the most relevant results, and references. Student-presented lectures are scheduled for the last two or three weeks of class.
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.
Title | Hours | ECTS | Learning Outcomes |
---|---|---|---|
Type: Directed | |||
Computer Lab | 8 | 0.32 | |
Lectures | 28 | 1.12 | |
Problem Set meetings | 16 | 0.64 | 7 |
Type: Supervised | |||
Meeting with instructor for feedback on the seminar project | 1 | 0.04 | 10, 9, 8 |
Type: Autonomous | |||
Group meetings for study/preparation for the Student-presented Seminar | 14 | 0.56 | 10, 9, 8 |
Individual practice on the linear programming software | 8 | 0.32 | 7 |
Self-study of lecture material | 26 | 1.04 | 10, 9, 7 |
Working on problem sets | 36 | 1.44 | 7 |
There are four graded tasks: a midterm exam, a computer lab test, a seminar project, and a final exam.
Course grade is calculated according to the following formula:
0.15 midterm exam score + 0.2 computer lab test score + 0.15 seminar project score+ 0.5 final exam score
The final exam is cumulative. A student missing the midterm exam due to medical or other excuses should submit documented evidence to be eligible for a make-up exam.
Exam Retake Option: There is only one possible retake for the final exam(50%). To be eligible to retake the final exam you should have participated, at least, in three graded tasks.
Participating in less than three graded tasks and not taking the final exam will result in a "Non-assessable" course grade.
After the final exam, course grades with distinction/honors are granted to those students whose work clearly merits it. Students retaking the final exam to improve their score may also apply for consideration for distinction.
Title | Weighting | Hours | ECTS | Learning Outcomes |
---|---|---|---|---|
Computer Lab test | 0.2 | 2 | 0.08 | 3, 4, 12 |
Final exam | 0.5 | 4 | 0.16 | 11, 3, 4, 5 |
Grading of the student-presented seminar (presentation and study guide) | 0.15 | 1 | 0.04 | 2, 1, 10, 9, 8, 7, 6 |
Midterm exam | 0.15 | 2 | 0.08 | 11, 3, 4, 5, 7 |
Retake exam | 0.5 | 4 | 0.16 | 11, 3, 4, 5 |
Recommended textbooks:
Basart, J.M. , Rifà, J, and Villanueva, M. "Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica". Col. Materials de la UAB, n. 36. 1997.
Graham, R.L. , Knuth, D. E. , and Patashnik, O. "Concrete mathematics: a foundation for computer science". Addison-Wesley. 1990.
Grimaldi, Ralph P. "Discrete and combinatorial mathematics: an applied introduction". 5th ed. Pearson.Addison-Wesley. 2004.
Rosen, Kenneth H. "Discrete mathematics and its applications". 6th ed. McGraw-Hill. 2007.
Suggested Readings on Graph Theory:
Bondy, J.A. , and Murty, U.S.R. "Graph Theory". Springer. 2008.
Wilson, R.J. , and Watkins, J. "Graphs: an introductory approach: a first course in discrete mathematics". Wiley, cop. New York. 1990.
Suggested Readings on Linear Programming:
Alabert, A. , and Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
Basart, J.M. "Programació lineal". Col. Materials de la UAB, n. 58.. 1998.
Luenberger, D. , and Ye, Y. "Linear and Nonlinear Programming". 3rd ed. Springer. 2008.
GLPK, Python, SageMath.