CmSc 250 Fundamentals of Computing III

Problems

There are five groups of problems below. Problems marked with “*” count for two.

You have to solve at least 25 problems, at least one of each group, at least 5 that involve programming and at least three marked with “*” (threeof those count for 6 problems).

Schedule for submitting the problems:

First 5 problems by 11/03

Next 5 problems by 11/10 (total 10)

Next 5 problems by 11/17 (total 15)

Last 10 problems by 12/01 (total 25)

A.General

  1. * A very large department has a mix of 100 professors: some are honest and hard-working, while others are deceitful and do not like students. The honest professors always tell the truth, but the deceitful ones sometimes tell the truth and sometimes lie. You can ask any professor the following question about any other professor: “Professor Y, is professor X honest?” Professor Y will answer either with “yes” or “no”. Design an algorithm that, with no more than 198 questions, would allow you to figure out which of the 100 professors are honest. It is known that there are more honest than dishonest professors.
  1. There are n black, m green, and k brown chameleons on a deserted island. When two chameleons of different colors meet they both change their color to the third one (e.g., black and green chameleons become brown). Design and implement an algorithm that for each choice of n, m, and k will decide whether it is possible that after some time all chameleons on the island are the same color (if you think that it is always possible, check the case n = 1, m = 3, and k = 5).
  1. *Design and implement an algorithm that fills a table n x m in the following way:

A[0][0] to a[0][m-1] = 1

A[n-1][0] to a[n-1][m-1] = 1

A[0][0] to a[n-1][0] = 1

A[0][m-1] to a[n-1][m-1] = 1

A[1][1] to a[1][m-2] = 2 (if the row exists and is not filled with 1)

A[n-2][1] to a[n-2][m-2] = 2 (if the row exists and is not filled with 1)

A[1][1] to a[n-2][1] = 2 (if the column exists and is not filled with 1)

A[1][m-2] to a[n-2][m-2] = 2 (if the column exists and is not filled with 1)

Etc

Example:

5 x 7 6 x 77 x 74 x 3

1 1 1 1 1 1 11 1 1 1 1 1 11 1 1 1 1 1 11 1 1

1 2 2 2 2 2 11 2 2 2 2 2 11 2 2 2 2 2 11 2 1

1 2 3 3 3 2 11 2 3 3 3 2 11 2 3 3 3 2 11 2 1

1 2 2 2 2 2 11 2 3 3 3 2 11 2 3 4 3 2 11 1 1

1 1 1 1 1 1 11 2 2 2 2 2 11 2 3 3 3 2 1

1 1 1 1 1 1 11 2 2 2 2 2 1

1 1 1 1 1 1 1

B.Big-Oh notation and algorithm efficiency

  1. Consider the following algorithm for finding the distance between the two closest elements in an array of numbers

ALGORITHM MinDistance(A[0..n-1])

// Input: Array A[0..n-1] of integers

// Output: Smallest distance between two of its elements

dmin 

for i  0 to n-1 do

for j  0 to n-1 do

if i  j and |A[i] – A[j]| < dmin

dmin  |A[i] – A[j]|

return dmin

Make as many improvements as you can in this algorithmic solution to the problem. (If you need to, you may change the algorithm altogether; if not, improve the implementation given.)

Write your improved algorithm in pseudocode and implement it.

  1. Design a linear-time algorithm to rearrange elements of a given array of n integers so that all its negative elements precede all its positive elements.The algorithm should not use more than constant extra memory, i.e. it should not use an additional array. Implement your algorithm
  1. Door in a wall. You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you know neither how far away nor in which direction. You can see the door only when you are right next to it. Design an algorithm that enables you to reach the door by walking at most O(n) steps where n is the (unknown to you) number of steps between your initial position and the door. Implement the algorithm
  1. Anagram checking. Design an algorithm for checking whether two given words are anagrams, i.e., whether one word can be obtained by permuting the letters of the other. (For example, the words tea and eat are anagrams.). Determine the size of the input and the basic operation. Analyze the algorithm. Implement the algorithm. Make sure the program runs in interactive mode with appropriate interface.
  1. Design a reasonably efficient algorithm for solving the following problem and determine its efficiency class.

