SCHOOL OF COMPUTER SCIENCES

SEMESTER I, ACADEMIC SESSION 2022/2023

Course Code/ CPT112

Kod Kursus
Course Title / Discrete Structures / Struktur Diskrit
Nama Kursus
Lecturers/Pensyarah Dr. Nur Intan Raihana Ruhaiyem / Dr. Sukumar Letchmunan
E-mail/Tel. intanraihana@usm.my (+6 04 6534387, room 528),
No/Room No. sukumar@usm.my (+6 010 3664173, room 607)
Course Units/Unit 4
Kursus
Student Learning 160
Time/ Masa
Pembelajaran
Pelajar
Breakdown of Examination / Peperiksaan 60% (3 hours / jam)
Assessments /
Coursework / Kerja Kursus 40%
Pecahan Penilaian
Coursework Tutorial / Tutorial 10% (2 x 5%)
Evaluation Basis/
Tests / Ujian 30% (2 x 1 hour / jam x 15%)
Pecahan Kerja
Kursus
Type of Course/ Core / Teras
Jenis Kursus
Prerequisites (if any) -
/Prasyarat (Jika ada)
Introducing the concept and characteristics of discrete structures, the nature and
Objective/Tujuan importance of algorithms in solving problems as well as providing the theoretical basis
needed in the field of computer science.
Memperkenalkan konsep dan ciri-ciri struktur diskrit, sifat dan kepentingan algoritma dalam
menyelesaikan masalah serta menyediakan asas teoritikal yang diperlukan dalam bidang
sains komputer.

Discrete structure is the study of mathematical structures that are fundamentally discrete
Course Synopsis/ which serves as a fundamental concept in Computer Science study. Topics include sets,
Sinopsis Kursus sequences, number systems, matrices, pigeonhole principle, discrete probability,
mathematical inductions, recurrence relations, relations, trees, graphs, and finite state
machines.
Struktur diskrit merupakan pengajian struktur matematik yang diskrit yang berfungsi
sebagai konsep asas dalam teras kajian Sains Komputer. Topik termasuk set, urutan,
sistem nombor, matriks, prinsip burung merpati, kebarangkalian diskrit, matematik induksi,
hubungan berulang, hubungan, pokok, graf dan mesin keadaan terhingga.

CLO1: Apply the right mathematical structures to be used in problem representation by

Course Learning
using the concepts and characteristics of mathematical structures.
Outcomes / Hasil
Mengaplikasi struktur matematik yang betul untuk digunakan dalam perwakilan
Pembelajaran
masalah dengan menggunakan konsep dan ciri-ciri struktur matematik.
Kursus
CLO2: Use algorithms and techniques in discrete problem solving.
Gunakan algoritma dan teknik yang sesuai dalam penyelesaian masalah diskrit.
CLO3: Demonstrate numeracy skill in mathematical structure to solve various domain
problems.
Menunjukkan kemahiran mengira dalam struktur matematik bagi menyelesaikan
pelbagai domain masalah.

NIRR_2022 | SOCS, USM

 Assessment
CLO Descriptions PLO LT SS
CLO – PLO Methods
Mapping / 1 Apply the right mathematical PLO1 C3
Pemetaan CLO - structures to be used in problem Final Exam (PA)
PLO representation by using the Test (13)
concepts and characteristics of
mathematical structures.
2 Use algorithms and techniques in PLO3 C3 CTPS Assignment (03)
discrete problem solving.

3 Demonstrate numeracy skill in PLO11 C3 CTPS

mathematical structure to solve Final Exam (PA)
various domain problems. Test (13)

Main References/ 1. Kenneth. H. Rosen, Discrete Mathematics and Its Applications, 8th Edition, McGraw
Rujukan Utama Hill International, 2018.
2. Richard Johnsonbaugh, Desrete Mathematics, 8th Edition, Pearson, 2017.
3. Harry Lewis and Rachel Zax, Essentiall Discrete Mathematics for Computer Science,
Princeton University Press, 2019.

Add. References / 1. B. Kolman, R.C. Busby, Discrete Mathematical Structures for Computer Science, 6th
Rujukan Tambahan Edition, Prentice-Hall, 2017. Parisi, WebGL: Up and Running Building 3D Graphics for
the Web, O'Reilly Media, 2012.
2. Susanna S. Epp. Discrete Mathematics with Applications, 5th Edition, Thomson
Brooks/Cole, 2019.
3. Jon Pierre Fortney, Discrete Mathematics for Computer Science, 1st Edition,
Routledge, 2020.

Delivery Final
Test Tutorial
Method Exam
BIL. CLO PLO
Marks #Test – Marks #Tutorial - Marks

1. Apply the right PLO1 Lectures & 50 marks Test 1 – 20 marks Tutorial 1 – 50 marks
mathematical Tutorials
structures to be Test 2 – 20 marks
used in problem
representation by
using the concepts
and characteristics
of mathematical
structures.
2. Use algorithms and PLO3 Lectures & 50 marks Test 1 – 20 marks Tutorial 2 – 100 marks
techniques in Tutorials
discrete problem Test 2 – 20 marks
solving.
3. Demonstrate PLO11 Lectures & 50 marks Test 1 – 20 marks Tutorial 1 – 50 marks
numeracy skill in Tutorials
mathematical Test 2 – 20 marks
structure to solve
various domain
problems.
Total Marks 150 120 200
Total Percentage (EW/CW) 60% 30% 10%
Overall Percentage 60% 40%

