Data and Alogarithms

Question 2 (25 marks)
A bibliography is an alphabetically ordered list of references. For example:

Miller, B. N., and Ranum, D. L. (2011) Problem Solving with Algorithms and Data Structures using Python, 2nd edn, Oregon, Franklin, Beedle & Associates, Incorporated.

The Open University (2013) Logic and the Limits of Computing, Milton Keynes, The Open University.

The bibliography can be represented by a collection of key–value pairs where the key is the Author and Date part of the reference, and the value is the remainder of the reference.

For example:

key: ‘Miller, B. N., and Ranum, D. L. (2011)’
value: ‘Problem Solving with Algorithms and Data Structures using Python, 2nd edn, Oregon, Franklin, Beedle & Associates, Incorporated.’
key: ‘The Open University (2013)’
value: ‘Logic and the Limits of Computing, Milton Keynes, The Open University.’
a.This part is about data structures that implement the Map ADT (Unit 4 sections 3 and 4): hash tables and binary search trees (BSTs). It assesses your skills in clear and succinct communication.
A bibliography ADT could be implemented using a hash table or a binary search tree that doesn’t self-balance (i.e. not an AVL tree) to store the key–value pairs.

What are some advantages and disadvantages of using each of these data structures for insertions, retrievals, deletions and outputting the bibliography? You should present the advantages and disadvantages in a table.

Which of these two data structures would you choose for this particular application? Give your reasons.

You may assume that:

Key–value pairs are added over a period of time, as references are found. That is, they will not be added in alphabetical order.
All keys are unique, i.e. no two references have the same author and date.
Deletions are allowed but are likely to be few for this application.
(10 marks)

b.This part is about binary search trees (Unit 4 Section 4 and Python activity 4.7) and relates to the professional skill of using data structures to solve computational problems. You need library file TMA02_Q2_BST.py, code file TMA02_Q2.py (which imports the library) and test file TMA02_Q2_tests.py from the TMA questions and guidance page.
i.Regardless of which data structure you preferred in part (a), implement a Bibliography ADT using a binary search tree. Implement functions addReference and removeReference in the code file. You may assume that all keys are unique. Copy the whole functions addReference and removeReference into your Solution Document.
(4 marks)

ii.To output the bibliography, you will need to traverse the tree. Do you need a preorder, inorder or postorder traversal? Justify your answer.
(2 marks)

iii.The function outputBibliography calls the helper function traverse, which should traverse the tree and return an ordered list of references, with a blank line between each reference and a space between the key and the value. Implement the function traverse. You may use the string operations listed in the Companion’s appendix. Copy the whole function traverse into your Solution Document.
(4 marks)

c.This part relates to the professional skill of applying computational thinking skills to solve a problem.
For this part you are not required to write any code.

Suppose now that there may be references with the same author and date.

For example, both these references can be added to the bibliography:

The Open University (2013) Logic and the Limits of Computing, Milton Keynes, The Open University.

The Open University (2013) Another Fascinating Booklet, Milton Keynes, The Open University.

Describe what changes, if any, you would need to make to functions addReference and removeReference (including their headers, if necessary) to deal with duplicate keys, i.e. duplicate author-date pairs. We are looking for a general understanding of the implications of allowing duplicate keys, not a worked solution.

(5 marks)

Question 3 (25 marks)
a.This question is about Graphs and their algorithms (Unit 5 Section 2 and the Companion). It relates to the professional skill of applying algorithms and data structures to practical problems. You need library file TMA02_Q3_Graph.py, code file TMA02_Q3.py and test file TMA02_Q3_tests.py from the TMA questions and guidance page.
Consider an unweighted undirected graph where the nodes represent people and the edges represent friendship relations, like this one with 2 separate groups of friends:

Social media companies may suggest new friends to a person by suggesting their friends’ friends. Alice would be suggested to befriend Xian, Yasmin and Zoe because those are the friends of Alice’s friends (Bob and Cleo). In a realistic graph, Alice has many friends, and so have each of her friends. Alice would get hundreds of suggestions.

Companies therefore score suggestions to only present the highest scoring ones. A simple score is the number of mutual friends. Xian’s and Zoe’s scores are both 1 because they have 1 mutual friend with Alice (Bob and Cleo, respectively). Yasmin has two mutual friends with Alice (Bob and Cleo) and so would be the top suggestion for Alice. The provided code file implements this approach: function friends_of_friends computes the friends of a person’s friends, common returns how many friends two people have in common, and suggested_friends uses the previous functions to rank the friends of friends.

i.Study the 3 provided files. Assuming a graph has n nodes and e edges, state and briefly justify the Big-O complexities of has_node, has_edge, nodes, edges, and common. State one complexity for each, because there is no difference between the best and worst case. Ignore the assertions. Take assignments as the basic unit of computation. For set and dictionary operations, use the complexities given in the Companion’s appendix.
(5 marks)

ii.The initial insight for the common function we provided can be written as follows, with mutual as the output:
Initialise mutual to zero. For each node in friendships, if that node has edges to person1 and to person2, then it is a mutual friend and so increment mutual.

