nstructions

Part $1$: After a grueling algorithms midterm, you decide to take the bus home. Since you like to plan ahead, you have a schedule that lists the times and locations of every stop of every bus in your city. Your city is currently suffering from a plague of zombies, so even though the bus stops have fences that supposedly keep the zombies out, you$$d still like to spend as little time waiting at bus stops as possible. Unfortunately, there isn$$t a single bus that visits both your exam building and your home so you must transfer between buses at least once. You decide the best approach is to implement a variation of the Dijkstra$$s algorithm for finding the shortest path home from the campus.

Describe and analyze an algorithm to determine a sequence of bus rides from the campus to your home, that minimizes the total time you spend waiting at bus stops. You can assume that there are b different bus lines, and each bus stops n times per day. Assume that the buses run exactly on schedule, that you have an accurate watch, and that walking between bus stops is too dangerous to even contemplate.

Implement your solution in a programming language of your choice.

Part $2$: The Quick Sort algorithm is a divide and conquer, recursive algorithm that takes a slightly different approach. You begin by taking the last element in the list and call that the pivot. Everything that$$s smaller than the pivot gets put into a $$left$$ list and everything that$$s greater gets put in a $$right$$ list. You then call quick sort on the left and right lists independently $($hence the recursion.$)$ After those two sorts come back, you concatenate the sorted left list, the pivot, and then the right list $($in that order.$)$ The base case is when you have a list of length $1$ or $0,$ where you just return the list given to you. Write a program to sort elements of an array using Quick Sort. Use recursion in your solution. Ideally, the program should be written in C but you can use any programming language of your choice.

Part $3$: The Merge Sort algorithm works by recursively dividing the input array into two halves until each half contains only one element or is empty. Then, it merges the sorted subarrays back together to produce the final sorted array. Write a program to sort elements of an array using Merge Sort. Use recursion in your solution.