Category Archives: Programming

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

Thoughts on Big Data and Visualization – 1

indignant চান্দু

Big data does not have a fixed definition, but it only means BIG data. I’m not trying to be funny. I meant to say it out loud: “bb-iii-ee-gg” data. The enormous amount of data could mean Terrabytes, Petabytes and nowadays I read papers about moving on to Exabytes. This will be a series of posts that set aside the technicalities (mostly) and describe my perspective on the current progress, and also what experts in the field say about the prospective outlook.

This is a hot topic nowadays among the journalists since it has found its use beyond the borders of science, but the research thrust has been there for more than two decades, dating back to the early days of scientific data analysis and visualization. There are doubts on the capabilities of this field, I met a few Data professors and experts who cast doubt on the current hype, I…

View original post 1,062 more words

Adventures of a Programmer: Parser Writing Peril I

De Amentiae Mundi

As menacedpromised in the last post: a description of the long path
to a well determined end.

Goal: Writing a small parser for a simple but complete language as a front-end for a for a calculator back-end. With emphasis on “complete”. A simple task one might think, a very simple one. One that could have been described in full in some book I mentioned in another post.

So in medias res, as Caesar wouldn’t have said (he spoke Greek) and of to the very beginning: The Plan. Not that I ever saw it but it is said that The Plan cometh at every beginning.
What is needed for the already briefly described…uhm…purpose, to avoid the repetition of the infamous two words, that are unbeknownst to many programmers, what does the parser need to parse? What do we need to do to enable the poor thing to do so?

View original post 1,108 more words

Big Data, Data Mining and Machine Learning: Under the Hood

Big Data, Data Mining and Machine Learning: Under the Hood.

Data Compression: What it is and how it works

Data Compression: What it is and how it works.

Break…?

This is a replica of the code that caused a major disruption of AT&T phone service throughout the U.S. AT&T’s network was in large part unusable for about nine hours starting on the afternoon of January 15, 1990. Telephone exchanges are all computer systems these days, and this code was running on a model 4ESS Central Office Switching System.
It demonstrates that it is too easy in C to overlook exactly which control constructs are affected by a “break” statement.
network code()
{
switch (line) {
case THING1:
doit1();
break;
case THING2:
if (x == STUFF) {
do_first_stuff();
if (y == OTHER_STUFF)
break;
do_later_stuff();
} /* coder meant to break to here… */
initialize_modes_pointer();
break;
default:
processing();
} /* …but actually broke to here! */
use_modes_pointer();/* leaving the modes_pointer
uninitialized */
}
This is a simplified version of the code, but the bug was real enough. The programmer wanted to break out of the “if” statement, forgetting that “break” actually gets you out of the nearest enclosing iteration or switch statement. Here, it broke out of the switch, and executed the call to use_modes_pointer() —but the necessary initialization had not been done, causing a failure further on.
This code eventually caused the first major network problem in AT&T’s 114-year history. The saga is described in greater detail on page 11 of the January 22, 1990 issue of Telephony magazine. The supposedly fail-safe design of the network signaling system
actually spread the fault in a chain reaction, bringing down the entire long distance network.
And it all rested on a C switch statement.