This Course Guide has been taken from the most recent presentation of the course. It would be useful for reference purposes but please note that there may be updates for the following presentation.
COMP 3630SED
Discrete Structures
Welcome to COMP 3630SED Discrete Structures! This is a six-credit-unit, 3000-level course. The course focuses on the development of your knowledge and understanding of analysing the correctness and time complexity of algorithms.
By studying this course, you will gain a foundation in discrete mathematics and master the techniques of algorithm analysis, which will be useful in studying other computing courses.
This course will be delivered using a wrap-around approach, in which HKMU-produced study units will guide you through readings from a set textbook, supplemented by extra readings from the companion website hosted at HKMU's Online Learning Environment (OLE), links to online resources and face-to-face sessions.
In this wrap-around approach, different learning modules are selected by the course team from various sources. Based on the latest edition of the chapters, cases, exercises and self-tests from the set textbook and supplementary readings, the course will provide you with coverage of the foundation in discrete mathematics and algorithm analysis.
Your study pathways through the readings will be set out in HKMU-produced study units. In addition to the guided activities and self-tests already provided in the textbook, the study units will include supplementary material and additional self-assessment opportunities. You will also have access to the OLE, and regular face-to-face meetings for lectures and tutorials.
Course aims
COMP 3630SED Discrete Structures aims to:
Course learning outcomes
By the end of the course, you should be able to:
The following introduces the organisation of the course content, the materials provided or required, as well as information on the course assessment. After going through them, you will be ready to set off on a journey into the realms of discrete mathematics and algorithm analysis.
Organisation of course content and study units
In addition to this Course Guide, the course will provide or expect students to have access to the following materials or resources.
Study units
All COMP 3630SED study units will be presented to you as hard copies and uploaded to the Online Learning Environment (OLE) as PDF files. There are eight study units.
Unit 1 introduces sets and logic: in this unit, you will learn about set notations, set operators, Venn diagrams, propositions, logical operators, truth tables, logical equivalence, De Morgan's Laws, rules of inference, predicates and universal and existential quantifiers.
Unit 2 covers the fundamentals of proofs: we will cover direct proofs, proof by contraposition, proof by contradiction, proof by cases and mathematical induction (MI).
Unit 3 discusses functions: you will be introduced to functions and their domain, codomain and range; arrow diagrams and common functions: modulus, floor and ceiling, one-to-one, onto and bijective functions, inverse and composition of functions, sequences and strings, relations, Cartesian products, partial order and total order.
Unit 4 provides a step-by-step guide to implementing counting methods and the Pigeonhole Principle: you will learn the basic principles, permutations and combinations, generalised permutations and combinations, binomial coefficients and combinatorial identities, and then the Pigeonhole Principle.
Unit 5 focuses on algorithms: you will learn the definition of an algorithm, and then we will go on to cover pseudocode and time complexity analysis, including best case, worst case, average case, asymptotic notation, recursive algorithms, proof of correctness and the Euclidean algorithm.
Unit 6 introduces recurrence relations: we will cover the Tower of Hanoi, solving recurrence relations, the Fibonacci sequence, selection sort, insertion sort, binary search and merge sort.
Unit 7 deals with graph theory: topics covered include graphs, vertices, edges, weighted graphs, paths and cycles, Hamiltonian cycle and the travelling salesperson problem.
Unit 8 consolidates the concepts of graph algorithms by introducing you to spanning trees, minimal spanning trees, breadth-first search, depth-first search and Dijkstra's algorithm.
Set textbook
The following textbook has been chosen as the set textbook for this course:
Johnsonbaugh, R. (2018) Discrete Mathematics, 8th ed., Global ed., Pearson.
This textbook will be provided to you as part of the course materials.
Presentation Schedule
The Presentation Schedule for this course is available on the OLE. On this schedule, you will see the approximate time for completing assignments, attending tutorials and surgeries and so on.
Assignments
All the assignments for this course will be released as electronic copies through the OLE with submission due dates in accordance with the timetable provided in the Presentation Schedule. Once an assignment is released, you will be required to download and complete it within the indicated period, and submit your work electronically through the relevant submission links on the OLE. For more details about the assignments, please refer to the 'Assessment' section of this Course Guide.
Equipment requirements
To access the OLE platform and complete your assignments in this course, you will need a personal computer (PC) or similar device with an Internet connection.
The following table summarises the assessment for this course.
| Assessment components | Weighting |
| Continuous assessment | |
| Assignment 1 | 16.66% |
| Assignment 2 | 16.66% |
| Assignment 3 | 16.66% |
| Examination | 50% |
Total | 100% |
Assignments
There are three assignments counting towards the overall continuous assignment score (OCAS) of COMP 3630SED, which are worth 50% of your course score (CS) for this course. All three individual assignments have equal weightings, with each of them counting as 16.66% of the CS.
The assignments will examine your understanding of the topics covered in the course, your ability to apply what you have learnt to analyse and solve problems, as well as your motivation to explore relevant technological developments.
Final examination
There will be a final examination for this course which is worth 50% of the CS. The examination will be centrally arranged by the university, and by default it will be a two-hour, closed-book written examination. The format and other details of the examination paper will be provided as a specimen paper and/or through announcement by email or Course News on the OLE near the end of this course.
Passing criteria
To pass the course, you are required to obtain a mark of at least 40% in both the overall continuous assignment score (OCAS) and the final examination.
The following table provides an overview of the course arrangement, which is tentative and may be subject to adjustment.
| Unit | Content | Weeks | Assessment |
| 1 | Sets and logic | 3 | |
| 2 | Proofs | 4 | |
| 3 | Functions | 4 | Assignment 1 |
| 4 | Counting methods and the Pigeonhole Principle | 4 | |
| 5 | Algorithms | 3 | |
| 6 | Recurrence relations | 4 | Assignment 2 |
| 7 | Graph theory | 4 | |
| 8 | Graph algorithms | 4 | Assignment 3 |
| Revision | 2 | ||
| 32 |
You will be supported throughout this course both by face-to-face sessions and through the Online Learning Environment (OLE). You will also be assigned a tutor who will support you in your learning throughout the course.
Tutors, tutorials and surgeries
There are six two-hour face-to-face tutorials and six two-hour surgeries designed to help you in this course. Although tutorials and surgeries are not compulsory, you are strongly encouraged to attend them.
Your tutor will mark and comment on your assignments, keep a close watch on your progress and on any difficulties you might encounter, and will try to help you throughout the course. As mentioned above, your assignments should be submitted through the OLE to your tutor before the due dates. Your tutor will mark them and return them to you as soon as possible.
Do not hesitate to contact your tutor by telephone, email or by posting questions on your group's discussion board if you need help. For example, contact your tutor if:
You will be notified of the dates, times, and location of the tutorials and surgeries, together with the name and phone number of your tutor, as soon as you are allocated a tutorial group.
Online Learning Environment (OLE)
This course is supported by the Online Learning Environment (OLE). You can find course materials and the latest course information on the OLE, and use the discussion board to communicate with your tutor, the Course Coordinator and your fellow students.
COMP 3630SED Discrete Structures introduces you to the foundation of discrete mathematics and will help you master the techniques of algorithm analysis which you will find useful in studying other computing courses. Topics of first few units include sets, logic, proofs, functions and algorithms, and in last two units, graph theory and graph algorithms will also be discussed. Theoretical concepts and practical techniques are integrated with the practical examples and proofs in the self-test exercises you will undertake as part of your study.
In order to understand the content of this course, you must analyse the course materials and apply the concepts learnt. We hope that you will find COMP3630SED Discrete Structures interesting and enjoyable, and that you will be able to apply the knowledge and skills you gain from this course throughout your career.
Good luck, and we hope that you will achieve great success and satisfaction from this course.
Ir Hung Chi-kwong, the developer of COMP 3630SED Discrete Structures, has extensive teaching and course development experience in engineering programmes. Previously, he was a part-time tutor at the Open University of Hong Kong and a part-time lecturer at Hong Kong Vocational Training Council (VTC), where he taught Professional Diploma courses related to Power Plant Control Engineering.
Before entering the teaching profession, he worked as a maintenance manager in Public Utilities of Hong Kong. He is a corporate member of the Hong Kong Institution of Engineers and a Chartered Engineer in the United Kingdom. He has implemented numerous engineering design projects in the power industry.
