# Monthly Archives: July 2014

## Algorithms: heap data structure and intro to Greedy Algorithms

I’m currently taking the Algorithms 1/Algorithms 2 courses on Coursera.  This is an aside from pure data viz, but is good to get this part of the core cs foundation.  And, it’s fun!

Today’s lectures & main take-away messages

Heaps as Data Structures: (1) if you find yourself doing repeated minimum (or maximum) computations, consider a heap and (2) choosing the right data structure can decrease an algorithm’s running time

Intro to Greedy Algorithms: (1) Greedy algorithms are one of the major algorithm design paradigms along with divide & conquer, randomized, and dynamic programming.  (2) Comparing Greedy to Divide & Conquer, greedy algorithms are generally easier to apply while you need the right insight to find how to decompose for D & C, easier to calculate Big O classification since often one aspect of the algorithm dominates, but typically non-trivial to prove correctness.

Optimal Caching as an…

View original post 117 more words

## Always write a generalized version of your algorithm

Suppose you want to find the minimum value in an array. Well, the Swift standard library has you covered:

Ok that’s cool. But suppose you have an array of strings of integers and you want the minimum numeric value.

Well, I guess you could map them to `Int` and then use the same function:

Nope, compiler error. `String.toInt` returns an `Int?`, because maybe the string isn’t a number.

Fair enough. I happen to know with my intimate knowledge of the problem domain that we can just ignore non-numeric values. So maybe filter those out?

Nope, more compiler errors, because now we have only non-`nil` values, but they’re still optionals and an `Int?` doesn’t conform to `Comparable`. So maybe another `map` to force-unwrap the results (force unwrap is OK because the filter will guarantee no non-nil elements):1

Ok that compiles now and does return the minimum numeric…

View original post 457 more words

# Introduction

his implementation support Member( )Insert( ), and Delete( ) functions. Populate the linked list with n random, but unique values. Each value should be between 0 and 2^16– 1. Then perform m random Member, Insert, and Delete operations on the link list. Let mMember, mInsert, and mDelete be the fractions of operations of each type. You may use any values within 0 and 2^16– 1 while performing these three operations.

However, to simplify the implementation, a new value inserted into the list cannot be a value already in the list (it may be a value that was initially added to the list, but later removed).

# Code

View original post

## Rotation in Binary trees

As a example I have use RIGHT-ROTATE to present the steps of the rotations. LEFT-ROTATE is also semantic.

RIGHT-ROTATE(T, x)

1.         y = x.left                              // set y
2.         x.left = y.right                    // turn y’s right sub tree into x’s left sub tree
3.         if y.right ≠ NULL
4.                         y.right.parent = x
5.         y.parent = x.parent         // link x’s parent to y
6.         if x.parent == NULL
7.                         T.root = y
8.         else if x == x.parent.left
9.                         x.parent.left = y
10.         else
11.                         x.parent.right = y
12.         y.right = x                            // put x on y’s right
13.         x.parent = y

Assumptions

• Assume that the n items are distinct.

View original post