avatarJen-Hsuan Hsieh (Sean)

Free AI web copilot to create summaries, insights and extended knowledge, download it at here

7131

Abstract

ned"> </div> </div> </figure></iframe></div></div></figure><h2 id="3cb7">Quick find vs Quick union</h2> <figure id="81cb"> <div> <div>

            <iframe class="gist-iframe" src="/gist/JenHsuan/e0416d659cd7e4722b51e7816a2fc617.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h1 id="819c">4. Improvement for quick union 1: weighting</h1><h2 id="b148">Purpose</h2><ul><li>Avoid tall trees</li><li>Keep track of size of each tree (number of objects)</li><li>Balance by linking root of smaller tree to root of larger tree</li></ul><figure id="cc4d"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*WxurvrMoL9qRzcJz-Yl2jg.png"><figcaption></figcaption></figure><h2 id="3f49">Proposition</h2><p id="1ffc">Depth of any node x is at most <code>log N</code></p><h2 id="4ad0">Why?</h2><ul><li>The depth of x increase <code>1/the size of the tree</code> at least doubles when tree T1 containing x is merged into another tree T2</li><li>The size of tree containing x can double at most <code>log N</code> times</li></ul><h2 id="1fce">Java implementation</h2><ul><li>link root of smaller tree to root of larger tree</li><li>update the <code>sz[]</code> array</li></ul>
    <figure id="11de">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/b73a5dbe48335c8f3cfbbcbf2a1ad372.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h2 id="8962">Proposition of Quick find, Quick union, and weighted quick-union</h2>
    <figure id="8f84">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/f2f34d7150b5cea03a54aa4fdbdac808.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h1 id="bdd4">5. Improvement for quick union 2: path compression</h1><h2 id="1041">Purpose</h2><ul><li>Flatten the tree</li><li>Just after computing the root of <code>p</code>, set the id of each examined node to point to that root</li></ul><figure id="4888"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*hXW_ji5Q8yXUfY_-k2tNKQ.png"><figcaption></figcaption></figure><h2 id="502e">Java implementation</h2>
    <figure id="3aa2">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/7731ec26bf5836ef8ed0e460eebde519.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h2 id="a59c">Proposition: Bottom line</h2><p id="4870">WQUPC reduces from 30 years to 6 seconds.</p>
    <figure id="8604">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/7615f343f19895d52a6186dd0113b710.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h1 id="844d">Related Leetcode questions</h1><ul><li><a href="https://leetcode.com/problems/two-sum/">2 sum</a> (easy)</li><li>3 sum</li><li><a href="https://leetcode.com/problems/binary-search/">binary search</a> (easy)</li><li><a href="https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/">Least common ancestor</a> (medium)</li><li><a href="https://leetcode.com/problems/redundant-connection/description/">Redundant Connection</a> (medium)</li><li><a href="https://leetcode.com/problems/number-of-operations-to-make-network-connected/">Number of Operations to Make Network Connected</a> (medium)</li></ul><h1 id="1cba">Week 1 Programming Assignment: Percolation</h1><p id="d0c3">It’s called percolation if the opened sited were connected from the top to the bottom. So what’s the probability? (The numbers of opened sites/The numbers of total sites)</p><h2 id="dfc2">Requirements in detail</h2><div id="1a9e" class="link-block">
      <a href="https://coursera.cs.princeton.edu/algs4/assignments/percolation/specification.php">
        <div>
          <div>
            <h2>Programming Assignment 1: Percolation</h2>
            <div><h3>Write a program to estimate the value of the percolation threshold via Monte Carlo simulation. Install our Java…</h3></div>
            <div><p>coursera.cs.princeton.edu</p></div>
          </div>
          <div>
            <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*gFanhnEHAvPEq8NH)"></div>
          </div>
        </div>
      </a>
    </div><h2 id="8697">Solutions</h2><ul><li>Percolation.java</li></ul>
    <figure id="b4fb">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/6af62f46d7d976c0162451c5d84629ca.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><ul><li>PercolationStats.java</li></ul>
    <figure id="d1bc">
        <div>
          <div>
            
            <iframe class="gist-iframe" src="/gist/JenHsuan/9a4ea791a5f5f4f605d0fe9f8e3fb90e.js" allowfullscreen="" frameborder="0" height="undefined" width="undefined">
          </div>
        </div>
    </figure></iframe></div></div></figure><h2 id="1aba">Grades</h2><figure id="2fcf"><img src="https://cdn-images-1.readmedium.com/v2/resize:fit:800/1*xPoj48U0tPeH_QoB_XcJQg.png"><figcaption></figcaption></figure><h1 id="41ef">References</h1><ul><li><a href="https://algs4.cs.princeton.edu/code/">Java Algorithms and Clients</a></li><li><a href="https://blog.csdn.net/haronchou/article/details/113752047">普林斯顿算法 — — week1 作业一 percolation</a></li><li><a href="https://blog.csdn.net/simon_world/article/details/40249827">CheckStyle报错的常见问题及解决方式</a></li><li><a href="https://github.com/allegoricalJest/coursera-percolation">allegoricalJest/coursera-percolation</a></li><li><a href="https://stackoverflow.com/questions/2387656/what-is-olog-n">What is O(log* N)?</a></li><li><a href="https://github.com/ybruce61414">ybruce61414</a> / <a href="https://github.com/ybruce61414/LeetCode"><b>LeetCode</b></a></li></ul><h1 id="16b6">Summary</h1><p id="67b1"><i>Thanks for your patient. I am <a href="https://www.linkedin.com/in/jen-hsuan-hsieh-6a13347a/">Sean</a>. I work as a software engineer.</i></p><p id="95c5"><i>This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.</i></p><ul><li>Subscribe me</li></ul><div id="00b7" class="link-block">
      <a href="https://medium.com/@seanhsieh_63050/membership">
        <div>
          <div>

