what is the Complexity of Bubble Sort?

Complexity of Bubble Sort : The time for a sorting algorithm is measured in terms of the number of comparisons. The number f(n) of comparisons in the bubble sort is easily computed.Specially, there are n - 1 comparisons during the first pass, which places the largest element in the last position; there are n - 2 comparisons in the second step, which places the second largest element in the next-to-last position; and so on.  Thus f(n) = (n-1)...

Read More

/* Another Methods of Traversing in a Linear Array  */ #include<stdio.h>         /* Header File that are called standard input output*/ #include<conio.h>        /* Header File that are called consol input output*/ void main(){       /*start the main function and void that are not return type*/ clrscr();            /* Clear the screen at every time when input new element*/ int...

Read More

Traversing in a Linear Array

/* Traversing in a Linear Array  */ #include<stdio.h>         /* Header File that are called standard input output*/ #include<conio.h>        /* Header File that are called consol input output*/ void main(){       /*start the main function and void that are not return type*/ clrscr();            /* Clear the screen at every time when input new element*/ int LA[] = {5,6,7,8,3};  ...

Read More

Procedure P2.9A : CROSSOUT(A, N, K)

1.  If A[K] = 1, then : Return. 2.  Repeat for L = 2K to N by K: Set A[L] : 1. [End of loop] 3. Return. If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOL...

Read More

Complexity;Space-Time Tradeoffs

Briefly describe the notations of (a) the complexity of an algorithm and (b) the space-time tradeoff of algorithms  : (a)  The complexity of an algorithm is a function f(n) which measures the time and/or space used by an algorithm in terms of the input size n. (b) The space-time tradeoff refers to a choice between algorithmic solutions of a data processing problem that allows one to decrease the running time of an algorithmic solution by increasing the space to store the data and vice versa. If You want to learn about the technology,...

Read More

Program to convert an Expression from Infix to Postfix

#include<stdio.h> #include<stdlib.h> #define MAXCOLS 80 #define TRUE 1 #define FALSE 0 void postfix(char*, char *); int isoperand(char); void popandtest(struct stack*, char*, int*); int prcd(char, char); void push(struct stack*, char); char pop(struct stack*); void main(){ char infix[MAXCOLS]; char postr[MAXCOLS]; int pos = 0; while ((infix[pos++] = getchar()) != '\n' ); infix[--pos]='\0'; printf("%s%s", "the original infix expression is", infix); postfix(infix, postr); printf("%s\n", postr); }   /* end of main */ If...

Read More

Using One-Dimensional Arrays Of C Programming Language

#define NUMELTS 100 void main(){         int num[NUMELTS ];                        /*   array of numbers     */     int i;     int total;                                           ...

Read More

Evaluation of Postfix Expression

