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

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):¹

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

Chameerawijebandara's Blog

View original post

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.

View original post