Options

<h2>Join Medium with my referral link — Jen-Hsuan Hsieh (Sean)</h2> <div><h3>As a Medium member, a portion of your membership fee goes to writers you read, and you get full access to every story…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*HotGzJ9QwFkeUJCo)"></div> </div> </div> </a> </div><ul><li>The Facebook page for articles</li></ul><div id="633c" class="link-block"> <a href="https://www.facebook.com/imalayman"> <div> <div> <h2>A Layman</h2> <div><h3>A Layman. 81 likes. The page sharing the information about programming languages, algorithm, databases, devops and…</h3></div> <div><p>www.facebook.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*7t8weBH0eq-il9Lq)"></div> </div> </div> </a> </div><ul><li>The latest side project: Daily Learning</li></ul><div id="af2a" class="link-block"> <a href="https://daily-learning.herokuapp.com/"> <div> <div> <h2>ALayman Daily Learning</h2> <div><h3>Daily learning provides articles, challenges, or videos to people who are also self-learner for programming.</h3></div> <div><p>daily-learning.herokuapp.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/0*7820hJWu4Uq6b1eH)"></div> </div> </div> </a> </div><h1 id="e3cf">Related topics</h1><p id="0421">How to use the two-way binding in Knout.js and ReactJS?</p><div id="bb06" class="link-block"> <a href="https://readmedium.com/how-to-use-the-two-way-binding-in-knout-js-and-reactjs-afea126d0236"> <div> <div> <h2>How to use the two-way binding in Knout.js and ReactJS?</h2> <div><h3>Components built by different frameworks must have the same action in one website. What we have to realize is how to…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*SK9-uglh85Hl4wAh3OHQ_g.png)"></div> </div> </div> </a> </div><p id="7d15">Learn how to use SignalR to build a chatroom application</p><div id="ebac" class="link-block"> <a href="https://readmedium.com/learn-how-to-use-signalr-to-build-a-chatroom-application-63e8bb8049ff"> <div> <div> <h2>Learn how to use SignalR to build a chatroom application</h2> <div><h3>The Introduction of SignalR</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*j6m4jnkuRKkQ6rrkqLFeGA.png)"></div> </div> </div> </a> </div><p id="6252">My reflection of <effective sql="">:</effective></p><div id="a401" class="link-block"> <a href="https://readmedium.com/how-to-design-the-data-model-my-reflection-of-effective-sql-adba6376588a"> <div> <div> <h2>How To Design The Data Model? — My reflection of <effective sql=""></effective></h2> <div><h3><effective 61="" sql:="" specific="" ways="" to="" write="" better="" sql=""> gave me many tips for using the database.</effective></h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*trYud-lAkP2-bXo82U9bQA.png)"></div> </div> </div> </a> </div><div id="249d" class="link-block"> <a href="https://readmedium.com/how-to-design-the-index-my-reflection-of-effective-sql-b23d24212974"> <div> <div> <h2>How To Design The Index? — My reflection of <effective sql=""></effective></h2> <div><h3><effective 61="" sql:="" specific="" ways="" to="" write="" better="" sql=""> gave me many tips for using the database.</effective></h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*l4nVJqhrI1_sFMy2zQ8N0w.png)"></div> </div> </div> </a> </div><div id="6af9" class="link-block"> <a href="https://readmedium.com/whats-if-we-can-t-change-the-design-my-reflection-of-effective-sql-3704b87c49b5"> <div> <div> <h2>What if we can’t change the design? — My reflection of <effective sql=""> Part 3</effective></h2> <div><h3><effective 61="" sql:="" specific="" ways="" to="" write="" better="" sql=""> gave me many tips for using the database.</effective></h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*jqUMxB_afM-552DjqBo3gA.png)"></div> </div> </div> </a> </div><p id="75de">IT &amp; Network:</p><div id="79e8" class="link-block"> <a href="https://readmedium.com/back-to-the-basic-introduction-to-dns-f63aebe7bee7"> <div> <div> <h2>Back to the basic: Introduction to DNS</h2> <div><h3>I decided to back to the basic and enhance these bits of knowledge. I also expect that this article can help someone…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*m4nxtUjDkrX9lClzHnnboA.png)"></div> </div> </div> </a> </div><p id="e02d">Database:</p><div id="74a6" class="link-block"> <a href="https://readmedium.com/learning-sql-server-part-1-locking-in-sql-server-807f79cbe9dd"> <div> <div> <h2>Learning SQL server part.1 — lock and concurrency in SQL server</h2> <div><h3>Even though I used the SQL server for a long time, I didn’t know it very well. However, I received an alert with the…</h3></div> <div><p>medium.com</p></div> </div> <div> <div style="background-image: url(https://miro.readmedium.com/v2/resize:fit:320/1*f4tAhp00tEK51-KU73J5Yw.png)"></div> </div> </div> </a> </div></article></body>

