CEG220: Introduction to C Programming for Engineers – I

Section 2

Homework for Week 6

1. Write a program that reads in 100 doubles from a file. Now compute the standard deviation.

2. Let’s say you’re writing a program that requires adding up all the values in a given array. Sure, you can do it in a for loop, and once you have your program working, you find that it is incredibly slow. Adding all of the values in an array of size n takes n steps. What we need to ask ourselves: Is there a faster (more optimized) way to do this? Yes –it can be done in log₂ n steps:
1. Group the array into pairs. Add the pairs.
2. Pair up the pairs. Add them.
3. Continue until there are no more pairs and only one value left – the sum.

3. Implement a sorting algorithm of your choice (mergesort, quicksort, bubblesort) that takes a Boolean value, ascending that, if true will sort in ascending order, and if false, will sort in descending order.

4. Now that we know how to use arrays well, we also need to find elements in the array quickly. If we have to search through at most n elements in the array (worst case) to find one element, and do this n times, it’s already taken us n x n = n² steps to perform this series of tasks. Therefore, we must use a heuristic to help speed up the problem. Your task is to devise an algorithm (in pseudo code) that will either find the value’s position in the array, or tell if the value exists. There is one restriction: you cannot use a standard for loop to iterate from 0 to n-1.