Algorithms: heap data structure and intro to Greedy Algorithms

Originally posted on 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 117 more words

Always write a generalized version of your algorithm

Originally posted on Airspeed Velocity:

Suppose you want to find the minimum value in an array. Well, the Swift standard library has you covered:

1

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:

1

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?

1

Nope, more compiler errors, because now we have only non-nil values…

View original 621 more words

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

Originally posted on 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

1

/* File: serial_linked_list .c
* Purpose: Implement a linked list as a Parallel program (based on Pthreads) with read-write locks for the entire linked list
* Implementation should support Member( ), Insert( ), and Delete( ) functions.
* Populate the linked list with n…

View original 1,160 more words

Complete binary search tree in Java

Originally posted on Chameerawijebandara's Blog:

1

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package trees;

/**
*
* @author wijebandara
*/
public class BinarySearchTrees {

private NodeBST head;

/**
*
* @param n
*/
public void insert(int n) {
if (head != null) {
NodeBST hold = head;
while (true) {
if (hold.data > n) {
if (hold.left == null) {
hold.left = new NodeBST(n, hold);
break;
} else {
hold = hold.left;
}
} else {
if (hold.right == null) {
hold.right = new NodeBST(n, hold);
break;
} else {
hold = hold.right;
}
}
}
} else {
head = new NodeBST(n);
}

}

/**
*
*/
public void showPostOrder() {
if (head != null) {
showPostOrder(head);
System.out.println();
} else {
System.out.println("NULL");
}
}

private void showPostOrder(NodeBST hold) {
if (hold.right != null) {
showPostOrder(hold.right);
}

if (hold.left != null) {
showPostOrder(hold.left);

View original 672 more words

Rotation in Binary trees

Originally posted on 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

Words for young game developers and Northern Game Summit

Originally posted on digitalerr0r:

Last week I attended the Northern Game Summit, an awesome event hosted in Kajaani Finland. The event gathered somewhere around 700 attendees who all got one thing in common – creating awesome games.

I was lucky enough to be invited there to keep three presentations around Unity and game development. My talks was around getting started with developing games, getting your games published to Windows Store and Windows Phone Store, and how to get connected using the cloud.

Most of my content was based on my Unity for Windows tutorial series – but the coolest thing was the networking and meeting some of the guys behind Angry Birds, Badland, EVE Online, Alan Wake and a lot of motivated startups and students with one thing on their mind – trying to create good games, and experience worth hours of gameplay for us consumers.

Somehow, Finland manages to create games that…

View original 377 more words

How to program a Role Playing Game with Sprite Kit

Originally posted on Sprite Kit Lessons:

For anyone that stumbles onto this blog, you’ll probably be interested in some “premium” video tutorials.  Assorted code snippets are great, but there comes a time for epic learning, and that can best be delivered with a real project and video tutorials.  My latest Sprite Kit lesson is 8 hours long (divided up into shorter 10-20 minute movies) and covers a long-time favorite topic of mine, Role Playing Games!. I’ll give you a brief overview of the lesson below, but you can find out more at the sales page.

Sprite Kit RPG Tutorial

Each level is a physics based world, one thing we will do early on is program our own debug borders around the physics objects. This way we can see exactly what the collision area is around the world, characters, etc. This was an easy option to turn on with Cocos2d, but unfortunately with Sprite Kit, you need to do a…

View original 1,372 more words

2013-9-30 journal, design

Originally posted on Sean Hogan Game/Stuff/Devblog:

While working today, I decided on something sort of interesting with one of the entities in the game.  It arose accidentally.

In Even the Ocean, there are entities which launch water very quickly. It’s magic water though (…or something!), and when you touch it, your velocity becomes the same as the water – so the bullets launch upwards, thus, you kind of get boosted upwards into the air when touching a bullet.

 

I can choose how many “bullets” each entity launches – I set the default to five. The bullets all launch at the same time, but have staggered velocities (i/n * max_vel, where i = bullet index, n = nr of bullets). The way I set the velocity of the player is: if on a frame of the game, the bullet touches the player, then increment a “push velocity” counter which will be added to the players velocity…

View original 287 more words

The Simpler the Better

Originally posted on ThatsMaths:

This week’s That’s Maths in The Irish Times ( TM030 ) is about Linear Programming (LP) and about how it saves millions of Euros every day through optimising efficiency.

A Berkeley graduate student, George Dantzig, was late for class. He scribbled down two problems written on the blackboard and handed in solutions a few days later. But the problems on the board were not homework assignments; they were two famous unsolved problems in statistics. The solutions earned Dantzig his Ph.D.

View original 475 more words

Graph Search (Depth Search)

Originally posted on ahmetsaracoglu:

Image

Depth Search is an algorithm that traverses a graph to find an item, the logic behinds this search is this, Let’s assume that the first node be A, and I am looking at the neighbour of A node and there are 3 neighbours, B,C,E are the nodes alphabeticaly in order.

The first node to be visited in this list is B, after, I am going to visit the neighbour of B’s node, and it has only one neighbour, and that is D, now the turn is D’s neighbour and that is only one, final node is G.

Then, the tour is A, B, D, G and if the item being searched has been found on this stage, then we terminate the process, if we can not find it, then we should backtrack from G to the previous node, and that is D and now I am searching D’s neighbours except G…

View original 111 more words

Follow

Get every new post delivered to your Inbox.

Join 226 other followers