DOWLOADS 7 (Submitted Solutions to UVA Online Judge||online Judge Solution Archive.)

Problem Id.	Title	Download
10698	Football Sort	Download/View
10699	Count the Factors	Download/View
10700	Camel Trading	Download/View
10701	Pre in and Post	Download/View
10702	Travelling Salesman	Download/View
10703	Free Spots	Download/View
10705	The Fun Number System	Download/View
10706	Number Sequence	Download/View
10714	Colliding Ants	Download/View
10716	Evil Straw Warts Live	Download/View
10717	Mint	Download/View
10718	Bit Mask	Download/View
10719	Quotient Polynomial	Download/View
10720	Graph Construction	Download/View
10722	Super Lucky Numbers	Download/View
10724	Road Construction	Download/View
10730	Antiarithmetic	Download/View
10739	String to Palindrome	Download/View
10740	Not the Best	Download/View
10742	The New Rule in Euphomia	Download/View
10745	Dominant Strings	Download/View
10759	Dice Throwing	Download/View
10763	Foreign Exchange	Download/View
10771	Barbarian tribes	Download/View
10776	Determine The Combination	Download/View
10780	Again Prime No time	Download/View
10783	Odd Sum	Download/View
10784	Diagonal	Download/View
10785	The Mad Numerologist	Download/View
10787	Modular Equations	Download/View
10788	Parenthesizing Palindromes	Download/View
10789	Prime Frequency	Download/View
10790	How Many Points of Intersection	Download/View
10791	Minimum Sum LCM	Download/View
10793	The Orc Attack	Download/View
10800	Not That Kind of Graph	Download/View
10801	Lift Hopping	Download/View
10803	Thunder Mountain	Download/View
10806	Dijkstra Dijkstra	Download/View
10810	Ultra Quicksort	Download/View
10812	Beat the Spread	Download/View
10813	Traditional BINGO	Download/View
10814	Simplifying Fractions	Download/View
10815	Andy s First Dictionary	Download/View
10816	Travel in the Desert	Download/View
10818	Dora Trip	Download/View
10819	Trouble of 13	Download/View
10820	Send A Table	Download/View
10822	Planet of the Rock, Paper and Scissors	Download/View
10823	Of Circles and Squares	Download/View
10827	Maximum Sum on a Torus	Download/View
10830	A New Function	Download/View
10832	Yoyodyne	Download/View
10842	Traffic Flow	Download/View
10843	Anne's game	Download/View
10848	Make Palindrome Checker	Download/View
10849	Move the bishop	Download/View
10852	Less Prime	Download/View
10855	Rotated square	Download/View
10856	Recover Factorial	Download/View
10860	Many a Little makes a Mickle	Download/View
10862	Connect the Cable Wires	Download/View
10871	Primed Subsequence	Download/View
10874	Segments	Download/View
10878	Decode the Tape	Download/View
10879	Code Refactoring	Download/View
10880	Colin and Ryan	Download/View
10890	Maze	Download/View
10891	Game of Sum	Download/View
10892	LCM Cardinality	Download/View
10895	Matrix Transpose	Download/View
10896	Known Plaintext Attack	Download/View
10898	Combo Deal	Download/View
10901	Ferry Loading III	Download/View
10903	Rock	Download/View
10908	Largest Square	Download/View
10910	Mark s Distribution	Download/View
10911	Forming Quiz Teams	Download/View
10912	Simple Minded Hashing	Download/View
10913	Walking on a Grid	Download/View
10914	Abundance and Perfect Numbers	Download/View
10916	Factstone Benchmark	Download/View
10917	Walk Through the Forest	Download/View
10919	Preqrequisites	Download/View
10920	Spiral Tap	Download/View
10921	Find the Telephone	Download/View
10922	2 the 9s	Download/View
10923	Seven Seas	Download/View
10924	Prime Words	Download/View
10925	Krakovia	Download/View
10926	How Many Dependencies	Download/View
10929	You can say 11	Download/View
10930	A-Sequence	Download/View
10931	Parity	Download/View
10935	Throwing cards away I	Download/View
10937	Blackbeard the Pirate	Download/View
10938	Flea Circus	Download/View
10940	Throwing Cards Away II	Download/View
10943	How do you add	Download/View
10944	Nuts for nuts..	Download/View

10 Challenging Star Pattern Programs in C

Computer languages are not as easy as human languages, they need you to become a computer yourself, think like a computer and write an algorithm. Computer programs are fun if you take them up as a challenge, as unsolved puzzles. There is lot of fun in taking up the challenge, understanding the problem, writing an algorithm, writing a program and most importantly running the program and obtaining required output.
Here are few challenging C program questions for you. Let’s see how many of them you would be able to write without seeing the program solution given below. These questions are to print patterns using asterisk(star) character. Comment below if you have tougher pattern questions.

1. Write a C program to print the following pattern:

   *
        *  *
     *  *  *
   *  *  *  *
   

2. Write a C program to print the following pattern:

   *                   *
   * * *           * * *
   * * * * *   * * * * *
   * * * * * * * * * * *
   

3. Write a C program to print the following pattern:

   *                         *
     *                   *
   *     *             *     *
     *     *       *     *
   *     *      *      *     *
     *     *       *     *
   *     *             *     *
     *                   *
   *                         *
   

