Monthly Archives: July 2014

Algorithms: heap data structure and intro to Greedy Algorithms

drawing with data

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

Advertisements

Always write a generalized version of your algorithm

Airspeed Velocity

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

Linked List with read-write locks for the entire linked list in C

Chameerawijebandara's Blog

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

Complete binary search tree in Java

Rotation in Binary trees

Chameerawijebandara's Blog

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.

step_0step_1step_2step_3step_4step_5step_6step_7

View original post