Art of Programming Contest - C Programming Tutorials | Data Structures | Algorithms

Review Note

A Computer programming contest is a pleasurable event for the budding programmers, but only a few books are available as a training manual for programming competitions. This book is designed to serve as a textbook for an algorithm course focusing on programming as well as a programming course focusing on algorithms. The book is specially designed to train students to participate in competitions such as the ACM International Collegiate Programming Contest.

The book covers several important topics related to the development of programming skills such as, fundamental concepts of contest, game plan for a contest, essential data structures for contest, Input/output techniques, brute force method, mathematics, sorting, searching, greedy algorithms, dynamic programming, graphs, computational geometry, Valladolid Online Judge problem category, selected ACM programming problems, common codes/routines for programming, Standard Template Library (STL), PC2 contest administration and team guide.The book also lists some important websites/books for ACM/ICPC Programmers.

I believe that the book will be book will be of immense use for young programmers interested in taking part in programming competitions.

Dr. M. Lutfar Rahman
Professor, Department of Computer Science and Engineering (CSE)
University of Dhaka.
Bangladesh.

Combinatorial Algorithms

This pdf book contains senior-level algorithms for computer engineering students. They are

• Notes on solving recurrences
• Introduction
• Divide and conquer
• Dynamic programming
• Randomization: Nuts and bolts
• Randomized treaps
• Randomized mincut
• Uniform and universal hashing
• Skip lists
• Amortized analysis
• Scapegoat trees and splay trees
• Union-find
• Fibonacci heaps
• Graph algorithms
• Representing and searching graphs
• Single-source shortest paths
• All-pairs shortest paths
• Minimum spanning trees
• Seminumerical algorithms
• Fast Fourier transforms
• Number-theoretic algorithms
• String matching
• String matching: Rabin-Karp
• String matching: Knuth-Morris-Pratt
• Computational Geometry
• Convex hulls
• Plane sweep algorithms
• Polygon triangulation
• Lower bounds
• Information theory
• Adversary arguments
• Reductions and transformations
• NP-hard, NP-easy, and NP-complete problems

The FXT library: Fast transforms and low level algorithms

Here you find

• the FXT package
• the "Algorithms for programmers" text (the fxtbook)
• the amorphous FFT bucket moved to the fftpage

The FXT library

Latest FXT version: fxt-2007.01.13.tgz (approx. 950kB), distributed under the GPL.

Here are a some (well, more than 200) demos.

Much of the low level bit-magic code is shown on the bit wizardry page.

Read the short description in description.txt, the Linux Software Map (LSM) file fxt.lsm

Generated doc-oids:

• aux0-doc.txt auxiliary routines
• aux1-doc.txt auxiliary routines for 1-dim arrays
• aux2-doc.txt auxiliary routines for 2-dim arrays
• bits-doc.txt bit wizardry
• bpol-doc.txt binary polynomials and arithmetic over GF(2**n)
• comb-doc.txt combinatorics (combinations, partitions etc.)
• convolution-doc.txt convolution
• mult-doc.txt multiplication of large numbers
• correlation-doc.txt correlation
• dctdst-doc.txt cosine and sine transforms
• ds-doc.txt data structures (FIFO, heap etc.)
• fft-doc.txt fast Fourier transforms
• realfft-doc.txt real valued FFTs
• fht-doc.txt fast Hartley transforms
• walsh-doc.txt Walsh transforms
• haar-doc.txt Haar transforms
• mod-doc.txt modular arithmetics and number theory
• ntt.h-doc.txt number theoretic transforms
• perm-doc.txt permutations
• sort-doc.txt sorting and searching
• data-doc.txt tables of mathematical data. The tables can also be accessed via the mathdata page. generated index of all docs

Algorithms

Algorithms

by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

Prologue

Look around you. Computers and networks are everywhere, enabling an intricate web of complex human activities: education, commerce, entertainment, research, manufacturing, health management, human communication, even war. Of the two main technological underpinnings of this amazing proliferation, one is obvious: the breathtaking pace with which advances in microelectronics and chip design have been bringing us faster and faster hardware.

This book tells the story of the other intellectual enterprise that is crucially fueling the computer revolution:

Books and algorithms
Two ideas changed the world. In 1448 in the German city of Mainz a goldsmith named Johann Gutenberg discovered a way to print books by putting together movable metallic pieces. Literacy spread, the Dark Ages ended, the human intellect was liberated, science and technology triumphed, the Industrial Revolution happened. Many historians say we owe all this to typography. Imagine a world in which only an elite could read these lines! But others insist that the key development was not typography, but algorithms....

Java Data Structures (2nd edition)

Welcome to Java Data Structures (2nd edition). This document was created with an intent to show people how easy Java really is, and to clear up a few things I've missed in the previous release of the document.............

In contrast to what most people think about Java, it being a language with no pointers, data structures are quite easy to implement. In this section, I'll demonstrate few basic data structures. By learning how easy they are to implement in Java, you'll be able to write any implementation yourself.

I also think that this document is a pretty good introduction to Data Structures in general. All these concepts can be applied in any programming language......