4. Write a C program to print the following pattern:

   *   *   *   *   *
    *   *   *   *
      *   *   *
        *   *
          *
        *   *
      *   *   *
    *   *   *   *
   *   *   *   *   *
   

5. Write a C program to print the following pattern:

   *
          * * *
        * * * * *
      * * * * * * *
    * * * * * * * * *
      * * * * * * *
        * * * * *
          * * *
            *
          * * *
        * * * * *
   

6. Write a C program to print the following pattern:

   *
         * *
           * * *
             * * * *
           * * *
         * *
       *
   

7. Write a C program to print the following pattern:

   * * * * * * * * *
   * * * *   * * * *
   * * *       * * *
   * *           * *
   *               *
   * *           * *
   * * *       * * *
   * * * *   * * * *
   * * * * * * * * *
   

8. Write a C program to print the following pattern:

   * * * * * * * * * * * * * * * * *
    * * * * * * *   * * * * * * *
      * * * * *       * * * * *
        * * *           * * *
          * * * * * * * * *
            * * * * * * *
              * * * * *
                * * *
                  *
   

9. Write a C program to print the following pattern:

   *
      * * *
    * * * * *
   * * * * * * *
   *           *
   * *       * *
   * * *   * * *
   * * * * * * *
   * * *   * * *
   * *       * *
   *           *
   * * * * * * *
    * * * * *
      * * *
        *
   

10. Write a C program to print the following pattern:

    * * * * * * * * * * * * * * * * * * * * * * * * *
     *           *   *           *   *           *
       *       *       *       *       *       *
         *   *           *   *           *   *
           *               *               *
         *   *           *   *           *   *
       *       *       *       *       *       *
     *           *   *           *   *           *
    * * * * * * * * * * * * * * * * * * * * * * * * *
    

1. Write a C program to print the following pattern:

*
     *  *
  *  *  *
*  *  *  *

Program:

/* This is a simple mirror-image of a right angle triangle */

#include 
int main() {
char prnt = '*';
int i, j, nos = 4, s;
for (i = 1; i <= 5; i++) {
for (s = nos; s >= 1; s--) {  // Spacing factor
  printf("  ");
 }
 for (j = 1; j <= i; j++) {
  printf("%2c", prnt);
 }
 printf("\n");
 --nos;   // Controls the spacing factor
}
return 0;
}

Download Code
2. Write C program to print the following pattern:

   *                   *
   * * *           * * *
   * * * * *   * * * * *
   * * * * * * * * * * *

Program:

#include
int main() {
char prnt = '*';
int i, j, k, s, c = 1, nos = 9;
for (i = 1; c <= 4; i++) {
    // As we want to print the columns in odd sequence viz. 1,3,5,.etc
 if ((i % 2) != 0) {
  for (j = 1; j <= i; j++) {
printf("%2c", prnt);
}
for (s = nos; s >= 1; s--) { //The spacing factor
   if (c == 4 && s == 1) {
    break;
   }
   printf("  ");
  }
  for (k = 1; k <= i; k++) {
   if (c == 4 && k == 5) {
    break;
   }
   printf("%2c", prnt);
  }
  printf("\n");
  nos = nos - 4;  // controls the spacing factor
  ++c;
 }
}
return 0;
}

Download Code
3. Write C program to print the following pattern:

   *                         *
     *                   *
   *     *             *     *
     *     *       *     *
   *     *      *      *     *
     *     *       *     *
   *     *             *     *
     *                   *
   *                         *

Program:

#include
int main() {
char prnt = '*';
int i, j, k, s, p, r, nos = 7;

for (i = 1; i <= 5; i++) {
 for (j = 1; j <= i; j++) {
if ((i % 2) != 0 && (j % 2) != 0) {
printf("%3c", prnt);
}
else if ((i % 2) == 0 && (j % 2) == 0) {
printf("%3c", prnt);
}
else {
printf("   ");
}
}
for (s = nos; s >= 1; s--) {  // for the spacing factor
  printf("   ");
 }
 for (k = 1; k <= i; k++) { //Joining seperate figures
if (i == 5 && k == 1) {
continue;
}
if ((k % 2) != 0) {
printf("%3c", prnt);
}
else {
printf("   ");
}
}
printf("\n");
nos = nos - 2;   // space control
}  nos = 1;  // remaining half..
for (p = 4; p >= 1; p--) {
 for (r = 1; r <= p; r++) {
if ((p % 2) != 0 && (r % 2) != 0) {
printf("%3c", prnt);
}
else if ((p % 2) == 0 && (r % 2) == 0) {
printf("%3c", prnt);
}
else {
printf("   ");
}
}
for (s = nos; s >= 1; s--) {
  printf("   ");
 }
 for (k = 1; k <= p; k++) {
  if ((k % 2) != 0) {
   printf("%3c", prnt);
  }
else {
   printf("   ");
  }
 }
 nos = nos + 2;  // space control
 printf("\n");
}
return 0;
}

Download Code

Explanation: This can be seen as an inverted diamond composed of stars. It can be noted that the composition of this figure follows sequential pattern of consecutive stars and spaces. In case of odd row number, the odd column positions will be filled up with ‘*’, else a space will be spaced and vice-versa in case of even numbered row. In order to achieve this we will construct four different right angle triagles aligned as per the requirement.

