1.     The Fibonacci numbers are calculated with the following formula:

Nombor Fibonacci dikira dengan rumus berikut:

0                          n = 0

So,

Maka,

f2 = f1 + f0 = 1 + 0 = 1

f3 = f2 + f1 = 1 + 1 = 2

f4 = f3 + f2 = 2 + 1 = 3

……… ..

(a)   Write a straightforward recursive function to calculate Fibonacci number.

Tulis suatu fungsi rekursi mudah untuk mengira nombor Fibonacci.

(20/100)

(b)    What is the time complexity of the function in (1)(a) above, in big O?

Explain your answer.

Apakah kekompleksan masa fungsi dalam (1)(a) di atas, dalam O besar? Jelaskan jawapan anda.

(20/100)

(c)    What is dynamic programming? Apply dynamic programming approach to  calculate  a   Fibonacci  number,  and  describe  the  way  dynamic

programming  calculates  the  Fibonacci  number  using  an  appropriate example.

Apakah     itu     pengaturcaraan     dinamik?     Terapkan     pendekatan pengaturcaraan  dinamik untuk mengira suatu nombor Fibonacci,  dan terangkan   pendekatan   pengaturcaraan   dinamik   mengira   nombor Fibonacci dengan contoh yang sesuai.

(40/100)

(d)   What  is the time  complexity of the approach  in  (1)(c)?  Explain your answer.

Apakah kekompleksan masa bagi pendekatan dalam (1)(c)? Jelaskan jawapan anda.

(20/100)

2.     Alex was asked to design the algorithm of tic-tac-toe-V2 game that will play against a human player. The rules of tic-tac-toe-V2 are just like the usual tic- tac-toe game, but instead of having 3x3 squares, it can have nxn squares, where n>3, and the players that connect 4 or more points first is the winner. He has to design the algorithm in such a way that it has a good time complexity, interesting and challenging to the user.

Alex diminta untuk mereka bentuk algoritma bagi permainan tic-tac-toe- V2 yang   bermain   menentang   seorang   pemain   manusia.   Peraturan   bagi permainan   tic-tac-toe- V2   adalah   seperti   permainan   tic-tac-toe   biasa. Permainan ini tidak mempunyai segi empat 3x3, tetapi boleh mempunyai nxn segi empat dengan n>3, dan pemain yang menghubungkan dahulu 4 atau lebih  nod  adalah  pemenang.  Dia  hendaklah  mereka  bentuk  algoritma berkenaan supaya permainan berkenaan mempunyai kekompleksan masa yang baik, menarik dan mencabar kepada pengguna.

(a)    When and how can randomness be applied in the game to make it more

interesting?

Bilakah   dan   bagaimanakah   kerawakan   boleh   diterapkan   dalam permainan berkenaan untuk menjadikannya lebih menarik?

(20/100)

(b)    One of the functions that  is computational  intensive  is the function to

calculate the minimum number of steps for a user/computer to win the game. Explain the reasons this function is computational intensive.

Salah satu fungsi yang mengambil masa pemprosesan yang banyak ialah fungsi untuk mengira bilangan langkah  terkecil untuk pengguna atau computer menang suatu permainan. Terangkan sebab mengapa fungsi ini mengambil masa pemprosesan yang banyak.

(20/100)

(c)   Apply a brute-force approach to the function in (2)(b) above. Explain the approach and the time complexity of the brute-force approach.

Terapkan pendekatan  daya  kasar untuk fungsi dalam  (2)(b)  di atas. Jelaskan   pendekatan    tersebut   dan   kekompleksan   masa    untuk pendekatan daya kasar tersebut.

(28/100)

(d)   Propose an efficient algorithm using backtracking strategy for the function in (2)(b), and describe the way the strategy is applied so that the algorithm has better time complexity as compared to the function in (2)(c). What is the time complexity for the proposed algorithm?

Cadangkan     suatu     algoritma     efisyen     menggunakan     strategi pematahbalikan untuk fungsi (2)(b), dan terangkan cara strategi tersebut digunakan supaya algoritma tersebut mempunyai kekompleksan masa yang  lebih  baik  berbanding  dengan  fungsi  dalam   (2)(c).  Apakah kekompleksan masa bagi algoritma yang dicadangkan?

(32/100)

3.     (a)   Manipulate the following graph (the original graph) by deleting an edge or more (if required, otherwise explain) to make it:

Manipulasikan graf berikut (graf yang asal) dengan menghapus satu atau lebih tepi (jika diperlukan, jika tidakjelaskan) untuk menjadikannya:

(i)   a disconnected graph.

sebuah graf tak terkait.

(ii)  a simple graph.

sebuah graf mudah

(iii) a bipartite graph.

sebuah graf dwipihak.

(iv) contain a path that is not simple.

mengandungi sebuah lintasan yang bukan mudah.

(v)  contain a cycle that is simple.

mengandungi sebuah kitar yang mudah.

(25/100)

Given the following graph,

Diberi graf berikut,

2

1

(i)   identify the separation edges and separation vertices.

kenal pasti tepi-tepi pemisahan dan bucu-bucu pemisahan.

(ii)   create the  bi-connected component(s) of the graph  based on the

separation vertices that you have obtained in 3(b)(i) above.

