COS10003 Computer and Logic Essentials
COS10003 Computer and Logic Essentials – Assignment 3
Semester 1 2020
Aim
This assessment task allows you to demonstrate your problem solving ability on problems covering
counting, algorithms, complexity and graphs. It is worth 20 of your final mark for this unit.
Due date
This assignment is due by 11:59pm Monday 25 May 2020.
Due date and submission
Each individual student should submit their assignment via Canvas before the deadline. You
can submit several times before the deadline; each new submission will overwrite your previous
submission.
Before submitting the assignment, please ensure that you have undertaken the following activities:
• Checked Canvas for announcements/discussions related to the assignment and for any up-
dates/clarifications;
• Ensured that the work submitted by you is your original work. If this is not the case, then
further investigation will take place and a penalty or sanction may be applied. Note this
includes:
– sharing your original work with other students either on purpose or by accident – unde
no circumstances should you show or give your assignment to another student, no
should you ask to see another student’s assignment;
– soliciting answers from online forums and tutoring sites (even if money has not changed
hands);
– copying answers publicly posted online.
• Reviewed the declaration at https:
www.swinburne.edu.au/cu
ent-students/manage-course
exams-results-assessment/submit-work/assessment-declaration/. Electronic submission of
1
https:
www.swinburne.edu.au/cu
ent-students/manage-course/exams-results-assessment/submit-work/assessment-declaration
https:
www.swinburne.edu.au/cu
ent-students/manage-course/exams-results-assessment/submit-work/assessment-declaration
COS10003 Computer and Logic Essentials
your assignment signifies that you agree with this declaration. Note a cover page is not
equired, however please put your prefe
ed name and student ID on at least the first page,
ideally all pages.
If you have exceptional circumstances that mean you are unable to submit the assignment by the
due date and time, please contact the convenor as soon as practicable prior to the due date. Note
evidence of circumstances will be required.
For students with EAPs allowing extensions: you are required to request an extension on o
efore the Friday before the due date by emailing the convenor and nominating your ideal due date.
In general, up to seven days’ extension can be allowed; any more than this will most likely require an
alternative assessment task or a hint to withdraw from the unit.
General instructions
This is an individual assignment. It is prefe
ed that you use word processing software to create
your submission; if handwriting is required or prefe
ed please scan your document as a single PDF
ather than submitting images.
Before submitting, please check that your PDF contains all your images, working, and text. Afte
submitting, please check that the submitted document is as you expected; instructions for how to
do this are in Canvas. With the number of submissions we expect, we are unable to inform you
individually that your submission appears to be incomplete. Resubmissions are allowed only
during the late submission window and will attract a late penalty.
Marking scheme
Marks will be awarded in accordance with the scheme allocated for each sub-part of the problems
as indicated in the assignment. Partial marks will be awarded to the extent that the component
parts of the question have been co
ectly answered. Please note that if a problem requires the
answer to be justified, no marks will be awarded for simply giving the co
ect answer.
Stars
The stars suggest the difficulty of the problem:
? Should be straightforward based on lecture and tutorial material.
2
COS10003 Computer and Logic Essentials
?? Should be more challenging but still based on lecture and tutorial material.
? ? ?Might require some further thought or extra research beyond lecture and tutorial material.
Questions
Counting
1. Everyone is still stuck at home. However we have plenty of things we can do to keep us busy.
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.
a) ? [ XXXXXXXXXX = 5 marks] During the day, there are jobs that need doing, such as:
• clean the kitchen
• play games
• open the front door and think about going outside
• sit on the couch and stare into space
• read a comic
Assume that each activity is undertaken at most once a day (i.e., so once you have cleaned the
kitchen for the day you don’t clean it again). The amount of time spent on each activity is also
unimportant, however, for example, cleaning before playing and playing before cleaning should be
considered different. We are interested in working out the different ways people spend their day.
i. How many different activity patterns can be formed from those five activities?
ii. How many patterns contain only three types (e.g., clean - sit - read)?
iii. How many patterns with at least four different activities start with playing games?
) ? [2 + 1 = 3 marks] You have found six ingredients in your fridge that need to be used up.
i. How many ways could these be combined? Explain in a sentence how you calculated you
answer.
ii. How many ways could you use three ingredients only?
3
COS10003 Computer and Logic Essentials
c) ?? [2 + 1 = 3 marks] You find 12 LEGO minifigures in your desk drawer, all different. You would
like to put them in groups and assign them to different locations around the house.
i. If there are four different locations around the house, and three minifigures are to be placed
at each location, how many different ways can the minifigures be a
anged?
ii. Show a second approach to your answer to i.
d) ?? [3 marks] After all of this, you decide you probably should do some study, and put togethe
a schedule for the next fortnight (14 days). You don’t study more than once a day. If you have
10 study sessions planned, explain using the counting principles covered in class how this
means you will study on consecutive days at least once in the next fortnight.
Algorithms
2. [7 marks] You have been given a file with two columns: a name and an integer (whole number)
epresenting how many times the person logged onto Canvas this semester, between 0 and
255 inclusive. The file will look something like:
Otto 10
Gary 125
Elise 201
Cara 83
...
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) ? [5 marks] Draw a flowchart (following the conventions used in class) that reads the file and
then calculates and prints the number of students who have logged in at least 50 times this
semester.
) ?? [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.
4
COS10003 Computer and Logic Essentials
3. [4 marks] Your colleague is working on two algorithms, X and Y, that determines whether two
people are a certain distance apart. They use a number of different inputs, n. They are seeking
your advice.
a) ?? [2 marks] If they tell you that algorithm X has a worst-case runtime complexity of O(n2)
and algorithm Y has a worst-case runtime complexity of O(n3), which algorithm would you
ecommend and why?
) ? ? ? [2 marks] Your colleague then adds that the average-case time complexity for X is Θ(n2)
and for Y is Θ(n). Does this change your advice at all, and why?
Your answers should be no longer than a sentence or two.
4. ?? [4 marks] Write a recursive function sum_odd(n), using the pseudocode principles covered
in the lecture, to sum up the numbers i between 1 and n where the binary representation of i
contains an odd number of 1s, e.g., 14 is represented as 0b1110 which contains an odd numbe
of 1s.
You can assume that you have access to a function binary_ones(d), which returns the number of
ones in the binary representation of d. You should not write out this function, but can call it in you
pseudocode. You may also assume that n will be greater than 0 – e
or 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.
5
COS10003 Computer and Logic Essentials
Graphs and trees
5. [7 marks] Using the following graph representation (G(V,E,w)):
V = {a, b, c, d, e, f}
E = {{a, b}, {a, f}, {a, d}, {b, e}, {b, d}, {c, f}, {c, d}, {d, e}, {d, f}}
W (a, b) = 5,W (a, f) = 10,W (a, d) = 11
W (b, e) = 13,W (b, d) = 8,W (c, d) = 4
W (c, f) = 3,W (d, e) = 15,W (d, f) = 7
a) ? [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,
i. Provide the order of the edges as they are removed from S, and note whether it is kept o
discarded.
ii. Draw the resulting spanning tree F.
6. ?? [4 marks] Determine whether the following graph contains Eulerian and Hamiltonian cycles
(and provide an example of an Eulerian/Hamiltonian cycle if so; do not provide all cycles) and
explain
iefly how you found them.
V = {a, b, c, d, e, f, g, h}
E = {{a, b}, {b, c}, {c, d}, {a, d}, {e, f}, {f, g}, {g, h}, {e, h}, {a, e}, {b, f}, {c, g}, {d, h}}
6
COS10003 Computer and Logic Essentials – Assignment 3
Aim
Due date
Due date and submission
General instructions
Marking scheme
Stars
Questions
Counting
Algorithms
Graphs and trees