algorithms
Northeastern University CS5800 Algorithms, Spring 2024 Instructor: Hyonho Lee Assignment 7 (Total Marks: 50 pts) Due Date: April 1, 2024, 6pm Name: Student Number: Collaborators: I, , read and understood Northeastern University’s Academic Integrity Policy (https://osccr.sites.northeastern.edu/academic-integrity-policy/). 1. (25 pts) (Exercise 20.2-7) There are two types of professional wrestlers: “faces” (short for “babyfaces”, i.e., “good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may or may not be a rivalry. You are given the names of n professional wrestlers, V, and a list of r pairs of wrestlers, E, for which there are rivalries. Write a Python function, designate(V, E), that returns a pair of two lists: a list of faces and a list of heels if it is possible to designate them such that each rivalry is between a face and a heel. designate(V, E) should return None if it is impossible to designate faces and heels. Your algorithm should run in O(n + r) time. For example, if V is [‘The Rock’,‘Steve Austin’] and E is [(‘The Rock’,‘Steve Austin’)], then there are two wrestlers, The Rock and Steve Austin, and they are rivals with each other. In this case, we can designate The Rock as a face and Steve Austin as a heel. Hence, designate() should return ([‘The Rock’],[‘Steve Austin’]). Note that ([‘Steve Austin’],[‘The Rock’]) is also correct. If V is [‘The Rock’,‘Steve Austin’,‘Triple H’] and E is [(‘The Rock’,‘Steve Austin’), (‘The Rock’,‘Triple H’),(‘Steve Austin’,‘Triple H’)], then there are three wrestlers, The Rock, Steve Austin and Triple H, and they are all rivals with each other. In this case, we cannot designate them as faces and heels. If The Rock is a face and Steve Austin is a heel, then Triple H cannot be either a face or a heel, since Triple H is a rival with both The Rock and Steve Austin. Therefore, designate() should return None. 1 def designate(V, E): ## Write Your Code Here ## V = [‘The Rock’,‘Steve Austin’] E = [(‘The Rock’,‘Steve Austin’)] designate(V, E) # this should return ([‘The Rock’],[‘Steve Austin’]) or ([‘Steve Austin’],[‘The Rock’]). V = [‘The Rock’,‘Steve Austin’,‘Triple H’] E = [(‘The Rock’,‘Steve Austin’),(‘The Rock’,‘Triple H’),(‘Steve Austin’,‘Triple H’)] designate(V, E) # this should return None. 2. (25 pts) You are given a strange dictionary from an alien. All words still use alphabets, but the order of words is not alphabetical order. Your task is to write a Python function, alienDictionary(dict), which returns the correct order of characters in the alien language. An input, dict, is a list of words (strings), which represents the alien dictionary. For example, if an input is [‘bbc’,‘ba’,‘cb’,‘a’], then you can deduce that character b comes before character a (since bbc comes before ba), b comes before c (since ba comes before cb), and c comes before a (since cb comes before a). So, alienDictionary() should return [‘b’,‘c’,‘a’]. Assume that an input does not have conflict ordering. For example, if an input is [‘ab’,‘ba’,‘a’], then a is before b (since ab comes before ba), but b is also before a (since ba comes before a). In this case, we cannot find a correct ordering of alphabets. So [‘ab’,‘ba’,‘a’] is an invalid dictionary. Assume all inputs are valid. (You don’t have to check if an input is valid.) def alienDictionary(dict): ## Write Your Code Here ## alienDictionary([‘bbc’,‘ba’,‘cb’,‘a’]) # returns [‘b’,‘c’,‘a’]. alienDictionary([‘baa’,‘abcd’,‘abca’,‘cab’,‘cad’]) # returns [‘b’,‘d’,‘a’,‘c’] 2 Practice Exercises (The following questions will not be graded. Do not submit solutions. But similar questions may appear in the exams.) Exercise 20.1-5 (22.1-5 of the 3rd Ed.) Exercise 20.2-6 (22.2-6 of the 3rd Ed.) Exercise 20.2-8 (22.2-8 of the 3rd Ed.) Exercise 20.3-2 (22.3-2 of the 3rd Ed.) Exercise 20.3-6 (22.3-7 of the 3rd Ed.) Exercise 20.3-9 (22.3-10 of the 3rd Ed.) Exercise 20.3-12 (22.3-12 of the 3rd Ed.) Exercise 20.4-2 (22.4-2 of the 3rd Ed.) Exercise 20.4-3 (22.4-3 of the 3rd Ed.) Exercise 20.4-5 (22.4-5 of the 3rd Ed.) Problem 20-2 (22-2 of the 3rd Ed.) Problem 20-3 (22-3 of the 3rd Ed.) Problem 20-4 (22-4 of the 3rd Ed.) 3
Collepals.com Plagiarism Free Papers
Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.
Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS
Why Hire Collepals.com writers to do your paper?
Quality- We are experienced and have access to ample research materials.
We write plagiarism Free Content
Confidential- We never share or sell your personal information to third parties.
Support-Chat with us today! We are always waiting to answer all your questions.