Give an initial insight for a more efficient algorithm for common. You can only refer to operations provided in the Graph class or listed in the Companion’s appendix.

(2 marks)

iii.Explain why your algorithm is more efficient than ours for the typical case in which every person has some friends but is not friends with everyone else. You are not required to provide a Big-O analysis.
(2 marks)

iv.Rewrite the common function in the code file, following your insight in (ii).

1. You can only use the provided graph’s methods and any Python data structures and operations in the Companion’s appendix.

2. You may add comments and print statements to the Graph class for debugging purposes, but don’t change the class in any other way.

3. Run the test file. Your tutor will use different tests, so make sure your code solves the general problem, not just the problem instances (tests) that we provide. We recommend that you add your own tests to the test file.

4. Finally, copy the whole function into your Solution Document.

(3 marks)

v.A social media company wants to tell a user, when they look up the profile of another user, who to ask to be introduced to that person (if it’s possible). For example, if Zoe looks up Xian, she would see that she could ask Cleo to ask Alice to ask Bob to introduce Xian. If Zoe looks up Fran, she wouldn’t get any such information. Explain what graph algorithm you would adopt or adapt to solve this problem. Don’t write code. You are not restricted to the Graph class: you can use any graph algorithm in Unit 5.
(5 marks)

b.This part is about the algorithms and data structures in Units 3 to 5.
Training company TComp needs to hold information about the courses it offers, and which courses are pre-requisites for each other. Course X having pre-requisites A, B and C means that in order to do course X you should have completed courses A, B and C. Those pre-requisite courses may also have their own pre-requisites, and a course may be a pre-requisite for more than one other course.

When a customer applies for a place on a course, they complete an online application form, which is sent to a processing centre that processes applications in the order that they arrive. Courses have a limited number of places, so places are allocated to each course in the order the applications are received until the course is full. Any remaining applications are stored in case vacancies arise later.

State and briefly justify which abstract data types (ADTs) and how many instances of them you would need to represent:

i.the course descriptions and the links to their pre-requisites;
(5 marks)

ii.the applications submitted for places on the courses.
(3 marks)

State explicitly any assumptions you make. Describe the ADT with as much detail as possible, e.g. if you choose a sequence, state what are the items in the sequence, whether it is sorted or not, and if so by which criterion and whether in ascending or descending order.

Question 4 (25 marks)
This question is about spanning trees (Unit 5 Section 2.2.2), minimum spanning trees and Prim’s algorithm (Unit 5 Section 2.4) and assesses your skills in clear and succinct communication, which are required for the last question in the exam. Moreover, explaining a topic to others is a good way to consolidate one’s own learning.

Write a report that explains what the minimum spanning tree problem is and how it can be solved with Prim’s algorithm and Kruskal’s algorithm. Kruskal’s algorithm is not taught on M269 so you will need to find out about it yourself (remember you can use Library resources to do this e.g. Finding resources for your assignment). Your report must have this structure:

A suitable title.
An introductory paragraph explaining what a spanning tree is, then what a minimum spanning tree (MST) is, and the problem of finding it.
One or two paragraphs explaining how Prim’s algorithm solves the MST problem with an example.
One or two paragraphs explaining how Kruskal’s algorithm solves the MST problem with the same example, but showing how Kruskal’s algorithm arrives at this solution in a different way.
A concluding paragraph explaining what the greedy algorithm technique is and why these are examples of it.
A bibliography section with all sources that you consulted, apart from the M269 materials.
At the end of the report note the number of words that you used for points 1 to 5. Please aim for 700 words. If you find yourself writing more, you are probably not explaining clearly, and if you have written a lot less, you probably have not explained well enough.
You may create your own figures or use someone else’s, as long as you acknowledge them, to support your explanation and reduce the need for text. Figure captions and text in the figures count towards the word limit, i.e. select all your text and figures and apply your word processor’s word count tool.

The report is aimed at students of M269. Assume they have studied up to and including Unit 5, Section 2.2.1 i.e. they have just learnt about the graph data type.

Make sure that you explain everything in your own words. The OU uses software to detect text plagiarised from articles and web pages. Omitting or replacing some words, changing the order of sentences, or copying from multiple sources does not fool the software. Detected cases will be passed to the OU’s plagiarism team.

Before writing your first draft, you may wish to look back at TMA 01 Question 2: skim Joe’s report, your feedback to him, and your tutor’s feedback on your feedback. This will help you avoid making the same mistakes as Joe.

Your report will be marked against the following criteria:

a.Content (points 2 to 5): Is the explanation clear and complete? Will the reader understand Minimum Spanning Trees and the differences between Prim’s and Kruskal’s algorithms as a way to solve them? Will they understand how these are both examples of greedy algorithms?
(15 marks)

b.Writing (all points): Is the title descriptive? Does your report follow the structure above? Does it follow the Checklist with advice on writing and the OU Harvard guide to citing references (both in the TMA questions and guidance page)? Have you kept to the word limit?
(10 marks)

Note that the checklist mentioned is generic and not specific to this TMA. In particular, your report needs no headings other than the title.

After completing and revising your answers, up