Differences

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

--- courses:cs211:winter2018:journals:donohuem:home [2018/01/16 19:05] – donohuem
+++ courses:cs211:winter2018:journals:donohuem:home [2018/04/02 13:56] (current) – donohuem
@@ Line 1: / Line 1: @@
 ====== Mark's Wiki ======
   * [[preface|Preface: First two pages]]
+  * [[chapter1|Chapter 1: Section 1.1]]
-====== Week 1 ======
+  * [[chapter2|Chapter 2: Sections 2.1-2.5]]
+  * [[chapter3|Chapter 3: Sections 3.1-3.6]]
-===== Preface =====
+  * [[chapter4|Chapter 4: Sections 4.1, 4.2, 4.4-4.8]]
-The authors begin by stating the prevalence of algorithms and algorithmic ideas across a variety of fields, including biology, economics, and, most importantly, computer science. Although not exclusive to computer science, algorithmic problems form the heart of this field of study. Additionally, the authors explain that this core of computer science can be divided into **two fundamental components**: understanding the pure mathematics of a problem, and then, based on the problem, choosing the best algorithmic design for solving this problem. Finally, the authors state the objective of the book. They wish to teach not only the raw logistics of an algorithm, but also the motivations and basic design principles behind every algorithm and problem. On a scale of 1 to 10, I would give this section a 6 in terms of readability.
+  * [[chapter5|Chapter 5: Sections 5.1-5.3]]
+  * [[chapter6|Chapter 6: Sections 6.1-6.3]]
-===== Chapter 1.1 =====
+  * [[chapter7|Chapter 7: Sections 7.1-7.2, 7.5, 7.7]]
-Section 1.1 begins with an introduction of the **Stable Matching Problem**. The motivation behind this problem is to create a **self-enforcing** matching process, where the self interests of two given parties prevent matched pairs from being retracted and redirected. The authors explain this problem through the context of applicants seeking summer internships with certain employers. Given E employers and A applicants, as well as a list of preferences for each party, the goal of the problems is that either:
-  * E prefers every one of its accepted applicants A; or
-  * A prefers his/her current situation over working for employer E.
-If these two conditions hold, then the outcome is stable. Later, the authors switch the context of the problem from employers and applicants to men and women, where, given n men and n women, we must create a stable, perfect matching for every set of preference lists among the men and women. To do this, we utilize the Gale-Shapley algorithm:
-     set every couple to be unmatched
-     while some man is free and has not proposed to every woman:
-          choose man m
-          w = woman of highest order preference on man m's list and has not been proposed to yet
-          if w is free:
-               match m and w
-          elif w prefers m over currently matched m'
-               match m and w and free m'
-          else
-               w rejects m
-Some observations of this algorithm are that a womans' partner increases (in terms of her preferences) over time, and that mens' partners decrease over time. Additionally, once a woman has been matched, she can no longer be unmatched, whereas a man can.