Reference no: EM132893961

COS1000S Computer and Logic Essentials - Swinburne University of Technology

Aim

This assessment task allows you to demonstrate your problem solving ability on problems covering counting, algorithms, complexity and graphs.

Questions

Counting

1. After a year of not doing much, everyone has decided to get active. We thought about this in assignment 1 as well.
For all parts of this question, working is required, including combinatoric/factorial notation as needed as well as final answers.

a) During a given day, there are many activities that could be done, such as:

• go shopping
• get an immunisation
• visit the gym
• go to a tutorial
• join a virtual student event.

Assume that each activity is undertaken at most once a day (i.e., so once you have visited the gym you don't visit it again). The amount of time spent on each activity is also unimportant, however, for example, shopping before a tutorial and a tutorial before shopping should be considered different. We are interested in working out the different ways people spend their day.

i.How many di fferent activity patterns can be formed from those five activities? ii.How many patterns contain only three activities (e.g., shop - immunisation - gym)? iii.How many patterns with at least four di fferent activities start with going shopping?

b) You have twelve friends that you haven't seen in a year that you would like to meet up with. For parts i-iii, your reasoning needs to be explained in a sentence or two; 0 marks will be awarded for a number or expression alone.

i. You have won a voucher for 5 people to go indoor rockclimbing. How many options are there for inviting your friends to join you?
ii. All twelve friends are invited to meet you at an outdoor gym for some exercise at a particular time. How many outcomes are there from this invite?
iii. With eleven friends, you are going to a concert in the city but are required to sit in pods of four at the venue. How many different ways can the pods be organised?
iv. Show a second approach to your answer to iii.

c) After all these social activities, you decide you probably should do some cleaning at home, and put together a schedule for the next month (30 days). You don't clean more than once a day. If you have 20 cleaning sessions planned, explain using the counting principles covered in class how this means you will clean on consecutive days at least once in the next month.

Algorithms

2. You have been given a file with two columns: a name and an integer (whole number) representing how many times the person with that name has used the Swinburne app to sign on to visit campus this year. The file will look something like:
Aakaansh 10
Aaron 25
Erika 0
Linh 15
...

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).
a) Draw a flowchart (following the conventions used in class) that reads the file and then calculates and prints the number of students that have applied to visit campus more than 24 times this year.

b) What is the likely complexity of your program using big-O notation? Clearly point out what the primary parameters are and define your terms.

in the lecture, to calculate the nth value in the sequence mystery(n) = -4 ∗ mystery(n - 1) -

3. Write a recursive function mystery(n), using the pseudocode principles covered 4 ∗ mystery(n - 2), where mystery(0) = 1 and mystery(1) = -2. You may also assume that n will be greater than or equal to 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

4. Using the following graph representation (G(V,E,w)):
V = {1, 2, 3, 4, 5, 6, 7}
E = {{1, 3}, {1, 5}, {1, 7}, {2, 3}, {2, 4}, {2, 6}, {3, 4}, {3, 5}, {3, 7} {5, 7}, {6, 7}}
W (1, 3) = 2, W (1, 5) = 7, W (1, 7) = 19
W (2, 3) = 12, W (2, 4) = 9, W (2, 6) = 16
W (3, 4) = 4, W (3, 5) = 5, W (3, 7) = 20
W (5, 7) = 18, W (6, 7) = 11
a) Draw the graph including weights.

b) 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,

i. Provide the order of the edges as they are removed from S, and note whether it is kept or discarded.
ii. Draw the resulting spanning tree F.

Probability

5. A game has been set up that requires players to pay money to play, where the outcome will be determined by drawing cards from a standard 52 card pack.

a) Players pay $10 to play by drawing one single card. If they draw a red face card, they win $50; if they draw a black card, they win $20. Any other cards means that the player wins nothing.

i. If the deck is fair, what is the expected value?

ii. What value (to the nearest cent) should players pay to make the game fairer?

b) As a further challenge, the game is changed so that the player takes three cards. In this variant, the player still pays $10 to play, but must have selected three red face cards to win $50, and exactly two red cards and one black card to win $20.

What is the expected value in this case? Use counting notation as part of your working.

Attachment:- Computer and Logic Essentials.rar