CS计算机代考程序代写 algorithm /Users/billy/gits/moc-2021/tutes/week01.dvi

/Users/billy/gits/moc-2021/tutes/week01.dvi

School of Computing and Information Systems

COMP30026 Models of Computation Tutorial Week 1

26–30 July 2021

Introduction to tutorials

Welcome to the first Models of Computation tutorial for 2021. We hope you will enjoy the tutorials,

and also that you will contribute to making them enjoyable for your class mates. Your tutor will

explain how they would like to run your tutorial.

The exercises

T1.1 Connect to your tutorial’s Microsoft Teams Team (see the tutorial table on the welcome page

of Canvas). Your tutor will show you around the different channels you can use and how you

can participate in the tutorial.

T1.2 Introduce yourself to your classmates and tell them a bit about yourself.

T1.3 Three playing cards lie face down on a table. One is red, one is black, and one is the joker.

On the back of each card is written a sentence:

Card 1 Card 2 Card 3

C
a
r
d
3
is

th
e
jo
k
e
r
!

C
a
r
d
1
is

b
la
c
k
!

I
a
m

th
e
jo
k
e
r
!

The red card has a true sentence written on its back and the black card has a false sentence.

Which card is red, which is black, and which is the joker? Is the solution unique?

T1.4 What is an algorithm? Discuss with your group and try to come up with a definition – the

more specific, the better. The following questions might help in prompting discussion. Give

examples where relevant.

• What do algorithms do?

• What kinds of inputs/outputs do they have?

• What is the difference between an algorithm and a function?

• What does it mean for an algorithm to solve a particular problem?

• What does it mean for a human/computer to “run” an algorithm?

• Are there any sensibility constraints on what kinds of steps an algorithm can require of

the human/computer?

• When are two algorithms the same?

T1.5 In Lecture 1 we play a word rewriting game. Here is an example of a similar kind of game,

the so-called Post’s Correspondence Problem. We have a set of “dominoes” such as

{

b

ca
,

a

ab
,

ca

a
,

abc

c

}

The dominoes use a small alphabet, say the letters a, b, and c. Each domino has a string

written in the upper half, and one in the lower half. The given set of dominoes is always

finite, but there is an unbounded supply of each domino, that is, we can use it many times.

The goal is to find a sequence of dominoes which, when laid side by side, spell out identical

non-empty strings across the top and the bottom (or alternatively, determine that no solution

is possible). For example, the set given above has a solution, namely

a

ab

b

ca

ca

a

a

ab

abc

c

(a) Can you find a solution to
{

baa

abaaa
,

aaa

aa

}

?

(b) How about
{

a

cb
,

bc

ba
,

c

aa
,

abc

c

}

?

(c) How about
{

ab

aba
,

bba

aa
,

aba

bab

}

?

T1.6 Can you come up with a general algorithm to solve Post’s Correspondence problem? Refer

back to your discussion of what an algorithm is – does it qualify as an algorithm? What are

its inputs and outputs? Will your algorithm always arrive at the answer?