Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:garrett:entries:week_8 [2012/03/13 23:44] – created garrettheath4
+++ courses:cs211:winter2012:journals:garrett:entries:week_8 [2012/03/14 03:27] (current) – added section 5.5 garrettheath4
@@ Line 2: / Line 2: @@
 ===== Chapter Scores =====
-  * **Readability Score**: FIXME
+  * **Readability Score**: 4 / 10 {{:courses:cs211:winter2012:journals:garrett:entries:rating_2.png?100|}}
-  * **Interest Score**: FIXME
+  * **Interest Score**: 7 / 10 {{:courses:cs211:winter2012:journals:garrett:entries:rating_3_5.png?100|}}
 ===== Readings =====
@@ Line 16: / Line 16: @@
 {{:courses:cs211:winter2012:journals:garrett:entries:journal_8_-_algorithm_1.png?500|}}
-This algorithm, however, is inefficient because it is {{:courses:cs211:winter2012:journals:garrett:entries:bigo-n-squared.png?40|}}
+This algorithm, however, is inefficient because it is {{:courses:cs211:winter2012:journals:garrett:entries:bigo-n-squared.png?38|}}.  An optimization can be found with a **divide and conquer algorithm** in which we divide the plane in half and recursively find the closest pair of points.  In this algorithm, a problem with boundary cases of points near the dividing line quickly arises but is squelched when we realize that points beyond a distance of half of the smallest distance so far don't have to be examined.
 === 5.5: Integer Multiplication ===
+**Problem:** Given an ''n''-digit number ''A'' and an ''n''-digit number ''B'', find the product ''A x B''.
+The initial solution to this problem is obvious:\\
+{{:courses:cs211:winter2012:journals:garrett:entries:journal_8_-_algorithm_2.png?500|}}
+Naturally, this algorithm is inefficient because its nested ''for'' loop makes it {{:courses:cs211:winter2012:journals:garrett:entries:bigo-n-squared.png?38|}}.  By using a divide and conquer algorithm, we can divide up the problem and remove unnecessary operations to discover an algorithm that is {{:courses:cs211:winter2012:journals:garrett:entries:bigo-n-1-59.png?55|}}.
 ~~DISCUSSION~~