Month: July 2015

Which Programming Languages Get Used Most At Hackathons?

Anirudh Non Technical , ,

For a quick peek into the list:

The Top 10 Languages At Devpost’s Hackathons:

  1. HTML/CSS (see note below)
  2. JavaScript
  3. Python
  4. Java
  5. C/C++
  6. PHP
  7. Objective-C
  8. C#
  9. Swift
  10. JSON (which isn’t … really a programming language, but is on their list for some reason, so I’m including #11 too)
  11. Ruby

Read the full Techcrunch article to know why.

In stark contrast:

The Top 10 Languages according to IEEE Spectrum’s 2015 Rankings:

  1. Java
  2. C
  3. C++
  4. Python
  5. C#
  6. R
  7. PHP
  8. JavaScript
  9. Ruby
  10. Matlab

Note: HTML isn’t quite a “programming” language — it’s a markup language, meaning it’s a means of laying out the elements of a document. But it’s a “language” none the less, and one that pretty much every web developer taps endlessly, so we’ll let the semantic stuff slide

R — The Big Mover in IEEE Spectrum’s 2015 Rankings for Top 10 Programming Languages

Anirudh Non Technical , , ,

The column on the left is the 2015 ranking; the column on the right is the 2014 ranking for comparison:

top-tech-rankings

source: The 2015 Top Ten Programming Languages

The thing to note is that the top 5 languages haven’t budged from their positions. R has pushed past PHP, JavaScirpt and Ruby, which have maintained their relative positions.  So this year’s rankings have been about R moving forward.

Object Oriented Programing with Python – Particle Diffusion Simulation

Anirudh Technical , , , , ,

I’m a newbie to the programming world. I first started programming in Python in May this year, a month after I started this blog, so I still haven’t learnt enough to contribute to economics as is the stated goal of this blog. But I know I’ll get there in a year or less.

This blog was also meant to document my learning. In May, I would have called myself Newb v0.0. Today, 3 months later, I’d like to call myself Newb v0.3 and the goal is to be at least Expert v1.0 by January 2016.

With the help of Rice University’s awesome classes on Python programming I created a cool simulation of particles diffusing into space, using the concept of Classes, which I learnt just yesterday!

Click to check out the code !

Screenshot from 2015-07-23 11:49:00

Screenshot from 2015-07-23 11:49:10

Screenshot from 2015-07-23 11:49:39

Number of Inversions in an Unsorted Array: Python Code

Anirudh Technical , ,

This is my solution to the first programming assignment of Tim Roughgarden’s course on Algorithms  that was due 12:30 PM IST today. Here’s the question quoted as it is:

Programming Question-1
Download the text file here. (Right click and save link as) This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.
So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / any other punctuation marks. You can make up to 5 attempts, and we’ll use the best one for grading.
(We do not require you to submit your code, so feel free to use any programming language you want — just type the final numeric answer in the following space.)

My Solution

I modified an earlier code I wrote for merge sort to arrive at the solution. It needed just a couple of modifications, and if you look carefully, it turns out that the number of inversions are unearthed each and every time we merge two sorted sub-arrays. So, intuitively, if the merge sort algorithm was O(nlog2 n), it would take almost as many operations for counting inversions. In python, the code to sort and count inversions in an array of 10,000 integers took less than 3 seconds.

# load contents of text file into a list
# numList
NUMLIST_FILENAME = "IntegerArray.txt"
inFile = open(NUMLIST_FILENAME, 'r')
with inFile as f:
numList = [int(integers.strip()) for integers in f.readlines()]
count = 0
def inversionsCount(x):
global count
midsection = len(x) / 2
leftArray = x[:midsection]
rightArray = x[midsection:]
if len(x) > 1:
# Divid and conquer with recursive calls
# to left and right arrays similar to
# merge sort algorithm
inversionsCount(leftArray)
inversionsCount(rightArray)
# Merge sorted sub-arrays and keep
# count of split inversions
i, j = 0, 0
a = leftArray; b = rightArray
for k in range(len(a) + len(b) + 1):
if a[i] <= b[j]:
x[k] = a[i]
i += 1
if i == len(a) and j != len(b):
while j != len(b):
k +=1
x[k] = b[j]
j += 1
break
elif a[i] > b[j]:
x[k] = b[j]
count += (len(a) - i)
j += 1
if j == len(b) and i != len(a):
while i != len(a):
k+= 1
x[k] = a[i]
i += 1
break
return x
# call function and output number of inversions
inversionsCount(numList)
print count
view raw countInversions.py hosted with ❤ by GitHub

Test my solution here with your own test cases.

Introducing cricketr! : An R package to analyze performances of cricketers

Anirudh Technical , , ,

Wicked! Or must I say ‘howzzat!?’

Giga thoughts ...

Yet all experience is an arch wherethro’
Gleams that untravell’d world whose margin fades
For ever and forever when I move.
How dull it is to pause, to make an end,
To rust unburnish’d, not to shine in use!
Ulysses by Alfred Tennyson

Introduction

This is an initial post in which I introduce a cricketing package ‘cricketr’ which I have created. This package was a natural culmination to my earlier posts on cricket and my completing 9 modules of Data Science Specialization, from John Hopkins University at Coursera. The thought of creating this package struck me some time back, and I have finally been able to bring this to fruition.

So here it is. My R package ‘cricketr!!!’

This package uses the statistics info available in ESPN Cricinfo Statsguru. The current version of this package only uses data from test cricket. I plan to develop functionality for One-day and…

View original post 4,951 more words

Statistics: The Sexiest Job of the Decade

Anirudh Non Technical , , , , , ,

Anyone who’s got a formal education in economics knows who Hal Varian is. He’s most popularly known for his book Intermediate Economics. He’s also the Chief Economist at Google. He is known to have famously stated more or less, that statisticians and data analysts would be the sexiest jobs of the next decade.

That has come true, to a great extent, and we’ll be seeing more.

Great places to learn more about data science and statistical learning:
1] Statistical Learning (Stanford)
2] The Analytics Edge (MIT)

