## Quick Links

- Integer Division & Modulo Idioms
- Assignment Idioms
- Conditional Idioms
- Loop 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; }`

- Check if a user provided number,

## 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.`// 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`

```c++ 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.`// 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.`// 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).`// 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; }`