Algorithms, Part 1 Course from Princeton — Union-find and Week 1 assignment Percolation

Introduction

Algorithms, Part 1 is a solid course for IT or software engineers to learn algorithms which are provided by Princeton. Of course, we still have to take time to clarify the concepts after completing the class.

Union-Find is a data structure for recording whether points are in the same set. In this article, we will focus on Union-find and its improvements algorithms.

About this Series

This series aims to wrap up contents of Algorithms, Part 1.

Agenda

It includes the following topics in this article.

1. Analysis of algorithms

Example — 2 sum

Approximately how many array accesses as a function of input size N?

Bottom line: use cost model and tilde notation to simplify counts

Simplification 1: cost model

Use some basic operation as a proxy for running time

Simplification 2: tilde notation

  • Estimate running time (or memory) as a function of input size N
  • Ignore lower order terms - When N is large, terms are negligible - When N is small, we don’t care

Common math formulas

  • 1 + 2 + ... + N = 1/2 * N * (1 + N)
  • 1^k + 2^k + ... + N^k = 1/(k + 1) * N ^ (k + 1)
  • 1 + 1/2 + ... + 1/N= Log N
  • Triple loops = 1/6 * N ^ 3

2. Algorithm design approach

Steps to develop a usable algorithm

Optimal algorithm

Lower bound equals to upper bound (to within a constant factor)

  • e.g 1., Brute-force algorithm for -sum is optimal: it’s running time is N
  • e.g 2., Merge sort is an optimal algorithm - upper bound: ~N log N - lower bound: ~N log N

Approach

  1. Develop an algorithm
  2. Prove a lower bound
  3. If this a gap between lower bound and the upper bound, lower the upper bound (discover a new algorithm) or raise the lower bound (more difficult)

3. Union-Find

Goal

Design efficient data structure for union-find

  • Number of objects N can be huge
  • Number of operations M can be huge
  • Find queries and union commands may be intermixed

Quick find (eager approach)

  • Integer array id of N
  • Interpretation - p and q are connected iff(if and only if) they have the same id

Java implementation

  • union too expensive (N array accesses)
  • trees are flat, but too expensive to keep them flat

Quick union (lazy approach)

  • Integer array id of N
  • Interpretation - id[i] is the parent of i - Root of i is id[id[id[...id[i]...]]]

Java implementation

  • tree can get tall
  • find too expensive (could be N array accesses)

Quick find vs Quick union

4. Improvement for quick union 1: weighting

Purpose

  • Avoid tall trees
  • Keep track of size of each tree (number of objects)
  • Balance by linking root of smaller tree to root of larger tree

Proposition

Depth of any node x is at most log N

Why?

  • The depth of x increase 1/the size of the tree at least doubles when tree T1 containing x is merged into another tree T2
  • The size of tree containing x can double at most log N times

Java implementation

  • link root of smaller tree to root of larger tree
  • update the sz[] array

Proposition of Quick find, Quick union, and weighted quick-union

5. Improvement for quick union 2: path compression

Purpose

  • Flatten the tree
  • Just after computing the root of p, set the id of each examined node to point to that root

Java implementation

Proposition: Bottom line

WQUPC reduces from 30 years to 6 seconds.

Related Leetcode questions

Week 1 Programming Assignment: Percolation

It’s called percolation if the opened sited were connected from the top to the bottom. So what’s the probability? (The numbers of opened sites/The numbers of total sites)

Requirements in detail

Solutions

  • Percolation.java
  • PercolationStats.java

Grades

References

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

  • Subscribe me
  • The Facebook page for articles
  • The latest side project: Daily Learning

Related topics

How to use the two-way binding in Knout.js and ReactJS?

Learn how to use SignalR to build a chatroom application

My reflection of :

IT & Network:

Database:

Algorithms
Princeton
Software Development
Union Find
Data Structures
Recommended from ReadMedium