1. Write a C program to print the following pattern:

   *   *   *   *   *
    *   *   *   *
      *   *   *
        *   *
          *
        *   *
      *   *   *
    *   *   *   *
   *   *   *   *   *

Program:

#include
int main() {
char prnt = '*';
int i, j, s, nos = 0;
for (i = 9; i >= 1; (i = i - 2)) {
 for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (j = 1; j <= i; j++) {
  if ((i % 2) != 0 && (j % 2) != 0) {
   printf("%2c", prnt);
  } else {
   printf("  ");
  }
 }
 printf("\n");
 nos++;
}
nos = 3;
for (i = 3; i <= 9; (i = i + 2)) {
for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (j = 1; j <= i; j++) {

  if ((i % 2) != 0 && (j % 2) != 0) {
   printf("%2c", prnt);
  } else {
   printf("  ");
  }
 }
 nos--;
 printf("\n");
}
return 0;
}

Download Code
2. Write a C program to print the following pattern:

   *
          * * *
        * * * * *
      * * * * * * *
    * * * * * * * * *
      * * * * * * *
        * * * * *
          * * *
            *
          * * *
        * * * * *

Program:

#include
int main() {
char prnt = '*';
int i, j, k, s, nos = 4;
for (i = 1; i <= 5; i++) {
for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (j = 1; j <= i; j++) {
  printf("%2c", prnt);
 }
 for (k = 1; k <= (i - 1); k++) {
if (i == 1) {     continue;
}
printf("%2c", prnt);
}
printf("\n");   nos--;
}
nos = 1;
for (i = 4; i >= 1; i--) {
 for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (j = 1; j <= i; j++) {
  printf("%2c", prnt);
 }
 for (k = 1; k <= (i - 1); k++) {
  printf("%2c", prnt);
 }
 nos++;
 printf("\n");
}
nos = 3;
for (i = 2; i <= 5; i++) {
if ((i % 2) != 0) {
for (s = nos; s >= 1; s--) {
   printf("  ");
  }
  for (j = 1; j <= i; j++) {
   printf("%2c", prnt);
  }
 }
 if ((i % 2) != 0) {
  printf("\n");
  nos--;
 }
}
return 0;
}

Download Code
3. Write a C program to print the following pattern:

   *
         * *
           * * *
             * * * *
           * * *
         * *
       *

Program:

/*
   This can be seen as two right angle triangles sharing the same base
   which is modified by adding few extra shifting spaces
*/
#include 
// This function controls the inner loop and the spacing
// factor guided by the outer loop index and the spacing index.
int triangle(int nos, int i) {
char prnt = '*';
int s, j;
for (s = nos; s >= 1; s--) {    // Spacing factor
 printf("  ");
}
for (j = 1; j <= i; j++) {      //The inner loop
 printf("%2c", prnt);
}
return 0;
}

int main() {
int i, nos = 5;
//draws the upper triangle
for (i = 1; i <= 4; i++) {
triangle(nos, i);    //Inner loop construction
nos++;              // Increments the spacing factor
printf("\n");  }
nos = 7;  //Draws the lower triangle skipping its base.
for (i = 3; i >= 1; i--) {
 int j = 1;
 triangle(nos, i);  // Inner loop construction
 nos = nos - j;     // Spacing factor
 printf("\n");
}
return 0;
}

Download Code
4. Write a C program to print the following pattern:

   * * * * * * * * *
   * * * *   * * * *
   * * *       * * *
   * *           * *
   *               *
   * *           * *
   * * *       * * *
   * * * *   * * * *
   * * * * * * * * *

Program:

#include 

int main() {
char prnt = '*';
int i, j, k, s, nos = -1;
for (i = 5; i >= 1; i--) {
 for (j = 1; j <= i; j++) {
printf("%2c", prnt);
}
for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (k = 1; k <= i; k++) {
  if (i == 5 && k == 5) {
   continue;
  }
  printf("%2c", prnt);
 }
 nos = nos + 2;
 printf("\n");
}
nos = 5;
for (i = 2; i <= 5; i++) {
 for (j = 1; j <= i; j++) {
printf("%2c", prnt);
}
for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (k = 1; k <= i; k++) {
  if (i == 5 && k == 5) {
   break;
  }
  printf("%2c", prnt);
 }
 nos = nos - 2;
 printf("\n");
}
return 0;
}

Download Code
5. Write a C program to print the following pattern:

   * * * * * * * * * * * * * * * * *
    * * * * * * *   * * * * * * *
      * * * * *       * * * * *
        * * *           * * *
          * * * * * * * * *
            * * * * * * *
              * * * * *
                * * *
                  *

Program:

#include 
int main() {
char prnt = '*';
int i, j, k, s, sp, nos = 0, nosp = -1;
for (i = 9; i >= 3; (i = i - 2)) {
 for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (j = 1; j <= i; j++) {
printf("%2c", prnt);
}
for (sp = nosp; sp >= 1; sp--) {
  printf("  ");
 }
 for (k = 1; k <= i; k++) {
if (i == 9 && k == 1) {
continue;
}
printf("%2c", prnt);
}
nos++;
nosp = nosp + 2;
printf("\n");
}
nos = 4;
for (i = 9; i >= 1; (i = i - 2)) {
 for (s = nos; s >= 1; s--) {
  printf("  ");
 }
 for (j = 1; j <= i; j++) {
  printf("%2c", prnt);
 }
 nos++;
 printf("\n");
}

return 0;
}

