125 Ad spot 125 Ad spot

ACMSolver or Art of Programming? 24 X 7 Updates

From 2002 ACMSolver is campaigning for free programming knowledge!

19 June 2011 0 Comments

Let’s Learn Programming (Sticky Post-updated daily)

Let’s Learn Programming (Sticky Post-updated daily)

Let’s create an alternative approach in computer programming learning.. here I plan to create a comic series using the characters from Futurama, my favorite TV series. Let me know what you think of this approach- Arefin

previous episodes..? click below

[...]

Tags:
24 September 2011 0 Comments

Power up C++ with the Standard Template Library: Part I

By DmitryKorolev

(collected from Topcoder)

Containers
Before we begin
Vector
Pairs
Iterators
Compiling STL Programs
Data manipulation in Vector
String
Set
Map
Notice on Map and Set
More on algorithms
String Streams
Summary

Perhaps you are already using C++ as your main programming language to solve TopCoder problems. This means that you have already used STL in a simple way, because arrays and strings are passed to your function as STL objects. You may have noticed, though, that many coders manage to write their code much more quickly and concisely than you.

Or perhaps you are not a C++ programmer, but want to become one because of the great functionality of this language and its libraries (and, maybe, because of the very short solutions you’ve read in TopCoder practice rooms and competitions).

Regardless of where you’re coming from, this article can help. In it, we will review some of the powerful features of the Standard Template Library (STL) – a great tool that, sometimes, can save you a lot of time in an algorithm competition.

The simplest way to get familiar with STL is to begin from its containers.

Containers
Any time you need to operate with many elements you require some kind of container. In native C (not C++) there was only one type of container: the array.

The problem is not that arrays are limited (though, for example, it’s impossible to determine the size of array at runtime). Instead, the main problem is that many problems require a container with greater functionality.

For example, we may need one or more of the following operations:

  • Add some string to a container.
  • Remove a string from a container.
  • Determine whether a string is present in the container.
  • Return a number of distinct elements in a container.
  • Iterate through a container and get a list of added strings in some order.

Of course, one can implement this functionality in an ordinal array. But the trivial implementation would be very inefficient. You can create the tree- of hash- structure to solve it in a faster way, but think a bit: does the implementation of such a container depend on elements we are going to store? Do we have to re-implement the module to make it functional, for example, for points on a plane but not strings?

If not, we can develop the interface for such a container once, and then use everywhere for data of any type. That, in short, is the idea of STL containers.

Before we begin let me tell you about the cool dell coupons we have obtained for you from our friends at techcouponcode, they have offers that give 10 to 30% off the latest Dell computers so make sure to swing by and check out the savings today.
When the program is using STL, it should #include the appropriate standard headers. For most containers the title of standard header matches the name of the container, and no extension is required. For example, if you are going to use stack, just add the following line at the beginning of your program:

#include <stack>

Container types (and algorithms, functors and all STL as well) are defined not in global namespace, but in special namespace called “std.” Add the following line after your includes and before the code begin:

using namespace std;

Another important thing to remember is that the type of a container is the template parameter. Template parameters are specified with the ‘<’/’>’ “brackets” in code. For example:

vector<int> N;

When making nested constructions, make sure that the “brackets” are not directly following one another – leave a blank between them.

vector< vector<int> > CorrectDefinition;
vector<vector<int>> WrongDefinition; // Wrong: compiler may be confused by 'operator >>'

Vector
The simplest STL container is vector. Vector is just an array with extended functionality. By the way, vector is the only container that is backward-compatible to native C code – this means that vector actually IS the array, but with some additional features.

 vector<int> v(10);
 for(int i = 0; i < 10; i++) {
      v[i] = (i+1)*(i+1);
 }
 for(int i = 9; i > 0; i--) {
      v[i] -= v[i-1];
 }

[...]

Tags: , ,
1 September 2011 0 Comments

Offtopic! PhD comics….

Tags:
31 August 2011 0 Comments

Some algorithms you will need all the time…

ReHash – A console-based hash calculator -

http://www.codeproject.com/cpp/rehash.asp
A console-based hash calculator. Supported algorithms: CRC-16, CRC-16-CCITT, CRC-32, FCS-16, FCS-32, GHash-32-3, GHash-32-5, GOST-Hash, HAVAL-5-256, MD2, MD4, MD5, SHA-1, SHA-256, SHA-384, SHA-512, Tiger.

Using PPMD for compression -

http://www.codeproject.com/cpp/ppmd.asp
This article presents a class for using PPM to compress a file.