Data Structures

These notes provide an introduction to some of the most commonly occurring data structures. The language used is Java. The aim is not the greatest generality. The DataStructures package developed here is not as extensive as the Collections framework, first released with Java 1.2. For portable applications, you should use the Collections framework where possible.

The DataStructures package, however, includes graphs which are not currently in the Collections framework; and the greater simplicity of the DataStructures package makes it more suitable as a basis for learning about fundamental principles of data structures and algorithms.

Data Structures and Algorithms with Object-Oriented Design Patterns in Java

The primary goal of this book is to promote object-oriented design using Java and to illustrate the use of the emerging object-oriented design patterns. Experienced object-oriented programmers find that certain ways of doing things work best and that these ways occur over and over again. The book shows how these patterns are used to create good software designs. In particular, the following design patterns are used throughout the text: singleton, container, enumeration, adapter and visitor.

Virtually all of the data structures are presented in the context of a single, unified, polymorphic class hierarchy. This framework clearly shows the relationships between data structures and it illustrates how polymorphism and inheritance can be used effectively. In addition, algorithmic abstraction is used extensively when presenting classes of algorithms. By using algorithmic abstraction, it is possible to describe a generic algorithm without having to worry about the details of a particular concrete realization of that algorithm.

A secondary goal of the book is to present mathematical tools just in time. Analysis techniques and proofs are presented as needed and in the proper context. In the past when the topics in this book were taught at the graduate level, an author could rely on students having the needed background in mathematics. However, because the book is targeted for second- and third-year students, it is necessary to fill in the background as needed. To the extent possible without compromising correctness, the presentation fosters intuitive understanding of the concepts rather than mathematical rigor.

single linked list

/*
* Simple operations on linked list. If any problem
* please mail to me jagannath_pattar@yahoo.Co.In
*/

#include

/*
* Data structure used, its simple :)
*/
Typedef struct linked_list_s
{
int value;
struct linked_list_s *next;
}linked_list_t;

/*
* Add a node at the end of the list.
*/
Linked_list_t* add_node(linked_list_t *head, int value)
{
linked_list_t *newNode = NULL;
linked_list_t *node = head;
linked_list_t *prev = head;

newNode = (linked_list_t *)calloc(1, sizeof(linked_list_t));
newNode->value = value;

while(node)
{
prev = node;
node = node->next;
}
if(prev == node)
return newNode;

prev->next = newNode;

return head;
}

/*
* delete a specified node from the list.
*/
Linked_list_t* delete_node(linked_list_t *head, int value)
{
linked_list_t *node = NULL;
linked_list_t *prev = NULL;

for(node = head; node != NULL; prev = node, node = node->next)
{
if(node->value == value)
{
//Check for head node modification
if(prev == NULL)
{
head = head->next;
free(node);
return head;
}

prev->next = node->next;
free(node);
return head;
}
}
return head;
}

/*
* display all the nodes of the list.
*/
Void list_nodes(linked_list_t *head)
{
linked_list_t *node = head;
printf("\nHead");
while(node)
{
printf("->%d ",node->value);
node = node->next;
}
printf("->NULL\and");
}


/*
* Display all the nodes in reverse order withoout modifying list.
*/
Void list_nodes_in_reverse_order(linked_list_t *head)
{
linked_list_t *end = NULL;
linked_list_t *node = NULL;

printf("\nReverse Head");
while(head != end)
{
node = head;
while(node->next != end)
node = node->next;

printf("->%d ",node->value);
end = node;
}
printf("->NULL\and");
}


/*
* Reversing the linked list with recursion; I recommond this method..
*/
Linked_list_t* reverse_with_recursion_anotherway(linked_list_t* current, linked_list_t* parent)
{
linked_list_t* revhead = NULL;

if(current == NULL)
revhead = parent;
else
{
revhead = reverse_with_recursion_anotherway(current->next, current);
current->next = parent;
}
return revhead;
}

/*
* Reversing the linked list;
*/
Linked_list_t* reverse_with_recursion(linked_list_t* node)
{
linked_list_t* temp = NULL;

if(node->next == NULL)
return node;

temp = reverse_with_recursion(node->next);
temp->next =node;
return node;
}

/*
* reversing linked list without recursion.
*/
Linked_list_t* reverse_without_recursion(linked_list_t* head)
{
linked_list_t* prevNode = NULL;
linked_list_t* currNode = head;
linked_list_t* nextNode = head->next;

while(currNode)
{
currNode->next = prevNode;
prevNode = currNode;
if(nextNode == NULL)
break;
currNode = nextNode;
nextNode = nextNode->next;
}
return currNode;
}

/*
* main program, which displays menu for maitaining linked list.
*/
Main()
{
int choice = -1;
int value = 0;
linked_list_t *head = NULL;
linked_list_t *node = NULL;

do
{
printf("\and what you wanna do?\and");
printf("1. Add

What is a linked list?? /* this is for your further reference and reading */

In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references ("links") pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order. A linked list is a self-referential datatype because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access. Several different types of linked list exist: singly-linked lists, doubly-linked lists, and circularly-linked lists.