Requirement that code should be written in C

Problem Four: Finding Cities What city are you closest to right now? What are the ten closest cities to you? The fifty closest cities? Even if you know your area pretty well, you might not be able to answer these questions purely off the top of your head. Let's imagine that you have a list of all the cities in your area. Each city is tagged with its location, which you can imagine is a point in the 2D plane. (We'll pretend that the world is flat at least in a small neigh- borhood around your location. Thanks multivariable calculus.) You also have your own (x, y) location Design a algorithm that, given a list of n cities and some number k returns a list of the k cities that are closest to you. sorted by increasing order of distance. Your algorithm should run in time O(n + k log k). Then prove your algorithm meets the required time bounds. Some specific details and edge cases to watch for. You can assume for simplicity, that no two cities are at the same distance from you. By "distance" we mean Euclidean distance. We're already assuming the world is flat, so while we're at it seems pretty reasonable to also ignore things like roads and speed limits. As a hint, think about the algorithms you studied in CS1B and see if any of them would make for good subroutines. To make things easier for me to grade. I recommend doing the following when writing up your solution: 1. Start off by giving a quick two-sentence, high-level description of your approach. This makes it easier for me to contextualize what it is that you're trying to do. 2. Next, go into more detail. Describe how your algorithm works, one step at a time. Please don't write actual code unless it would be nearly impossible to describe the algortihm in plain English (Trust me - from experience reading code is often much harder than reading prose!) 3. Write a runtime analysis. Go at whatever level of detail seems most appropriate. A note on this problem, and other problems going forward: when measuring runtime in the context of al- gorithms and data structures, it's important to distinguish between deterministic and randomized algo- rithms. There's a lot of research into how to take randomized algorithms with a nice expected runtime and convert them into deterministic algorithms with a nice worst-case runtime. Since this is designed as a warm-up. I will accept either a deterministic algorithm with a worst-case runtime of O(n = k log k) or a randomized algorithm with an expected runtime of O(n + k log k), though in the future I will tend to be a bit stricter about avoiding randomness. Problem Four: Finding Cities What city are you closest to right now? What are the ten closest cities to you? The fifty closest cities? Even if you know your area pretty well, you might not be able to answer these questions purely off the top of your head. Let's imagine that you have a list of all the cities in your area. Each city is tagged with its location, which you can imagine is a point in the 2D plane. (We'll pretend that the world is flat at least in a small neigh- borhood around your location. Thanks multivariable calculus.) You also have your own (x, y) location Design a algorithm that, given a list of n cities and some number k returns a list of the k cities that are closest to you. sorted by increasing order of distance. Your algorithm should run in time O(n + k log k). Then prove your algorithm meets the required time bounds. Some specific details and edge cases to watch for. You can assume for simplicity, that no two cities are at the same distance from you. By "distance" we mean Euclidean distance. We're already assuming the world is flat, so while we're at it seems pretty reasonable to also ignore things like roads and speed limits. As a hint, think about the algorithms you studied in CS1B and see if any of them would make for good subroutines. To make things easier for me to grade. I recommend doing the following when writing up your solution: 1. Start off by giving a quick two-sentence, high-level description of your approach. This makes it easier for me to contextualize what it is that you're trying to do. 2. Next, go into more detail. Describe how your algorithm works, one step at a time. Please don't write actual code unless it would be nearly impossible to describe the algortihm in plain English (Trust me - from experience reading code is often much harder than reading prose!) 3. Write a runtime analysis. Go at whatever level of detail seems most appropriate. A note on this problem, and other problems going forward: when measuring runtime in the context of al- gorithms and data structures, it's important to distinguish between deterministic and randomized algo- rithms. There's a lot of research into how to take randomized algorithms with a nice expected runtime and convert them into deterministic algorithms with a nice worst-case runtime. Since this is designed as a warm-up. I will accept either a deterministic algorithm with a worst-case runtime of O(n = k log k) or a randomized algorithm with an expected runtime of O(n + k log k), though in the future I will tend to be a bit stricter about avoiding randomness