Download Code
6. Write a C program to print the following pattern:

   *
      * * *
    * * * * *
   * * * * * * *
   *           *
   * *       * *
   * * *   * * *
   * * * * * * *
   * * *   * * *
   * *       * *
   *           *
   * * * * * * *
    * * * * *
      * * *
        *

Program:

#include 
/*
* nos = Num. of spaces required in the triangle.
* i   = Counter for the num. of charcters to print in each row
* skip= A flag for checking whether to
*       skip a character in a row.
*
*/
int triangle(int nos, int i, int skip) {
char prnt = '*';
int s, j;
for (s = nos; s >= 1; s--) {
 printf("  ");
}
for (j = 1; j <= i; j++) {
 if (skip != 0) {
  if (i == 4 && j == 1) {
   continue;
  }
 }
 printf("%2c", prnt);
}
return 0;
}

int main() {
int i, nos = 4;
for (i = 1; i <= 7; (i = i + 2)) {
 triangle(nos, i, 0);
 nos--;
 printf("\n");
}
nos = 5;
for (i = 1; i <= 4; i++) {
triangle(1, i, 0); //one space needed in each case of the formation
triangle(nos, i, 1); //skip printing one star in the last row.
nos = nos - 2;
printf("\n");
}
nos = 1;
for (i = 3; i >= 1; i--) {
 triangle(1, i, 0);
 triangle(nos, i, 0);
 nos = nos + 2;
 printf("\n");
}
nos = 1;
for (i = 7; i >= 1; (i = i - 2)) {
 triangle(nos, i, 0);
 nos++;
 printf("\n");
}
return 0;
}

Download Code
7. Write a C program to print the following pattern:

   * * * * * * * * * * * * * * * * * * * * * * * * *
    *           *   *           *   *           *
      *       *       *       *       *       *
        *   *           *   *           *   *
          *               *               *
        *   *           *   *           *   *
      *       *       *       *       *       *
    *           *   *           *   *           *
   * * * * * * * * * * * * * * * * * * * * * * * * *

Program:

#include 

/*
* nos = Num. of spaces required in the triangle.
* i   = Counter for the num. of characters to print in each row
* skip= A flag for check whether to
*       skip a character in a row.
*
*/

int triangle(int nos, int i, int skip) {
char prnt = '*';
int s, j;
for (s = nos; s >= 1; s--) {
 printf("  ");
}
for (j = 1; j <= i; j++) {
if (skip != 0) {
if (i == 9 && j == 1) {
  continue;
}
}
if (i == 1 || i == 9) {
printf("%2c", prnt);
}
else if (j == 1 || j == i) {
printf("%2c", prnt);
} else {
printf("  ");
}  }
return 0; }
int main() {
int i, nos = 0, nosp = -1, nbsp = -1;
for (i = 9; i >= 1; (i = i - 2)) {
 triangle(nos, i, 0);
 triangle(nosp, i, 1);
 triangle(nbsp, i, 1);
 printf("\n");
 nos++;
 nosp = nosp + 2;
 nbsp = nbsp + 2;
}
nos = 3, nosp = 5, nbsp = 5;
for (i = 3; i <= 9; (i = i + 2)) {
 triangle(nos, i, 0);
 triangle(nosp, i, 1);
 triangle(nbsp, i, 1);
 printf("\n");
 nos--;
 nosp = nosp - 2;
 nbsp = nbsp - 2;
}
return 0;
}

Download Code

ALGORITHMS (Sorting, Dynamic, Number Theory, Searching)

Category	Title	Source Code
Dynamic	0/1 - Knapsack	Download/View
Dynamic	Coin Change	Download/View
Dynamic	Coin Change(Recursive/Memor)	Download/View
Dynamic	L I S	Download/View
Dynamic	Matrix Chain multiplication	Download/View
Dynamic	Maximum Product	Download/View
Graph	Bellman-Ford	Download/View
Graph	BFS	Download/View
Graph	Dijkstra	Download/View
Graph	Finding Articulation Point	Download/View
Graph	MST ( Kruskal )	Download/View
Graph	MST ( Prim )	Download/View
Graph	Topological Sort	Download/View
Medians and Order Statistics	Finding Maximum and Minimum	Download/View
Number theory	Caculating GCD of two integers	Download/View
Number theory	Calculating LCM of two integers	Download/View
Number theory	Counting Divisor of an integer	Download/View
Number theory	Counting number of digits of n!	Download/View
Number theory	Counting Tailing zero/s of n!	Download/View
Number theory	Factorization of an integer	Download/View
Number theory	Factorrization of n!	Download/View
Number theory	Generating Prime Numbers	Download/View
Number theory	Relatively Prime	Download/View
Searching	Linear Search	Download/View
Sorting	Bubble Sort	Download/View
Sorting	Bubble Sort (1st Improvement)	Download/View
Sorting	Bubble Sort (2nd Improvement)	Download/View
Sorting	Bucket Sort	Download/View
Sorting	Heap Sort	Download/View

Simple Solutions for Complex Problems on Single Linked List..

Listed here are few common complex operations of single linked list that is to be needed by certain applications. These operations should be done in single traversal for improved performance.