You are given n telephone bills and m checks sent to pay the bills (n ≥ m). Assuming that telephone numbers are written on the checks, find out who failed to pay. (For simplicity, you may also assume that only one check is written for a particular bill and that it covers the bill in full.)

  1. Design a reasonably efficient algorithm for solving the following problem and determine its efficiency class.

You have a file of n student records indicating each student’s ID number and home state. Find out the number of students from each of the 50 U.S. states.

  1. Consider the following problem: Given an array of n integers A[1..n] and an integer P, find two distinct indices i and j such that A[i] + A[j] = P

a. Design a brute force algorithm for solving the problem. What is the time efficiency of the algorithm?

b. Use the idea of presorting and design an algorithm with O(nlog(n)) efficiency

  1. *Consider the method findTriples defined below. It returns true if there are three equal integers in the array A. Ignore all syntax errors.

int findTriples(int[] A)

{

for (int i = 0; iA.length; i++)

for(int j = i+1; j < A.length; j++)

for(int k = j + 1) ; k < A.length ; k++)

if(A[i] == A[j] & A[i] == A[k]

A[j] == A[k])

return true;

return false;

}

  1. What is the running time of the method?
  2. If it takes 10 seconds to run findTriples on an array of 100 elements, approximately how long will it take to run on an array of 400 elements?
  3. Design an algorithm that performs the same task with (N2) complexity, where N is the length of the array. Write its code.
  4. Design and describe using pseudocode and algorithm that performs the same task with  (NlogN) complexity.
  5. Design and describe verbally an algorithm that performs the same task with (N) complexity, where N is the length of the array, using additional memory.
  1. Let A be an array of N integers not necessarily sorted. An element x of A is said to be a majority element if the number of elements of A that are equal to X is at least (n+1)/2. Design and implement an algorithm that determines whether A has a majority element or not, and outputs such an element when A does have a majority element. The worst-case running time of your algorithm must be O(n).
  1. In sorting algorithms the "copy" operation takes much time, especially when the elements to be sorted are large (e.g. a record containing several fields of type "string"). The time can be reduced by avoiding the actual copying of the elements - manipulating a separate array that contains the indexes of the elements to be sorted. Choose a simple sorting algorithm (e.g. bubble sort or insertion sort) and implemented the above idea.
  1. You are given an unsorted array of n-1 distinct integers from the range 1 to n. Write and implement a linear-time algorithm to find the missing number. The algorithm should use constant extra memory, i.e. you are not allowed to use an additional array of n elements.
  1. * There are n people. The entry K[i][j] of K[1..n][1..n] is 1 when person iknows person j and 0 otherwise. (We assume that K[i][i] = 1 for everyi.) A celebrity is a person who is known by everyone and does not knowanyone besides himself/herself. For example, in the left diagram belowperson 3 is a celebrity. There is no celebrity in the situation in the rightdiagram:

.

Designand implement an O(n) algorithm which finds a celebrity or concludes that there is none. (This can be done trivially in O(n2).)

C.Proofs

  1. Prove using mathematical induction that 1 + 2 + 4 + … + 2p = 2 p+1 – 1
  2. Prove using mathematical induction that q0 + q1 + q2 + … + qp = (qp+1 – 1)/(q-1)
  3. Using mathematical induction, prove the following:

Given a sequence a1, a2, .., an, … such that an = a n-1 + d for n > 1

Then an = a1 + (n-1)*d for n > 1

  1. Prove using mathematical induction that a tree with N nodes has N-1 links
  2. Prove using mathematical induction that a perfect binary three of height h has 2h nodes at the bottom level (with height 0)
  3. Prove using mathematical induction that in a perfect binary tree of height h the number of nodes with height > 0 is 2h - 1
  4. Consider a binary tree with N nodes where each node has either 0 or two children. Prove using mathematical induction that the number of the leaves is

(N+1)/2

  1. Consider a tree with N nodes where each node has either 0 or three children. Find out how many leaves the tree has and prove your result.
  2. * Compute the sum of all depths of the nodes in a perfect binary tree with N nodes. Use the method in Theorem 6.1, p. 211

D.Trees

  1. * Draw a binary tree with ten nodes labeled.0, 1, 2, ..., 9 in such a way that the inorder and postorder traversals of the tree yield the following lists: 9, 3, 1, 0, 4, 2, 7, 6, 8, 5 (inorder) and 9, 1, 4, 0, 3, 6, 7, 5, 8, 2 (postorder).

