Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

2017 B SEMESTER EXAMINATIONS

Introduction to Computer Science 2

COMP104- 17B (HAM)


1.    Explain the difference between the following pairs of C# object-oriented terminology:

(a)  object and class

(b)  abstract method and virtual method

(c)  call by reference and call by value

(d)  local variable and private class variable

(e)  List<> and ArrayList

(f)   iteration and recursion

(g)  inheriting from an interface and inheriting from a class

(h)  private methods and protected methods

(i)   composition and inheritance

(j)   Requires and Ensures in Code Contracts (10 marks, 1 for each part)

2.    (a)  Add the following 8-bit binary numbers: 00111010 and 01011101 . (2 marks)

(b)  How many ways are there of representing the value 0 in 2s complement form? (2 marks)

(c)  Write down the negative number  – 113  in 8-bit 2s complement form. (2 marks)

(d)  Write binary 01011101 in hexadecimal . (2 marks)

(e) What is the highest positive value that can be represented in 8-bit 2s complement form? (2 marks)


3 .    Indicate for each of the following statements whether it is true or false:

(a)  a pre-condition for a method is expressed using a Contract.Requires statement

(b)  when an arithmetic calculation exceeds the maximum or minimum value that can be

represented, the C# program always throws an exception

(c)  an interface cannot be instantiated to give an object

(d)  to be called a iterative solution the code in question must use a method that calls itself from within its own body

(e)  a protected method is only accessible from within that class or one of its subclasses

(f)   an argument in a method passed as a ref parameter must be unassigned before the

method is called

(g)  a virtual method can be overridden in a subclass

(h)  all items stored in an ArrayList must be of the same class

(i)   Finite State Machines can solve a larger set of problems than Turing Machines

(j)   If the input is large enough, an algorithm of complexity O(n !) will outperform (i .e .,

solve a problem more quickly than) an algorithm of complexity O(n log n) . (10 marks, 1 for each part)

4 .    (a)  Write out the Boolean expression for the following circuit:

  (3 marks)

(b)  Apply De Morgan’s law to eliminate the OR operation(s) for your expression in (a)   (2 marks)

(c)  Write out the Truth Table for the circuit given in (a) (3 marks)

(d)  From inspecting the Truth Table in (c), draw a simpler equivalent circuit , using AND, OR and NOT gates, to that given in (a) . (2 marks)

5 .    Problem Description: The Department of Internal Affairs keeps track of births, deaths and marriages in New Zealand . Every record has a registration number, a date, and a place it was registered . For births, the records keep track of the baby's name and parents' names . A death record stores the name of the deceased and the cause of death, along with the doctor, coroner or medical examiner who diagnosed it . A marriage record stores the names of the bride and groom (both prior to marriage and their married names), and their parents' names. They also want to bring adoption and name changes into the same system.

The Department is looking at launching a website that makes these records available to registered genealogists and interested members of the public . To do this they want to start identifying different records that are about the same person, for example, their birth record and their death record . Further records associated with that person will allow a user to build a family tree, which can be saved if they are a registered genealogist .

(a)  Identify 6 nouns in the description above that would make suitable candidates for

representation  as  objects  in  the  design  of  a  program  that  supports  the  required functionality . (2 marks)

(b)  Identify three nouns in the above description that would benefit from sharing the same

base-class through inheritance . Detail any separation of fields between the base-class and its three subclasses . Note: the nouns chosen need not be restricted to those given in your answer to (a) . (2 marks)

(c) Write a suitable enumerated type for the categories of people who can diagnose cause of death, i .e . doctor, coroner and medical examiner . (2 marks)

(d) Identify two classes that are in a has a’ relationship in the above description . Show how these two classes would be related using a UML diagram. (2 marks)

(e)  Assume   class Genealogist : User {}

(i)  Which of the following will cause a run time error?

1.    User u = new User ();

Genealogist g = (Genealogist) u;

2.    Genealogist g = new Genealogist (); User u = (User) g;

(ii)  Which of the following will cause a compile time error?

1.    User u = new User (); Genealogist g = u;

