Algorithm, Class Notes

[Algo] Introduction

“Eventhough you only see me, behind me is the whole team”

Text:

  • Algorithm Design, John Kleigberg. “Beautifully written book”, stated the professor. This is the main book that will be used throughout.
  • Introduction to Analysis of Algorithm 3rd ed by Cormen and the other 3 author never get mentioned their name🙂

Student’s responsibilities :

  • Attend lecture
  • Study material from the textbook. Student should skim the textbook’s chapter before the class’ session to get a feel. Doing it otherwise would introduce boredness during class because class’s material would feel repetitive. Hmm, good idea🙂
  • Do Homework problem as many as you can.

Grade:

  • Exam 1 ( 30% ) on Feb 19th
  • Exam 2 ( 30% ) on Apr 1st
  • Exam 3 ( 40% ) on Apr 29th

It totals to 100%. So what is the purpose of doing homework. Doing homework you will get feedback from the grader, TA. Feedback is important. It will help you become a better student.

Prerequisite:

  • Discreet mathematics – introduction of some sort.
  • Asymptotic notation, specifically , big O.
  • Basic data structure : array, link list, stack, queue.
  • Sorting methods.
  • Graph basic : trees, cycles, DAG, adjacency list/matrix.
  • Graph search : BFS, DFS

In this course, we will be touching the following area:

  1. Major Algorithm technique ( Exam 1 )
    • Greedy
    • Divide & Conquer
    • Dynamic programming
  2. Network flow( Exam 2 )
  3. NP, NP Complete, NP Hard.
  4. Approximate methods
  5. Linear programming

[3->5 : Exam 3]

So why should we study algorithm? Because algorithms are taking over the world.

What makes Algorithm successful ?

Correct result

Speed/Performance : Hardware & Software => SMP, DMP, Memory Hierarchy

Our approach to designing an algorithm is the followings:

  1. Come up with a concise problem statement : what is it that we are trying to solve. Discreet set notation helps with the logic.
  2. Present solution : steps of the algorithm
  3. Prove correctness : Prove that the algorithm works : contradiction, induction, etc
  4. Complexity analysis : We are only interested in the worse case.

Let’s look at the problem of stable matching. We have to match pair of woman and man from the group of people, respectively.

1.  Problem statement :

We have the two set of interests :

set of M(en)       = { m1, m2, … , mn }

– – —-W(omen) = { w1, w2, … , wn }

We have to find ( mi, wj ). In other word, find matching of S in a set of ordered pair

Definition : A perfect matching S is a matching that each member of M and member of W appear in exactly one pair in S’. So [S]( mi, wj ) = ( wj, mi ) [S’]

Preference list : m of M ranks all women : w > w’. Pmi = { Wi1, Wi2, … , Win }. The same is for women’s

But say we have matched (m,w), (m’,w’). What if m prefer w’ to w ? Is ( m’, w’ ) at risk ? ( divorce ? ) . Not necessarily => (m, w’) = instability w.r.t. S ( w’ must be content w/ m too — mutual preference must work here )

* Conclusion : S is stable if

  1. It is perfect
  2. No instability w.r.t S

2. Gale-Shapley Algorithm

3. Proof of correctness.

a. In w’s perspective, she starts single; once she gets engaged, she can only get into better engagement ( m’ propose and m’ > m )

b. In m’s perspective, he starts single; once he gets engaged, he might be dropped repeatedly only to a lower ranking woman.

c. Algorithm terminates after n^2 iteration

d. Solution is perfect matching and stable

 

Proof : Assume instability exists in our solution involving 2 pair (m,w), (m’,w’)

Question : Did m propose to w’ at some point ? If no, then W must be higher than w’ => contradiction ( because he will always pick the w with a highest preference which is currently w ). If yes. he must’ve been rejected in favor of m” ( in w’ perspective, m” > m ) and due to (3.a) m” = m’ or m’ is better than m” => contradiction . We ended up with the following pairs:

(m,w) , (m’,w’) : men propose

(m,w’), (m’, w) : women propose .

Regardless, it will become stable.

4. Complexity Analysis

  1. Identify Freeman . O(1)
  2. For a man m, identify the highest ranking woman to whom he has not yet proposed. O (1)
  3. For a woman w, decide if w is engaged , if so , to whom ? O(1)
  4. For a woman w and two men m & l, decide which man is preferred by w.
  5. Place a man back in the list of free men ( m or l ).

Note : 2 late chinese women sitting next to me watching chinese movie or sth laughing and joking in chinese the whole time. Pssst.

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s