[SOLVED] Csci 3104 assignment 1

Question 1 : Everyday Algorithms.

Write down a ten sentence description of an algorithm that drives an important piece of technology that you encounter in your every day life. Research on the Internet to find out what sort of algorithms can solve the core problem behind the technology and how it works.

Examples:

1. Auto-complete feature when typing text messages on my iphone,
2. My email service automatically tags dates/times so that I could insert them in my calendar, or
3. My python IDE automatically takes me to a function’s code from a call site.

YOUR ANSWER HERE

Question 2(a): Insert into a sorted array.

Write a python3 function insert_into(a, j) that given sorted array a and a number j, returns a new array that includes the contents of the original array and the newly inserted element j, so that the returned array is also sorted.

You are not allowed to use inbuilt routines in python such as sort. You should also avoid using the list insert method.

# Answer 2(a): IMPLEMENT HERE. Each time you edit, do not forget to type shift+enter
def insert_into(a, j):
    
    # YOUR CODE HERE
    raise NotImplementedError()


# Press Shift enter when you are done with your code

Question 2(b): Running time of your insertion routine

For an input of size nn, how much time does your routine take to run in the worst case? You can use big-theta notation ΘΘ for your answer.

YOUR ANSWER HERE

Question 3: Tournaments

A tennis tournament has nn participants who must play matches in rounds to determine a winner. For instance if n=100n=100, then the first round has 5050 matches, the second round has 2525 matches and so on. If the number of players left in a round is odd, then one lucky player is chosen at random to move to the next round without contest.

Do not use asymptotic (O,Ω,ΘO,Ω,Θ) notations in your answer below. Provide exact numbers as much as possible.

1. Write down a formula involving nn for the total number of rounds played? (Hint: You should try some values for nn, before you attempt to derive a formula ).
2. Show that the total number of matches played cannot exceed nn. (Hint: write down a series summation for the total number of matches played and use known facts about summation of geometric series ).
3. How many matches does the overall winner need to play in the best case?
4. How many matches does the overall winner need to play in the worst case?
5. Assume that every player has a unique hidden talent score so that for any match, the higher talent score is always going to win. Is the winner always guaranteed to be the highest talent score? Is the runner up (i.e, the person who lost to the winner in the final match) always the second highest talent score? If your answer is no, illustrate using a counter-example.
6. From the answer in 5. design a scheme to identify the second highest talent score among the nn participants. Your scheme may select some players and schedule extra matches. (Hint: Look up the term repechage in olympics sports)

YOUR ANSWER HERE

Autograder for quesion 2(a): Do not edit code below.

## DO NOT EDIT TESTING CODE FOR YOUR ANSWER ABOVE
# Press shift enter to test your code. Ensure that your code has been saved first by pressing shift+enter on the previous cell.
from IPython.core.display import display, HTML
def test_insert():
    failed = False
    test_cases = [ # (Input Array, Inserted Number, Expected Output)
             ([1,3,6,8,10], 4 , [1,3,4,6,8,10]),
             ([1,1,1,1,3,3,5,5,7,7], 1, [1,1,1,1,1,3,3,5,5,7,7]),
             ([-10,9,15,18,35,44], 47, [-10, 9, 15, 18, 35, 44, 47]),
             ([], 10, [10]),
             ([-10, 9, 10, 20, 35], -20, [-20, -10, 9, 10, 20, 35]),
             ([0,0,0,0,0,0], 0, [0,0,0,0,0,0,0])]
    for (test_array, j, expected_output) in test_cases:
        obtained_output = insert_into(test_array, j)
        if obtained_output != expected_output:
            s1 = '<font color="red"> Failed - test case: Inputs: a=' + str(test_array)+ ' j=' + str(j)
            s2 = '  <b> Expected Output: </b> ' + str(expected_output) + ' Your code output: ' + str(obtained_output) + ' </font>'
            display(HTML(s1+s2))
            failed = True
            
    if failed:
        display(HTML('<font color="red"> One or more tests failed. </font>'))
    else:
        display(HTML('<font color="green"> All tests succeeded! </font>'))
test_insert()