Graduate

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 […]

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 […]

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] + […]

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 […]

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] = […]

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 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. […]

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 […]

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 […]

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 […]

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 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 […]

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 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  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  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 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 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 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 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 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  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 […]

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  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  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  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 […]

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  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  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 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 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  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 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 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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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. […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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, […]

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 […]

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 […]

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 […]

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, […]

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 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 […]

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 […]

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 […]

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 […]

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. […]

#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 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 […]

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 […]

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 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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path. Input The input file […]

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 […]

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, […]

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 […]

A snail is at the bottom of a 6-foot well and wants to climb to the top. The snail can climb 3 feet while the sun is up, but slides down 1 foot at night while sleeping. The snail has a fatigue factor of 10%, which means that on each successive day the snail climbs […]

“PATH” is a game played by two players on an N by N board, where N is a positive integer. (If N = 8, the board looks like a chess board.) Two players “WHITE” and “BLACK” compete in the game to build a path of pieces played on the board from the player’s “home” edge […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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, […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]