16 April 2011 Comments Off

Robert Sedgewick’s Algorithm Lectures

Hello programmers, Today I would like to give you the links of  Robert Sedgewick’s Algorithm Lectures. Robert Sedgewick works in the Department of Computer Science, Princeton University, Princeton, NJ 08544

Below are links to the lecture slides. This list is tentative and is to be considered subject to change. Minor updates are possible at any time. Substantive updates (not unlikely the evening before a lecture) will be marked with the date of change. Here are the reported errata.

LECTURE SLIDES DEMOS
Intro · Union find
Analysis of algorithms
Stacks and queues (new 2/7)
Elementary sorts sorting animations
Mergesort sorting animations
Quicksort
Priority queues
Symbol tables · BSTs
Balanced search trees
Hash tables · Applications
Undirected graphs (new 3/10) DFS BFS maze
Directed graphs (fixed 3/23) DFS topological sort
Minimum spanning trees (new 3/23) Graph applet
Shortest paths (new 3/28) Dijkstra
Radix sorts string sorting
Tries
Data compression
Substring search substring search
Regular expressions
Geometric primitives convex hull Voronoi
Geometric search·Intersection sweep line intersection
Reductions·Intractability
Combinatorial search The Longest Path [mp3]

This file with all the slides for Lectures 1-10 (28 MB) is suitable for uploading to a portable device, as is this file with all the slides for Lectures 12-24 (40 MB) and this file with all the slides for the course (66 MB). These files do not reflect changes made as the semester progresses

15 March 2011 Comments Off

Top Coder – Algorithm Tutorials

Q. How to do better in Contests?

A. Very nice place to start is the TopCoder Algorithm Tutorials. They have some very good articles. But at the end of the day, you will need to study a good book on algorithms. The most popular one is CLRS (“Introduction to Algorithms” by Cormen et. al.). I would also recommend “Algorithm Design” by Kleinberg and Tardos.

Also, sites like TopCoder, Google Code Jam and CodeForces have problem analyses and the code submitted during the contest available. Reading those is a great way learning new techniques and approaches.….

Writer                                         Tutorials

lbackstrom The Importance of Algorithms
antimatter How To Dissect a TopCoder Problem Statement
Dumitru How to Find a Solution
leadhyena_inran Planning an Approach to a TopCoder Problem:
Section 1
Section 2
dimkadimon Mathematics for TopCoders
lbackstrom Geometry Concepts:
Section 1: Basic Concepts
Section 2: Line Intersection and its Applications
Section 3: Using Geometry in TopCoder Problems
gladius Introduction to Graphs and Their Data Structures:
Section 1: Recognizing and Representing a Graph
Section 2: Searching a Graph
Section 3: Finding the Best Path through a Graph
supernova Greedy is Good
Dumitru Dynamic Programming: From novice to advanced
misof Computational Complexity
Section 1
Section 2
Dan[Popovici] & mariusmuja Using Regular Expressions
supernova Understanding Probabilities
timmac Data Structures
cucu New Features of Java 1.5
timmac Sorting
_efer_ Maximum Flow
Section 1
Section 2
misof Representation of Integers and Reals
Section 1
Section 2
lovro Binary Search
bmerry A bit of fun: fun with bits
danielp Range Minimum Query and Lowest Common Ancestor
DmitryKorolev Power up C++ with the Standard Template Library: Part I
DmitryKorolev Power up C++ with the Standard Template Library: Part II: Advanced Uses
medv Prime Numbers, Factorization and Euler Function
jmzero An Introduction to Recursion, Part 1
jmzero An Introduction to Recursion, Part 2
cpphamza An Introduction to Binary Search and Red-Black Trees
bmerry Line Sweep Algorithms
Zealint Minimum Cost Flow
Part 1 – Key Concepts
Part 2 – Algorithms
Part 3 – Applications
rasto6sk Algorithm Games
boba5551 Binary Indexed Trees
TheLlama Introduction to String Searching Algorithms
Zealint Maximum Flow: Augmenting Path Algorithms Comparison
x-ray Basics of combinatorics
NilayVaish A New Approach to the Maximum Flow Problem
vlad_D Disjoint-set Data Structures
luison9999 Using Tries
dcp An Introduction to Multidimensional Databases
zmij The Best Questions for Would-be C++ Programmers
Part 1
Part 2
innocentboy Primality Testing : Non-deterministic Algorithms
x-ray Assignment Problem and Hungarian Algorithm
15 March 2011 Comments Off

Benelux Algorithm Programming Contest 2011

Benelux Algorithm Programming Contest (BAPC) 2011! Every year, the universities and colleges organise programming contests for students. The participants of these contests cooperate in teams of three persons. Each team tries to solve as many problems as possible within 5 hours by writing computer programs. This years BAPC will take place in Eindhoven (The Netherlands) on October 15th, 2011.

The contests are split up into different rounds, spanning different geographical regions: first the local championships, then the Benelux Algorithm Programming Contest, followed by the North Western European Regional Contest, and finally the World Finals.

Every autumn a Benelux Algorithm Programming Contest is held somewhere in the Benelux. Participation in the Benelux Algorithm Programming Contest is possible for (almost) every student from any university from the Benelux.

If you are interested in programming and algorithms, do participate!

Location

The BAPC 2011 will take place in the Auditorium of the Eindhoven University of Technology on October 15th, 2011.

Eindhoven University of Technology
Den Dolech 2
5612 AZ Eindhoven

For a map, see here. The Auditorium is the building with AUD in it. For the route, see here.

29 August 2010 Comments Off

Prim’s Algorithm- MST

#include<iostream.h>
#include<queue>
#include<vector>
#define INF 100000

using namespace std;

struct edge {
vector<int>Adj;
vector<int>Cost;
};

struct node{
int x, y;
};

edge Ed[100];
int N, E;
int key[100];
char F[100];
int P[100], Cost;
int SS[100][100];

class comp{
public:
bool operator() ( const node &a, const node &b)
{
return a.y > b.y;
}
};

void CT(int u) {
if(F[u] == 1 || u == 1) return;
F[u] = 1;
if(P[u] == -1) return;
Cost += SS[u][P[u]];
CT(P[u]);
}

int Prim() {
int i, j, u, v, c,cost;
Cost =  0;
priority_queue<node, vector<node>, comp> Q;
node temp, dum;
for(i = 1; i<= N; i++)
key[i] = INF;
key[1] = 0;
temp.x = 1;
temp.y = 0;
Q.push(temp);
P[1] = -1;
while(!Q.empty()) {
temp = Q.top();
Q.pop();
u = temp.x;
F[u] = 1;
for(i = 0; i<Ed[u].Adj.size(); i++) {
v = Ed[u].Adj[i];
c = Ed[u].Cost[i] + temp.y;
if(F[v] == 0) {
if(key[v] > c) {
dum.x = v;
dum.y = c;
key[v] = c;
P[v] = u;
Q.push(dum);
}
}
}
}
for(i = 1; i<= N; i++) F[i] = 0;
for(i = 1; i<= N; i++) {
if(F[i] == 0)
CT(i);
}
return Cost;
}

void main() {
int c, u, v, n;
cin>>N>>E;
n = E;
while(n--) {
cin>>u>>v>>c;
Ed[u].Adj.push_back(v);
Ed[u].Cost.push_back(c);
Ed[v].Adj.push_back(u);
Ed[v].Cost.push_back(c);
SS[u][v] = SS[v][u] = c;
}
cout<<Prim()<<endl;
}
Tags: ,