Here are few of them and their solutions..

1. Reverse the list.
2. Find n-th node from tail end.
3. Find middle node of the list.
4. Delete a node whose address is known, without having the head node's address.

1. Reverse the list
Logic :

a. Get each node from front end till last.
b. Add them into another list at front.

2. Find n-th node from tail end.

a. Have two pointers pointer1 and pointer2.
b. Point all of them to head initilally.
c. Move only pointer1 for n nodes.
d. Move both pointers for the rest nodes of list.
e. At the end of traversal, pointer2 will be pointing to n-th node from tail.

3. Find middle node of the list.

a. Have two pointers pointer1 and pointer2.
b. Point all of them to head initilally.
c. Move only pointer1 by one node.
d. Move pointer2 by two nodes till the end of list.
e. At the end of traversal, pointer1 will be pointing to middle node from tail.

4. Delete a node without having the head node's address

a. copy the contents of next node's data to current node's data.
b.Store the next node's next node at current node's link.

In all cases, we have to take care of boundary conditions as well as memory leaks.
Here is the code..

Code: C

#include

struct node
{
int data;
struct node* next;
};

// Functions for allocating/deallocating memory
struct node* create_node(int data);

// Utility functions that can be used in reverse_list
struct node* insert_at_front(struct node* head, struct node* new_node);
struct node* insert_at_end(struct node* head, struct node* new_node);

struct node* remove_from_front(struct node* head);
struct node* reverse_list(struct node* head);

// Delete a node without having the head pointer..
void delete_this_node(struct node* cur_node);

// Find nth node from tail in single traversal..
struct node* find_nth_from_end(struct node* head, int n);

// Find middle node of the list in single traversal..
struct node* find_middle_node(struct node* head);

// Dump the list/node..
void dump_list(struct node* head);
void dump_node(struct node* pNode);
void copy_node(struct node* src, struct node* dest);

// Main function
int main(void)
{
struct node *list = NULL, *temp_node = NULL;
int i = 0;

// Create list with 10 members...
for(i = 0; i <= 10; i++) {
temp_node = create_node(i);
list = insert_at_end(list, temp_node);
}

// Add 5 more in front...
for(i = 14; i >= 11; i--) {
temp_node = create_node(i);
list = insert_at_front(list, temp_node);
}

dump_list(list);

// To reverse a single linked list in single traversal.......
/*
list = reverse_list(list);
*/

// Delete a particular node without having the head pointer
/*
temp_node = list;

for(i = 0; i <= 15; i++) {

if(i == 4) {
delete_this_node(temp_node);
break;
}

temp_node = temp_node->next;
}
dump_list(list);
*/

// To find nth node from the end of list in single traversal....
/*
temp_node = find_nth_from_end(list, 10);

dump_node(temp_node);
*/

// To find the middle node of list in single traversal......

/*
temp_node = find_middle_node(list);

dump_node(temp_node);

list = reverse_list(list);

dump_list(list);

temp_node = find_middle_node(list);

dump_node(temp_node);
*/
return 0;
}

// Allocate memory and store the data
struct node* create_node(int data)
{
struct node *new_node = NULL;

new_node = (struct node*)malloc(sizeof(struct node));

new_node->data = data;
new_node->next = NULL;

return new_node;
}

// Deallocate the memory
void free_this_node(struct node* pNode)
{
free(pNode);
pNode = NULL;

return;
}

// Insert a node at front end
struct node* insert_at_front(struct node* head, struct node* new_node)
{
if(new_node) {
new_node->next = head;
return new_node;
}
else
return NULL;
}

// Insert a node at tail end
struct node* insert_at_end(struct node* head, struct node* new_node)
{
struct node *temp = NULL;

if(head) {

temp = head;

while(temp->next)
temp = temp->next;

temp->next = new_node;
}
else {
head = new_node;
}

return head;
}

// Remove a node from front end..
struct node* remove_from_front(struct node* head)
{
if(head) {
head = head->next;
return head;
}
else
return NULL;
}

// Reverse the list in single traversal..
struct node* reverse_list(struct node* head)
{
struct node *result = NULL, *temp_head = NULL, *temp = NULL;

temp_head = head;

while(temp_head) {

temp = temp_head;

temp_head = remove_from_front(temp_head);

temp->next = NULL;

result = insert_at_front(result, temp);
}

return result;
}

// Delete a node without the help of head node..
void delete_this_node(struct node* cur_node)
{
struct node *temp = NULL;
if(cur_node && cur_node->next) {

copy_node(cur_node, cur_node->next);
temp = cur_node->next;
cur_node->next = cur_node->next->next;

free_this_node(temp);
}
else if(cur_node) {
free_this_node(cur_node);
}
else
return;
}

// Find n-th node from tail end in single traversal...
struct node* find_nth_from_end(struct node *head, int n)
{
struct node *temp = NULL, *result = NULL, *temp_head = NULL;
int i = 0;

result = temp_head = temp = head;

for(i = 0; i < n; i++) {
if(!temp_head) {
printf("Out of Range\n");
return NULL;
}
temp_head = temp_head->next;
temp = temp->next;
}

while(temp_head) {
temp_head = temp_head->next;
temp = temp->next;
result = result->next;
}

return result;
}