2.    Genealogist g = new Genealogist (); User u = g; (2 marks)

6 .    This question relates to WRAMP instructions and programs.

(a)  For each of the three specifications below write one WRAMP instruction that satisfies

the specification:

(i)  Set the value in register $1 to the decimal value of 10.

(ii)  Add the value in $4 to the value in $3 and store the result in $3.

(iii)  Load the value currently pointed to by the stack point $sp into $8 . (3 marks, 1 for each part)

(b)    Prior to the WRAMP code below being executed, the registers $1, $2, $3, and $4 have

all been set to the hexadecimal value 0xE0 . What are their values, again expressed in hexadecimal, after the code has been executed?

subui $1, $1, 1

slli  $2, $2, 4

andi  $3, $3, 0xF0

seq   $4, $4, $0 (4 marks)

(c)     The excerpt of WRAMP assembly code below encodes the same logic as a high-level language if-statement with an else clause (e .g ., in C#) .  Assuming, in the high-level language, that the variables: m is mapped to $2, x to $3 and y to $4, write out an if- statement that is equivalent to the WRAMP code .

Note: although the assembly code also uses $13, you do not need to declare any additional high-level language variables to those already mentioned to answer the question .

slt $13, $3, $4

beqz $13, label

add $2, $0, $3

j label2

label:

add $2, $0, $4

label2:

… (3 marks)

7 .    (a)  What would be the output of the following program?

static bool mystery(string s)

{

if (s .Length < 2){

return true;

}

else {

string inner_s = s.Substring(1, s.Length - 2);

return (s[0] == s[s.Length-1]) && mystery(inner_s);

}

}

static void Main(string[] args)

{

string test1 = "abccba";

Console.WriteLine(test1 + " = " + mystery(test1).ToString());

string test2 = "abcdcba";

Console.WriteLine(test2 + " = " + mystery(test2).ToString());

string test3 = "abcabc";

Console.WriteLine(test3 + " = " + mystery(test3).ToString());

string test4 = "abcdcbb";

Console.WriteLine(test4 + " = " + mystery(test4).ToString());

}

Recall   that   string  string.Substring(int  startIndex,  int length) retrieves a substring from this instance . The substring starts at a specified character position and has a  specified length .”  Character positions are numbered starting at zero . For example,    s.Substring(0,1) retrieves the first character from string ‘s’ . (4 marks)

(b)  What would be a more appropriate name for the mystery method? (1 marks)

(c)  You have to write a method sumN that calculates the total sum of the first N integers (N>=1) starting at 1. For example, sumN(5) is 15. Here is a recursive definition:

“The sum of the first N integers when N is 1, is 1. The sum of the first N integers

when N is greater than 1 is N PLUS the sum of the first N– 1 integers.” Turn this recursive definition into a C# recursive function . (5 marks)

8 .    The following is a syntactic description of a Turing Machine:

; State 1

S1 x x r S1

S1 @ @ r S2

S1 _ _ * halt-reject

S1 . . * halt-reject

; State 2

S2 x x r S2

S2 . . r S2

S2 _ _ * halt-accept

Where the start state is S1 and the input tape consists of x, @, . and the blank symbols.

The syntax used in the description above is the same as the on-line Turing Machine web- site studied in lectures, where:

•    Each line contains one tuple of the form '<current state> <current symbol> <new symbol> <direction> <new state>'.

•    You can use any number or word for <current state> and <new state>, e.g., 10, a, state1. State labels are case-sensitive.

•    You can use any character for <current symbol> and <new symbol>, or '_' to represent blank (space). Symbols are case-sensitive.

•     <direction> should be 'l', 'r' or '*', denoting 'move left', 'move right' or 'do not move', respectively.

•     Anything after a ';' is a comment and is ignored.

•    The machine halts when it reaches any state starting with 'halt', e.g., halt-reject, halt-accept.

(a)  Draw the Turing Machine Diagram of the above machine description: (2 marks)

(b)  What are the halt states for the following inputs:

[email protected]

[email protected]

[email protected]

[email protected](4 marks)

(c)  Using a simplified input alphabet of x’, ‘@’ and ‘ . ’ the intention of the Turing       Machine is to determine if an input string is a valid email address.  There are, however, some deficiencies as currently implemented.  In summary, valid email addresses:

• Can include multiple dots on either side (left part or right part) of the ‘@’ symbol.

• The dots, however, cannot appear consecutively.

• The final character in either the left or right part cannot be a dot.

• The part to the left of the ‘@ ’ symbol may have no dots at all.

• The part to the right must include at least one.

• The ‘@’ symbol itself can only appear once.

Draw an improved Turing Machine that correctly handles all the cases itemize above. You do not need to write the full Turing Machine tuple description. (4 marks)

9 .    Here are the Ball and Paddle classes from an in-development Break-Out program (see next page for a snapshot of the original game by Atari) .

public class Ball {

private int x;

private int y;

private Brush green_brush;

private const int RADIUS = 20;

public Ball(int x, int y) {

this.x = x;

this.y = y;

green_brush = new SolidBrush(Color.Green);

}

public int X { get { return x; } }

public int Y { get { return y; } }

public void Move(int delta_x, int delta_y) {

x += delta_x;

y += delta_y;

}

public void Draw(Graphics paper) {

Rectangle rect

= new Rectangle(x - RADIUS, y - RADIUS, 2 * RADIUS, 2 * RADIUS);

paper.FillEllipse(green_brush, rect);

}

}

public class Paddle {

private int x;

private int y;

private Brush blue_brush;

private const int WIDTH = 10;

private const int HEIGHT = 30;

public Paddle(int x, int y) {

this.x = x;

this.y = y;

blue_brush = new SolidBrush(Color.Blue);

}

public int X { get { return x; } }

public int Y { get { return y; } }

public void Move(int delta_x, int delta_y) {

x += delta_x;

y += delta_y;

}

public void MoveRight(int v) { Move(v,0); }

public void MoveLeft(int v) { Move(-v,0); }

public void Draw(Graphics paper) {

Rectangle rect

= new Rectangle(x - WIDTH / 2, y - HEIGHT / 2, WIDTH, HEIGHT);

paper.FillRectangle(blue_brush, rect);

}

}


The following snapshot is taken from the original Atari Break Out game, and is used as inspiration for the in-development C# program.  In the C# program, the ball has be “upgraded” to be round!

 

(a)  Write an abstract class called Sprite that contains all code elements common to both Ball and Paddle, so that they can both inherit from it . (5 marks)

(b)  Rewrite both Ball and Paddle to be subclasses of your new Sprite class. (5 marks)


10 .  Recall the sorting algorithms (given in pseudo code):

Bubble Sort:

for i := 1:n,

swapped := false

for j := n:i+1,

if a[j] < a[j-1],

swap a[j],a[j-1]

swapped := true

// invariant: a[1 . .i] in final position

break if not swapped

end

Selection Sort:

for i := 1:n,

k := i

for j := i+1:n, if a[j] < a[k], k := j

// invariant: a[k] smallest of a[i . .n]

swap a[i],a[k]

// invariant: a[1 . .i] in final position

end

For the following array of eight integers:

4

1

2

5

6

9

8

8

Answer the following questions:

(a) When  using  BubbleSort,  how  many  number  comparison  operations  and  swap operations are performed? (Note: the number of comparisons and swaps need not be the same .) (3 marks)

(b) When  using  SelectionSort,  how  many  number  comparison  operations  and  swap operations are performed? (Note: the number of comparisons and swaps need not be the same .) (2 marks)

(c) Write out the Big O notation for the following runtime complexities:

T(f(A)) = 2n3  + 5n2   + 9n

T(f(A)) = 5n3  + 2n4   + 10n + 110 ,

T(f(A)) = 3n  + 4n2

T(f(A)) = 2n  + 2n2  + 2n!           (4 marks)

(d) In terms of the Big O notations given in (c), which one has (or ones share) the biggest growth rate? (1 mark)