Blog Archives

Princeton Univerisy Lectures: Algorithms Part I – Analysis of Algorithms(3) – Mathematical Models

1

by Kevin Wayne, Robert Sedgewick Observing what’s happening as we did in the last section it gives us a, a way to predict performance but it really doesn’t help us understand what the algorithm’s doing. So next, we’re going to

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Analysis of Algorithms(2) – Observations

1

by Kevin Wayne, Robert Sedgewick  Okay, so the first step is to be able to make some observations about the running time of the programs. And for analysis of algorithms that’s easier than in a lot of scientific disciplines, as

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Analysis of Algorithms(1) – Introduction

1

by Kevin Wayne, Robert Sedgewick  Welcome back. Today we’re going to do some math and some science. Not a lot, but we need to have a scientific basis for understanding the performance of our algorithms to properly deploy them in

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(5) Union-Find Applications

46

by Kevin Wayne, Robert Sedgewick  Alright. Now that we’ve seen efficient implementations of algorithms that can solve the unifying problem for huge problem instances let’s look to see how that might be applied. There’s a huge number of applications of

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(4) Quick Union Improvements

a

by Kevin Wayne, Robert Sedgewick  Okay. So, we’ve looked at the quick union and quick find algorithms. Both of which are easy to implement. But simply can’t support a huge dynamic connectivity problems. So, how are we going to do

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(3) Quick Union

1

All right so QuickFind is too slow for huge problems. So, how are we going to do better? Our first attempt is an alternative called, Quick-union. This is so called lazy approach to algorithm design where we try to avoid doing work until we have to. It uses the same data structure or array ID with size M but now it has a different interpretation. We are going to think of that array as representing a set of trees that’s called a forest as depicted at right. So, each entry in the array is going to contain a reference to its parent in the tree. So, for example, 3’s parent is four, 4’s parent is nine. So 3’s entry is four and 4’s entry is nine in the array. Now each entry in the array has associated with it a root. That’s the root of its tree.

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(2) Quick Find

a

Now we’ll look at our first implementation of an algorithm for solving the dynamic connectivity problem, called Quick-find.
This is a so called eager algorithm, for solving kind activity problem. The data structure that we’re going to use to support the algorithm is simply an integer array indexed by object. The interpretation is the two objects, P and Q are connected if and only if, their entries in the array are the same.
So for example in this example with our ten objects the idea array that describes the situation after seven connections is illustrated in the middle of the slide. So that, after the, at this point zero, five, and six are all in the same connected component, because they have the same array entry, zero. One, two, and seven all have entry one. And three, four, eight, and nine all have entry eight.

Tagged with:
Posted in Algorithm

Princeton Univerisy Lectures: Algorithms Part I – Union-Find(1) Dynamic Connectivity

algorithm

Welcome back to algorithms. Today, we’re going to talk about the union find problem. A set of algorithms for solving the so-called dynamic connectivity problem. We’ll look at two classic algorithms. Quick Find and Quick Union, and some applications and improvements of those algorithms. The subtext of today’s lecture really is to go through the steps that we’ll follow over and over again to develop a useful algorithm. The first step is to model the problem. Try to understand, basically, what are the main elements of the problem that need to be solved. Then we’ll find some algorithm to solve the problem.

Tagged with:
Posted in Algorithm