Algorithm Lab                

Introduction                

In this lab, we will practice using a number of C++ algorithms. Here is the file algorithm.cc:                 

#include <algorithm>
#include <iostream>
#include <list>
#include <string>
#include <vector>

using namespace std;

int main() {
    vector<short> pi = {3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4};
    string alpha="abcdefghijklmnopqrstuvwxyz", digits="0123456789";
    char cbuf[100] = { };       // contains 100 '\0' chars
    list<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    short powers[] = {1,2,4,8,16,32,64};
    int ibuf[100];              // contains unknown values

    cout << "Exercise 0\n";
    cout << "Exercise 1\n";
    cout << "Exercise 2\n";
    cout << "Exercise 3\n";
    cout << "Exercise 4\n";
    cout << "Exercise 5\n";
    cout << "Exercise 6\n";
    cout << "Exercise 7\n";
    cout << "Exercise 8\n";
    cout << "Exercise 9\n";
    cout << "Exercise 10\n";
}

Copy it to your current directory, like this:                 

    cp ~cs253/Lab/Algorithm/algorithm.cc .

We will modify it during this lab. At the end of the lab, copy algorithm.cc to recit13.txt, and turn it in for credit.                 

The <algorithm> (it’s a link--click on it) header file defines several dozen algorithms. We will not cover them all. Instead, we will select ten or so, and focus on those as exercises. Each exercise will contain a link to the algorithm that you must use.                 

Overview                

All algorithms use half-open intervals. That is, they take pairs of iterators (or plain pointers) that describe part of an array, vector, linked list, or other container.                 

For example, the copy() algorithm takes three arguments:

• first (beginning of input range)
• last (one past the end of input range)
• d_first (start of output)

The copy() algorithm copies the half-open interval [first,last) to d_first. We don’t need a fourth argument that defines the end of the output range—we just keep copying, writing to subsequent locations starting at d_first, until we run out of input range.                 

The various algorithms are all like that. They use half-open intervals to achieve various goals.                 

For all of these exercises, you must use the indicated algorithm to accomplish the task. You may not do it by other means. The purpose is to gain proficiency in using these algorithms.                 

Exercises                

Exercise 0: copy()                

After cout << "Exercise 0\n"; using the copy() algorithm, copy the alphabet from alpha to cbuf and display it, by adding this code:                 

    copy(alpha.begin(), alpha.end(), cbuf);
    cout << "Exercise 0: " << cbuf << '\n';

Compile & execute this code; observe that it works.                 

Exercise 1: reverse()                

After cout << "Exercise 1\n"; add code that uses the reverse() algorithm to reverse the order of the first 26 characters in cbuf, in place. Do not simply reverse all the characters by typing them in z…a order. Instead, use the reverse() algorithm to do the work. Write the reversed alphabet from cbuf.                 

Exercise 2: transform()                

Let’s assume that, from now own, you know to add to add code after cout << "Exercise N\n";.                 

Use transform() to copy from primes to ibuf, incrementing each value by 1, so that ibuf will contain 3, 4, 6, 8, …. Use a lambda-expression to do the increment. Display the first ten ints in ibuf.                 

Exercise 3: any_of()                

Using any_of(), display "div 2\n" if primes contains an even number. Also, display "div 42\n" if primes contains a number divisible by 42.                 

Exercise 4: find()                

Using find(), look for a 13 in primes. Using the iterator returned by find(), display the number after 13 (it should be 17).                 

Exercise 5: count()                

Using count(), display how many times the digit 3 occurs in the vector pi.                 

Exercise 6: count_if()                

Using count_if(), display how many of the digits in the vector pi are less than 5.                 

Exercise 7: max_element()                

Use max_element() to find the largest digit in pi. Display it.                 

Exercise 8: sort()                

Using sort(), sort the digits of pi and display them.                 

Exercise 9: binary_search()                

The algorithm lower_bound() finds an element in a sorted interval using a binary search. If that element is not present, it returns an iterator indicating where it should go.                 

Use lower_bound() to find the 7 in the sorted pi. Display the index of the 7, where 0 is the first entry, 1 is the next entry, etc., by calculating the difference between the iterator returned by lower_bound() and the .begin() iterator for pi.                 

Exercise 10: set_intersection()                

Using set_intersection(), calculate the set intersection (elements in common) between pi and powers. Put them into ibuf, and display them. set_intersection() returns an iterator, one past where it wrote the last element. Use a for loop, from &ibuf[0] to that iterator, to display only the relevant the contents of ibuf.                 

How to submit your work                

Copy algorithm.cc to recit13.txt, and then:                 

• Use web checkin, or Linux checkin:

~cs253/bin/checkin RECIT13 recit13.txt                 

How to receive negative points:                

Turn in someone else’s work.