Undergraduate Course: Discrete Mathematics and Mathematical Reasoning (INFR08023)
Course Outline
School  School of Informatics 
College  College of Science and Engineering 
Course type  Standard 
Availability  Available to all students 
Credit level (Normal year taken)  SCQF Level 8 (Year 2 Undergraduate) 
Credits  20 
Home subject area  Informatics 
Other subject area  None 
Course website 
http://www.inf.ed.ac.uk/teaching/courses/dmmr/ 
Taught in Gaelic?  No 
Course description  Discrete mathematics and formal mathematical reasoning. 
Information for Visiting Students
Prerequisites  None 
Displayed in Visiting Students Prospectus?  Yes 
Course Delivery Information

Delivery period: 2012/13 Semester 1, Available to all students (SV1)

Learn enabled: No 
Quota: None 
Location 
Activity 
Description 
Weeks 
Monday 
Tuesday 
Wednesday 
Thursday 
Friday 
Central  Lecture   111  17:10  18:00      Central  Lecture   111    11:10  12:00    Central  Lecture   111     17:10  18:00  
First Class 
Week 1, Monday, 17:10  18:00, Zone: Central. Faculty Room South David Hume Tower 
Exam Information 
Exam Diet 
Paper Name 
Hours:Minutes 


Main Exam Diet S1 (December)   2:00   
Summary of Intended Learning Outcomes
 Reason mathematically about basic (discrete) structures (such as numbers, sets, graphs, and trees)used in computer science.
 Use of mathematical and logical notation to define and formally reason about mathematical concepts such as sets, relations, functions, and integers, and discrete structures like trees, graphs, and partial orders;
 Evaluate elementary mathematical arguments and identify fallacious reasoning
 Construct inductive hypothesis and carry out simple induction proofs;
 Use graph theoretic models and data structures to model and solve some basic problems in Informatics (e.g., network connectivity, etc.)
 Prove elementary arithmetic and algebraic properties of the integers, and modular arithmetic, explain some of their basic applications in Informatics, e.g., to cryptography.
 Compare the asymptotic growth growth rates of basic functions; derive asymptotic bounds, and limits, for simple series and recurrence relations. Use these to derive bounds on the resource consumption (e.g., running time) of simple iterative and recursive algorithms.
 Calculate the number of possible outcomes of elementary combinatorial processes such as permutations and combinations.
 Be able to construct discrete probability distributions based on simple combinatorial processes, and to calculate the probabilities and expectations of simple events under such discrete distributions. 
Assessment Information
Written Examination: 85%
Assessed Assignments: 15% 
Special Arrangements
None 
Additional Information
Academic description 
Not entered 
Syllabus 
1) Foundations (Chapters 1 & 2 of [Rosen])
2) Basic number systems, and rudimentary algorithms on numbers and matrices (Chapter 3, [Rosen])
3) Induction and Recursion (Chapter 4 [Rosen])
4) Basic Counting (Chapter 5 [Rosen])
5) Graphs (and binary relations): [Chapter 9, and parts of Chapter 8]]
6) Trees: (Chapter 10 [Rosen])
7) Discrete probability [Chapter 6, plus some supplementary material] 
Transferable skills 
Not entered 
Reading list 
REQUIRED TEXTBOOK:
* Kenneth Rosen, Discrete Mathematics and its Applications, 7th Edition, McGrawHill, (due to be published in July), 2012. Alternatively, 6th Edition, 2007.
Additional Reference Material:
* MIT Mathematics for Computer Science Lecture notes (online) 
Study Abroad 
Not entered 
Study Pattern 
Lectures 30
Tutorials 10
Timetabled Laboratories 0
Coursework Assessed for Credit 40
Other Coursework / Private Study 120
Total 200 
Keywords  Not entered 
Contacts
Course organiser  Prof Colin Stirling
Tel: (0131 6)50 5186
Email: cps@inf.ed.ac.uk 
Course secretary  Ms Kendal Reid
Tel: (0131 6)50 5194
Email: kr@inf.ed.ac.uk 

