nbangla

PSEUDOCODE ARTICULATION-BRIDGE-DFS-VISIT(G,u) time = time + 1 u.d = u.low = time u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) if u.d == 1 if G.Adj[u].size >= 2 AND v.low > u.d bridgeCounter = bridgeCounter + 1 bridge.push(edge(u,v)) else if v.low &gt u.d bridgeCounter = bridgeCounter + 1 bridge.push(edge(u,v)) u.low = min(u.low, v.low) else if u.π != v u.low = min(u.low, v.d) u.color = BLACK time = time + 1 u.f = time

PSEUDOCODE ARTICULATION-POINTS-DFS-VISIT(G,u) dfn = dfn + 1 u.d = u.low = dfn u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) if u.d == 1 if G.Adj[u].size >= 2 AND v.low > u.d articPointsList.push_front(u) else if v.low &gt= u.d articPointsList.push_front(u) u.low = min(u.low, v.low) else if u.π != v u.low = min(u.low, v.d) u.color = BLACK

Many algorithms that work with directed graphs begin with such a decomposition. After decomposing the graph into strongly connected components, such algorithms run separately on each one and then combine the solutions according to the structure of connections among components. ALGORITHM STRONGLY-CONNECTED-COMPONENTS(G) call DFS(G) to compute finishing times u.f for each vertex u compute GT call DFS(GT), but in the main loop of DFS, consider the verteces in order of decreasing u.f (as computed in line 2) output the vertices of each tree in the depth-first forest formed in line 4 as a separate strongly connected component

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) ALGORITHM TOPOLOGICAL-SORT(S) Find the indegree INDEG(N) of each node N of S. (This can be done by traversing each adjacency matrix.) Put in a queue all the nodes with zero indegree. Repeat Steps 5 and 6 until the queue is empty. Remove the front node N of the queue. Repeat the following for each neighbor M of the node N: (a) Set INDEG(M) := INDEG(M) - 1. [This deletes the edge from N to M.] (b) If INDEG(M) = 0, then: Add M to the rear of the queue. [End of loop.] [End of Step 3 loop.] Exit.

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.) PSEUDOCODE TOPOLOGICAL-SORT(G) call DFS(G) to compute finishing times v.f for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices

.:: PSEUDOCODE ::. DFS(G) for each vertex u ∈ G.V u.color = WHITE u.π = NIL time = 0 for each vertex u ∈ G.V if u.color == WHITE DFS-VISIT(G,u) DFS-VISIT(G,u) time = time + 1 u.d = time u.color = GRAY for each v ∈ G.Adj[u] if v.color == WHITE v.π = u DFS-VISIT(G,v) u.color = BLACK time = time + 1 u.f = time

Breadth-first search গ্রাফ অনুসন্ধানের জন্য একটি সহজ অ্যালগরিদম এবং অনেক গুরুত্বপূর্ণ গ্রাফ অ্যালগরিদমের জন্য এটি হচ্ছে মূল আদর্শ। Prim’s minimum-spanning tree অ্যালগরিদম এবং Dijkstra’s single-source shortest-paths অ্যালগরিদম Breadth-first search -এর আইডিয়াগুলি অনুসরন করে। .:: PSEUDOCODE ::. BFS(G,s) for each vertex u ∈ G.V - {s} u.color = WHITE u.d = ∞ u.π = NIL s.color = GRAY s.d = 0 s.π = NIL Q = ∅ ENQUEUE(Q,s) while Q ≠ ∅ u = DEQUEUE(Q) for each v ∈ G.Adj[u] if v.color == WHITE v.color = GRAY v.d = u.d + 1 v.π = u ENQUEUE(Q,v) u.color = BLACK

An Assembly Language program to read a upercase character from keyboard and print it's lowercase character on the screen. ♣ Try it out :: .model small .stack 100h .data .code main proc mov ax,@data mov ds,ax mov ah,1 int 21h add al,32 mov bl,al mov ah,2 mov dl,' ' int 21h mov ah,2 mov dl,bl int 21h mov ah,4ch int 21h main endp end main ♣ Sample Input and Output :: M m

An Assembly Language program to read a lowercase character from keyboard and print it's upercase character on the screen. ♣ Try it out :: .model small .stack 100h .data .code main proc mov ax,@data mov ds,ax mov ah,1 int 21h sub al,32 mov bl,al mov ah,2 mov dl,' ' int 21h mov ah,2 mov dl,bl int 21h mov ah,4ch int 21h main endp end main ♣ Sample Input and Output :: m M