Give an example of two permutations of the same n labels 0, 1, 2, .., n−1 that cannot be inorder and postorder traversal lists of the same binary tree.

Design and implement an algorithm that constructs a binary tree for which two given lists of n labels 0, 1, 2, .., n−1 are generated by the inorder and postorder traversals of the tree. Your algorithm should also identify inputs for which the problem has no solution.

  1. Write a pseudocode for a recursive algorithm that computes the number of the leaves in a binary tree. What is the basic operation? Set up and solve a recurrence relation for the number of basic operations made by your algorithm. Implement the algorithm.
  1. Write a pseudocode for a recursive algorithm that computes the sum of the depths of all nodes in a binary tree (not perfect). What is the basic operation? Set up and solve a recurrence relation for the number of basic operations made by your algorithm (assume that the tree is well-balanced). Implement the algorithm.
  1. * Design and implement a tree class where the tree is represented by an one-dimensional array. Provide methods to
  1. create the tree given a list of parent-child pairs
  2. find the number of the leaves in the tree
  3. for any node print the path from that node to the root

Assume that the nodes are labeled with successive numbers 0 to N

Analyze the complexity of each method.

E.Recurrence relations

  1. Solve the following recurrence relations, with initial condition T(1) = 1
  2. T(N) = T(N/2) + LogN
  3. T(N) = T(N/2) + N
  4. T(N) = 2T(N/2) + N
  5. T(N) = 2T(N/2) + NLogN
  6. T(N) = 2T(N/2) + N2
  1. * von Neumann’s neighborhood. How many one-by-one squares are generated by the algorithm that starts with a single square and on each of its n iterations adds new squares all round the outside. How many one-by-one squares are generated on the nth iteration? The results for n = 0, 1, and 2 are illustrated below:

Find the number of cells in the von Neumann neighborhood of range n by setting up and solving a recurrence relation

  1. Consider the algorithm for computing the n cubes: S(n) = 13 + 23 + … + n3

Algorithm S(n)

//Input: A positive integer n

//Output: The sum of the first n cubes

if n = 1 return 1

else return S(n − 1) + n ∗ n ∗ n

a. Set up and solve a recurrence relation for the number of times the

algorithm’s basic operation is executed.

b. How does this algorithm compare with the straightforward nonrecursive

algorithm for computing this function?

  1. * Consider the following recursive algorithm

Algorithm Q(n)

//Input: A positive integer n

if n = 1 return 1

else return Q(n − 1) + 2 ∗ n − 1

a. Set up a recurrence relation for this function’s values and solve it

to determine what this algorithm computes.

b. Set up a recurrence relation for the number of multiplications made by

this algorithm and solve it.

c. Set up a recurrence relation for the number of additions/subtractions

made by this algorithm and solve it.

  1. Write a pseudocode for a recursive algorithm for finding the position of the largest element in an array of n numbers. Set up and solve a recurrence relation for the number of key comparisons made by your algorithm. How does this algorithm compare with the iterative algorithm for this problem? Implement the recursive algorithm
  1. Write a pseudocode for a recursive algorithm that determines whether a given word is a palindrome. A given word is a palindrome if it can be read backwards, for example pop, rotor, noon. Set up and solve a recurrence relation for the number of key comparisons made by your algorithm. How does this algorithm compare with the iterative algorithm for this problem? Implement both algorithms.
  1. Write a pseudocode for a recursive algorithm that reverses the contents of an array. Set up and solve a recurrence relation for the number of swaps made by your algorithm. How does this algorithm compare with the iterative algorithm for this problem? Implement both algorithms.
  1. * There are n bacteria and 1 virus in a Petri dish. Within the firs minute, the virus kills one bacterium and produces another copy of itself, and all of the remaining bacteria reproduce, making 2 viruses and 2*(n-1) bacteria. In the second minute, each of the viruses kills a bacterium and produces a new copy of itself (resulting in 4 viruses and 2*(2*(n-1) -2) = 4*n – 8 bacteria; again, the remaining bacteria reproduces. This process continues every minute. Will the viruses eventually kill all the bacteria? If so, design and implement an algorithm that will compute how many steps it will take. How does the running time of your algorithm depend on n?

1