Genetic and Ant Colony Optimization Algorithms -

http://www.codeproject.com/cpp/GeneticandAntAlgorithms.asp
Genetic and Ant Colony Optimization Algorithms

A Mersenne Twister Class -

http://www.codeproject.com/cpp/mersennetwisterclass.asp
A pseudorandom number generator.

CFraction – a double / fraction / string conversion class -

http://www.codeproject.com/cpp/fraction.asp
A class that converts between doubles, strings and fractional representations.

File Exist Algorithms -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=5186&lngWId=3
This function will check to see if a file exist in the computer if it doesnt it will return -1 else 0.

Resize the array -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=8553&lngWId=3
resize the array in the class while the run-time

Create and pass a 2D dynamic array -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=4770&lngWId=3
These program shows how to create and pass a 2D dynamic array to a function. It can be very useful for applications that you might create.

PAGE REPLACEMENT ALGORITHMS (FIFO) -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=4986&lngWId=3
A representation of the First In First Out Algorithm in Page Replacement Algorithms

A Alphabetic Diomond V 1.0 -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=6539&lngWId=3
This is my first submission on PSC.My this Code Prints the Alphabetic Diamond.Look Output here, it is so easy. It will take a number input for no. of alphabets should be in Diamond.It is the Demonstration of for loop

A Fraction Calculator -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=3684&lngWId=3
This is just a simple Calculator that allows someone to +,-,*,/ fractions. Was a class lab thought it might actually be useful to someone.

A Faster Way to “MOD” and how to grab a digit from an Integer -

http://www.planetsourcecode.com/vb/scripts/ShowCode.asp?txtCodeId=6567&lngWId=3
This program is to show how to get the last digit of an integer type without using “last_digit = num % 10″ It also shows that “%” is slower than my optimized code due to “%” using division My optimized code is faster than using “%” about 90% of the time

C++ Datastructures and Algorithms -

http://www.mathtools.net/C_C__/Algorithms_and_Data_structures/index.html

An Introduction to Data Structures with C++

-

http://www.intelligentedu.com/blogs/post/Best_New_Training_Sites/303/An-Introduction-to-Data-Structures-with-C

C++ Datastructures -

http://www.hermetic.ch/cfunlib.htm

C++ Algorithms

-

http://oopweb.com/Algorithms/Files/Algorithms.html

Computer science C++ programs and source code by James Pate Williams, Jr. -

http://www.mindspring.com/~pate/
Queen Search algorithm for solving the n-queens algorithm, Morris’ breakout algorithm, Dozier and Williams’ breakout algorithms, Simulated annealing solution of the n-queens problem.

Cenelia Gonzales C++ sources -

http://www.ai-search.4t.com
Collection of algorithm source code includes. String Tokenizer, Fuzzy String Matching, Rational Number Class, Simple FSM, Equation Solver, Guessing Games.

Vivek Patel C++ Sources -

http://www.vivekpatel.cjb.net/
Data Structures(Arrays, Linked List, Stack) and Algorithm related sources.

MTS-HOME -

http://www.mts-home.cjb.net/
Collection of sources C,C++ and other languages by Muhammad Tahir Shahzad. C++ sections includes. Algortihms, Data Structures, Numerical Analysis and other topics.

Solving NonLinear Equations -

http://www.cpp4u.com/files/progdize2/NA_ALIRAZA.zip
C# Author ALI RAZA SHAIKH

AVL Tree -

http://www.cpp4u.com/files/progdize2/5-1.zip
C++ Author ALI RAZA SHAIKH

Huffman Coding (Encryption) -

http://www.cpp4u.com/files/progdize2/5-2-a.zip
Huffman Coding Encryption. Huffman coding is to use an encryption key to. shuffle the Huffman tree before the encoding. C++ Author ALI RAZA SHAIKH

Gauss Jordon -

http://www.cpp4u.com/files/progdize2/Gauss-Jordan.zip
Solution of equation by Gauss-Jordan C# Author FIDA HUSSAIN

Rational Number Class -

http://www.cpp4u.com/files/ai/Rational_Numbers_Class-1.zip
Class to represent valid rational numbers

Tower of Hanoi -

http://cpp4u.com/files/MTS/Algorithms/ALGO-05.zip
A C++ Program to solve the Towers of Hanoi Problem (using Recursive Algorithm). Author:Muhammad Tahir Shahzad

Fibonacci series -

http://cpp4u.com/files/MTS/Algorithms/ALGO-09.zip
A C++ Program to computes the n_th term of the fibonacci series using Dynamic Programming Technique. Author:Muhammad Tahir Shahzad

