CSCI 103L – CS Idioms

Quick Links

Integer Division & Modulo Idioms
Assignment Idioms
- Swap / Rotation
- Moving Window / Shifting
Conditional Idioms
Loop Idioms
- Map Idiom
- Reduction Idiom
- Search Idioms

Integer Division / Modulo

Unit Conversion Idiom

Name : Unit conversion
Motivating Example(s):
- Cents to change (e.g. quarters, dimes, …)
- Ounces to pounds, Items to Dozens, Feet to miles, etc.
Description : Convert a single value into larger units.
Structure: To convert a number n in units-A to units-B (where the conversion factor is k units-A per unit-B): use the integer division, n / k, to determine the integral (whole) number of units-B and n % k to determine the remaining (leftover) units-A.

Example(s): - Convert the given number of ounces to pounds (lbs.) and pounds. There are 16 ounces per pound.

    int oz, lbs;
    cin >> oz; // get the number of ounces
    cout << oz << " ounces => ";

    lbs = oz / 16;  // Convert to the number of pounds
    oz = oz % 16;   // Update remaining ounces
    cout << lbs << " pounds, " <<  oz << " ounces." << endl;

Isolating Digits Idiom

Name : Isolating Digits
Description : Extract the k least-significant digit(s) of a number n (e.g. given n=1234, extract the 1’s digit, 4 or the last 2 digits, 34, etc.). You can also extract the more-significant digits (i.e. the digits above the k least-significant digits).
Structure: The least significant digits can be accomplished with the modulo (%) operator by taking the remainder of n % 10^k (i.e. divide n by 10 to the power of k and take the remainder). Finding the more significant digits beyond the lower k digits can be found by simply using integer division of the same two values: n / 10^k.

Example(s):

Find the 1’s digit of a number

    int n;
    cin >> n; // get an integer from the user

    cout << "The 1s digit of " << n << " is " << n % 10 << endl;

To determine the level of a USC class number (1xx, 2xx, 3xx, 4xx, 5xx, etc.)

    int n;
    cin >> n; // get an integer like 102, 155, etc.

    cout << "Your class' level is " << n/100 << endl;

Divisibility/Factor Idiom

Name : Divisibility/Factor Check
Description : Check whether a number, n, is divisible by some other number, k, (i.e. k is a factor of n) by checking if the remainder of n divided by k is 0.
Structure: This check can be accomplished with the modulo (%) operator and checking if n % k yields 0.

Example(s):

Check if a user provided number, n, is divisible by 3

    int n;
    cin >> n; // get an integer from the user

    if(n % 3 == 0){
        cout << n << " is divisible by 3." << endl;
    }

To check if a number is even or odd, simply check if a number is divisible by 2.

    int n;
    cin >> n; // get an integer from the user

    if(n % 2 == 0){
        cout << n << " is even" << endl;
    }
    else {
        cout << n << " is odd" << endl;
    }

Assignment Idioms

Swap (Rotation)

Name: Swap
Motivating Example(s): Swap or exchange the value of two (or potentially more) variables
Description: Use a temporary variable (to hold a copy of one of the variables) and three assignment statements.
Related to: Moving Window Idiom

Structure: Use a temporary variable (to hold a copy of one of the variables) and three assignment statements. Start by making a copy of the one of the variables and then each successive assignment should overwrite the variable that was just copied.

Rotate Idiom Swap Idiom

      // variables to be swapped
      int x1, x2;

      int temp;

      // Shift each item in reverse order
      // overwriting the value to be dropped first
      temp = x1;      // Make a copy of the first variable
      x1 = x2;        // Now overwrite the first with the second
      x2 = temp;      // Replace the second with the copy of the first

Example(s):

Given two integers, a and b, put the greater number into a and the smaller in b

    int a, b;
    cin >> a >> b;  // Get two numbers

    // Check if b is greater than a
    if(b > a) {
        // Swap the value so the greater values is in a
        int temp = a;
        a = b;
        b = temp;
    }

    // Otherwise the larger number is already in a

Moving-Window (Shifting Values)

Name: Moving-window
Motivating Example(s): Track the best or newest n values,
Description: Use k variables to store values such that when one is added, other values shift variable locations and one value is dropped. In it’s simplest form (k=1) we only need to store 1 variable and overwrite it each time we get a new value, but it becomes more error-prone when k > 1.
Related to: Swap Idiom

Structure: Carefully order assignment statements such that you overwrite (assign) the variable to be dropped (oldest) first and then move each value in “reverse” order until you reach the variable that should get the newest value, at which point you assign the new value to that variable. Be careful not to go in the wrong order (newest to oldest) or you will lose all your values.

Shift Idiom

    // k variables
    //  assume x1 holds the best/newest value while
    //         xk holds the worst/oldest value
    int x1, x2, ...,  xkm1, xk;

    int new_value;
    cin >> new_value; // get a new value

    // Shift each item in reverse order
    // overwriting the value to be dropped first
    xk = xkm1;      // Replace the oldest
    ...             // with 2nd oldest
    x3 = x2;
    x2 = x1;        // The prior newest becomes second newest
    x1 = new_value; // The newest is now update with the latest value

    // We can repeat and do it again
    cin >> new_value; // get another new value

    // Repeat the same assignments as above
    xk = xkm1;
    ...

Example(s):

Produce the sum of the last two numbers entered by the user (e.g. if the user enters: 4 6 2 7 5 produce the output: 10 8 9 12).

     int last, current;
     cin >> last >> current;  // Get the first two numbers to get started
     cout << "Last 2 numbers sum to: " << last + current << endl;

     // Now we'll get one new number at a time, but before we overwrite
     // current we shift it to become the last value.
     last = current;
     cin >> current;
     cout << "Last 2 numbers sum to: " << last + current << endl;

     last = current;
     cin >> current;
     cout << "Last 2 numbers sum to: " << last + current << endl;

     last = current;
     cin >> current;
     cout << "Last 2 numbers sum to: " << last + current << endl;

A certain wealthy businesswoman has a 3 car garage. Because there is only room for 3 cars, each time she purchases a new car she has to sell the car she’s had the longest. The program below tracks which cars are in her garage at each point in time

    string c1, c2, c3; // c1 is the newest car and c3 the oldest
    cin >> c3 >> c2 >> c1;  // She can store her first 3 cars
        // Assume user types in make/model (e.g. "Tesla Model 3")

    cout << "Owned cars: " << c1 << " " << c2 << " " << c3 << endl;

    // Now she'll get a new car but needs to sell her oldest
    c3 = c2;    // 2nd oldest becomes the oldest (oldest is dropped)
    c2 = c1;    // Previous newest becomes second newest
    cin >> c1;  // Input the make/model of the new car
    cout << "Owned cars: " << c1 << " " << c2 << " " << c3 << endl;

    // She buys another
    c3 = c2;    // 2nd oldest becomes the oldest (oldest is dropped)
    c2 = c1;    // Previous newest becomes second newest
    cin >> c1;  // Input the make/model of the new car
    cout << "Owned cars: " << c1 << " " << c2 << " " << c3 << endl;

Common Mistakes:

Because statements execute sequentially (one after the next) and what we assign to a variable in one step is the value that will be used by the next statement to reference that variable, if we assign in the wrong order we will overwrite all our data as in the example below.

    string c1, c2, c3; // c1 is the newest car and c3 the oldest
    cin >> c3 >> c2 >> c1;  // She can store her first 3 cars
        // Assume user types in make/model (e.g. "Tesla Model 3")

    cout << "Owned cars: " << c1 << " " << c2 << " " << c3 << endl;

    //*************************************************************
    // Do NOT use this code - it is an example of what *NOT* to do.
    //*************************************************************

    // Assigning in the wrong order will overwrite all our data
    // Suppose c1 was "Tesla", c2 was "BMW" and c3 was "Audi"
    cin >> c1;  // We now input "Lexus" overwriting "Tesla"
    c2 = c1;    // We then take "Lexus" (new val of c1) and overwrite "BMW"
    c3 = c2;    // And then take "Lexus" from c2 and overwrite "Audi"
    cout << "Owned cars: " << c1 << " " << c2 << " " << c3 << endl;

    // This would print: "Owned cars: Lexus Lexus Lexus"