// Find middle node of list in single traversal...
struct node* find_middle_node(struct node* head)
{
struct node *temp_head = NULL, *temp = NULL, *result = NULL;

temp_head = temp = result = head;

while(temp && temp->next) {

if(temp->next->next) {
temp = temp->next->next;
result = result->next;
}
else
temp = temp->next;
}

return result;
}

// Dump the list...
void dump_list(struct node* head)
{
struct node *temp = NULL;

printf("\n");

if(head) {

temp = head;

while(temp) {
printf("%d ", temp->data);
temp = temp->next;
}
}
else {
printf("Empty List");
}

printf("\n");
}

// Copy data in b/w two nodes...
void copy_node(struct node* src, struct node* dest)
{
src->data = dest->data;

return;
}

// Dump a node
void dump_node(struct node* pNode)
{
if(pNode)
printf("\nNode details : Addr : %x, data : %d\n", pNode, pNode->data);
else
printf("\n Node is NULL \n");

return;
}

Uncomment the relevant snippet from main for testing it.

Self Printing Programs

As the topic says, self printing programs are nothing but they reproduce themselves as output. Such programs are referred as Quines from the name of the logician Willard van Orman Quine who introduced the concept.


I said an 'Ah!!!' when I heard about Quines for first time, spent more hours to find the magic behind Quines. After an analysis over a long period of time, I realized that there is no magic but logic behind it.


Its quite easier in few languages, which handle code segments as data. But in C, both are being handled as separate segments. Thus, writing quines is interesting and challenging. But if we understand the idea behind it clearly, we can easily write them in C also.


This article explains several ways of writing quines in C.


The simple and straight forward solution we usually think of is 'open the source file and print its contents'. It does not work all the times, say if we have only the executable, not the source code, this solution will not work.


Treat Code as Data


Easiest way is to treat the code statements as data to be printed. Look at the following program.


Code: C

char x[]="main() { int j; putchar(99); putchar(104); putchar(97);putchar(114); putchar(32);putchar(120); putchar(91); putchar(93);putchar(61); putchar(34); for(j=0; j; main() { int j; putchar(99); putchar(104); putchar(97); putchar(114); putchar(32); putchar(120);putchar(91); putchar(93); putchar(61); putchar(34); for(j=0; j(x); ++j) putchar(x[j]);putchar(34); putchar(59); putchar(10); for(j=0 ; j(x); ++j) putchar(x[j]); putchar(10); }

Quote:

Author: Dave

Type the above program in just two lines, one for declaration of x and another for the main. The string x has the whole program instructions. Design your main to print the string which has the code statemets. The trickest part of writing quines is 'the statement which is used to print the code must also be printed'.

Lets see how it works.


The putchar statements before the first for loop print till

Code:

char x[] =”

The first for loop print the string contents.

Code:

main() { int j; putchar(99); putchar(104); putchar(97); putchar(114); putchar(32); putchar(120);putchar(91); putchar(93); putchar(61); putchar(34); for(j=0; j

The putchars in between the for loops print

Code:

“;

We have printed the declaration of x so far. The only task is left for us, to print the main program. This is taken care by the second for loop. The last putchar adds a newline into the output.

Quote:

The putchar statements recieves ASCII values of the characters. Replace the ASCII values and try with actual characters, ie replace putchar(99) by putchar('c'). You will come to know the difficulty of using characters directly.

Format specifiers


Another way of writing them is with the aid of format specifiers intelligently.

Code: C

main(){char q=34,n=10,*a="main(){char q=34,n=10,*a=%c%s%c;printfa,q,a,q,n);}%c";printf(a,q,a,q,n);}

Quote:

Author: John Burger, David Brill, Filip Machi0

The above program is one liner, the statement has to be focussed is printf only. It's not difficult to understand that the following contents are printed.

Code:

main(){char q=34,n=10, *a=

Now, replace the %c with double quotes(“) and %s with the string a and so on.... Hence the resultant printf statement will be as follows,

Code: C

printf(“main(){char q=34,n=10,*a=%c%s%c;printf(a,q,a,q,n);}%c”,q,”main(){char q=34,n=10,char *a=%c%s%c;printf(a,q,a,q,n)}”,q,n);

Macros


Here is another way of writing is using macros. The fact behind it upon substitution of macro, we will get a printf statement which dumps the actual code.

Code: C

#define T(a) main(){printf(a,#a);} T("#define T(a) main(){printf(a,#a);}\nT(%s)")

Quote:

Author: Joe Miller

Expand the macro for to understand the execution..


Palindromic Quines


It is awesome when I come to know about the following program. The program itself is palindrome as well as quine.

Code: C

/**/char q='"',*a="*//**/char q='%c',*a=%c%s%c*/};)b(stup;]d[b=]d-852[b)--d(elihw;)q,a,q,q,2+a,b(ftnirps{)(niam;031=d tni;]952[b,",b[259];int d=130;main(){sprintf(b,a+2,q,q,a,q);while(d--)b[258-d]=b[d];puts(b);}/*c%s%c%=a*,'c%'=q rahc/**//*"=a*,'"'=q rahc/**/

Quote:

Author: Dan Hoey

Winner of Worst Abuse of the Rules


Given below has won the 'Worst Abuse of the Rules Award' in 1994 Obfuscated C Contest.

Code: C

main(){char*a="main(){char*a=c%s%c%;printf(a+42,34,a,34);};)43,a,43,24+a(ftnirp;%c%s%c=a*rahc{)(niam";printf(a+42,34,a,34);}

Quote:

Author: smr

For more quines in your favorite languages, refer http://www.nyx.net/~gthompso/quine.htm


Here are my attempts

Type these programs as it is given... Don't even add/delete a single NEWLINE or SPACE or TAP characters

Code: C

// First Program #include h> main() { char *a = "#include %cmain()%c{%c%cchar *a = %c%s%c;%c%cprintf(a,10,10,10,9,34,a,34,10,9,10,10);%c}%c"; printf(a,10,10,10,9,34,a,34,10,9,10,10); } // Second Program #define print(s) (#s) main() { char *a = "printf(print(#define print(s) (#s)%cmain()%c{%c%cchar *a=%c%s%c;%c%c%s%c}%c),10,10,10,9,34,a,34,10,9,a,10,10);"; printf(print(#define print(s) (#s)%cmain()%c{%c%cchar *a=%c%s%c;%c%c%s%c}%c),10,10,10,9,34,a,34,10,9,a,10,10); } // Third Program #define T(a,b) strcat(a,b) main() { char s1[256] = "#define T(a,b) strcat(a,b)%cmain()%c{%c", s2[256] = "%cchar s1[256] = %c%s%c, s2[256] = %c%s%c, s3[256] = %c%s%c;%c%c%cprintf(T(s1,s2),10,10,10,9,34,s3,34,34,s2,34,34,s3,34,10,10,9,10,10);%c}%c", s3[256] = "#define T(a,b) strcat(a,b)%cmain()%c{%c"; printf(T(s1,s2),10,10,10,9,34,s3,34,34,s2,34,34,s3,34,10,10,9,10,10); }

I hope this article gives much better hopes in writing quines. To conclude, with little intelligency all of us can write quines.

Fast Algorithm for Computing Matrix Multiplication!!!!

Mostly people are using this algorithm to compute matrix multiplication:


Code: C

#define n 1000 int main() { int a[n][n],b[n][n],c[n][n]; c[0][0]=0; for( i=0;i) { for(j=0;j) { for(k=0;k) { c[i][j] = c[i][j] + a[i][k] * b[k][j] } } } return 0; }

In this program( a short algo) , every time we are taking one element of an array to catche and processing for it. Means At one time cpu reading one element value of a array and b Array and compute and store to c Array.


To reading every time elements from array , why we are taking some group of element i.e. Block size, then no need to read every element. A groups of element will be on catche and we can do fast as given above algo. This algorithm called " Block Algorithm". This Block algorithm can be applied many place where this type of situation will come.


Block Algorithm for Matrix Multiplication:

Code: C

#define n 1000 #define BlockSize 100 int main() { int a[n][n],b[n][n],c[n][n]; c[0][0]=0; for( i1=0;i1<(n/BlockSize);++i1) { for(j1=0;j1<(n/BlockSize);++j1) { for(k1=0;k1<(n/BlockSize);++k1) { for(i=i1=0;i(i1+BlockSize-1);++i) { for(j=j1=0;j(j1+BlockSize-1);++j) { for(k=k1;k(k1+BlockSize-1);++k) { c[i][j] = c[i][j] + a[i][k] * b[k][j] } } } } } } return 0; }

Decimal, Hex, Octal and Binary Number inter Conversion

Introduction

The article discusses about all the number formats viz Binary, Decimal, Octal, Hex and BCD (Binary coded decimal) and conversion from Decimal to Binary, Octal and Hex and also the reverse conversion.

Binary

A numbering system based on 2 in which 0 and 1 are the only available digits.

Decimal

decimal fraction: a proper fraction whose denominator is a power of 10

Octal

A numbering system that uses eight digits, 0 through 7. It is used as a shorthand system for representing binary characters that use six bits.

Hexa Decimal

A numbering system which uses a base of 16. The first ten digits are 0-9 and the next six are A-F.

Binary to Decimal


void Bin2Dec()
{
int bin,n,r,s=0,i;
printf("Enter a binary number\n");
scanf("%d",&bin);
n=bin;
for(i=0;n!=0;i++)
{
r=n%10;
s=s+r*(int)pow(2,i);
n=n/10;
}
printf("The equivalent number of %d is %d\n",bin,s);
}

Octal to Decimal


void Oct2Dec()
{
int oct,n,r,s=0,i;
printf("Enter an octal number\n");
scanf("%d",&oct);
n=oct;
for(i=0;n!=0;i++)
{
r=n%10;
s=s+r*(int)pow(8,i);
n=n/10;
}
printf("The equivalent number of %d is %d\n",oct,s);
}

Hex to Decimal


void Hex2Dec()
{
char hex[N];
int i,j,n[N],l;
long double dec=0;
printf("Enter the hexa decimal number and find it's decimal equivalent\n");
fflush(stdin);
gets(hex);
l=strlen(hex);
for(i=0;i=0;j--)
{
printf("%d",bin[j]);
}
printf("\n");
}

Decimal to Octal


void Dec2Oct()
{
int n,r[10],i;
printf("Enter a number to find it's octal equivalent\n");
scanf("%d",&n);
printf("The octal equivalent of %d is ",n);
for(i=0;n!=0;i++)
{
r[i]=n%8;
n=n/8;
}
i--;
for(;i>=0;i--)
printf("%d",r[i]);
printf("\n");
}

Decimal to Hex


void Dec2Hex()
{
int n,r[10],i;
printf("Enter a number to get its hexadecimal equivalent\n");
scanf("%d",&n);
for(i=0;n!=0;i++)
{
r[i]=n%16;
n=n/16;
}
i--;
for(;i>=0;i--)
{
if(r[i]==10)
printf("A");
else if(r[i]==11)
printf("B");
else if(r[i]==12)
printf("C");
else if(r[i]==13)
printf("D");
else if(r[i]==14)
printf("E");
else if(r[i]==15)
printf("F");
else
printf("%d",r[i]);
}
printf("\n");
}

Write a c Program to Replace a Substring by a New Substring.

fnReplaceString()
{
char acInpString[MAX_LENGTH],acOrig[MAX_LENGTH],acReplace[MAX_LENGTH];
char *pcInpStringPtr = acInpString;
char *pcOrigPtr = acOrig;
char *pcReplacePtr = acReplace;
char *pPos;
int iRes = 0;
int iCount = 0;
fflush(stdin);
system("clear");

/* gets the input string from user */
GET_STRING(acInpString);

printf("\n Enter substring to be replaced\n");
gets(acOrig);

printf("\n Enter Substring to be placed \n");
gets(acReplace);

/* check if substring to be replaced is present in entered string by user */
if(!(pPos=strstr(acInpString,acOrig)))
{
printf("\n SUBSTRING TO BE REPLACED NOT PRESENT IN GIVEN STRING \n");
}
else
{
char acTemp[MAX_LENGTH];
strncpy(acTemp,pcInpStringPtr,pPos-pcInpStringPtr);
sprintf(acTemp+(pPos-pcInpStringPtr), "%s%s", pcReplacePtr, pPos+strlen(pcOrigPtr));
puts(acTemp);

}
}

Write a C Program to Find out the Last Date of Modification.

Answer:

#include

#include

#include

void main()

{

struct stat status;

FILE *fp;

fp=fopen("test.txt","r");

fstat(fileno(fp),&status);

clrscr();

printf("Last date of modification : %s",ctime(&status.st_ctime));

getch();

}

Explanation:

Function int fstat(char *, struct stat *) store the information of open file in form of structure struct stat

Structure struct stat has been defined in sys\stat.h as

struct stat {

short st_dev, st_ino;

short st_mode, st_nlink;

int st_uid, st_gid;

short st_rdev;

long st_size, st_atime;

long st_mtime, st_ctime;

};

Here

(e)st_dev: It describe file has stored in which drive of your computer.

(f)st_mode: It describes various modes of file like file is read only, write only, folder, character file etc.

(g)st_size: It tells the size of file in byte.

(h)st_ctime:It tells last data of modification of the file in date format.

Function ctime convert date type in string format

Write the C Program Color Graphics Mode

Write the c program to switch the 256 color graphics mode ?.

Ans:
#include
#include
void main()
{
int x,y,b;
union REGS i,o;
i.h.ah=0;
i.h.al=0x13;
int86(0x10,&i,&o);
getch();
}

Write a c program to create a directory in current working directory?

Ans:
#include
void main()
{
union REGS i,o;
i.h.ah=0x39;
i.x.dx="lakshmi";
int86(0x21,&i,&o);
getch();
}

System Level Programming by C Program

Important structure and union:

The header file dos.h defines two important structures and one union. They are:

1. struct BYTEREGS {

unsigned char al, ah, bl, bh;

unsigned char cl, ch, dl, dh;

};

2. struct WORDREGS {

unsigned int ax, bx, cx, dx;

unsigned int si, di, cflag, flags;

};

3. union REGS {

struct WORDREGS x;

struct BYTEREGS h;

};

Note: Try to remember above structures and union.

There is also one very important function int86 () which has been defined in dos.h header file. It is general 8086 software interrupt interface. It will better to explain it by an example.

Write a c program to display mouse pointer?
Answer:

#include

#include

void main()

{

union REGS i,o;

i.x.ax=1;

int86(0x33,&i,&o);

getch();

}

Explanation: To write such program you must have one interrupt table. Following table is only small part of interrupt table.

This table consists for column. They are:

(1) Input

(2) Output

(3) Service number

(4) Purpose

Now look at the first row of interrupt table. To show the mouse pointer assign ax equal to 1 i.e. service number while ax is define in the WORDREGS

struct WORDREGS {

unsigned int ax, bx, cx, dx;

unsigned int si, di, cflag, flags;

};

And WORDRGS is define in the union REGS

union REGS {

struct WORDREGS x;

struct BYTEREGS h;

};

So to access the structure member ax first declare a variable of REGS i.e.

REGS i, o;

Note: We generally use i for input and o for output

To access the ax write i.x.ax (We are using structure variable i because ax is input

(See in the interrupt table)

So to show mouse pointer assign the value of service number to it:

i.x.ax=1;

To provide this information to microprocessor
we use int86 function. It has three parameters

1. Interrupt number i.e. 0x33

2. union REGS *inputregiste i.e. &i

3. union REGS *outputregiste i.e. &o;

So write: int86 (0x33, &i, &o);