Algorithms Answers

Squaring a binary number requires a number of
additions (of binary digits) - as well as other manipulations such as
copying strings of bits and layout. Assuming an addition counts as
one operation and other manipulations don't count as operations
then calculate a worst case scenario value for the Big-O of the
squaring function assuming the values being squared have N binary
digits - i.e. Squaring = O(f(N)). Approximate f(N).

Language used to solve Computer mathematical computations is termed as

A. Pascal
B. Fortran
C. Ada
D. COBOL

A person enters the bank and stand in the queue to get his salary. When his turn comes, he request the cashier that i need my salary with minimum notes and coins. Write the program for the cashier that first ask the cashier to enter the salary amount and then display the number of notes and coins of (rs. 5000, rs 1000, rs 100, rs 50, rs 20, rs 10, rs 5, rs 2, rs 1)

Write an algorithm to calculate the average mark out of 100, given three assignment marks, each of which is marked out of 20.
Trace the algorithm using 15, 20 and 10 as the three assignment marks.

Amanada, a school kid, is learning English alphabets. Her teacher devised a small game to make the task fun. A grid of ‘m’ rows and ‘n’ columns is filled with English alphabets.She needs to search English words in this grid by moving one step at a time in any of the adjacent grid cells.A grid of alphabets and a set of English words are given. Amanda can start from anywhere in the grid and can move in any of the 8 adjacent grid cells, one step at a time. Each grid cell can only be used once.

Write the pseudocode that will produce a slip similar to the one illustrated at
the beginning of the question

Williams & Son
VAT nr: 0123456
Product Price
Screwdriver R 100
Super glue R 20
_______________________
Total: R120

Implement the basic recursive implementation of Fibonacci number function and find the largest Fibonacci number that your computer can compute. The algorithm is as follows:
int Fib(int n)
{
 if(n<2) return n;
 return Fib(n-1) + Fib(n-2);
}

Using JFLAP, create a PDA (pushdown automata) for the following two language(s):

L = {a^n b a^n | n > 0}
both are seperate
L = {a^i b^j c^k | i = j or i=k, i, j, k > 0}

Develop a nonrecursive algorithm for Algorithm 7-1, “Find Smallest Node
in a BST.”

Prove or disprove the following: 

1. lg√n ∈ O(lg n) (√n means square root of n)

2. lg n ∈ O(lg√n) 

3. 2n+1 ∈ O(2n)