Algorithm Assignment: Insertion Sort, Quicksort, and Queues

Create a Word document (or something else of your choice). Answer the following questions. Make a PDF with your answers. Cite any sources you use to answer questions.

1. Why would anyone ever use Insertion Sort? We know Quicksort and Mergesort are faster. Explain why Insertion Sort could be of practical use to a programmer.

2. The quicksort parition we looked at used the last element in the range as the pivot. We also talked about using a random element as the pivot.
a. What if we used the average of all the numbers in the range as the pivot?
b. Would it always divide in half giving a Theta(n log2(n)) algorithm or would we still have a worst case of Theta(n^2) algorithm?
c. Give an argument for which you think is correct. Make sure to use examples in your argument.

3. The quicksort parition we looked at used the last element in the range as the pivot. We also talked about using a random element as the pivot.
a. What if we actually found the exact middle element to use as the partition? We would always divide exactly in half.
b. Would this improve the time for quicksort or would finding the middle element take so long it would slow quicksort down? Explain your argument.

4. You work at a company that makes specialized security briefcases. You need to test a new model to see how many floors up it can be dropped from and not smash. Assume the test is boolean (Yes/No). Either the case breaks enough someone can get the contents or they cannot access the contents.
a. Give a building with N floors, come up with an Algorithm to find the lowest floor the briefcase smashes from. Your goal is to optimize the number of tests. Come up with an algorithm that throws as few briefcases as possible.

b. You only need to describe how the algorithm works, you may use pseudocode or plain English.

5. Nuts and Bolts by G. J. E. Rawlins You have a mixed pile of N nuts and N bolts and need to quickly find the corresponding pairs of nuts and bolts. Each nut matches exactly one bolt, and each bolt matches exactly one nut. By fitting a nut and bolt together, you can see which is bigger, but it is not possible to directly compare two nuts or two bolts.
a. Give a Theta(n log n) method for solving the problem. You only need to describe how the algorithm works, you may use pseudocode or plain English. You may not compare nuts to each other. You may not compare bolts to each other.

The goal of this assignment is to implement and use a queue. You will implement the queue using nodes and pointers. This is a specialized version of a linked list.

Read more about

queues: https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm

Part 2a: queue.h, queue.c, queue_tests.c

Create and implement a Queue Data Structure. Implement the following methods. You must use the Node Struct from lecture.

You should make your own tests to make sure everything works correctly.

Part 2b: josephus.c (25 points)

This question is from Algorithms, 4th Edition by Sedgewick and Wayne.

In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to N-1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated.

Use your Queue to solve this problem. Write a program josephus.c that takes to command line argument N and M. Your program will print out the order in which people are eliminated (and thus would show Josephus where to sit in the circle). You must use your Queue from the previous part to solve this problem.