Concepts in Computing
CS4 - Winter 2007
Instructor: Fabio Pellacini

HW 4, due Monday, Feb 5

Instructions

This homework is comprised of a set of written questions. You are not required to write your answers in HTML. However, you should still upload them to your private directory and provide a printout. Upload your file in a format we can read -- plain text, HTML, PDF, Word, or RTF. No timestamp is required. Some of the following problems require you to write algorithms. Do so using the notation introduced in class. Please be precise, since we will take away points if the syntax is different than the one we have introduced.

Problems

  1. Algorithm: Average Value of an Array [20 points] Write an algorithm to compute the average value of the elements of an array. You can place your code inside the following function fragment:
    
    	function ComputeAverage(A) {
    	    var average = 0;
    	    // put your algorithm here
    	    return average;
    	}    
    
  2. Algorithm: Normalize Values in an Array [25 points] Write an algorithm that given an array of numbers, first computes its maximum value, then divides each element by it. This is known as normalization and it is a very useful in many contexts. You have to use the predefined function max(a,b) that returns the maximum of a,b. For example var m = max(2,3); will set m to 3. You can place your code inside the following function fragment:
    
    	function Normalize(A) {
    		var maximum = 0;
    		// put the code to find the maximum here
    		
    		// put the code to divide each element of A  
    		   // by the maximum and put back the value in A
    		return A;
    	}
    
  3. Algorithm: Computing Duplicates [30 points] Write an algorithm that computes the number of duplicate elements in a sorted array. For example, given A[] = {1,2,2,3,4,4,4,5,5} the values 2,4,5 have 1,2,1 duplicates respectively, so your function should return 4 i.e. 1+2+1. You can place your code inside the following function fragment:
    
    	function CountDuplicates(A) {
    	    var numDuplicates = 0;
    	    // put your algorithm here
    	    return numDuplicates;
    	}    
    
  4. Search [25 points] You are given the sorted array A[] = {3, 6, 9, 12, 14, 18, 21, 22, 31, 43}. For each of the search algorithms covered in class, and listed below, list which numbers will be tested in the array while searching for the numbers 12 and 19:
    1. linear search 1: Search
    2. linear search 2: SortedSearch
    3. binary search: BinarySearch