Thursday March 9

Resume (PDF)

Presentation (PDF)

Presentation (PPTX)

Presentation (PPT)

My Portfolio

Language Polyglot

Merge Sort - Monday Dec. 12

Presentations ...

• PowerPoint
• PDF format

Code ...

//
//  mergesort
//

#include <iostream>
#include <vector>
#include <string>
#include <chrono>
using namespace std;

string chars = "qwertyuioplkjhgfdsazxcvbnm";
int charsPerString = 8;
int stringsPerVector = 20000;

char randomChar() {
    return chars[rand() % chars.size()];
}

string makeRandomString() {
    string s;
    for (int i=0; i<charsPerString; i++) {
        s = s + randomChar();
    }
    return s;
}

vector<string> makeRandomStrings() {
    vector<string> vs;
    for (int i=0; i<stringsPerVector; i++) {
        vs.push_back(makeRandomString());
    }
    return vs;
}

void printVector (vector<string> &vs) {
    for (int i=0; i<vs.size(); i++) {
        cout << vs[i] << endl;
    }
    cout << endl;
}

void bubblesort (vector<string> &vs) {
    for (int i=0; i<vs.size()-1; i++) {
        for (int j=0; j<vs.size()-i-1; j++) {
            if (vs[j] > vs[j+1]) {
                string swapper = vs[j];
                vs[j] = vs[j+1];
                vs[j+1] = swapper;
            }
        }
    }
}

vector<string> merge (vector<string> &a, vector<string> &b) {
    
    // create a new deck
    vector<string> result (a.size() + b.size());
    
    // i -> first deck (a)
    // j -> second deck (b)
    int i = 0;
    int j = 0;
    
    // k -> result deck
    for (int k=0; k<result.size(); k++) {
        
        // finished with a and b?
        if (i >= a.size() && j >= b.size()) {
            break;
        }
        
        // finished with a?
        else if (i >= a.size()) {
            result[k] = b[j++];
        }
        
        // finished with b?
        else if (j >= b.size()) {
            result[k] = a[i++];
        }
        
        // compare
        else if (a[i] < b[j]) {
            result[k] = a[i++];
        }
        else {
            result[k] = b[j++];
        }
    }
    return result;
}

vector<string> partial (vector<string> &vs, long start, long end) {
    vector<string> result (end-start+1);
    for (int i=0; i<result.size(); i++) {
        result[i] = vs[start+i];
    }
    return result;
}

vector<string> mergeSort(vector<string> &vs) {
    
    // check base case for recursion
    if (vs.size() <= 1) {
        return vs;
    }
    
    // find midpoint
    long mid = vs.size() / 2;
    
    // divide into two
    vector<string> lowerHalf = partial (vs, 0, mid-1);
    vector<string> upperHalf = partial (vs, mid, vs.size()-1);
    
    // sort using mergeSort
    vector<string> lowerSorted = mergeSort(lowerHalf);
    vector<string> upperSorted = mergeSort(upperHalf);
    
    // merge the two halves
    return merge(lowerSorted, upperSorted);
}


int main(int argc, const char * argv[]) {
 
    vector<string> unsorted = makeRandomStrings();
    
    printVector (unsorted);
    
    auto beforeMerge = chrono::high_resolution_clock::now();
    vector<string> sorted = mergeSort(unsorted);
    auto afterMerge = chrono::high_resolution_clock::now();
    auto mergeElapsedTime = afterMerge - beforeMerge;
    
    printVector (sorted);
    
    auto beforeBubble = chrono::high_resolution_clock::now();
    bubblesort (unsorted);
    auto afterBubble = chrono::high_resolution_clock::now();
    auto bubbleElapsedTime = afterBubble - beforeBubble;
    
    printVector (unsorted);
    
    cout << "Merge Sort: " << mergeElapsedTime.count() << endl;
    cout << "Bubble Sort: " << bubbleElapsedTime.count() << endl;
    cout << "Improvement factor: " << bubbleElapsedTime / mergeElapsedTime << endl;
    
    return 0;
}

Merge Sort vs. Bubble Sort

I wrote a program that creates 500,000 random strings and sort them twice, once using Merge Sort, and once using Bubble Sort. The Merge Sort completed almost immediately. The Bubble Sort ran for hours ... I started it before lunch, and it just finished.

I added code to calculate the elapsed time for each sort. The Merge Sort was faster by a factor of 3533.

We can code this project together on Monday night. It's 150 lines of code, so bring your computer and be prepared to type fast.

Multiple choice final exam

The multiple choice final exam is not posted yet. It has 40 questions. There will be a time limit of 3 hours. It will cover these topics:

• Most important skill for computer programmers
• Compiling vs. interpreting code
• Portability
• Algorithms
• Strings
• Variables
• Keywords
• Statement
• Functions
• Return values
• Assignment
• Calling a function
• Integer division
• Recursion
• Scaffolding
• Debugging
• Dead code
• Void
• Generalization
• Object
• Traversal
• Compound data types
• Call by reference
• Structure
• Instance variable
• Pure function
• Const
• Top-down design
• Vector
• Loops
• Random numbers
• Constructor
• CPP and H files
• Ordered and unordered sets
• Binary / Bisection search
• Merge sort vs. Bubble sort
• Pseudocode 

split

void split(const string &s, char delim, vector<string> &elems) {

    //-------------------------------------------------------

    // This function splits a line into a vector of strings

    // based on a separating character, such as a comma.

    // s is the input string

    // delim is the separating character.

    // elems is the vector that will hold the output.

    //-------------------------------------------------------

    stringstream ss;

    ss.str(s);

    string item;

    elems.clear();

    while (getline(ss, item, delim)) {

        elems.push_back(item); }

}

Lab Materials for Dec. 5

Presentation

• PowerPoint format
• PDF format

Data

Fields: City, Province, Population, Population Growth in %

Toronto,ON,2615060,9.63
Montreal,QC,1649519,6.62
Calgary,AB,1096833,42.8
Ottawa,ON,833391,22.5
Edmonton,AB,812201,31.79
Missasauga,ON,713443,31.06
Winnipeg,MB,663617,7.3
Vancouver,BC,603502,17.41
Brampton,ON,523911,96.31
Hamilton,ON,519949,11.15

The code:

//
//  main.cpp
//  Dec5Class
//
//  Created by Mark Brautigam on 12/5/16.
//  Copyright © 2016 Mark Brautigam. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

struct City {
    string name;
    string province;
    int population;
    double delta;
};

string baseDir = "/Users/markb/Desktop/";

void split(const string &s, char delim, vector<string> &elems) {
    //-------------------------------------------------------
    // This function splits a line into a vector of strings
    // based on a separating character, such as a comma.
    // s is the input string
    // delim is the separating character.
    // elems is the vector that will hold the output.
    //-------------------------------------------------------
    stringstream ss;
    ss.str(s);
    string item;
    elems.clear();
    while (getline(ss, item, delim)) {
        elems.push_back(item); }
}

void readFileIntoVector (string filepath, vector<City> &vc) {
    ifstream input;
    input.open(baseDir + "canada.csv");
    string line;
    vector<string> fields;
    City city;
    while (!input.eof()) {
        // input >> line;
        getline(input, line);
        if (line.length() < 2)
            continue;
        split (line, ',', fields);
        city.name = fields[0];
        city.province = fields[1];
        city.population = atoi(fields[2].c_str());
        city.delta = atof (fields[3].c_str());
        vc.push_back(city);
    }
    return;
}

void printData(const vector<City> &vc, string fn) {
    ofstream output;
    output.open (fn);
    
    for (int i=0; i<vc.size(); i++) {
        output.width(15);
        output << left << vc[i].name << " ";
        output.width(5);
        output << left << vc[i].province << " ";
        output.width(10);
        output << right << vc[i].population << " ";
        output.width(8);
        output << right << fixed << setprecision(2) << vc[i].delta << " ";
        output << endl;
    }
    output.close();
}

bool outOfOrder(const City &a, const City &b, int sortfield) {
    switch (sortfield) {
        case 0 : return a.name       > b.name;
        case 1 : return a.province   > b.province;
        case 2 : return a.population > b.population;
        case 3 : return a.delta      > b.delta;
        default : return a.name      > b.name;
    }
}

void bubblesort (vector<City> &vc, int sortfield) {
    for (int i=0; i<vc.size(); i++) {
        for (int j=0; j<vc.size()-1; j++) {
            // if (vc[j].delta > vc[j+1].delta) {
            if (outOfOrder (vc[j], vc[j+1], sortfield)) {
                City swap = vc[j];
                vc[j] = vc[j+1];
                vc[j+1] = swap;
            }
        }
    }
}

int requestSortfield() {
    cout << "Choose a field to sort on by number:\n";
    cout << "0 : City\n";
    cout << "1 : Province\n";
    cout << "2 : Population\n";
    cout << "3 : Population Change\n";
    cout << "Your choice: ";
    int user;
    cin >> user;
    return user;
}

int main(int argc, const char * argv[]) {
    
    vector<City> cities;
    
    readFileIntoVector (baseDir + "canada.csv", cities);
    int sortfield = requestSortfield();
    bubblesort (cities, sortfield);
    
    string outputFileName =
        baseDir + "canada-sorted-" + to_string(sortfield) + ".txt";
    
    printData(cities, outputFileName);
    
    return 0;
}

Final Exam: Coding Portion

Here are the instructions: Final exam

Here is the data you will need:

1,Dublin,Dublin,1273069,1380.8,Leinster,7.02
2,Antrim,Ballymena,618108,202.9,Ulster,1.80
3,Down,Downpatrick,531665,215.6,Ulster,8.72
4,Cork,Cork,519032,69.0,Munster,7.84
5,Galway,Galway,250541,40.7,Connacht,8.15
6,Londonderry,Coleraine,247132,119.1,Ulster,4.78
7,Kildare,Naas,210312,124.1,Leinster,12.87
8,Limerick,Limerick,191809,69.4,Munster,4.21
9,Meath,Navan,184135,78.6,Leinster,13.08
10,Tyrone,Omagh,177986,54.5,Ulster,8.37
11,Armagh,Armagh,174792,131.8,Ulster,7.26
12,Donegal,Lifford,161137,32.9,Ulster,9.42
13,Tipperary,Nenagh,158754,36.8,Munster,6.37
14,Kerry,Tralee,145502,30.1,Munster,4.05
15,Wexford,Wexford,145320,61.2,Leinster,10.30
16,Wicklow,Wicklow,136640,67.4,Leinster,8.28
17,Mayo,Castlebar,130638,23.3,Connacht,5.49
18,Louth,Dundalk,122897,148.7,Leinster,10.45
19,Clare,Ennis,117196,33.8,Munster,5.63
20,Waterford,Dungarvan,113795,61.2,Munster,5.40
21,Kilkenny,Kilkenny,95419,46.0,Leinster,8.98
22,Westmeath,Mullingar,86164,46.7,Leinster,8.59
23,Laois,Portlaoise,80559,46.8,Leinster,20.13
24,Offaly,Tullamore,76687,38.3,Leinster,8.21
25,Cavan,Cavan,73183,37.7,Ulster,14.34
26,Sligo,Sligo,65393,35.5,Connacht,7.39
27,Roscommon,Roscommon,64065,25.0,Connacht,9.01
28,Fermanagh,Enniskillen,61170,36.1,Ulster,6.33
29,Monaghan,Monaghan,60483,46.7,Ulster,8.01
30,Carlow,Carlow,54612,60.8,Leinster,8.47
31,Longford,Longford,39000,35.7,Leinster,13.40
32,Leitrim,Carrick-on-Shannon,31796,19.9,Connacht,9.84