Fractional knapsack for report
A draft report has five chapters. The table shows the lengths of the chapters & their importance where the scale is from 1(low) to 10(high). The report must be at most 600 pages long. The problem is to edit the report so that the overall importance is maximized. Implement the fractional knapsack algorithm using Greedy […]
AVL Tree
Copy code Algorithm Input A tree rooted at root. Output Tree after insertion of node. Complexity O(logn) AVL Insertion AVL insert (root) if item <info[root] then AVL insert(left[root]) else AVL insert(right[root]) if (root = null) Temp[info]=item; Temp =root; if (left[root]=null and right[root]=null) then Root [info]=item; if (item <info [root] ) then Left [root] =temp; if […]
Convex hull
Copy code Algorithm Input Set S of points. Output Set of points which form convex hull . Complexity O(nlgn) Convex hull(S: set of points {P = (P.x,P.y)}): Select the rightmost lowest point P0 in S. Sort S angularly about P0 as a center. For ties, discard the closer points. Let P[N] be the sorted array […]
Bellman Ford Problem
Copy code Algorithm Input Graph (G). Output Sorted path from source to destination . Complexity O(VE). Initialize (G, s) 1 for each vertex v in V[G] 2 do d[v]= ∞ 3 parent[v] =NIL 4 d[s] =0 Relax (u, v, w) 1 if d[v] > d[u] + w (u, v) 2 then d[v] = d[u] + […]
Operations on binomial heaps
Copy code Algorithm Algorithm to find minimum Input Binomial heap . Output pointer of minimum key Complexity O(lgn). BINOMIAL-HEAP-MINIMUM(H) 1 y= NIL 2 x = head[H] 3 min = ∞ 4 while x ≠ NIL 5 do if key[x] < min 6 then min = key[x] 7 y =x 8 x = sibling[x] 9 return […]
Operations on fibonacci heaps
Copy code Algorithm Algorithm for insertion Input Fibonacci heap. Output Fibonacci heap after insertion Complexity O(l). FIB-HEAP-INSERT(H, x) 1 degree[x] = 0 2 p[x] =NIL 3 child[x] = NIL 4 left[x] =x 5 right[x] = x 6 mark[x] = FALSE 7 concatenate the root list containing x with root list H 8 if min[H] = […]
Jugs
In the movie “Die Hard 3″, Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle. You have two jugs, A and B, and an infinite […]
Searching quickly
Searching and sorting are part of the theory and practice of computer science. For example, binary search provides a good example of an easy-to-understand algorithm with sub-linear complexity. Quicksort is an efficient O(nlogn) [average case] comparison based sort. KWIC-indexing is an indexing method that permits efficient “human search” of, for example, a list of titles. […]
Following orders
Order is an important concept in mathematics and in computer science. For example, Zorn’s Lemma states: “a partially ordered set in which every chain has an upper bound contains a maximal element.” Order is also important in reasoning about the fix-point semantics of programs. This problem involves neither Zorn’s Lemma nor fix-point semantics, but does […]
Numbering Paths
Problems that process input and generate a simple “yes” or “no” answer are called decision problems. One class of decision problems, the NP-complete problems, are not amenable to general efficient solutions. Other problems may be simple as decision problems, but enumerating all possible “yes” answers may be very difficult (or at least time-consuming). This problem […]
Software CRC
You work for a company which uses lots of personal computers. Your boss, Dr Penny Pincher, has wanted to link the computers together for some time but has been unwilling to spend any money on the Ethernet boards you have recommended. You, unwittingly, have pointed out that each of the PCs has come from the […]
Roman Roulette
The historian Flavius Josephus relates how, in the Romano-Jewish conflict of 67 A.D., the Romans took the town of Jotapata which he was commanding. Escaping, Jospehus found himself trapped in a cave with 40 companions. The Romans discovered his whereabouts and invited him to surrender, but his companions refused to allow him to do so. […]
Ugly Numbers
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the 1500’th ugly number. Input and Output There is no […]
Run, Run, Runaround Numbers
An N-digit runaround number is characterized as follows: It is an integer with exactly N digits, each of which is between 1 and 9, inclusively. The digits form a sequence with each digit telling where the next digit in the sequence occurs. This is done by giving the number of digits to the right of the digit where […]
The Seasonal War
The inhabitants of Tigerville and Elephantville are engaged in a seasonal war. Last month, Elephantville successfully launched and orbited a spy telescope called the Bumble Scope. The purpose of the Bumble Scope was to count the number of War Eagles in Tigerville. The Bumble Scope, however, developed two problems because of poor quality control during […]
Pesky Palindromes
Pesky Palindromes A palindrome is a sequence of one or more characters that reads the same from the left as it does from the right. For example, Z, TOT and MADAM are palindromes, but ADAM is not. Your job, should you choose to accept it, is to write a program that reads a sequence of […]
The Bases are Loaded
The Bases Are Loaded Write a program to convert a whole number specified in any base (2..16) to a whole number in any other base (2..16). “Digits” above 9 are represented by single capital letters; e.g. 10 by A, 15 by F, etc. Each input line will consist of three values. The first value will […]
Let Me Count The Ways
Let Me Count The Ways After making a purchase at a large department store, Mel’s change was 17 cents. He received 1 dime, 1 nickel, and 2 pennies. Later that day, he was shopping at a convenience store. Again his change was 17 cents. This time he received 2 nickels and 7 pennies. He began […]
Hi-Q
Hi-Q is a popular solitaire game that comes in a small box with a playing board that has little holes in the shape of a cross and 32 little pegs that fit into the holes. Starting with the centermost hole open, players move the pegs by jumping one peg over another, either in a horizontal […]
Call Forwarding
Call Forwarding Thanks to computer technology the functionality of phone systems has been greatly enhanced in the last ten years. We have automated menus, sophisticated answering machines, conference call capabilities, group addressing and so on. A common feature of a company’s phone system is the ability to set call forwarding. For example, if Bob at […]
Basically Speaking
Basically Speaking The Really Neato Calculator Company, Inc. has recently hired your team to help design their Super Neato Model I calculator. As a computer scientist you suggested to the company that it would be neato if this new calculator could convert among number bases. The company thought this was a stupendous idea and has […]
Polynomial Showdown
Polynomial Showdown Given the coefficients of a polynomial from degree 8 down to 0, you are to format the polynomial in a readable format with unnecessary characters removed. For instance, given the coefficients 0, 0, 0, 1, 22, -333, 0, 1, and -1, you should generate an output line which displays x^5 + 22x^4 – 333x^3 […]
Board Silly
Board Silly You are a member of a team of programmers whose task is to write a board game. Your job is to write the part that examines a board layout and enumerates all possible moves for a given player. The game you are writing is played on an 8 by 8 grid of squares […]
Just the Facts
The expression N!, read as “N factorial,” denotes the product of the first N positive integers, where N is nonnegative. So, for example, N N! 0 1 1 1 2 2 3 6 4 24 5 120 10 3628800 For this problem, you are to write a program that can compute the last non-zero digit of any factorial for ( ). For […]
Equation Elation
Equation Elation The author of an elementary school algebra text book has approached you to write a program to solve simple algebra equations. The author wants to use a program to avoid human errors in preparing the solutions manual. The text book author will provide a text file of the simple problems for your problem […]
Word Index
Word Index Encoding schemes are often used in situations requiring encryption or information storage/transmission economy. Here, we develop a simple encoding scheme that encodes particular types of words with five or fewer (lower case) letters as integers. Consider the English alphabet {a,b,c,…,z}. Using this alphabet, a set of valid words are to be formed that are in […]
Integer Inquiry
Integer Inquiry One of the first users of BIT’s new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking various sums of those numbers. “This supercomputer is great,” remarked Chip. “I only wish Timothy were here to see these results.” (Chip moved […]
Circumference of the Circle
The Circumference of the Circle To calculate the circumference of a circle seems to be an easy task – provided you know its diameter. But what if you don’t? You are given the cartesian coordinates of three non-collinear points in the plane. Your job is to calculate the circumference of the unique circle that intersects […]
Knight Moves
Knight Moves A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of […]
Eeny Meeny Moo
Eeny Meeny Moo Surely you have made the experience that when too many people use the Internet simultaneously, the net becomes very, very slow. To put an end to this problem, the University of Ulm has developed a contingency scheme for times of peak load to cut off net access for some cities of the […]
Matrix Chain Multiplication
Matrix Chain Multiplication Suppose you have to evaluate an expression like A*B*C*D*E where A,B,C,D and E are matrices. Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. However, the number of elementary multiplications needed strongly depends on the evaluation order you choose. For example, let A be a 50*10 matrix, […]
Encoder and Decoder
Encoder and Decoder Being in charge of the computer department of the Agency of International Espionage, you are asked to write a program that will allow a spy to encode and decode their messages. You can assume a spy’s message is at most 80 characters long, and it includes all the upper and lowercase letters […]
Marvelous Mazes
Marvelous Mazes Your mission, if you decide to accept it, is to create a maze drawing program. A maze will consist of the alphabetic characters A-Z, * (asterisk), and spaces. Input and Output Your program will get the information for the mazes from the input file. This file will contain lines of characters which your program must interpret […]
Kibbles `n’ Bits `n’ Bits `n’ Bits
Kibbles `n’ Bits `n’ Bits `n’ Bits A certain frazzled programmer is writing a program that receives two numbers at a time in hexadecimal form, performs an addition or subtraction on them, and outputs the result in decimal form. However, the binary representation of the hexadecimal numbers also needs to be output, in the exact […]
Population Explosion
Population Explosion You just received a call from NASA’s chief scientist who is working on a habitable structure to be built on the moon. He has designed various models of enclosed cities that people could live in, but he is unsure as to how these models will stand up to population growth. Therefore, since your […]
Maximum Sum
Background A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In […]
History Grading
Background Many problems in Computer Science involve maximizing some measure according to constraints. Consider a history exam in which students are asked to put several historical events into chronological order. Students who order all the events correctly will receive full credit, but how should partial credit be awarded to students who incorrectly rank one or […]
Tree Summing
Background LISP was one of the earliest high-level programming languages and, with FORTRAN, is one of the oldest languages currently being used. Lists, which are the fundamental data structures in LISP, can easily be adapted to represent other important data structures such as trees. This problem deals with determining whether binary trees represented as LISP […]
Climbing Trees
Background Expression trees, B and B* trees, red-black trees, quad trees, PQ trees; trees play a significant role in many domains of computer science. Sometimes the name of a problem may indicate that trees are used when they are not, as in the Artificial Intelligence planning problem traditionally called the Monkey and Bananas problem. Sometimes trees […]
Unidirectional TSP
Background Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) — finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit […]
Postal Worker Rings Once
Graph algorithms form a very important part of computer science and have a lineage that goes back at least to Euler and the famous Seven Bridges of Königsberg problem. Many optimization problems involve determining efficient methods for reasoning about graphs. This problem involves determining a route for a postal worker so that all mail is delivered while […]
Mutant Flatworld explorers
Copy code C Code #include<stdio.h> #define MAXN 52 char Grid[MAXN][MAXN]; char Cmd[110]; char Side[] = “WNES”; int X[] = {0, -1, 0, 1}; int Y[] = {-1, 0, 1, 0}; int D[5]; int R, C; void Ini() { int i; for(i = 0; Side[i]; i++) { D[Side[i]] = i; } } void Move(int r, int […]
Stack of Flapjacks
Copy code C Code #include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 32 int St[MAXN],Or[MAXN]; int N; char str[10000]; int com(const void *a, const void *b) { return *(int *)a – *(int *)b; } int Search(int end, int key) { int i; for(i = 0; i<= end; i++) { if(St[i] == key) break; } return N-i; } int […]
Poker Solitaire Evaluator
Input The input will contain several test cases. First line of the input is the an integer which indicate the number of test case followed by a blank line. Each consecutive test case will also separated by a blank line. Each test case gets 25 cards, 5 cards per line. Each card consists of two characters. […]
Project Scheduling
An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, “carthorse” is an anagram of “orchestra”. Blanks within a phrase are ignored in forming anagrams. Thus, “orchestra” and “horse cart” are also anagrams. Write a program that reads a list of phrases and prints all pairs […]
Linear Cellular Automata
A biologist is experimenting with DNA modification of bacterial colonies being grown in a linear array of culture dishes. By changing the DNA, he is able “program” the bacteria to respond to the population density of the neighboring dishes. Population is measured on a four point scale (from 0 to 3). The DNA information is […]
Overflow
Write a program that reads an expression consisting of two non-negative integer and an operator. Determine if either integer or the result of the expression is too large to be represented as a “normal” signed integer (type integer if you are working Pascal, type int if you are working in C). Input An unspecified number of lines. Each line […]
Mirror, Mirror
A square pattern of light and dark cells is shown in its original state and a transformed state. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations: 90 Degree Rotation: The pattern was rotated to the right 90 degrees. 180 […]
Wetlands of Florida
A construction company owns a large piece of real estate within the state of Florida. Recently, the company decided to develop this property. Upon inspection of the property, however, it was revealed that the land, at various locations, contained bodies of water. This came as a shock to the owners of the company, for they […]
Heads Tails Probability
The probability of n heads in a row tossing a fair coin is 2–n. Calculate the probability for any positive integer n ( 0 Input A list of valid values of n (one per line). Output Print a table of n and 2–n in the following for the given values of n, using the following format: 2^-n = z.xxxe-y where z is a nonzero decimal digit, each x is a decimal […]
What Goes Up
Write a program that will select the longest strictly increasing subsequence from a sequence of integers. Input The input file will contain a sequence of integers (positive, negative, and/or zero). Each line of the input file will contain one integer. Output The output for this program will be a line indicating the length of the longest subsequence, […]
Permutation Arrays
In many computer problems, it is necessary to permute data arrays. That is, the data in an array must be re-arranged in some specified order. One way to permute arbitrary data arrays is to specify the permutations with an index array to point out the position of the elements in the new array. Let x […]
The Department of Redundancy Department
Write a program that will remove all duplicates from a sequence of integers and print the list of unique integers occuring in the input sequence, along with the number of occurences of each. Input The input file will contain a sequence of integers (positive, negative, and/or zero). The input file may be arbitrarily long. Output […]
Pascal s Triangle of Death
In this problem, you are asked to generate Pascal’s Triangle. Pascal’s Triangle is useful in many areas from probability to polynomials to programming contests. It is a triangle of integers with “1” on top and down the sides. Any number in the interior equals the sum of the two numbers above it. For example, here […]
English Number Translator
In this problem, you will be given one or more integers in English. Your task is to translate these numbers into their integer representation. The numbers can range from negative 999,999,999 to positive 999,999,999. The following is an exhaustive list of English words that your program must account for: negative, zero, one, two, three, four, […]
Boggle Blitz
In the game of Boggle, you are presented with an NXN table of letters. The object is to find words in the mix of letters. A word may be started anywhere in the table and is constructed by forming a chain of adjacent letters. Adjacent means diagonal, vertical or horizontal. A word cannot use any […]
Triangle Wave
Triangle Wave In this problem you are to generate a triangular wave form according to a specified pair of Amplitude and Frequency. Input and Output The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed […]
Rotating Sentences
In “Rotating Sentences,” you are asked to rotate a series of input sentences 90 degrees clockwise. So instead of displaying the input sentences from left to right and top to bottom, your program will display them from top to bottom and right to left. Input and Output As input to your program, you will be […]
Pig-Latin
You have decided that PGP encryptation is not strong enough for your email. You have decided to supplement it by first converting your clear text letter into Pig Latin before encrypting it with PGP. Input and Output You are to write a program that will take in an arbitrary number of lines of text and […]
Kindergarten Counting Game
Everybody sit down in a circle. Ok. Listen to me carefully. “Woooooo, you scwewy wabbit!” Now, could someone tell me how many words I just said? Input and Output Input to your program will consist of a series of lines, each line containing multiple words (at least one). A “word” is defined as a consecutive […]
Simply Subsets
After graduating from the University of Notre Dame, you obtained a job at Top Shelf Software, Inc., as an entry-level computer engineer. On the first day, your manager sits down with you and tasks you with the following job: “We want to see how well you understand computer programming and the abstract science behind it. […]
What’s The Frequency, Kenneth?
#include <stdio.h> main() { int i; char *suffix[]= { “st”, “nd”, “rd” }; char *item[]= { “Unix” , “cat”, “sed”, “awk”, “grep”, “ed”, “vi”}; printf(“In the beginning, there was nothing.\n”); for (i= 0; i < 7; i++) printf(“And on the %d%s day, God created %s. And it was good.\n”, i + 1, (i < 3) […]
Jill Rides Again
Jill likes to ride her bicycle, but since the pretty city of Greenhills where she lives has grown, Jill often uses the excellent public bus system for part of her journey. She has a folding bicycle which she carries with her when she uses the bus for the first part of her trip. When the […]
Word
Dr. R. E. Wright’s class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet {a,b} The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in […]
Gossiping
There was a public bus transport in one town. All buses had circular lines. Each line had at least two stops. Some lines had some stops in common. When two or more bus drivers met on some stop they announced each other all news they knew, so that after leaving the stop they all knew […]
String Distance and Transform Process
String Distance is a non-negative integer that measures the distance between two strings. Here we give the definition. A transform list is a list of strings, where each string, except for the last one, can be changed to the string followed by adding a character, deleting a character or replacing a character. The length of […]
Binomial Showdown
In how many ways can you choose k elements out of n elements, not taking order into account? Write a program to compute this number. Input Specification The input file will contain one or more test cases. Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n). Input is terminated by two zeroes for n and k. Output Specification For each […]
Dungeon Master
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded […]
Frogger
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping. Unfortunately Fiona’s stone is […]
Artificial Intelligence
Physics teachers in high school often think that problems given as text are more demanding than pure computations. After all, the pupils have to read and understand the problem first! So they don’t state a problem like “U=10V, I=5A, P=?” but rather like “You have an electrical circuit that contains a battery with a voltage […]
Balancing Bank Accounts
Once upon a time there was a large team coming home from the ACM World Finals. The fifteen travellers were confronted with a big problem: In the previous weeks, there had been many money transactions between them: Sometimes somebody paid the entrance fees of a theme park for the others, somebody else paid the hotel […]
Error Correction
A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here’s a 4 x 4 matrix which has the parity property: 1 0 1 0 0 0 0 0 1 1 1 1 0 1 0 1 The sums of […]
Goldbach’s Conjecture
In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture: Every number greater than 2 can be written as the sum of three prime numbers. Goldbach cwas considering 1 as a primer number, a convention that is no longer followed. Later on, Euler re-expressed […]
Heavy Cargo
Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you […]
DDF
An integer a is a positive factor of an integer b if a is greater than zero and there exist some integer n such that aXn=b. Consider a sequence of integer x1,x2,….xn. This sequence is a Decimal-Digit Factor Sequence (DDF) if each number in the sequence is a positive integer where x1 > 1 and […]
Wormholes
In the year 2163, wormholes were discovered. A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties: Wormholes are one-way only. The time it takes to travel through a wormhole is negligible. A wormhole has two end points, each situated in a star system. A […]
Dividing Coins
It’s commonly known that the Dutch have invented copper-wire. Two Dutch men were fighting over a nickel, which was made of copper. They were both so eager to get it and the fighting was so fierce, they stretched the coin to great length and thus created copper-wire. Not commonly known is that the fighting started, […]
Oil Deposits
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A […]
The Boggle Game
The language PigEwu has a very simple syntax. Each word in this language has exactly 4 letters. Also each word contains exactly two vowels (y is consider a vowel in PigEwu). For instance, “maar” and “even” are legitimate words, “arts” is not a legal word. In the game boggle, you are given a 4×4 array […]
Scheduling Lectures
You are teaching a course and must cover n ( $1 \le n \le 1000$) topics. The length of each lecture is L ( $1 \le L \le 500$) minutes. The topics require $t_1, t_2, \dots, t_n$ ( $1 \le t_i \le L$) minutes each. For each topic, you must decide in which lecture it […]
Counterfeit Dollar
Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is […]
Is It A Tree?
A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties. There is exactly one node, called the root, to which no directed edges point. Every node except the root has exactly one […]
Cellular Structure
Sample notation O = OA means that if we added to chain of a healthy organism a cell A from the right hand side, we would end up also with a chain of a healthy organism. It would grow by one cell A. A laboratory researches a cluster of these organisms. Your task is to […]
Secret Research
At a certain laboratory results of secret research are thoroughly encrypted. A result of a single experiment is stored as an information of its completion: `positive result’, `negative result’, `experiment failed’ or `experiment not completed’ he encrypted result constitutes a string of digits S, which may take one of the following forms: $\bullet$ positive result […]
500!
In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its […]
Ecosystem
There are various food chains in any ecosystem, hawk, mouse and corn to name one. Mice feed on corn, hawks eat mice and life goes on. Given the relations between the species one can easily create food chains. One can also determine whether a chain is a cyclic one with caterpillars, plants, fungi and bacteria, […]
The Net
Taking into account the present interest in the Internet, a smart information routing becomes a must. This job is done by routers situated in the nodes of the network. Each router has its own list of routers which are visible for him (so called “routing table”). It is obvious that the information should be directed […]
Compression (II)
The fast growth of program sizes and amount of stored data raises the need for efficient compression algorithms. They can significantly reduce the amount of storage space. Also the “Internet boom”, still suppressed by slow links has big influence on new developments in this field. One of the most modern methods is block sorting. Its […]
Squares (III)
A few days earlier a certain mathematician had been fired from his job so he has made up his mind to take revenge on his former employers and has changed all the numbers in their databases to their corresponding forms in different numerical systems using different bases. At the beginning it seemed to everyone to […]
Don’t Get Rooked
In chess, the rook is a piece that can move any number of squares vertically or horizontally. In this problem we will consider small chess boards (at most 4$\times$4) that can also contain walls through which rooks cannot move. The goal is to place as many rooks on a board as possible so that no […]
Self Numbers
In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any […]
Do the Untwist
Cryptography deals with methods of secret communication that transform a message (the plaintext) into a disguised form (the ciphertext) so that no one seeing the ciphertext will be able to figure out the plaintext except the intended recipient. Transforming the plaintext to the ciphertext is encryption; transforming the ciphertext to the plaintext is decryption. Twisting […]
Max. and Min. from n numbers
Copy code Algorithm Input An array of numbers Output Min and max Complexity O(n) Minmax (A) 1 set n=number of element in array; 2 initialize min=max=a[1]; 3 for i=1 to n 4 if (A[i]<min) 5=”” then=”” min=”A[i];” 6=”” if=”” (a[i]=””>max) 7 Then max =A[i]; 8 print min and max; Algorithm Description A is the array […]
Sum of Fibonacci Series
Copy code Algorithm Input n=No of element in the series Output Sum of series of n elements Complexity O(nlogn) Fibonacci(fib,n) 1. Set sum=0; 2. If (n==0 or n==1) then 3. fib=n; 4. Sum=sum+fib; 5. Return fib.; 6. Call Fibonacci(fibA,n-2); 7. Call Fibonacci(fibB,n-1); 8. Set Fib=fibA+fibB; 9. Sum=sum+fib; 10. Return Fib; 11. Outside the function print […]
Armstrong Numbers
Copy code Algorithm Input An integer and number of digits in the integer Output Number is Armstrong or not. Complexity O(d) where d is the number of digits in the integer Armstrong(num,digits) 1 n=num 2 while(num>0) do 3 digit =n%10; 4 sum=sum+pow(digit,digits) 5 n= n/10; 6 if (sum =num) 7 print it is an Armstrong […]
Lowercase to Uppercase
Copy code Algorithm Input Lower case character Output Uppercase character. Complexity O (n). Upper to lower case (char[]) 1. Set n=number of character in char[]; 2. For i=1 to n 3. Do if (95 <=char[i] <=122) 4. Then char[i]=(char[i]-32); 5. Print char[i]; Algorithm Description 1. Chat[] :character array; 2. For loop for each element in […]
Optimal binary search tree
Copy code Algorithm Input The probabilities p1, …, pn and q0, …, qn and the size n, and it returns the tables e and root. Output It returns the tables e and root. Complexity O(n^3). OPTIMAL-BST(p, q, n) 1 for i = 1 to n + 1 2 do e[i, i – 1] = qi-1 […]
Uppercase to Lowercase
Copy code Algorithm Input Uppercase character. Output Lower case character. Complexity O (n). Upper to lower case (char[]) 1. Set n=number of character in char[]; 2. For i=1 to n 3. Do if (65 <=char[i] <=90) 4. Then char[i]=(char[i]+32); 5. Print char[i]; Algorithm Description Char[] :character array; For loop for each element in the array. […]
Depth First Search
Copy code Algorithm Copy code C Code //WAP to implement Depth First Search #include<stdio.h> #include<conio.h> int n,adj[10][10],visited[10]; void input(); void dfs(int); int main() { int s; printf(“Enter no. of nodes in a Graph “); scanf(“%d”,&n); input(); printf(“From which node u wanna start dfs “); scanf(“%d”,&s); if(s>n) printf(“Invalid node “); else { printf(“DFS output is :\n”); […]
Breadth First Search
Copy code Algorithm Input No. of nodes in graph (tested for 10 nodes) and its adjacency matrix Output Breadth First traversal of Graph Complexity O(V+E) BFS(G) 1. Initialize all vertices to the ready state (STATUS = 1) 2. Put the starting vertex A in QUEUE and change the status of A to the waiting state […]
Dijkstra’s Algorithm
Copy code Algorithm Input Graph (G). Output Sorted path from source to destination . Complexity O(vlogv+E). Initialize (G, s) 1 for each vertex v in V[G] 2 do d[v]= ∞ 3 parent[v] =NIL 4 d[s] =0 Relax (u, v, w) 1 if d[v] > d[u] + w (u, v) 2 then d[v] = d[u] + […]
Euler Path
Copy code Algorithm Input Adjacent vertices of every node. Output Euler path exist or not. complexity O (1). Eular_path (G); For Each Vertex v ϵ V (G) Enter No. of Adjacent Vertex. If (vertex % 2=1) Count++; If (count=2) Print Graph contains Euler path. Else Print Euler path doesn’t exist. Algorithm Description G: graph, v: […]
Median of n numbers
Copy code Algorithm Randmized select(a,p,r,i) 1. If(p=r) then Return a[p]; 2. q=randomized partition(a,p,r) k=q-p+1; 3. if (i=k)then return a[q]; 4. else if (i<k)then return randmized select(a,p q-1,i); 5. else return randomized select (a,q+1,r,i-k) randomized partition(a,p,r) 1 x=a[r]; 2 i=p-1; 3 for j=p to r-1 4 do if (a[j]<=x) then i=i+1; exchange a[i+1] and a[j]; 5 […]
Queue using two stacks
Copy code Algorithm Input An integer to be enqueue. Output An integer to be dequeue. Complexity O(n). Enqueue() 1. Top1= Top1 +1; 2. A1[Top1]=item; Dequeue() 1. If(Top=-1)then Print queue is empty; 2. While(top1>=0) Do Top2=Top2+1; A2[Top2]=A1[Top1]; Top1=Top1-1; End of loop. 3. Print A2[Top2]; 4. Top2=Top2-1; 5. While(Top2>=0) Top1=Top1+1; A1[Top1]=A2[Top2]; Top2 =Top2-1; Algorithm Description We are […]
Kruskal’s Algorithm
Copy code Algorithm [This algorithm takes a graph G as an input and w is the weight. Here V[G] are the set of vertices of a graph. (u,v) is an edge between any two vertices u and v. Finally it returns a set A having edges for Minimum spanning tree of G] Input No. of […]
Least common subsequence
Copy code Algorithm Input Two Strings (tested for 20 character string) Output Longest Common Subsequence Complexity O(mn) LCS(X, Y) [length[X] counts the length of String X. b and c matrix is maintained in which information about longest common subsequence is stored using dynamic programming.] 1 m ← length[X] 2 n ← length[Y] 3 for i […]
Minimal Spanning Tree using Prim’s Algorithm
Copy code Algorithm Input No. of Vertex , Edges weights between vertices Output Minimum spanning tree of graph Complexity O(E + V lg V) MST-PRIM(G, w, r) [This algorithm takes a graph G as an input and w is the weight. Here V[G] are the set of vertices of a graph. (u,v) is an edge […]
Quick Sort
Copy code Algorithm Input Array of integers (tested for 20 inputs) Output Sorted sequence Complexity Worst case : Θ(n2) QUICKSORT(A, p, r) [Quicksort is based on the divide-and-conquer paradigm which takes an array A to sort. Here the initial call is QUICKSORT(A, 1, length[A]) so p is the first element and r is the last […]
Tower of Hanoi
Copy code Algorithm input Number of disk output Print: disk moved successfully complexity O(n). Tower(n , beg , aux , end) 1. If (n=1) then Beg = end; Return; 2. Call Tower(n-1 , beg ,end , aug ); 3. Call Tower (1 ,beg ,aux ,end ); 4. Call Tower (n-1,aux ,beg ,end); Algorithm Description Copy […]
Linked List
This problem discusses all the implementation of the linked list functions Copy code Algorithm Getnode()//creates node 1. [allocate memory for node] Set temp:=(node *)malloc(sizeof(node)); 2. If (temp==NULL) then: return “error†and exit 3. Else return temp; 4. Exit Insert_beg(x)//inserts element x at beginning of list 1. Call getnode(); 2. [store value in newly created node] […]
Stack Operations
Copy code Algorithm Push(stack, top, maxstk, item)// inserts an item onto the stack 1. [stack already filled?] If top = maxstk then : print : OVERFLOW and return. 2. Set top : = top +1 . [increases top by 1] 3. Set stack[top] := item [inserts item in new TOP position] 4. Return. Pop(stack, top, […]
Queue Operations
Copy code Algorithm Enqueue(queue, n, front, rear, item)//inserts item into a queue 1. [queue already filled?] If front := 1 and rear := n or front := rear +1 then: Print OVERFLOW and return 2. [find new value of rear] If front : =NULL , then [Q initially empty] Set front := 1 and rear […]
Binary Search
Copy code Algorithm Input Array of integers Output Loc of searched element. Complexity O(logn). Binary_search(a,n) 1. [initialize segment variables] Set beg:=0,end:=n and mid:=int((beg+end)/2); 2. Repeat steps 3 to 6 while beg<= end and a[mid]!=item 3. If item<a[mid] then : set end := mid-1; 4. Else Set beg:= mid+1; 5. Set mid := int((beg+end)/2) 6. [end […]
Bubble Sort
Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n^2). Bubble_sort(A,n)//here A is an array with n elements and this algorithm sorts the element in A. 1. Repeat steps 2 -5 for i=1 to n-1 2. Set j := 1;[initializes pass pointer j] 3. Repeat while (j<= n-i):[executes passes] 4. If A[j]>A[j+1] then: […]
Selection Sort
Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n^2). Min_val(a,I,n) This procedure finds the location loc of the smallest element in array a of size n 1. Set min = a[I] and loc = I [Initializes pointers] 2. Repeat step 3 for j = I+1 to n 3. If min>A[j] then: a. […]
Insertion Sort
Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n^2). Insertion_sort(a,n) 1. Set n=Input size of array; 2. Repeat steps 4-10 for i=1 to n 3. Set temp = a[i]; 4. Set j = i-1; 5. Repeat steps 7-9 while( temp<a[j]) 6. Set a[j+1] = a[j]; 7. [decrease j] j= j-1; 8. If […]
Counting Sort
Copy code Algorithm Input Array of integers Output Sorted array Complexity O(n). COUNTING-SORT(A, B, k) 1 for i ← 0 to k 2 do C[i] ← 0 3 for j ← 1 to length[A] 4 do C[A[j]] ← C[A[j]] + 1 5 C[i] now contains the number of elements equal to i. 6 for i […]
Find missing number
Copy code Algorithm An array contains n-1 unique integers in the range [0,n-1]that is there one number from the range that is not in A. Design an O(n) time algorithm for finding that number. You are allowed to use only O(1) additional space besides the array A itself Missing number (A,size)//returns the missing element in […]
Count number of 1’s in matrix
Copy code Algorithm Suppose each row of an nXn array A consists of 1’s and 0’s such that in any row I of A all the 1’s come before any 0’s in that row. Suppose further that the number of 1’s in the row I is atleast the number in row I+1,for I=0,1….n-2.Assuming A is […]
Josephus permutation problem
Solve Josephus permutation problem which is defined as: Suppose n people are arranged in a circle & we are given a positive integer m n) { System.out.println(“\n m should be less than n… Enter m again :”) ; m = Integer.parseInt(br.readLine()); } int a[] = new int[10]; for(i=0;i<n;i++) a[i] = 0; m1 = m; System.out.print […]
Evil king and poissoned bottle
An evil king has a cellar containing n bottles of expensive wine, and his guards have just caught a spy trying to poison the king’s wine. Fortunately, the guards caught the spy after he succeeded in poisoning only one bottle. Unfortunately they don’t know which one. To make the matter worse the poison the spy […]
Binary Search Tree
Copy code Algorithm Insert(n) //creates BST and inserts node n 1. [initialize pointer] *t := root; 2. Check if (root==NULL) then: a. Allocate memory for root node. b. Set root->data := n and root->r:=root->l:=NULL; 3. Else a. Repeat steps b, c, and d while(t) b. If (n<t->data) then: i. If(t->l!=NULL) then : Set t := […]
Election Winner
Copy code Algorithm Input Number of voter .leader id Output Winner of the election. complexity O(n). Election() 1. Set n=Input number of candidates participating in election. 2. Set b[X] //input vote from X number of voters where X is unknown 3. for j=1 to n. 4. do Initialize candidate array a[j] = 0 5. for […]
Order of the four railroad cars
To find the order of the four railroad cars moving-in and moving out on the tracks numbered 1-4. Copy code Algorithm Input Order of car. Output Order is possible or not Complexity O(c). Algo_car() 1. i=j=k=flag=0 and top=-1 //Initialize segment variables; 2. For i=0 to 3. 3. do perm[i] //input the order in which railroad […]
Parking Order
Copy code Algorithm Input Number of parking slots and wake up sequence. Output Parking order. Complexity O(m). Parking() 1. Set m= number of parking slots. 2. Set A[] wake up sequence. 3. Set b[i] = stores the parking order. 4. Repeat for i=1 to m. Do If ( b[a[i]]==0 ) then Set b[a[i]] = i. […]
Anagram
Copy code Algorithm Input Two string s1 and s2. Output S1 is anagram of s2 or not. complexity O(n). Anagram(s1,s2) 1. [Initialize segment variables] MAX_ASCII := 127, TRUE := 1 and FALSE :=0. 2. Set freq[i] : = 0 for i=0 to MAX_ASCII 3. Repeat while(*s1) Set freq[(INT) *s1++]++. 4. Repeat while(*s2) Set freq[(INT) *s2++]–. […]
Polynomial Addition
Copy code Algorithm Input inputs polynomial expression in terms of coefficient and power Output Sum of two polynomial expressions Complexity O(n). create()// inputs polynomial expression in terms of coefficient and power 1. Repeat while(1) a. [Input the coff and pow]. b. if (node→pow==0) then: i. Set ptr=node, node=NULL, ptr→link:=node and break. c. [whether to input […]
Sparse Matrix
Copy code Algorithm Input Number of rows and columns Output Sparse matrix Complexity O(n). create(h)//Creates sparse matrix using linked list 1. [Input number of rows(r) and columns(c)] 2. [ create the head node]. 3. [initialize row & col no and rw & col ptrs] h→r=r, h→c=c, h→rptr=h, h→cptr=h; 4. Set h→data=0; 5. [ create column […]
Magic Square
Copy code Algorithm odd_num(n)//creates magic square for odd number n 1. [initialize segment variables] num=1 and nn=n*3/2; 2. Repeat for i=0 to n a. Repeat for j=0 to n i. Set m[(j-i+nn)%n][(i*2-j+n)%n]=num++; 3. [End] even_num( n)//creates magic square for even number n 1. [initialize segment variables] num:=1, nminus:=n-1,nmiddle:=n/2,nn=n*n+1 and osl:=0. 2. Set first_block:=(n-2)/4, second_block=nminus-first_block. 3. […]
Sum of digits
Copy code Algorithm Input An integer Output Sum of digits. complexity O(d).[no. of digit in the number] Sod(a) 1. [Initialize sum] sum := 0. 2. Repeat while(n>0) Set d=n%10 ; sum=sum+n; Set n=n/10 ; 3. return sum. Algorithm Description Copy code C Code #include<stdio.h> #include<conio.h> int main() { int n,i,d,sum=0; printf(“\n enter any integer number […]
Palindrome
Copy code Algorithm Input An integer Output Palindrome or not complexity O(d).(number of digit) Palindrome(n) 1. [initialize segment variables]m := n, i:=n. 2. Repeat while(m>0) Set i:=i%10; rev:=i+rev*10; m:=m/10 ; i:=m; 3. if(rev==n)then print : “Number is palindrome”. 4. Else print: “Number is not a palindrome”. 5. Exit Algorithm Description Palindrome(n) checks whether given number […]
Roots of Quadratic Equation
Copy code Algorithm Input Coefficient of quadratic equation Output Roots complexity O(n). Roots (a,b,c) 1. Initialize root1:=root2:=0. 2. Set cal := (sqrt((b*b)-(4*a*c)))/(2*a). 3. Set root1 : = -b + cal. 4. Set root2 : = -b – cal. 5. If(root1<0 or root2<0) then print : “Imaginary roots†6. Else return 7. end Algorithm Description Roots() […]
Reverse a string
Copy code Algorithm Input A string; Output Reverse of string complexity O(n). Reverse(s1)//reverses string s1 1. Initialize ctr := 0. 2. while(s1!=’\0’) 3. [increment ctr] ctr++, 4. Repeat for i=ctr to 0 print : *(s1+i) 5. [end] Algorithm Description Ctr :counter; Ctr count the number of elements in the string. For loop for print the […]
Heap Sort
Copy code C++ Code /* program to heap sort array elements */ #include<iostream> #include<math.h> using namespace std; int b[100],ptr=0,tn; //function to form heap of a given tree void heapify(int n,int a[]) { //if no node left if(n==0) { return; } int l,r,tmp,curr; //decrease current node number curr=n-1; l=(curr+1)*2-1; r=l+1; //if parent if less then left […]
Strassen Multiplication
Copy code JAVA Code import java.io.*; class multiply { int a[][]=new int[16][16]; int b[][]=new int[16][16]; int c[][]=new int[16][16]; void input(int a[][],int n)throws IOException { int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) { System.out.println(“Input the element”+i+”,”+j); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); a[i][j]=Integer.parseInt(br.readLine()); } } void display(int a[][],int n) { int i,j; for(i=0;i<n;i++) { System.out.println(“”); for(j=0;j<n;j++) System.out.print(“\t”+a[i][j]); } System.out.println(“\n”); […]
Integer Multiplication
Copy code C++ Code /* Program for integer multiplication */ #include<iostream> #include<cstring> #include<cmath> using namespace std; //function to calculate size of a given number in form of array int size(char a[]) { int length=0; //loop till end of the array while(a[length]!=’\0′) { length++; } return length; } //funtion to add bits of number void add(char […]
Fractional knapsack using greedy algorithm
Copy code C++ Code /* program to implement fractional knapsack problem using greedy programming */ #include<iostream> using namespace std; int main() { int array[2][100],n,w,i,curw,used[100],maxi=-1,totalprofit=0; //input number of objects cout<<“Enter number of objects: “; cin>>n; //input max weight of knapsack cout<<“Enter the weight of the knapsack: “; cin>>w; /* Array’s first row is to store weights […]
To draw hash table using linear probing
Copy code JAVA Code import java.io.*; class hash { public static void main(String args[]) throws Exception { int n=11,l,i,k,flag; int a[]=new int[11]; int hash[]=new int[11]; BufferedReader cin= new BufferedReader (new InputStreamReader(System.in)); System.out.println(“Enter the elements “); for(i=0;i<n;i++) { a[i]= Integer.parseInt(cin.readLine()); hash[i]=0; } for(i=0;i<n;i++) { k=(2*a[i]+5)%11; flag=0; while(flag!=1){ if(hash[k]==0){ hash[k]=a[i]; flag=1; } else k=(k+1)%11;//linear probing } } […]
To draw hash table using quadratic probing
Copy code JAVA Code import java.io.*; class hash_quadratic{ public static void main(String args[]) throws Exception{ int n=11,i,k,j,flag; int a[]=new int[11]; int hash[]=new int[11]; BufferedReader cin= new BufferedReader (new InputStreamReader(System.in)); System.out.println(“enter the elements to be sorted”); for(i=0;i<n;i++){ a[i]= Integer.parseInt(cin.readLine()); hash[i]=0; } for(i=0;i<n;i++){ flag=0; j=0; while(flag!=1){ k=((2*a[i]+5)%11+j*j)%11; if(hash[k]==0){ hash[k]=a[i]; flag=1;} else{ j++; } } } System.out.println(“hash table […]
Merge Sort
Copy code JAVA Code import java.io.*; class merge_sort { public static void main(String args[]) throws Exception { merge_sort m=new merge_sort(); int n,end,beg,i; BufferedReader cin= new BufferedReader (new InputStreamReader(System.in)); int arr[]=new int[10]; System.out.println(“enter 10 elements to be sorted”); for(i=0;i<10;i++) { arr[i]= Integer.parseInt(cin.readLine()); } beg=0; end=9; m.mergesort(arr,beg,end); System.out.println(“THE ELEMENTS AFTER SORTING ARE:”); for(i=0;i<10;i++) System.out.println(arr[i]); } }
8 Queen Problem
Copy code JAVA Code import java.io.*; class queens{ int count=0; int x[]=new int[10]; boolean place(int k,int i) { int j; for(j=1;j<=k-1;j++) if((x[j]==i) || (Math.abs(x[j]-i)==Math.abs(j-k))) return false; return true; } void nqueens(int k,int n) { int r,i; for(i=1;i<=n;i++) { if(place(k,i)) { x[k]=i; if(k==n) { for(i=1;i<=n;i++) { for(r=1;r<x[i];r++) { System.out.print(” – “); } System.out.print(” * “); for(r=x[i]+1;r<=n;r++) […]
0/1 Knapsack Problem
Copy code JAVA Code import java.io.*; class knapsack10 { public static void main(String args[]) throws IOException { int capacity,n; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println (“\n Enter the number of items u want to enter:”); n= Integer.parseInt(br.readLine()); float p[]=new float[n+1]; float x[]=new float[n+1]; int i,j,k,w; int WEIGHT[]=new int[n+1],PROFIT[]=new int[n+1]; WEIGHT[0]=0; PROFIT[0]=0; for(i=1;i<=n;i++) { System.out.println (“\n Enter […]
Graph Coloring
Copy code JAVA Code /*To implement graph colouring*/ import java.io.*; class graph_colour { void colournext(int k,int colour[],int n,int m,int edge[][]) { int flag=0,j; do { flag=0; colour[k]=(colour[k]+1)%(m+1); if(colour[k]==0) return; for(j=0;j<n;j++) { if((edge[k][j]==1) && (colour[k]==colour[j])) flag=1; } }while(flag==1); } public static void main(String args[]) throws IOException { int i,t,j,h,n,m,k,flag=0,maxclique=0; System.out.println(“Enter the no. of vertices in the […]
8 Rooks & 8 Bishops Problem
Copy code JAVA Code import java.io.*; class bishop { static int a[][]= new int[8][8]; static int pl[][]= new int[8][8]; static int row; static int placerook(int i,int j) { int i1,j1,flag=0; i1=i; j1=j; while(i1>=0) { if(a[i1][j1]==0) flag=1; i1–; } return(flag); } static int placebishop(int i,int j) { int i1,j1,flag=0; i1=i; j1=j; while((i1>=0)&&(j1>=0)) {if(a[i1][j1]==1) flag=1; i1–; j1–;} […]
Fractional knapsack for report
A draft report has five chapters. The table shows the lengths of the chapters & their importance where the scale is from 1(low) to 10(high). The report must be at most 600 pages long. The problem is to edit the report so that the overall importance is maximized. Implement the fractional knapsack algorithm using Greedy […]
Find Max. and Next Max.
Copy code Algorithm Input An array of numbers Output Max and next max Complexity O(n) 1 Maximum(Array A) 2 Set n=number of element in array; 3 Compare first two numbers 4 If Array[first] is greater then set first= max and second=nextmax 5 otherwise set first=nextmax and second=max; 6 for i=2 to n do 7 if […]
Running on Safe Path
New Delhi is a place for people to run anywhere easily. The two-way streets run North-South or East-West dividing the city into regular blocks. Most street intersections are safe for pedestrians to cross. In some of them, however, crossing is not safe and pedestrians are forced to use the available underground passages. Such intersections are […]
Life, the Universe, and Everything
Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely… rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits. Input 1 2 88 42 99 […]
Small Factorials
You are asked to calculate factorials of some small positive integers. Input An integer t, 1
ONP: Transform the Expression
Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,…,z. Assume that there is only one RPN form (no expressions like a*b*c). Input t [the number of expressions
ADDREV: Adding Reversed Numbers
The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their […]
The 3n+1 problem
Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs. Consider the following algorithm: 1. input n 2. print n 3.if n = 1 then […]
Ecological bin packaging
Bin packing, or the placement of objects of certain weights into different bins subject to certain constraints, is an historically interesting problem. Some bin packing problems are NP-complete but are amenable to dynamic programming solutions or to approximately optimal heuristic solutions. In this problem you will be solving a bin packing problem that deals with […]
Fermat vs Pythagoras
Computer generated and assisted proofs and verification occupy a small niche in the realm of Computer Science. The first proof of the four-color problem was completed with the assistance of a computer program and current efforts in verification have succeeded in verifying the translation of high-level code down to the chip level. This problem deals […]
Stacking Boxes
Copy code C++ Code #include<stdio.h> #include<stdlib.h> #define MAXN 33 int B[MAXN][1][12]; int St[MAXN], V[MAXN]; int P[MAXN], N, D; int com(const void *a, const void *s) { return *(int *)a – *(int *)s; } int Biger(int n, int m){ int i; for(i = 0; i< D; i++) if(B[n][0][i] < = B[m][0][i]) return 0; return 1; } […]
Mar-Apr 2011: Airline Comparison
An Railway Reservation deprtment document contains a list of trains between pairs of stations. A trip may be built by sequencing trains. Two railway operators are equivalent if they offer connections between the same pairs of stations, irrespective of the number of scales in between. Problem Given the catalogs of two railway operators, determine if […]
Table of a given number
Copy code Algorithm Input Any integer number Output Its table from 1 to 10 Complexity O(1) Table (num) 1 for r=1 to 10 2 print ”num*r” 3 r=r+1 Algorithm Description Initialize the value of r from 1 and increment it up to 10 to print the table of number by multiplying it with the number. […]
Find whether a number is prime or not
Copy code Algorithm Input Any integer number (up to 32767) Output Is it a prime number or Not Complexity O(n) Prime(num) 1 Set i=2 2 while i #include< conio.h> int main() { int i,num; printf(“Enter a number”); scanf(“%d”,&num); i=2; while(i
L-R shift operator
Copy code Algorithm Input integer number Output Corresponding number after shifting Complexity O(1) L_R_Shift (a,s,ch) [‘a’ is any input number and s is the shift which needs to be done on the input number and ch takes the choice entered by user either for left shift or right shift] 1 if ch=’l’ OR ch = […]
Decimal to Binary
Copy code Algorithm Input Any integer number (up to 32767) Output Binary equivalent of input no. Complexity O(n) Dec_to_Bin(A ,num) 1 Set i=0 2 while num>0 3 A[i]=num%2 4 num=num/2 5 i=i+1 6 for n=i-1 to 0 7 print “its binary number is A[n] Algorithm Description let us convert a decimal number 95 to binary […]
Swap 2 numbers without using third variable
Copy code Algorithm Input Two numbers a and b to be swapped Output Numbers after swapping complexity O(1). Swap(a , b) 1. a=a+b; 2. b=a-b; 3. a=a-b; 4. print a and b Algorithm Description This algorithm takes two integers and swaps their values without using temporary variable Copy code C Code //Swap two numbers without […]
Reverse digits of a number
Copy code Algorithm Input An integer Output Reverse of number complexity O(d) where d is the number of digits in the number Digitsreverse(num) 1 while (num>0) then 2 digit =num%10; 3 print digit; 4 num= num/10; Algorithm Description This algorithm takes an integer and reverses its digits. It keeps on dividing it by 10 to […]
Find simple interest
Copy code Algorithm Input P(principal amount), r( Rate of interest) ,t(number of years); Output I(interest) complexity O(1) 1 Simpleinterest(p, r , t) 2 I =p*r*t; 3 Return I Algorithm Description Formula for calculating compound interest: Interest=principal amount *time *rate Where, P = principal amount (initial investment) r = annual nominal interest rate (as a decimal) […]
Find leap year
Copy code Algorithm Input An year Output Leap year or not complexity O(1). leapyear(year) 1 If (year %4==0 and year%100 !=0) 2 print “it is a leap year”; 3 else 4 if(year%400==0) 5 print “it is a leap year”; 6 else 7 print “it is not a leap year”; Algorithm Description Copy code C Code […]
LCM of two numbers
Copy code Algorithm Input Two integer a and b Output GCD of a and b. complexity O(d) where d is the number of digits in the smaller number gcd(a, b) 1 if (b = 0) then 2 Return a 3 else 4 Return gcd(b, a mod b) Algorithm Description LCM () function takes two parameter […]
GCD of two numbers
Copy code Algorithm Input Two integer a and b Output GCD of a and b. complexity O(d) where d is the number of digits in the smaller number gcd(a, b) 1 if (b = 0) then 2 Return a 3 else 4 Return gcd(b, a mod b) Algorithm Description Gcd () function takes two parameter […]
Find factorial of a number
Copy code Algorithm Input An integer. Output Factorial of given number. complexity O(n) Factorial(num) 1 if (num=0 or num=1) then 2 fact = 1; 3 else 4 for i 1 to n 5 fact=fact*i; 6 print fact Algorithm Description Factorial of a number is multiplying the numbers from 1,2,3…n where n is the number whose […]
Find compound interest
Copy code Algorithm Input P(Principal Amount), r(Rate of Interest) , n(Number of times interest is calculated in a year) , t(number of years); Output compound interest Complexity O(1) 1 Compoundinterest(p, r , n , t) 2 A = P*(1+(r/n))^nt; 3 CI = A – p; 4 Return CI Algorithm Description Compound interest arises when interest […]
Convert celsius to farenheit
Copy code Algorithm Input Temperature in Celsius. Output Temperature in Fahrenheit. complexity O(1) CelsiustoFahrenheit(Tc) 1 Tf = (9/5)*Tc+32; 2 print Tf. Algorithm Description Tc = temperature in degrees Celsius, Tf = temperature in degrees Fahrenheit. Copy code C Code //To convert the temperature from Celsius to Fahrenheit //Input : Enter any integer #include< stdio.h> #include< […]
Validity of a triangle
Copy code Algorithm Input Three angle of triangle Output Valid or invalid complexity O(1) Triangle_valid(angle1, angle2, angle3) 1 if (angle1 = 0 or angle2 = 0 or angle3 = 0) then 2 print triangle is invalid 3 else 4 sum=angle1 + angle2 +angle3; 5 if (sum = 180) then 6 print triangle is valid; 7 […]
Average of numbers
Copy code Algorithm Input Set of numbers and count of numbers n Output Average of numbers complexity O(n) Average(A) 1 Set n=size of array. 2 Set sum =0; 3 for i=1 to n 4 sum=sum + A[i]; 5 avg = sum/n; 6 print avg; Algorithm Description Algorithm adds up all the elements in the array […]
X^Y
Copy code Algorithm Input Two integer x and y Output Print x^y complexity O(logn) power(x,y) 1 if (y==0) then 2 return 1; 3 else if(y%2==0) 4 return power(x,y/2)*power(x,y/2); 5 else 6 return x*power(x,y/2)*power(x,y/2); Algorithm Description The algorithm takes advantage of the fact that if n is an even number then xn=xn/2*xn/2 otherwise xn=x*xn/2*xn/2 By this […]
Sum of n numbers
Copy code Algorithm Input N (The numbers from 1 to N will be added) Output Sum of first n numbers complexity O(1) Sum_Num(N) 1 Sum=N*(N+1)/2; 2 Print sum; Algorithm Description This algorithm adds all number from 1 to N. To add first N number program uses the formula sum=N*(N+1)/2; Copy code C Code //To find […]
Matrix Substraction
Copy code Algorithm Input Two matrices a and b Output Output matrix c containing elements after subtraction of b from a complexity O(n^2) Matrix-Subtraction(a,b) 1 for i =1 to rows [a] 2 for j =1 to columns[a] 3 Input a[i,j]; 4 Input b[i,j]; 5 C[i, j] = A[i, j] – B[i, j]; 6 Display C[i,j]; […]
Matrix Multiplication
Copy code Algorithm Input two matrixes. Output Output matrix C. Complexity O(n^3) Matrix-Multiply(A, B) 1 if columns [A] ≠ rows [B] 2 then error “incompatible dimensions” 3 else 4 for i =1 to rows [A] 5 for j = 1 to columns [B] 6 C[i, j] =0 7 for k = 1 to columns [A] […]
Even and Odd
Copy code Algorithm Input An integer. Output Print number is even or odd. Complexity O(1) Even-odd(n) 1 If (n%2=0) then 2 Print number is even 3 else 4 Print number is odd Algorithm Description Even-odd() function takes an integer and checks whether n is divisible by 2 or not.if its remainder is0 then number is […]
Division of two numbers
Copy code Algorithm Input Two numbers Output Quotient of two numbers Complexity O(n^2) Division (num1, num2) div=num1/num2; print div; Algorithm Description This function takes two integer num1 and num2 and divides number1 from number2 and assign its value to div which stores quotient after division. Copy code C Code //Division of two numbers //Input : […]
Decimal to Octal
Copy code Algorithm Input A decimal number Output An octal number complexity O(d)where d is the number of digits in the number Decimal_to_octal(num) 1 while (num>0) then 2 a[i] =num%8; 3 num= num/8; 4 i=i+1; 5 Print a[i] in reverse order Algorithm Description This algorithm takes an integer and converts it to octal number. The […]
Ascii value of [A to Z and a to z]
Copy code Algorithm Output: ASCII value of [A to Z and a to z] complexity:O(1) ASCII( ) 1 for i=65 to 90 2 print i and character value of i 3 for i=97 to 122 4 print i and character value of i Algorithm Description we have to print the character counterpart of the integer […]
Addition of two matrices
Copy code Algorithm Input Two matrices a and b Output Output matrix c containing elements after addition of a and b complexity O(n^2) Matrix-Addition(a,b) 1 for i =1 to rows [a] 2 for j =1 to columns[a] 3 Input a[i,j]; 4 Input b[i,j]; 5 C[i, j] = A[i, j] + B[i, j]; 6 Display C[i,j]; […]
Hello world!
Welcome to WordPress. This is your first post. Edit or delete it, then start writing!