In a paper called ‘Big Data: New Tricks for Econometrics‘, Varian goes on to say that:

In fact, my standard advice to graduate students these days is “go to the computer science department and take a class in machine learning.” There have been very fruitful collaborations between computer scientists and statisticians in the last decade or so, and I expect collaborations between computer scientists and econometricians will also be productive in the future.

See Also: Slides on Machine Learning and Econometrics

Algorithmic Game Theory Lecture Videos and Notes

Anirudh Non Technical , , , ,

Link to Stanford professor, Tim Roughgarden’s video lectures on algorithmic game theory (AGT):

2013 Iteration
http://theory.stanford.edu/~tim/f13/f13.html

2014 Iteration
http://theory.stanford.edu/~tim/f14/f14.html

I’m currently doing his Coursera MOOC on algorithms, divided into 2 parts:

https://www.coursera.org/course/algo
https://www.coursera.org/course/algo2

Turing's Invisible Hand

I’m teaching my algorithmic game theory course at Stanford this quarter, and this time around I’m posting lecture videos and notes.  The videos are a static shot of my blackboard lectures, not MOOC-style videos.

The course home page is here.  Week 1 videos and notes, covering several motivating examples and some mechanism design basics, are already available.  This week (Week 2) we’ll prove the correspondence between monotone and implementable allocation rules in single-parameter environments, and introduce algorithmic mechanism design via Knapsack auctions.

The ten-week course has roughly four weeks of lectures on mechanism design, three weeks on the inefficiency of equilibria (e.g., the price of anarchy), and three weeks on algorithms for and the complexity of learning and computing equilibria. Periodically, I’ll post updates on the course content in this space.  I would be very happy to receive comments, corrections, and criticisms on the course organization and content.

View original post

The Merge Sort — Python Code

Anirudh Technical , , ,

I have just begun working on a MOOC on algorithms offered by Stanford. Since this course gives us the liberty to choose a programming language, there isn’t any code discussed in those lectures. I plan to convert any algorithm discussed in those lectures into Python code. Since Merge Sort was the first algorithm discussed, I’m starting with that.

Merge Sort is supposedly a good introduction to divide and conquer algorithms, greatly improving upon selection, insertion and bubble sort techniques, especially when input size increases.

Pseudocode:

— Recursively sort the first half of the input array.
— Recursively sort the second half of the input array.
— Merge two sorted sub-lists into one list.

C = output [length = n]
A = 1st sorted array [n/2]
B = 2nd sorted array [n/2]
i = 0 or 1 (depending on the programming language)
j = 0 or 1 (depending on the programming language)

for k = 1 to n

if A(i) < B(j)
C(k) = A(i)
i = i + 1

else if A(i) > B(j)
C(k) = B(j)
j = j + 1

Note: the pseudocode for the merge operation ignores the end cases.

Visualizing the algorithm can be done in 2 stages — first, the recursive splitting of the arrays, 2 each 2 at a time, and second, the merge operation.

Merge-sort-example-300px MergeSort

Here’s the Python code to merge sort an array.

# Code for the merge subroutine
def merge(a,b):
""" Function to merge two arrays """
c = []
while len(a) != 0 and len(b) != 0:
if a[0] < b[0]:
c.append(a[0])
a.remove(a[0])
else:
c.append(b[0])
b.remove(b[0])
if len(a) == 0:
c += b
else:
c += a
return c
# Code for merge sort
def mergesort(x):
""" Function to sort an array using merge sort algorithm """
if len(x) == 0 or len(x) == 1:
return x
else:
middle = len(x)/2
a = mergesort(x[:middle])
b = mergesort(x[middle:])
return merge(a,b)
view raw mergesort.py hosted with ❤ by GitHub

We can divide a list in half log2 n times where n is the length of the list. The second process is the merge. Each item in the list will eventually be processed and placed on the sorted list. So the merge operation which results in a list of size n requires n operations. The result of this analysis is that log2 n splits, each of which costs n for a total of nlog2 n operations.

Other Algorithms:
Karatsuba Integer Multiplication Algorithm
Quick Sort Python Code