Exercise(s):
Understand the code above for outputting the sum of the last two numbers the user enters and consider how you can extend it if we want to produce the sum of the last 3 numbers entered, rather than last 2.

Conditional Idioms

Lookup Table

Name: Look-up table (Parallel cases)
Motivating Example(s):
- Determine win, lose, or draw based on score
- Determine your tax bracket
- Applying different rules based on age, year in school, or some other characteristic
Description: Break input options into mutually exclusive cases (or ranges) and convert (aka map) each input option to another output option

Structure: Use a single level (not nested) if…else if…else structure to check for each input case and convert to the desired output value.

Lookup-Table Idiom

// check each case
if( /* Case 1 condition */ ) {
    // Produce output 1
}
else if( /* Case 2 condition */ ) {
    // Produce output 2
}
else if( /* Case 3 condition */ ) {
    // Produce output 3
}
else {
    // Produce default output
}

Example(s):

Determine letter grades

int pct;
cin >> pct;  // Get user input

// Output all the odd numbers
if(pct >= 90){
    cout << "A" << endl;
}
else if(pct >= 80){
    cout << "B" << endl;
}
else if(pct >= 70){
    cout << "C" << endl;
}
else if(pct >= 60){
    cout << "D" << endl;
}
else {
    cout << "F" << endl;
}

Determine if a number if positive, negative, or 0

int n;
cin >> n;  // Get user input

// Output all the odd numbers
if(n > 0){
    cout << "Positive" << endl;
}
else if(n < 0){
    cout << "Negative" << endl;
}
else {
    cout << "Zero" << endl;
}

Decision Tree

Name: Decision Tree (Sequential cases)
Motivating Example(s):
- Help systems such as medical diagnosis, computer or automotive repair, etc.
- Multi-level menus (customer service or hierarchical organization)
Description: Use a sequence of checks or process of elimination to identify a particular case and perform an appropriate action.

Structure: Use nested if..else if...else statements. The outer if..else if statements check the most general cases (or the first level criteria) while the inner if…else if…else structure checks more specific values (or the next level criteria).

Decision Tree Idiom

// check each case
if( /* Top-level condition 1 */ ) {

    // Nested if statement for Next-level condition
    if( /* Next-level condition A */ ) {

    }
    else if ( /* Next-level condition B */ ) {

    }
    else { /* Next-level condition C */

    }
}
else if( /* Top-level condition 2 */ ) {
    // Nested if statement for Next-level condition

} else { /* Top-level condition 3 */ // Nested if statement for Next-level condition

} ```

Example(s):

Automated customer service

if( option1 == "accounts" )  {
    // account related services
    if( option2 == "balance" ) {
        // Code to retrieve balance
    }
    else if(option2 == "cancel" ) {
        // Code to cancel account
    }
}
else if (option1 == "hours")
{
    // code to list hours
}
else
{
    // repeat options
}

Choosing a major based on personal interest

      string general_interest, specific_interest;
      cin >> general_interest >> specific_interest;

      string suggested_major;
      if(general_interest == "engineering"){
          if(specific_interest == "software"){
              suggested_major = "CSCI";
          }
          else if(specific_interest == "cars"){
              suggested_major = "ME";
          }
          else {
              suggested_major = "EE";
          }
      }
      else if(general_interest == "sciences"){
          if(specific_interest == "medicine"){
              suggested_major = "BIO";
          }
          else if(specific_interest == "astronomy"){
              suggested_major = "PHYS";
          }
          else {
              suggested_major = "CHEM";
          }

      }
      else if(general_interest == "humanities"){
          if(specific_interest == "literature"){
              suggested_major = "ENGL";
          }
          else {
              suggested_major = "PSYC";
          }
      }
      else {
          suggested_major = "BUAD";
      }

Notes: This can be implemented with one level of if/else statements using logical-AND operators (&&) where general conditions are repeated with each specific condition (e.g. if(general_interest == "engineering" && specific_interest == "software") and else if("general_interest == "engineering" && specific_interest == "cars")).

Rule / Exception Idiom

Name : Rule/Exception
Description : Perform a default action and then us an if to correct for exceptional cases
Structure: Code for some default action (i.e. the rule) is followed by if statement with code to correct the exceptional case
```
// Default action

