Module Catalogues, Xi'an Jiaotong-Liverpool University   
 
Module Code: CSE107
Module Title: Foundations of Computing Science
Module Level: Level 1
Module Credits: 5.00
Academic Year: 2017/18
Semester: SEM1
Originating Department: Computer Science and Software Engineering
Pre-requisites: N/A
   
Aims
1. To introduce the notation, terminology, and techniques underpinning the discipline of Theoretical Computer Science.
2. To provide the mathematical foundation necessary for understanding datatypes as they arise in Computer Science and for understanding computation.
3. To introduce the basic proof techniques which are used for reasoning about data and computation.
4. To introduce the basic mathematical tools needed for specifying requirements and programs, and for analysing algorithms.
Learning outcomes 
At the end of this module the student should be able to :

1. Reason about simple datatypes using basic proof techniques;

2. Interpret set theory notation, perform operations on sets, and reason about sets;

3. Understand, manipulate and reason about unary relations, binary relations, and functions;

4. Represent statements in propositional logic and first-order predicate logic and to recognise, understand, and reason about formulas in propositional logic and first-order predicate logic;

5. Apply basic counting and enumeration methods as these arise in analysing permutations and combinations;

6. Perform simple calculation about discrete probability.
Method of teaching and learning 
Lectures: Students will be expected to attend formal lectures in a typical week. Formal lectures will be used to introduce students to the concepts and methods covered by the module.

Tutorials: Supporting tutorials are held each week in which students work under staff guidance on problem sets designed to reinforce understanding of the lecture material with the possibility of immediate feedback.

Private study: In a typical week students will be expected to devote approximately 6 hours of unsupervised time to private study; private study will provide time for reflection and understanding of lecture materials, background reading and completion of the assessment tasks.

Assessment: Continuous assessment will be used to test to the extent of theorectieal ideas grasped.
A final examination at the end of the module will assess the academic achievement of students.

Syllabus 
1. Number systems and proof techniques: natural numbers, integers, rationals, real numbers, prime numbers, proof by contradiction and proof by induction.

2. Approaches to describing collections of objects: sets and set operations, unary and binary relations, properties of binary relations, partial orders and equivalence relations, inverse relations, and compositions of relations.

3.Functions: properties of functions, inverse functions and compositions of functions, and the pigeonhole principle.

4.Logic: propositional logic - syntax and semantics of propositional logic, SAT, logical consequence, logical equivalence, normal forms and a proof system for propositional logic; first-order predicate logic - syntax, semantics and evaluation, a proof system for first-order predicate logic and undecidability of first-order predicate logic.

5.Combinatorics: notation for sums, products, and factorials, Binomial coefficients, counting permutations, subsets, subsequences and functions.

6.Discrete Probability: sample spaces, events, conditional probability, independence, random variables, variance and expectation.

7.Probability distributions (Binomial and Gaussian) and hypothesis testing.

Delivery Hours  
Lectures Seminars Tutorials Lab/Prcaticals Fieldwork / Placement Other(Private study) Total
Hours/Semester 26       26    98  150 

Assessment

Sequence Method % of Final Mark
1 Written Examination 80.00
2 Cousework 10.00
3 Cousework 10.00

Module Catalogue generated from SITS CUT-OFF: 10/22/2017 10:29:43 AM