parameter of the Geometric Distribution have to be changed (from 2/5) for the expected annual sum to
Question:
parameter of the Geometric Distribution have to be
changed (from 2/5) for the expected annual sum to be £750? [4 marks]
6 Probability
(a) Give a brief account of the Trinomial Distribution and include in your
explanation an expression that is equivalent to n
!
r!(n−
r)! prqn−r for the Binomial
Distribution. [5 marks]
(b) An indicator light can be in one of three states: OFF, FLASHING and ON, with
probabilities 1/2, 2/5 and 1/10 respectively. A test panel has fifive such lights
whose states are mutually independent.
(i) What is the probability that all fifive lights are OFF? [3 marks]
(ii) What is the probability that three lights are OFF, one light is FLASHING
and one light is ON? [3 marks]
(iii) What is the probability that three or more lights are OFF and at most one
is ON? [9 marks]
All results must be expressed as fractions.
6CST.2008.2.7
SECTION D
7 Software Design
Software systems often incorporate structural representations of the application
domain in which they operate. For example, a vehicle control system should be
aware of the fact that the car has precisely four wheels. This kind of information
must be captured, encoded and tested at each stage of the software design process.
Using the number of wheels in a car as a simple example, describe relevant design
activities and products at each of the following phases of a software project:
(a) inception; [4 marks]
(b) elaboration; [4 marks]
(c) construction; [4 marks]
(d) transition; [4 marks]
(e) system operation. [4 marks]
8 Regular Languages and Finite Automata
(a) Explain what is a context-free grammar and the language it generates.
[4 marks]
(b) What does it mean for a context-free grammar to be regular? Given any
deterministic fifinite automaton M, describe a regular context-free grammar
that generates the language of strings accepted by M. [4 marks]
(c) Construct a non-deterministic fifinite automaton with ε-transitions whose
language of accepted strings is equal to the language over the alphabet {a, b, c}
generated by the context-free grammar with non-terminals q0 and q1, whose
start symbol is q0 and whose productions are q0 → abq1, q1 → ε, q1 → q0 and
q1 → abc. [4 marks]
(d) Is every language generated by a context-free grammar equal to the
set of strings accepted by some non-deterministic fifinite automaton with
ε-transitions? Justify your answer. (Any standard results about regular
languages you use should be carefully stated, but need not be proved.)
[8 marks]
7 (TURN OVER)CST.2008.2.8
9 Professional Practice and Ethics
(a) The British Computer Society Code of Conduct has four sections. What kind
of professional conduct does each section cover, and how does each of these
kinds of conduct benefifit the profession and its members? [8 marks]
(b) True or False questions:
(i) A User can provide occasional use of the University computer system for
a friend who is a temporary visitor.
(ii) Circumstances that mitigate minor infractions of the rules promulgated
by the Information Technology Syndicate include, among other things,
inebriation.
(iii) Appropriate use of the Cambridge University Data Network (CUDN)
means bona fifide academic activity plus a low level for private purposes.
(iv) Small amounts of commercial activity are acceptable as long as the User
is acting in a private capacity.
[4 marks]
(c) The IT industry is increasingly aware of its own environmental impact.
Describe at least one environmental problem to which the industry contributes
and how, as an IT professional, you can help to solve this problem. [4 marks]
(d) "Social engineering is a greater threat to computer security than computer
cracking software." What is social engineering and what measures can be
taken to guard against it? [2 marks]
(e) What is copyleft and how is it used to protect free, open-source, software?
(a) Brieflfly explain the difffferences between combinational and sequential logic.
[2 marks]
(b) With the aid of appropriate diagrams, brieflfly explain the operation of Moore
and Mealy fifinite state machines and highlight their difffferences. [6 marks]
(c) The state sequence for a binary counter is as follows:
The counter is to be implemented using four synchronously clocked D-type
flflip-flflops.
(i) Draw a state table for the counter, showing the required D inputs.
[4 marks]
(ii) Find expressions for the D inputs, making use of unused states if
appropriate. [6 marks]
(iii) What problem could occur when the counter circuit is powered-up? Give
two possible general methods for overcoming the problem. [2 marks]
2CST.2008.2.3
2 Digital Electronics
(a) With the aid of relevant diagrams, show the effffect on the output of a
combinational logic circuit of a:
(i) static hazard;
(ii) dynamic hazard. [3 marks]
(b) Simplify the following expressions using Boolean algebra:
(i) X = (A + B + A . B).(A + B). A . B
(ii) Y = (A + B + A . B). C
[4 marks]
(c) Given:
F = A . B . C . D + A . C + B . C . D + B . C + A . C . D + A . B . C . D
(i) Show using a Karnaugh map that F can be simplifified to
F1 = A . B + A . B + A . C + B . C . D
[2 marks]
(ii) Show that there are a total of four possible expressions for F. [3 marks]
(iii) Show how F1 can be implemented using NAND gates and draw the circuit
diagram. Assume that complemented input variables are available.
[2 marks]
(iv) Show how the static 1 hazard in F1 can be eliminated using a Karnaugh
map-based approach. [2 marks]
(v) Now implement F1 assuming that only 2-input NAND gates are available.
[4 marks]
3 (TURN OVER)CST.2008.2.4
SECTION B
3 Discrete Mathematics
Let X and Y be sets. You are reminded that a relation from X to Y is a subset of
the product X × Y .
(a) Explain what it means for a relation f from X to Y to be a function, an
injection and a surjection from X to Y . [4 marks]
(b) A bijection from X to Y is defifined to be a function from X to Y which is
both an injection and a surjection. Prove that a function f from X to Y is a
bijection iffff it has an inverse function g, i.e. g is a function from Y to X such
that g ◦ f = idX and f ◦ g = idY .
[Remember to prove both the "if" and "only if" parts of the assertion.]
[12 marks]
(c) Describe, without proof, a bijection from P(X × Y ) to (X → P(Y )) and its
inverse. [4 marks]
4CST.2008.2.5
4 Discrete Mathematics
Let I be a non-empty subset of the natural numbers N = {1, 2, 3, · · ·}.
The set S is defifined to be least subset of N such that
I ⊆ S, and
if m, n ∈ S and m < n, then (n − m) ∈ S.
Defifine h to be the least member of S. This question guides you through to a proof
that h coincides with the highest common factor of I, written hcf (I), and defifined
to be the natural number with the properties that
hcf (I) divides n for every element n ∈ I, and
if k is a natural number which divides n for every n ∈ I, then k
divides hcf (I).
[Throughout this question you may assume elementary facts about division.]
(a) The set S may also be described as the least subset of N closed under certain
rules. Describe the rules. Write down a principle of rule induction appropriate
for the set S. [4 marks]
(b) Show by rule induction that hcf (I) divides n for every n ∈ S. [3 marks]
(c) Let n ∈ S. Establish that
if p.h < n then (n − p.h) ∈ S
for all non-negative integers p. [5 marks]
(d) Show that h divides n for every n ∈ S. [Hint: suppose otherwise and derive a
contradiction.] [5 marks]
(e) Explain very brieflfly why the results of parts (b) and (d) imply that h = hcf (I).
[3 marks]
5 (TURN OVER)CST.2008.2.6
SECTION C
5 Probability
(a) Suppose that X is a random variable whose value r is distributed Geometric(p).
Write down the expression for the probability P(X = r). [3 marks]
(b) By using a suitable generating function or otherwise, show that the expectation
E(X) = (1 − p)/p. [5 marks]
The University Computing Service defifine a serious power outage as a power cut that
lasts for longer than their Uninterruptable Power Supply equipment can maintain
power. During the course of an academical year the number of serious power outages
is a random variable whose value is distributed Geometric(2/5). Accordingly, the
probability of having no serious power outages during the course of a year is 2/5.
(c) The University is investigating a compensation scheme which would make no
payment over the year if the number of serious power outages were zero or
one but which would pay the Computing Service £1000 for every such outage
(including the fifirst) if the total number of serious power outages in a year were
two or more. Determine the expected annual sum that the Computing Service
would receive. [8 marks]
(d) To what value would the parameter of the Geometric Distribution have to be
changed (from 2/5) for the expected annual sum to be £750? [4 marks]
6 Probability
(a) Give a brief account of the Trinomial Distribution and include in your
explanation an expression that is equivalent to n
!
r!(n−
r)! prqn−r for the Binomial
Distribution. [5 marks]
(b) An indicator light can be in one of three states: OFF, FLASHING and ON, with
probabilities 1/2, 2/5 and 1/10 respectively. A test panel has fifive such lights
whose states are mutually independent.
(i) What is the probability that all fifive lights are OFF? [3 marks]
(ii) What is the probability that three lights are OFF, one light is FLASHING
and one light is ON? [3 marks]
(iii) What is the probability that three or more lights are OFF and at most one
is ON? [9 marks]
All results must be expressed as
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill