Aim
This assessment task allows you to demonstrate your problem solving ability on problems covering counting, algorithms, complexity and graphs.
Questions
Counting
For all parts of this question, working is required, including combinatoric/factorial notation as needed as well as final answers. An answer consisting of solely an integer will be awarded 0 marks.
** [2 + 2+ 2 = 6 marks] A committee of 9 persons is to be chosen from 7 lecturers and 10 students so as to contain at least 2 lecturers and 5 students. Find the number of ways a committee can be formed
i. containing at least 2 lecturers and 5 students
ii. if 5 particular students are always present in the committee
iiii. when 5 particular students are never together
** [2 + 2 = 4 marks] A traveller forgets their passcode consisting of four digits. However, he remembers that his passcode has the following digits in it: 3, 2, 7, 4. Find the total number of trials necessary to obtain the correct passcode:
if a number is repeated
if a number is not repeated
[2 marks] ** Four dice are rolled. Find the number of possible outcomes in which at least one die shows a 6.
[2 marks] ** There are twelve units titled COS1, COS1, COS3,...COS12. Out of the twelve units, six units are to be arranged in such a way COS1 must occur whereas COS4 and COS5 do not occur. Find the number of such possible arrangement.
[1 mark] * There are seven pens in drawer A and seven notebooks in drawer B. You have been asked to match each pen in drawer A with a notebook in drawer B. What is the total number of ways this can be done?
Algorithms
[7 marks] You have been given a file with two columns containing the names of students and the grade they got in a Computer Science course. The grading has the following rules: HD (score is greater than 79), D (Score is greater than 69), C (score is greater 59), P (score is greater than 49), and F (score is less than 50). The file will look something like:
Aakaansh 87
Aaron 69
Erika 80
Linh 71 ...
It is not known at the outset how many rows are in the file, however the file will be terminated by EOF (end of file).
- * [3 marks] Draw a flowchart (following the conventions used in class) that reads the file and then calculates and prints the number of students that scored HD, D, C, P, and F.
- * [2 marks] Draw a flowchart that reads the file and then calculates and prints the average score in the course.
- ** [2 marks] What is the likely complexity of your program using big-O notation? Clearly point out what the primary parameters are and define your terms.
** [5 marks] Write a recursive function decimalToBinary(n), using the pseudocode principles covered in the lecture, to convert a decimal number to its binary equivalent.
You may also assume that n will be greater than 0 – error checking is not needed.
Submission of actual code (e.g., in Ruby or Python or any other programming language) will be awarded zero marks – we are seeking pseudocode. Answers using iteration will be marked on pseudocode alone and cannot receive full marks.
Graphs and trees
[7 marks] Using the following graph representation (G(V,E,W)):
- V= {6, 7, 8, 9, 10, 11, 12}
- E= {{6, 8}, {6, 10}, {6, 12}, {7, 8}, {7, 9}, {7, 11}, {8, 9}, {8, 10}, {8, 12}, {10, 12}, {11, 12}}
- W(6, 8) = 7, W(6, 10) = 12, W(6, 12) = 24
- W(7, 8) = 17, W(7, 9) = 14, W(7, 11) = 21
- W(8, 9) = 9, W(8, 10) = 10, W(8, 12) = 25 W(10, 12) = 23, W(11, 12) = 16
- * [3 marks] Draw the graph including weights.
- ** [2 + 2 = 4 marks] Given the following algorithm for finding a minimum spanning tree for a graph: Given a graph (G(V,E)) create a new graph (F) with nodes (V) and no edges
Add all the edges (E) to a set S and order them by weight starting with the minimum weight While S is not empty and all the nodes V in F are not connected:
Remove the edge s from set S with the lowest weight
When s is added to F:
If it does not cause a cycle to form, keep it
Else discard it from F
Using your graph from a) as G,
- Provide the order of the edges as they are removed from S, and note whether it is kept or discarded.
- Draw the resulting spanning tree F.
Probability
[6 marks] Show your workings on how you arrived at the final solution
[1+1+1+1 = 4 marks] * Two dice are rolled, find the probability that the sum is I. Greater than 1
- Equal to 7
- Equal to 13
- Less than 5
[2 marks] ** In a particular chemistry experiment, the probability of success is thrice the probability of failure. Find the probability of at least six successes in eight trials.
Use counting notation as part of your working.