NIRR_2022 | SOCS, USM

 COURSE SYLLABUS AND PLANNER

Week Topics Main Non-Face Notes

Ref. Face to Face (F2F) to Face
(NF2F)
Async.
Physical Sync (Online) (Online)
Lect. Tut. Lect. Tut.
Sorotan Kursus
1
Course Overview 0.5
1&2 Basic Structures: R1: 5.5 1 8
Sets, Functions, Ch.2
Sequences, Sums, and
Matrices R2:
Struktur Asas: Ch.1 &
Set, Fungsi, Jujukan, 3
Jumlah dan Matriks

3 Algorithms: R1: 3 1 5
Examples of Algorithms, Ch.3
The Growth of Functions
Algoritma: Contoh-contoh R2:
Algoritma, Perkembangan Ch.4
Fungsi
4 Induction and Recursion: R1: 3 1 5 Tut. 1
Mathematical Induction, Ch.5 released
Recursive Function &
Algorithms
R2:
Induksi dan Rekursi:
Induksi Matematik, Fungsi Ch.4
& Algoritma Rekursi (4.4)

5&6 Counting: Basic R1: 5 2 7 Test 1

Principles, The Pigeonhole Ch.6 (week 6)
Principle, Permutations
and Combinations
R2: Tut. 1 due
Pengiraan: Pengiraan
Asas, Prinsip Pigeonhole, Ch.6 (week 6)
Permutasi dan Gabungan
7 Discrete Probability: Basic R1: 3 1 5
Probability, Probability Ch.7
Theory
Kebarangkalian Diskrit: R2:
Asas Kebarangkalian,
Teori Kebarangkalian Ch.6
(6.5)

8 Mid-semester break

9 Advanced Counting R1: 3 4

Techniques: Recurrence Ch.8
Relations, Linear
Recurrence Relations,
Divide-and-Conquer, R2:
Generating Functions, Ch.7
Inclusion-Exclusion
Teknik Pengiraan
Lanjutan: Hubungan
Berulang, Hubungan
Berulang Linear, Pecah
dan Perintah, Menjana
Fungsi, Kemasukan-
Pengecualian

NIRR_2022 | SOCS, USM

 10 Relations: Relations and R1: 3 1 5
Their Properties, Ch.9
Representing Relations,
Closures of Relations,
Equivalence Relations,
Partial Orderings
Perhubungan:
Perhubungan dan ciri-
cirinya, Mewakili
Perhubungan, Penutup
Hubungan, Hubungan
Kesamaan, Susunan
Separa
11 & Graphs: Graph R1: 6 2 8 Tut. 2
12 Terminology, Representing Ch.10 released
Graphs, Connectivity,
Shortest-Path Problems
R2:
Graf: Istilah Graf,
Perwakilan Graf, Ch.8
Keterkaitan, Masalah
Laluan Terpendek
13 & Trees: Applications of R1: 5 2 8
14 Trees, Tree Traversal, Ch.11
Spanning Trees, Minimum
Spanning Trees
R2:
Pepohon: Aplikasi
Pepohon, Penyusuran Ch.9
Pepohon, Pepohon
Rentangan, Pepohon
Rentangan Minimum
15 Languages and Finite R1: 3 1 5 Test 2
State Machines Ch. 13 (week 14)
Bahasa dan Keadaan
Mesin Terhingga R2: Tut. 2 due
Ch.12 (week 14)
+ revision final exam

Total Contact Hours of SLT 40 12 0 0 60

TOTAL 112

ANALYSIS OF CONTACT HOURS OF STUDENT LEARNING TIME

Components SLT (Week 1 – 7) SLT (Week 9 – 15)

Course Syllabus Lecture, Tutorial, Others 56.0 Lecture, Tutorial, Others 56.0

Coursework (F2F) Test 1.0 Test 1.0

Tutorial 13.5 Tutorial 13.5
Coursework (NF2F)
Test 2.0 Test 2.0
Sub-Total SLT 72.5 72.5
Final Exam (NF2F) – 12
Async.
Final Exam (F2F) – 3
Physical
TOTAL SLT 160

NIRR_2022 | SOCS, USM

 COURSE INFORMATION

Lecture Timetable :

Day Time Venue

Day 1
11:00 – 13:00 DK G31
(Monday)

Day 2
12:00 – 13:00 DK G31
(Tuesday)

*Tutorial Timetable – please refer to Year 1 complete schedule

Important Dates (Tentative) :

Event Date Week

Tutorial 1 Released 7 Nov 2022 04

Test 1 21 Nov 2022 06

Tutorial 1 Due 25 Nov 2022 06

Tutorial 2 Released 26 Dec 2022 11

Test 2 16 Jan 2023 14

Tutorial 2 Due 20 Jan 2023 14

NIRR_2022 | SOCS, USM