Evaluation of Postfix Expression :  Algorithm :  1. Add a right parenthesis ")" at the end of P.   [This acts as a sentinel] 2. Scan P from left to right and repeat Steps 3 and 4 for each element of P until the sentinel ")" is encountered. 3. If an operand is encountered, put it on STACK. 4. If an operator  is encountered, then : (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element.. (b) Evaluate B A (c) Place the result of (b) back on STACK. [End...

Read More

Arithmetic Expressions;Polish Notation

Arithmetic Expressions;Polish Notation :  Highest : Exponentiation Next Highest : Multiplication (*) and Division(/) Lowest : Addition(+) and Subtruction(-) If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SO...

Read More

Two-Way Header Lists

Two-Way Header Lists:   The advantages of a two-way list a circular header list may be combined into a two-way circular header list as .  The list is circular because the two end nodes point back to the header node.Observe that such a two-way list requires only one list pointer variable START, which points to the header node. This is because the two pointers in the header node point to the two ends of the list. If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning...

Read More

Inserting into a Sorted Linked List

Inserting into a Sorted Linked List:   Suppose ITEm is to be inserted into a sorted linked LIST.  Then ITEM must be inserted between nodes A and B so that                                                    INFO(A) < ITEM <= INFO(B) The following is a procedure which finds...

Read More

Deletion Algorithms

Deletion Algorithms: Algorithms which delete nodes from linked lists come up in various situations. We discuss two of them here. The first one deletes the node following a given node, and the second one deletes the node with a given ITEM of information. All our algorithms assume that the linked list is in memory in the form LIST(INFO, LINK, START, AVAIL). All of our deletion algorithms will return the memory space of the deleted node N to the beginning of the AVAIL list.  Accordingly,  all of our algorithms will include the following...

Read More

COPY(INFO, LINK, NAME1, NAME2, AVAIL)

COPY(INFO, LINK, NAME1, NAME2, AVAIL) This algorithm makes a copy of a list NAME1 using NAME2 as the list pointer variable of the new list. 1.     Set NAME2 : = NULL.   [Forms empty  list] 2.   [NAME1 empty?]  If NAME1 = NULL, then: Exit. 3.    [Insert first node of NAME1 into NAME2]        Call INSLOC(INFO, LINK, NAME2, AVAIL, NULL, INFO[NAME1]) or : (a)  If AVAIL = NULL, then : Write : OVERFLOW, and Exit. (b) Set NEW :  =...

Read More

Insertion Algorithms

Insertion Algorithms: (a)  Checking to see if space is available in the AVAIL list.  If not, that is, if AVAIL = NULL, then the algorithm will print the message OVERFLOW. (b)  Removing the first node from the AVAIL list.Using the variable NEW to keep track of the location of the new node, the step can be implemented by the pair of assignments NEW : = AVAIL,      AVAIL : = LINK[AVAIL] (c)  Copying new information into the new node.                                  ...

Read More

INSERT(INFO, LINK, START, AVAIL, ITEM)

Algorithm: INSERT(INFO, LINK, START, AVAIL, ITEM) This algorithm inserts ITEM into a sorted linked list. 1.   [Use Procedure FINDA to find location of the node preceding ITEM]   Call FINDA(INFO, LINK, START, ITEM, LOC) 2.  [Use Algorithm INSLOC to insert ITEM after the node with location LOC.]   Call INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) 3. Exit If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOL...

Read More

FINDA(INFO, LINK, START, ITEM, LOC)

FINDA(INFO, LINK, START, ITEM, LOC) This procedure finds the location LOC of the last node in a sorted list such that INFO[LOC] < ITEM, or sets LOC = NULL. 1.  [List of empty?]   If START = NULL, then : Set LOC : = NULL, and Return. 2.   [Special case?]  If ITEM <  INFO[START], then : Set LOC : = NULL, and Return. 3.  Set SAVE : = START and PTR : = LINK[START].     [Initializes pointers] 4.  Repeat Steps  5 and 6 while PTR != NULL. 5.  If ITEM <...

Read More

DELLOCHL(INFO, LINK, START, AVAIL, ITEM)

DELLOCHL(INFO, LINK, START, AVAIL,  ITEM) 1.  [Use Procedure FINDBHL to find the location of N and its preceding node.]   Call LINDBHL(INFO, LINK, START, ITEM, LOC, LOCP). 2.  If LOC = NULL, then : Write: ITEM not in list, and Exit. 3.  Set LINK[LOCP] : = LINK[LOC].   [Deletes node.] 4.  [Return deleted node to the AVAIL list.]     Set LINK[LOC] : = AVAIL and AVAIL : = LOC. 5.  Exit. If You want to learn about the technology, computer science & engineering, web...

Read More

FINDBHL(INFO, LINK, START, ITEM, LOC, LOCP)

Procedure: FINDBHL(INFO, LINK, START, ITEM, LOC, LOCP) 1.  Set SAVE : = START and PTR : = LINK[START].  [Initializes pointer]. 2. Repeat while INFO[PTR] != ITEM and PTR != START.    Set SAVE : = PTR and PTR : = LINK[PTR].  [Updates Pointers] [End of loop] 3.  If INFO[PTR] = ITEM, then:    Set LOC : = PTR and LOCP : = SAVE. Else:  Set LOC : = NULL and LOCP : = SAVE. [End of If structure] 4.  Exit. If You want to learn about the technology, computer science & engineering,...

Read More

SRCHHL(INFO, LINK, START, ITEM, LOC)

Algorithm: SRCHHL(INFO, LINK, START, ITEM, LOC) LIST is a circular header list in memory. This algorithm finds the location LOC of the node where ITEM first appears in LIST or sets LOC = NULL. 1.   Set PTR : = LINK[START] 2.  Repeat while INFO[PTR] != ITEM and PTR != START:    Set PTR : = LINK[PTR].    [PTR now points to the next node] [End of loop] 3.  If INFO[PTR] = ITEM, then: Set LOC : = PTR. Else : Set LOC : = NULL. [End of structure.] 4.Exit If You want to learn about...

Read More

Traversing a Circular Header List

(Traversing a Circular Header List)  Let LIST be a circular header list in memory.  This algorithm traverses LIST, applying an operation PROCESS to each node of LIST. 1.   Set PTR : = LINK[START].   [Initializes the pointer PTR] 2.   Repeat Steps 3 and 4 while PTR != START 3.   Apply PROCESS to INFO[PTR]. 4.  Set PTR : = LINK[PTR].   [PTR now points to the next node] [End of Step 2 loop.] 5. Exit. If You want to learn about the technology, computer science & engineering,...

Read More

Traversing a Circular Header List

(Traversing a Circular Header List)  Let LIST be a circular header list in memory.  This algorithm traverses LIST, applying an operation PROCESS to each node of LIST. 1.   Set PTR : = LINK[START].   [Initializes the pointer PTR] 2.   Repeat Steps 3 and 4 while PTR != START 3.   Apply PROCESS to INFO[PTR]. 4.  Set PTR : = LINK[PTR].   [PTR now points to the next node] [End of Step 2 loop.] 5. Exit. If You want to learn about the technology, computer science & engineering,...

Read More

DELETION FROM A LINKED LIST

DELETION FROM A LINKED LIST :   Let LIST be a linked list with a node N between nodes A and B Suppose node N is to be deleted from the linked list.The schematic diagram of such a deletion appears.The deletion occurs as soon as the nextpointer field of node A is changed so that it points to node B. Suppose our linked list is maintained in memory in the form                    LIST(INFO, LINK, START, AVAIL) When a node N is deleted from...

Read More

DELETION FROM A LINKED LIST

DELETION FROM A LINKED LIST :   Let LIST be a linked list with a node N between nodes A and B Suppose node N is to be deleted from the linked list.The schematic diagram of such a deletion appears.The deletion occurs as soon as the nextpointer field of node A is changed so that it points to node B. Suppose our linked list is maintained in memory in the form                    LIST(INFO, LINK, START, AVAIL) When a node N is deleted from...

Read More

Inserting after a Given Node

Algorithm:  INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC = NULL. 1.         [OVERFLOW?]  If AVAIL = NULL,  then:  Write:  OVERFLOW, and Exit. 2.      [Remove first node from AVAIL list.] 3.   Set INFO[NEW] : = ITEM.    [Copies new data into new node.] 4.  If LOC = NULL, then:   [Insert as first node.]        ...

Read More

Inserting after a Given Node

Algorithm:  INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC = NULL. 1.         [OVERFLOW?]  If AVAIL = NULL,  then:  Write:  OVERFLOW, and Exit. 2.      [Remove first node from AVAIL list.] 3.   Set INFO[NEW] : = ITEM.    [Copies new data into new node.] 4.  If LOC = NULL, then:   [Insert as first node.]        ...

Read More

Inserting at the Beginning of a List

Algorithm:   INSFIRST(INFO,  LINK,  START, AVAIL, ITEM) This algorithm inserts ITEM as the first node in the list. 1.     [OVERFLOW?]  If AVAIL = NULL , then : Write: OVERFLOW, and Exit. 2.   [Remove first node from AVAIL list. ]    Set NEW : = AVAIL and AVAIL : = LINK[AVAIL]. 3.  Set INFO[NEW] : = ITEM.  [Copies new data into new node] 4.  Set LINK[NEW] : = START.      [New node now points to original first node.] 5. ...

Read More

Inserting at the Beginning of a List

Algorithm:   INSFIRST(INFO,  LINK,  START, AVAIL, ITEM) This algorithm inserts ITEM as the first node in the list. 1.     [OVERFLOW?]  If AVAIL = NULL , then : Write: OVERFLOW, and Exit. 2.   [Remove first node from AVAIL list. ]    Set NEW : = AVAIL and AVAIL : = LINK[AVAIL]. 3.  Set INFO[NEW] : = ITEM.  [Copies new data into new node] 4.  Set LINK[NEW] : = START.      [New node now points to original first node.] 5. ...

Read More

Deleting the Node Following a Given Node

Algorithm: DEL(INFO,  LINK,  START,  AVAIL,  LOC,  LOCP) This algorithm deletes the node N with location LOC,  LOCP is the location of the node which precedes N or , where N is the first node,  LOCP = NULL. 1.   If LOCP = NULL, then:     Set START : = LINK[START].     [Deletes first node] Else:         Set LINK[LOCP]  : = LINK[LOC].    [Delete node N.] [End of structure .] 2.     ...

Read More

Deleting the Node Following a Given Node

Algorithm: DEL(INFO,  LINK,  START,  AVAIL,  LOC,  LOCP) This algorithm deletes the node N with location LOC,  LOCP is the location of the node which precedes N or , where N is the first node,  LOCP = NULL. 1.   If LOCP = NULL, then:     Set START : = LINK[START].     [Deletes first node] Else:         Set LINK[LOCP]  : = LINK[LOC].    [Delete node N.] [End of structure .] 2.     ...

Read More

Deleting the Node with a Given ITEM of Information

Procedure:   DELETE(INFO, LINK, START, AVAIL, ITEM) This algorithm deletes from a linked list the first node N which contains given ITEM of information. 1.  [Use procedure FINDB to find the location of N and its preceding node.] Call FINDB(INFO, LINK, START, ITEM, LOC, LOCP) 2.    If LOC  = NULL, then : write : ITEM not in list, and Exit. 3.  [Delete node.]    If LOCP = NULL, then:     Set START : = LINK[START].    [Delete first node] Else :   ...

Read More

Deleting the Node with a Given ITEM of Information

Procedure:   FINDB(INFO, LINK, START, ITEM, LOC, LOCP) This procedure finds the location LOC of the first node N which contains ITEM and the location LOCP of the node preceding N. If ITEM does not appear in the list, then the procedure sets LOC = NULL; and if ITEM appears in the first node, the it sets LOCP = NULL. 1.        [List empty?]  If START = NULL, then:                Set   LOC: = NULL and LOCP : =...

Read More