cipta komponen (-komponen) dwiterkait graf berkenaan berdasarkan bucu-bucu pemisahan yang anda peroleh dalam 3(b)(i) di atas.

(20/100)

(c)   The pseudocode for finding a minimum spanning tree based on the Prim Jarnik algorithm is given below.

Pseudokod  untuk  mencari  pepohon  rentang  minimum  berdasarkan algoritma Prim Jarnik diberikan di bawah.

AlgorithmPrimJarnikMST(G):

Indnt: A weighted connected graph G with n vertices and m edges

Ontdnt: A minimum spanning tree T for G

1   Pick any vertex v of G 2   [v]← 0

3   for each vertex u ≠ v do D[u]← +∞

4   Initialize T ← ∅

5   Initialize a priority queue Q with an item (u,null), D[u]) for each vertex u // D[u] = key

6    while Q is not empty do

7        (u,e) ← Q.removeMin()

8        Add vertex u and edge e to T

9        for each vertex z adjacent to u such that z is in Q do

10                if w((u,z)) < D[z] then D[z] ← w((u,z))

11                Change to (z,(u,z)) the element of vertex z in Q.

12                Change to D[z] the key of vertex z in Q.

13 return the tree T

(i)    Is this algorithm considered to be a greedy method? Explain.

Adakah algoritma ini dianggap sebagai kaedah tamak? Jelaskan.

(ii)   Explain the role of the priority queue Q, by referring to parts of the

pseudocode that involve Q.

Jelaskan peranan baris gilir Q, dengan merujuk bahagian pseudokod yang melibatkan Q.

(iii)  Which parts of the algorithm (pseudocode) have some similarities to Dijkstra’s algorithm for finding shortest path? Explain.

Bahagian   manakah   dalam   algoritma   (pseudokod)   berkenaan mempunyai  kesamaan  dengan  algoritma  Dijkstra  untuk  mencari lintasan terpendek?Jelaskan

(iv)  Identify which part of the algorithm (pseudocode) contributes most to the complexity of this algorithm? Explain.

Kenal  pasti  bahagian   manakah   dalam   algoritma   (pseudokod) berkenaan  paling  banyak  menyumbang  kepada  kekompleksan algoritma ini? Jelaskan.

(55/100)

4.     (a)   The  pseudocode  for  searching  a  pattern  within  a  string  based  on Knuth-Morris-Pratt algorithm (KMP) is given below.

Pseudokod untuk menggelintar sebuah pola di dalam sesuatu renteten berdasarkan algoritma Knuth-Morris-Pratt (KMP) diberi di bawah.

AlgorithmKMPMatch(T,P):

Indnt: Strings T (text) with n characters and P (pattern) with m characters

Ontdnt: Starting index of the irst substring of T matching P, or P is not a substring of T 1   f ← KMPFailureFunction(P) // constructs the failure function f for P

2   i ←0

3   j ←0

4   while i < n do

5           if P[j] = T[i] then

6                 if j = m-1 then

7                        return i-m +1 // a match!

8                 i ← i+1

9                 j ← j +1

10        else if j > 0 then      // no match, but we have advanced in P

11                j ← f(j -1)   // j indexes just after preix of P that must match

12        else i ← i+1

13 return “There is no substring of T matching P”

(i)   Explain the role of the function KMPFailureFunction in line 1 of the above pseudocode?

Jelaskan peranan fungsi KMPFailureFunction pada baris  1 dalam pseudokod di atas?

(ii)    Obtain the worst-case complexity of the algorithm based on the while

loop (lines 4- 12).

Dapatkan    kekompleksan    kes    terburuk   algoritma    berkenaan berdasarkan gelung while (baris 4- 12).

(iii)  The complexity of the function KMPFailureFunction  in line  1 of the pseudocode is O(m) for an efficient implementation of the function. So, what is the overall complexity of the KMP algorithm? Justify your answer.

Kekompleksan fungsi KMPFailureFunction pada baris 1 pseudokod berkenaan  ialah   O(m)   untuk  pelaksanaan  yang  cekap  fungsi berkenaan. Oleh itu, apakah kekompleksan keseluruhan algoritma KMP? Jelaskan jawapan anda.

(40/100)

(b)    The diagram that depicts how the Discrete Fourier Transform (DFT) and

the inverse DFT can be used to multiply two polynomials more efficiently is given below.

Gambar rajah yang menggambarkan bagaimana Jelmaan Fourier Diskret dan DFT songsang boleh digunakan  untuk mendarab dua polinomial dengan lebih cekap diberi di bawah.

(i)    Explain mathematically “Component Multiply” in the above diagram.

Jelaskan  secara  matematik  “Component Multiply” dalam  gambar rajah di atas.

(ii)   Based  on  the  above  diagram,  explain  (in  terms  of  big  O)  why

transforming   problems   (e.g.   multiplying   two   polynomials)   into equivalent problems makes the problems simpler and easier to solve.

Berdasarkan  gambar rajah  di atas, jelaskan  (dari segi  O  besar) mengapa    menjelmakan    masalah    (contoh:    pendaraban    dua polinomial)  kepada  masalah  yang  setara  menjadikan  masalah berkenaan lebih mudah dan senang untuk diselesaikan.

(30/100)