The assignment is on problems covering counting, algorithms, complexity and graphs
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 – under no circumstances should you show or give your assignment to another student, nor 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/current-students/manage-course/ exams-results-assessment/submit-work/assessment-declaration/. Electronic submission of 1 https://www.swinburne.edu.au/current-students/manage-course/exams-results-assessment/submit-work/assessment-declaration/ https://www.swinburne.edu.au/current-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 required, however please put your preferred 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 or before 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 preferred that you use word processing software to create your submission; if handwriting is required or preferred please scan your document as a single PDF rather than submitting images. Before submitting, please check that your PDF contains all your images, working, and text. After 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 correctly answered. Please note that if a problem requires the answer to be justified, no marks will be awarded for simply giving the correct 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) ? [2 + 1 + 2 = 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? b) ? [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 your 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 arranged? 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 together 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) representing 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. b) ?? [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 recommend and why? b) ? ? ? [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 number 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 your pseudocode. 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. 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. b) ?? [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 or 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 briefly 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