# 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

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

# 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

## 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)

- y = x.left // set y
- x.left = y.right // turn y’s right sub tree into x’s left sub tree
- if y.right ≠ NULL
- y.right.parent = x
- y.parent = x.parent // link x’s parent to y
- if x.parent == NULL
- T.root = y
- else if x == x.parent.left
- x.parent.left = y
- else
- x.parent.right = y
- y.right = x // put x on y’s right
- x.parent = y

Assumptions

- Assume that the n items are distinct.