An Assembly Language program to print a string "DaPrimitive Soource" on the screen. (USE: string output function) ♣ Try it out :: .model small .stack 100h .data msg db "DaPrimitive Soource",'$' .code main proc mov ax,@data mov ds,ax mov ah,9 mov dx, offset msg int 21h mov ah, 4ch int 21h main endp end main ♣ Sample Output :: DaPrimitive Soource

An assembly language program that will read a character from keyboard (console input without echo function) and print it on the screen. (USE: character output function) ♣ Try it out :: .model small .stack 100h .code main proc mov ah, 8 int 21h mov ah, 2 mov dl, al int 21h mov ah, 4ch int 21h main endp end main ♣ Sample Input and Output :: M

An assembly language program that will read a character from keyboard (console input with echo function) and print it on the screen. (USE: character output function) ♣ Try it out :: .model small .stack 100h .code main proc mov ah, 1 int 21h mov ah, 2 mov dl, al int 21h mov ah, 4ch int 21h main endp end main ♣ Sample Input and Output :: M M

136 Accepted View Problem UVA Problem: 136 - Ugly Numbers Time Limit: 3.00 Seconds Program Language: C++ Publisher: http://www.uvaonlinejudge.org ♣ Try it Out :: #include<iostream> using namespace std; int main() { int p,q,r, i=1, P,Q,R, ugly[1501]={0}; ugly[0]=1, p=q=r=0; while(ugly[1499] == 0) { P = ugly[p]*2; Q = ugly[q]*3; R = ugly[r]*5; if(P<Q && P<R) {ugly[i++]=P; p++;} else if(Q<P && Q<R) {ugly[i++]=Q; q++;} else if(R<P && R<Q) {ugly[i++]=R; r++;} else if(P == Q) {q++;} else if(P == R) {r++;} else if(R == Q) {r++;} } cout<<"The 1500'th ugly number is "<<ugly[1499]<<"."<<endl; return(0); } ♣ Source Codes :: 136 - Ugly Numbers.cpp 136 - Ugly Numbers.java আবূ হুরাইরাহ (রাঃ) হতে বর্ণিত আছে, তিনি বলেন, নবী (সাল্লাল্...

113 Accepted View Problem UVA Problem: 113 - Power of Cryptography Time Limit: 3.00 Seconds Program Language: C++ Publisher: http://www.uvaonlinejudge.org ♣ Try it Out :: #include<iostream> #include<cstdlib> #include<cstdio> #include<cmath> using namespace std; int main() { //freopen("113.in", "r", stdin); double n, p; while(cin>>n>>p) printf("%.0lf\n", pow(p,1/n)); return(0); } ♣ Source Codes :: 113 - Power of Cryptography.cpp 113 - Power of Cryptography.java

299 Accepted View Problem UVA Problem: 299 - Train Swapping Time Limit: 3.00 Seconds Program Language: C++ Publisher: http://www.uvaonlinejudge.org ♣ Try it Out :: #include<iostream> #include<cstdio> #include<cstdlib> #define FOR(i,n) for(int i=0; i<n; i++) using namespace std; int InsertionSort(int[], int); int main() { //freopen("299.in", "r", stdin); int N, Len; cin>>N; FOR(i,N) { cin>>Len; int Arr[Len]; FOR(j,Len) cin>>Arr[j]; cout<<"Optimal train swapping takes "<<InsertionSort(Arr,Len)<<" swaps."<<endl; } return 0; } int InsertionSort(int A[], int len) { int i, j, key, swaps = 0; for(j = 1; j <= len-1; j++) { key = A[j]; i = j - 1; while(i >= 0 && A[i] > key) { A[i+1] = A[i]; i--, ...

♣ Try it Out :: #include<stdio.h> #include<conio.h> int strLen(char *str) { int len=0; for(int i=0; str[i]!='\0'; i++) len++; return len; } int main() { char a[100]; printf("Please enter a word: "); scanf("%s", a); int L = strLen(a); printf("\nLenght = %d", L); getch(); return 0; } ♣ Output :: Please enter a word: Muhit Lenght = 5 ♣ Downloads :: Download source code Download executable file