if( /* Exceptional Case */ )
{
    // Code for exceptional case
}
```

Example(s):

Base pay plus bonus for certain exceptional employees

    bool earnedBonus = /* set somehow */;
    int bonus = /* set somehow */;

    int basePay = 100;
    if( earnedBonus == true )
    {
        basePay += bonus;
    }

Notes: This can be implemented with an if/else where an if implements the rule (or exception) and the else implements the other.

Loop Idioms

Map

Name: Map
Motivating Example(s):
- Map numeric scores to letter grades
- For each x compute f(x) (e.g. output the first n odd integers, n : 2*n+1)
Description: Convert (map) each value in a collection to another value
Related to: Often combined with the Selection idiom (if reducing only values that meet some criteria)

Structure: Loop through each element and apply the desired operation.

// loop through each instance
for( /* each instance, i */ ) {
    // Map each value based on i
}

Example(s):

Output the first n positive, odd numbers

int n;
cin >> n;  // Get user input

// Output all the odd numbers
for( int i = 0; i < n; i++ ) {
    cout << 2*i + 1 << endl;
}

Output the value of f(x) = ax^2 + bx + c for x in the range [-10,+10] with a stepsize of 0.2

double a, b, c, x;
cin >> a >> b >> c;  // Get the coefficients: a, b, c

// Generate each value of x
for( x = -10; x <= 10; x += 0.2 ) {
    // Now map x to f(x)
    cout << a*x*x + b*x + c << " ";
}
cout << endl;

Reduce

Name: Reduce / Combine / Aggregate
Motivating Example(s):
- Compute the average of a collection of numbers
- Perform numerical integration of a function over a range
Description: Combine/reduce all elements of a collection to a single (or constant number of) value(s)
Related to: Often combined with the Selection idiom (if reducing only values that meet some criteria)
Structure: Declare and initialize a “reduction” variable to store the combined/aggregated value (usually initalizing it to the identity function for the given operation such as 0 for addition, 1 for multiplication, etc.). Then loop through each element and combine the element with the “reduction” variable using the desired operation.
```
// reduction variable
int reduction_variable = identity_value; // (e.g. 0)
// loop through each instance
for( /* each instance, i */ ) {
    reduction_variable = reduction_vaiable op i
}
```

Example(s):

Average the first n integers input by the user

int n, val;
cin >> n;  // The user first enters the number, n
           // Then the user will enter n integers

int sum = 0; // Reduction variable
for( int i = 0; i < n; i++ ) {
    cin >> val;
    sum += val;
}
cout << "Average: " << (double) sum / n << endl;

Integrate the value of f(x) = ax^2 + bx + c for x in the range [-10,+10] using dx=0.01

double a, b, c, x;
cin >> a >> b >> c;  // Get the coefficients: a, b, c

// Compute f(x) and integrate each small f(x)*dx area
double sum = 0.0, dx = 0.01;
for( x = -10; x <= 10; x += dx ) {
    // Now map x to f(x)
    sum += (a*x*x + b*x + c) * dx;
}
cout << endl;

Search Idioms

Selection

Name: Selection
Motivating Example(s):
- Find the minimum or maximum element from a collection
- Count how many students scored an A on the exam
Description : Select a subset (possibly one or none) of elements from a collection based on a particular property
Related to: Distributed-AND Idiom and Distributed-OR Idiom

Structure: Loop through each element and check whether it meets the desired property. If so, perform a map, reduce, or other other update operation.

// declare/initialize any state variables needed
//  to track the desired result

// loop through each instance
for( /* each instance, i */ ) {
    // Check if this instance meets the property
    if(condition) {
        // Update state (variables) appropriately
    }
}
// The state variables now have the desired answer

Example(s):

Count how many students scored an A on the exam.

    int n, score;
    cin >> n;  // User will enter how many scores they will enter

    // declare/initialize any state variables needed
    //  to track the desired result
    int count = 0;
    // loop through each instance
    for( int i = 0; i < n; i++ ) {
        cin >> score;
        // Check if this instance meets the property
        if(score >= 90) {
            // Update state (variables) appropriately
            count++;
        }
    }
    // The state variables now have the desired answer
    cout << count << " people got an A" << endl;

Succeed Early / Fail At The End (Distributed-OR)

Name : Distributed-OR
Problem Characteristic: Succeed Early / Fail at the End
Motivating Example(s):
- Check if anyone got a perfect score on an exam
- Search for a number in a collection
Description : Determines if a property is true for SOME instance of a collection.
Related to: Distributed-AND Idiom

Structure: Loop through each instances and check whether an instance meets the desired property. If so, set a variable and stop the search. Only if we loop through all the instances can we prove no instance met the property, but if even just one case did meet the property we can stop.

    // default to false, then prove some instance meets
    // the desired property
    bool result = false;
    // loop through each instance
    for( /* each instance, i */ ) {
        // Check if this instance meets the property
        if(condition) {
            // Set the result and stop
            result = true;
            break;
        }
    }
    // if we made it through all iterations of the loop
    // the property is false

Example(s):

Determine if any one got a perfect scores (i.e. 100) on an exam.

int n, val;
cin >> n;  // User will enter how many scores they will enter

 // start with an assumption of false
bool result = false;
// loop through each case
for( int i = 0; i < n; i++ ) {
    cin >> val;
    // Check if this is a perfect score
    if(val == 100) {
        result = true;
        break;  // Stop the search
    }
}
// if we made it through all iterations of the loop
// the property is false
if(result == true) {
    cout << "There is a perfect score" << endl;
}
else {
    cout << "No perfect scores exist." << endl;
}

Find the index in an array of a specific target value, or -1 if the target number does not exist. (Note: This example uses arrays which may or may not have been covered in your lecture.)

int data[100], target;
cin >> target;  // The user will enter the desired target
                // to search for

 // start with an assumption that it is NOT present
int idx = -1;
// loop through each case
for( int i = 0; i < n; i++ ) {
    if(data[i] == target) {
        idx = i; // save the index where the target is located
        break;   // Stop the search
    }
}
// if we made it through all iterations of the loop
// the property is false
if(idx == -1) {
    cout << target << " does NOT exist in the array" << endl;
}
else {
    cout << target << " exists at index " << idx << endl;
}

Fail Early / Succeed At The End (Distributed-AND)

Name : Distributed-AND
Problem Characteristic: Fail Early / Succeed at the End
Motivating Example(s):
- Check if everyone passed the exam
- Determine if a number is prime
Description : Determines if a property is true for ALL instances of a collection.
Related to: Distributed-OR Idiom
Structure: Loop through each case or condition. If it is false, we have proven the property doesn’t hold for all instances and we quit the loop early (before checking the remaining instances. If it is true, move on to the next case. Not until we loop through all the instances can we prove the property is true, but if just one case is false we have proven the property is false and can stop.
```
// default to true, then prove it false
bool result = true;
// loop through each case
for( /* each instance, i */ ) {
    if(condition) {
        result = false;
        break;
    }
}
// check the result variable with an if statement

// if we made it through all iterations of the loop
// the property is true
```

Example(s):

Check if all n numbers entered are 70 or more

int n, val;
cin >> n;  // User will enter how many values they will enter

 // set a variable to true
bool result = true;
// loop through each case
for( int i = 0; i < n; i++ ) {
    cin >> val;
    if(val < 70) {
        result = false;
        break;
    }
}
// if we made it through all iterations of the loop
// the property is true
if(result == true) {
    cout << "All numbers are 70 or more" << endl;
}
else {
    cout << "At least one number less than 70" << endl;
}