complete unit 1.1

1 files changed, 63 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index 3e33b3f..6e1bcfe 100644
--- a/notes.md
+++ b/notes.md
@@ -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.