♣ The Algorithm :: Compute the initial values: dx = x 2 - x 1 Inc 2 = 2(dy - dx) dy = y 2 - y 1 d = Inc 1 - dx Inc 1 = 2dy Set (x,y) equal to the lower left-hand endpoint and x end equal to the largest value of x. If dx < 0, then x = x 2 , y = y 2 , x end = x 1 . If dx > 0, then x = x 1 , y = y 1 , x end = x 2 . Plot a point at the current (x,y) coordinates. Test to see whether the entire line has been drawn. If x = x end , stop. Compute the location of the next pixel. If d < 0, then d = d + Inc 1 . If d &gte; 0, then d = d + Inc 2 , and then y = y + 1. Increment x: x = x + 1. Plot a point at the current (x,y) coordinates. Go to step 4. ♣ C / C++ Code :: void BresenhamsLine(int x1, int y1, int x2, int y2) { int dx, dy, Inc1, Inc2, d, x, y, xend; dx = x2-x1; dy = y2 - y1; Inc1 = 2*dy; Inc2 = 2*(dy - dx); d = Inc1 - dx; if(dx < 0) { x=x2, y=y2, xend=x1; } else ...

♣ The Algorithm :: ♣ C / C++ Code :: void NormalLine(int x1, int y1, int x2, int y2) { int dx, dy, b, x, y, xend; float m; dx = x2 - x1; dy = y2 - y1; m = (float) dy / dx; b = y1 - m*x1; if(dx < 0) { x=x2, y=y2, xend=x1; } else if(dx > 0) { x=x1, y=y1, xend=x2; } while(x <= xend) { putpixel(x,y, LIGHTMAGENTA); x++; y = m*x + b; } } ♣ JAVA Code :: ♣ Source Codes :: Normal line algorithm.cpp Normal line algorithm.java আবদুল্লাহ বিন ওমার (রাঃ) হতে বর্ণিত। 'রসূলুল্লাহ (সঃ) বলেছেনঃ তোমাদের কেউ নামায পড়লে সে যেন তার দু'কাপড়ে নামায পড়ে। সৌন্দর্য প্রকাশের অগ্রাধিকার আল্লাহর জন্যই।' (তাহাওয়ী, বায়হাকী, তাবরানী)

♣ The Algorithm :: ♣ C / C++ Code :: void BresenhamsCircle(int h, int k, int r) { int x = 0, y = r; int d = 3 - 2*r; while(x <= y) { putpixel(x+h, y+k, MAGENTA); putpixel(y+h, x+k, MAGENTA); putpixel(-y+h, x+k, MAGENTA); putpixel(-x+h, y+k, MAGENTA); putpixel(-x+h, -y+k, MAGENTA); putpixel(-y+h, -x+k, MAGENTA); putpixel(y+h, -x+k, MAGENTA); putpixel(x+h, -y+k, MAGENTA); if(d < 0){ d += 4*x+6; x++; } else if(d >= 0) { d += 4*(x-y)+10; x++, y--; } } } ♣ JAVA Code :: ♣ Source Codes :: Bresenham's circle algorithm.cpp Bresenham's circle algorithm.java আবদুল্লাহ বিন ওমার (রাঃ) হতে বর্ণিত। 'রসূলুল্লাহ (সঃ) বলেছেনঃ তোমাদের কেউ নামায পড়লে সে যেন তার দু'কাপড়ে নামায পড়ে। সৌন্দর্য প্রকাশের অগ্রাধিকার আল্লাহর জন্যই।' (তাহাওয়ী, বায়হাকী, তাবরানী)

♣ Try it Out :: #include<iostream> #include<cstdlib> #include<cstdio> #define FOR(i,N) for(int i=1;i<=N;i++) #define MAX 51 using namespace std; class CacheMemory { public: string process; int burst_time, arrival_time; } P[MAX]; void sortByBurst_time(int nop) { FOR(i,nop) for(int j=i+1; j<=nop; j++) if(P[i].burst_time > P[j].burst_time) swap(P[i], P[j]); } int a_time[MAX], INF = 99999999; void sortArrival_time(int n) { FOR(i,n) for(int j=i+1; j<=n; j++) if(a_time[i] > a_time[j]) swap(a_time[i], a_time[j]); } int main() { //freopen("sjfs_p.in", "r", stdin); int n; cin>>n; FOR(i,MAX) a_time[i] = INF; FOR(i,n) { cin>>P[i].process>>P[i].arrival_time>>P[i].burst_time; a_time[i] = P[i].arrival_time; } sortByBurst_time(n); sortArrival_time(n); FOR(i,n) if(P[i]...