diff options
| -rw-r--r-- | notes.md | 63 |
1 files changed, 63 insertions, 0 deletions
@@ -4,3 +4,66 @@ * Classic data structures * Algorithmic Thinking * Sorting & trees + + +A data structure is a way to store and organize data in order to facilitate +access and modifications. No single data structure works well for all purposes, +and so it is important to know the strengths and limitations of several of them. + +Hard problems: There are some problems, however, for which no efficient solution +is known. These are known as NP-complete problems. + +NP-complete problems are interesting because an efficient algorithm hasn't been +found and nobody has proven that an efficient algorithm cannot exist. + +Np-complete is like god. Nobody knows if an efficient solutions exists or not. + +Also, if an efficient algorithm can be found for one NP-complete problem then an +efficient algorithm must exist for all of them. + +If you can show that a problem is NP-complete, you can instead spend your time +developing an efficient algorithm that gives a good, but not the best possible, +solution. + +The "traveling-salesman problem" is an NP-complete problem. So any solution is +good enough because an efficient solution has not been found yet. + +In order to elicit the best performance from multicore computers, we need to +design algorithms with parallelism in mind. Multithreaded algorithms exist to +take advantage of multiple cores. Championship chess programs use this. + + +1.1-1: Give a real-world example that requires sorting or a real-world example that +requires computing a convex hull. + + Names in an address book. + +1.1-2: Other than speed, what other measures of efficiency might one use in a +real-world setting? + + The amount of space required. + +1.1-3: Select a data structure that you have seen previously, and discuss its strengths and limitations. + + Balanced binary search trees are excellent for finding data quickly but a + bit complicated when it comes to trying to keep it balanced efficiently. + +1.1-4: How are the shortest-path and traveling-salesman problems given above similar? How are they different? + + The shortest path problem is looking for an efficient solution that routes + from point A to point B. The traveling-salesman problem is similar except + that the sales person needs to visit multiple locations then return to the + starting point in the most efficient way. These problems are similar because + the shortest path from point A to B can be used to help determine a good + enough solution for the traveling-salesman problem. + + Both of these problems are considered an NP-complete problems because it + hasn't been proven if an efficient algorithm can or cannot exist. + +1.1-5: Come up with a real-world problem in which only the best solution will do. + Then come up with one in which a solution that is "approximately" the best is good enough. + + * Traveling to Mars. Humans have a finite amount of time to live so choosing + a point in time to travel that doesn't align with orbital conditions might + make it impossible for humans to survie the trip. + * Driving directions from point A to B. |