Theory
of
Computer
Science
SCSJ
3203
Lecturers
Details
Dr.
Zalmiyah
Zakaria
Email:
zalmiyah@utm.my
/
zalmiyah@gmail.com
Room:
N28A
L5-16-01
Tel:
07
5538814
Theory of Computer Science
Course
Learning
Outcomes
Describe
the
theory
of
Computer
Science.
Apply
and
explain
the
theory
in
solving
the
given
problems.
Discuss
and
make
decision
to
solve
problems
related
to
computer
science
theory.
Work
collaboraUvely
in
a
team
to
solve
problems
using
current
informaUon
related
to
computer
science
theory
and
communicate
deliverables
in
wriUng
and
oral
presentaUon.
Theory of Computer Science
References
Teaching
Module
for
tutorial
sessions
Zalmiyah
Zakaria
dan
Paridah
Samsuri.
Theory
of
Computer
Science:
DeniUons
and
Examples.
Fourth
EdiUon,
2015.
Books
Thomas
A.
Sudkamp.
Languages
and
Machines.
2006.
Third
EdiUon.
Pearson
Addison-Wesley.
Michael
Sipser.
IntroducUon
to
the
Theory
of
ComputaUon.
2013.
Third
EdiUon.
Cengage
Learning.
John
C.
MarUn.
IntroducUon
to
Languages
and
the
Theory
of
ComputaUon.
2011.
Fourth
EdiUon.
McGraw
Hill.
Elaine
Rich.
Automata,
Computability
and
Complexity.
2009.
Pearson
InternaUonal
EdiUon.
Pearson
PrenUce
Hall.
Theory of Computer Science
Grading
No.
Assessment
Assignment
1
(Take
home
work)
Quizzes
2
(in-class
10-min
assessment)
Tutorials
3
(in-class
exercises
with
lecturers
supervision)
Number
%
each
%
total
10%
10
5%
10
4%
20
4
Mid-Term
Test
25%
25
5
Final
Exam
35%
35
Overall
Total
Sept2011
100
Theory of Computer Science
UTM
Aeendance
Policy
To
be
allowed
to
sit
for
nal
exam,
a
student
must
have
an
aeendance
more
than
80%.
First
warning
leeer
will
be
issued
for
the
rst
4
hours
not
aeending
the
class.
Second
warning
leeer
for
the
subsequent
4
hours.
Leeer
to
forbid
seaUng
for
nal
exam
will
be
issued
for
the
subsequent
3
hours.
Theory of Computer Science
How
to
do
well
This
is
essenUally
a
math
course:
you
must
learn
the
concepts
well;
if
you
dont
theres
almost
no
chance
of
success
if
you
do
learn
the
concepts,
there
is
very
liele
else
(facts,
etc.)
to
learn;
you
can
do
really
well!
You
must
do
problems.
Theres
no
replacement
for
this.
Aeending
lectures
is
highly
advised!
It
will
be
very
hard
to
learn
the
concepts
by
yourself
or
from
textbook.
Dont
postpone
learning;
you
will
not
be
able
to
make
up
later.
Topics
get
quickly
hard.
Come
regularly
to
discussion
secUons;
you
will
learn
a
lot
by
working
out
problems
and
learn
from
fellow
students
Theory of Computer Science
IntroducUon
&
MathemaUcs
Preliminaries
Important
Notes
No
programming
in
this
course
It
is
assumed
that
you
are
familiar
with:
programming
and
basic
algorithms
notaUon
big-oh
sets
Theory of Computer Science
MoUvaUon
to
this
course
What
are
the
capabiliUes
and
limitaUons
of
computer?
What
is
computaUon?
Consists
of
execuUng
an
algorithm.
StarUng
with
some
input
and
following
a
step
by
step
procedure
that
will
produce
a
result
A
computaUon
is
simply
a
sequence
of
steps
that
can
be
performed
by
a
computer
Theory of Computer Science
10
MoUvaUon
to
this
course
What
type
of
computer?
Abstract
machines
or
model
of
computaUon,
which
will
be
dened
mathemaUcally.
Language
that
can
be
accepted
by
this
machine
Sept2011
Theory of Computer Science
11
MathemaUcal
NoUons
and
Terminology
Used
Sets
FuncUons
and
RelaUons
Sequences
and
Tuples
Trees
Boolean
Logic
Theory of Computer Science
12
Sets
Importance:
languages
are
sets
Sets
are
a
collecUon
of
well
dened
objects
E.g.
:
A
=
{set
all
items
in
kitchen}
=
{utensils,
stove,
spoons.....}
B
=
{set
all
natural
numbers}
=
{1,
2,
3,
...}
Sets
are
denoted
by
capital
leeers
-
A,
B,
C,
etc.
&
the
objects
by
small
leeers
-
a,
b,
c,
etc.
The
objects
called
the
elements
or
members
of
the
set.
Theory of Computer Science
13
Sets
Sets
can
be
nite
or
innite.
Finite
sets
are
sets
with
a
small
number
of
members
can
dened
explicitly;
that
is,
their
members
can
be
listed.
.
E.g.:
X
=
{1,
2,
3},
Y
=
{a,
b,
c,
d,
e}
An
innite
set
contains
innitely
many
elements.
Sets
having
a
large
nite
or
innite
number
of
members
must
be
dened
implicitly.
E.g.:
set
of
natural
numbers
=
N
=
{0,
1,
2,
3,
...},
set
of
integers
=
Z
=
{
...
,
-2,
-1,
0,
1,
2,
...
}.
Note:
".
.
.
means
"conUnue
the
sequence
forever".
Theory of Computer Science
14
Sets
There
are
two
common
ways
of
lisUng
the
members
of
a
set:
Explicitly
-
List
all
the
elements,
e.g.
{a,
e,
i,
o,
u}.
Implicitly
-
Provide
some
sort
of
an
algorithm
or
rule,
such
as
a
grammar,
e.g.
{set
of
vowel
leeers},
{
x
|
x
A
or
x
B
}.
Theory of Computer Science
15
Sets
NotaUon:
If
x
is
a
member
of
set
S,
we
write
x
S
We
denote
the
empty
set
(the
set
with
no
members)
as
{}
or
If
every
element
of
set
A
is
also
an
element
of
set
B,
we
say
that
A
is
a
subset
of
B
(A
B)
Theory of Computer Science
16
Set
operaUons:
Union
The
union
of
sets
A
and
B,
wrieen
A
B,
is
a
set
that
contains
everything
that
is
in
A,
or
in
B,
or
in
both.
Formal
deniUon
for
the
union
of
two
sets:
A
U
B
=
{
x
|
x
A
or
x
B
}
Further
examples
{1,
2,
3}
U
{3,
4,
5}
=
{1,
2,
3,
4,
5}
{Johor,
Melaka}
U
{3,
4}
=
{Johor,
Melaka,
3,
4}
{1,
2}
U
=
{1,
2}
Theory of Computer Science
17
Set
operaUons:
IntersecUon
The
intersecUon
of
sets
A
and
B,
wrieen
A
B,
is
a
set
that
contains
all
the
elements
in
both
A
and
B.
Formal
deniUon
for
the
intersecUon
of
two
sets:
A
B
=
{
x
|
x
A
and
x
B
}
Further
examples
{1,
2,
3}
{3,
4,
5}
=
{3}
{Johor,
Melaka}
{3,
4}
=
No
elements
in
common
{1,
2}
=
Any
set
intersecUon
with
the
empty
set
yields
the
empty
set
Theory of Computer Science
18
Disjoint
sets
Two
sets
are
disjoint
if
they
have
no
elements
in
common,
that
is,
if
AB
=
.
E.g.:
The
set
of
the
even
numbers
and
the
set
of
the
odd
numbers
Formal
deniUon
for
disjoint
sets:
two
sets
are
disjoint
if
their
intersecUon
is
the
empty
set
Further
examples
{1,
2,
3}
and
{3,
4,
5}
are
not
disjoint
{Johor,
Melaka}
and
{3,
4}
are
disjoint
{1,
2}
and
are
disjoint
Their
intersecUon
is
the
empty
set
and
are
disjoint!
Their
intersecUon
is
the
empty
set
Theory of Computer Science
19
Set
operaUons:
Dierence
The
set
dierence
of
set
A
and
set
B,
wrieen
A
-
B,
is
a
set
that
contains
everything
that
is
in
A
but
not
in
B.
Formal
deniUon
for
the
dierence
of
two
sets:
A
-
B
=
{
x
|_
x
A
and
x
B
}
A
-
B
=
A
B
Further
examples
{1,
2,
3}
-
{3,
4,
5}
=
{1,
2}
{Johor,
Melaka}
-
{3,
4}
=
{Johor,
Melaka}
{1,
2}
-
=
{1,
2}
The
dierence
of
any
set
S
with
the
empty
set
will
be
the
set
S
Theory of Computer Science
20
Set
operaUons:
Symmetric
Dierence
A
symmetric
dierence
of
the
sets
contains
all
the
elements
in
either
set
but
NOT
both
Formal
deniUon
for
the
symmetric
dierence
of
two
sets:
A
B
=
{
x
|
(x
A
or
x
B)
and
x
A
B}
A
B
=
(A
U
B)
(A
B)
Further
examples
{1,
2,
3}
{3,
4,
5}
=
{1,
2,
4,
5}
{Johor,
Melaka}
{3,
4}
=
{Johor,
Melaka,
3,
4}
{1,
2}
=
{1,
2}
The
symmetric
dierence
of
any
set
S
with
the
empty
set
will
be
the
set
S
Theory of Computer Science
21
Complement
sets
The
complement
of
a
set
A,
wrieen
as
A
or
-A
or
(beeer)
A
with
a
bar
drawn
over
it,
is
the
set
containing
everything
that
is
not
in
A.
Formal
deniUon
for
the
complement
of
a
set:
=
{
x
|
x
A
}
Or
U
A,
where
U
is
the
universal
set
that
contains
"everything"
(meaning
"everything
we
are
interested
in
at
the
moment").
Then,
or
A
or
A
is
shorthand
for
U
-
A.
Further
examples:
{1,
2,
3}
=
{
,
-2,
-1,
0,
4,
5,
6,
}
Theory of Computer Science
22
Take 5..!
23
AddiUonal
terminology
The
cardinality
of
a
set
A,
wrieen
|A|,
is
the
number
of
elements
in
a
set
A.
The
powerset
of
a
set
A,
wrieen
P(A)
or
2A,
is
the
set
of
all
subsets
of
A.
The
notaUon
suggests
the
fact
that
a
set
containing
n
elements
has
a
powerset
containing
2n
elements,
including
empty
set.
Example:
2{a,b,c}
=
{,
{a},
{b},
{c},
{a,b},
{a,c},
{b,c},
{a,b,c}}
Note
that
the
empty
set
and
the
set
A
itself
are
in
As
power
set
Theory of Computer Science
24
Sequences
and
Tuples
A
sequence
of
objects
is
a
list
of
those
objects
in
some
order.
Usually
designate
by
wriUng
the
list
within
parenthesis,
e.g.
(2,
5,
7).
May
be
nite
or
innite.
Finite
sequences
called
tuples.
Sequence
with
k
elements
is
a
k-
tuples,
e.g.,
(2,
5,
7)
is
a
3-tuples.
Theory of Computer Science
25
Cartesian
product
(Cross
product)
The
Cartesian
product
of
two
sets
A
and
B,
denoted
A
B,
is
the
set
of
all
ordered
pairs
with
rst
element
from
A
and
second
element
from
B
A
B
=
{(a,
b)
|
a
A
and
b
B}
A
=
{1,2};
B
=
{3,4}
A
B
=
{1,2}
{3,4}
=
{(1,3),
(1,4),
(2,3),
(2,4)}
B
A
=
{3,4}
{1,2}
=
{(3,1),
(3,2),
(4,1),
(4,2)}
{1,
2}
{red,
white}
=
{(1,
red),
(1,
white),
(2,
red),
(2,
white)}.
We
can
generalize
this
to
ordered
k-tuples:
A1
A2
Ak
=
{(a1,
a2,
,
ak
|
ai
Ai
for
each
i}
Theory of Computer Science
26