fibonacci series using Toplogical Odering -

http://cpp4u.com/files/MTS/Algorithms/ALGO-10.zip
A C++ Program to computes the n_th term of the fibonacci series using Toplogical Odering and Dynamic Programming Technique. Author:Muhammad Tahir Shahzad

Prim’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-11.zip
A C++ Program to implement the Prim’s Algorithm to solve Minimum Spanning Tree Problem (MST). Author:Muhammad Tahir Shahzad

Prim’s Algorithm with Graphics -

http://cpp4u.com/files/MTS/Algorithms/ALGO-12.zip
A C++ Program to implement the Prim’s Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics. Author:Muhammad Tahir Shahzad

Prim’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-13.zip
A C++ Program to implement the Prim’s Algorithm to solve Minimum Spanning Tree Problem (MST) using Graphics and with Mouse support. Author:Muhammad Tahir Shahzad

Kurskal’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-14.zip
A C++ Program to implement the Kurskal’s Algorithm to solve Minimum Cost Spanning Tree Problem (MST). Author:Muhammad Tahir Shahzad

Kurskal’s Algorithm -

http://cpp4u.com/files/MTS/Algorithms/ALGO-15.zip
A C++ Program to implement the Kurskal’s Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics. Author:Muhammad Tahir Shahzad

Kurskal’s Algorithm with Graphics with Mouse Support -

http://cpp4u.com/files/MTS/Algorithms/ALGO-16.zip
A C++ Program to implement the Kurskal’s Algorithm to solve Minimum Cost Spanning Tree Problem (MST) using Graphics with Mouse Support. Author:Muhammad Tahir Shahzad

Towers of Hanoi -

http://cpp4u.com/files/MTS/data-structures/DS-37.zip
“A C++ Program to solve the mystery of Towers of Hanoi.Author:Muhammad Tahir Shahzad URL www.wol.net.pk/mtshome TurboC”

Blitz++ a C++ class library -

http://www.oonumerics.org/blitz/
Blitz++ is a C++ class library for scientific computing which provides performance on par with Fortran 77/90. It uses template techniques to achieve high performance. The current versions provide dense arrays and vectors, random number generators, and small vectors and matrices.
Tags: ,
7 August 2011 0 Comments

Let’s Learn STL (Rerefences)

The Standard Template Libraries (STL’s) are a set of C++ template classes to provide common programming data structures and functions such as doubly linked lists (list), paired arrays (map), expandable arrays (vector), large string storage and manipulation (rope), etc. The STL library is available from the STL home page. This is also your best detailed reference for all of the STL class functions available.

  • From YoLinux and Wiki
    • Sequences:
      • vector: (this tutorial) Dynamic array of variables, struct or objects. Insert data at the end.
      • deque: Array which supports insertion/removal of elements at beginning or end of array
      • list: (this tutorial) Linked list of variables, struct or objects. Insert/remove anywhere.
    • Associative Containers:
      • set (duplicate data not allowed in set), multiset (duplication allowed): Collection of ordered data in a balanced binary tree structure. Fast search.
      • map (unique keys), multimap (duplicate keys allowed): Associative key-value pair held in balanced binary tree structure.
    • Container adapters:
      • stack LIFO
      • queue FIFO
      • priority_queue returns element with highest priority.
    • String:
      • string: Character strings and manipulation
      • rope: String storage and manipulation
    • bitset: Contains a more intuitive method of storing and manipulating bits.
  • Operations/Utilities:
    • iterator: (examples in this tutorial) STL class to represent position in an STL container. An iterator is declared to be associated with a single container class type.
    • algorithm: Routines to find, count, sort, search, … elements in container classes
    • auto_ptr: Class to manage memory pointers and avoid memory leaks.
Tags: ,
5 August 2011 0 Comments

No More Free Books….

Due to copyright issue, ACMsolver website will offer no more free books for download. Thanks for understanding. Anyway, next edition of Art of Programming Contest (fully revised) is planned to release after 2014. Till then..

16 July 2011 0 Comments

Bunch of Programming Judges…

Some of the online judges designed for programming course are:

  • Moodle Online Judge Plugin, an assignment type for Moodle, which can automatically grade C/C++ assignments.
  • HUSTOJ, HUST Online Judge,C/C++/Pascal/Java/Ruby/Bash/Python supported, an open source OJ system using GPL2.0 license, which support LiveCD mode and FPS format.
  • FPS, Free Problem Set, an open source problemset exchange format based on XML, which providing more than 400 free problems in FPS format.
Tags: ,