NCHCS773 Discrete Structures Course Descriptor

Course Summary

This course introduces students to the mathematical “tools” (e.g. proof techniques), data structures and algorithms that form the foundation of computer science. At the same time, it explains how these concepts are used in modern, real-world applications.

In this course, students have the opportunity to learn: (i) how data are represented on a computer; (ii) basic logical operations on data and how they can be combined to implement more complex relations; (iii) basic data structures (e.g. sets, sequences, lists, trees, and graphs) and algorithms to manipulate them (e.g. sorting an array) or query them (e.g. finding shortest paths in a graph); and (iv) basic mathematical techniques (e.g. counting or induction) and how they can be used to estimate the space and time complexity of algorithms (i.e. their growth) as a function of the input size.

This course is suitable for graduate students of disciplines other than computing who are keen to acquire new (or deepen their existing) knowledge of computing.

Course Aims

The aims of this course are to:

• Systematically understand data representation, logical operations on data, use of basic data structures and algorithms to manipulate data in modern software.
• Critically evaluate which basic data structures, algorithms or logical operations are best-suited to implement a small computing problem (e.g. a function).

Learning Outcomes

On successful completion of the course, students will be able to:

Knowledge and Understanding

Subject Specific Skills

Transferable and Professional Skills

Teaching and Learning

Teaching and learning strategies for this course will include: 

• 15 (10 x 1.5) hours of full-cohort lectures
• 15 (10 x 1.5) hours of lab sessions
• 20 (10 x 2) office hours 

There will be one lecture and one lab session per teaching week, 1¹/₂ hours each. Lab sessions give students the opportunity to work on their (formative and summative) assignments with the help of the course leader and teaching assistants.

Course information and supplementary materials are available on the University’s Virtual Learning Environment (VLE).

Students are required to attend and participate in all the formal and timetabled sessions for this course. Students are also expected to manage their directed learning and independent study in support of the course.

Employability Skills

• Communication skills
• Mathematical skills
• Programming skills

Assessment

Formative

Students will be formatively assessed during the course by means of set assignments. These do not count towards the end of year results but will provide students with developmental feedback. Set assignments will also amplify problem-solving skills useful for the set exercises.

Summative

Assessment will be in the form of set exercises:

The set exercises will be assessed in accordance with the assessment aims set out in the Programme Specification. 

Feedback

Students will receive formal feedback in a variety of ways: written (including via email correspondence); oral (on an ad hoc basis) and indirectly through discussion during group tutorials. Students will also attend the formal meeting, Collections, in which they will receive constructive and developmental feedback on their  performance. 

Feedback is provided on summative written assignments which will be handed back to the students.

Indicative Reading

Note: Comprehensive and current reading lists for courses are produced annually in the Course Syllabus or other documentation provided to students; the indicative reading list provided below is used as part of the approval/modification process only.

Books

Harriet Fell and Javed Aslam. 2017. Discrete Structures. Cognella Academic Publishing

Kenneth H. Rosen. 2019. Discrete Mathematics and its Applications (8^th ed.). McGraw-Hill, Inc.

Indicative Topics

Students will study the following topics: 

• Number representations (e.g. binary and hexadecimal)
• Logic, logical operators
• Integer functions
• Combinatorics: sets, counting and probability
• Sequences, sums, and series (e.g. arithmetic and geometric)
• Basic data structures: array, list, stack, queue, hash tables
• Graphs, their representation and elementary algorithms (e.g. spanning trees)
• Algorithms for searching and sorting
• Recursion, mathematic induction, and recurrences
• Runtime analysis: Big-O notation and complexity classes