# 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

**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; }`

**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; }`

**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; }`

**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`

:- linear search 1:
`Search`

- linear search 2:
`SortedSearch`

- binary search:
`BinarySearch`

- linear search 1: