Assignment 2
HIT 400 – Discrete Structures
This assignment is worth 20 % of the assessment for this unit. Late submissions will not be accepted unless prior arrangements have been made.
Show all working and explanations. Remember to write sentences.
Successfully completion of tutorial exercises is worth 20% of your mark
Question 1 (30 Marks)
Solve the following recurance relations
T(n) = T(n-1) + 4n -1
T(n) = 4T(n/2)
Question 2 (10 Marks)
Solve the following recurance relations
T0(k) = T0(k-1) + T1(k)
T1(k) =T0(k-1)+(d-2)T1(k-1)

Question 3 ( 25 Marks)
Draw a DFA diagram that represents a standard Drink machine accepting money
Question 4 ( 15 Marks)
In your own works describe the difference between NP, NP-Hard and co-NP
What does it mean if the polynomial hierarchy collapse s

1

1

Assignment 2
HIT 400 – Discrete Structures
This assignment is worth 20 % of the assessment for this unit. Late submissions will not be accepted unless prior arrangements have been made.
Show all working and explanations. Remember to write sentences.
Successfully completion of tutorial exercises is worth 20% of your mark
Question 1 (30 Marks)
Solve the following recurance relations
T(n) = T(n-1) + 4n -1
T(n) = 4T(n/2)
Question 2 (10 Marks)
Solve the following recurance relations
T0(k) = T0(k-1) + T1(k)
T1(k) =T0(k-1)+(d-2)T1(k-1)

Question 3 ( 25 Marks)
Draw a DFA diagram that represents a standard Drink machine accepting money
Question 4 ( 15 Marks)
In your own works describe the difference between NP, NP-Hard and co-NP
What does it mean if the polynomial hierarchy collapse s

1

1