CSI 1430 Final Exam Review Notes

Loop

• A program construct that repeatedly executes statements (loop body) while the loop's expression is true.
• When the expression is false, execution proceeds past the loop.

Iteration

• Each time through a loop's statements.

Program Execution

• Programs execute one statement at a time.

While Loop

• A program construct that repeatedly executes sub-statements (loop body) while the loop's expression evaluates to true.
• Once entering the loop body, execution continues to the body's end, even if the expression would become false midway through.

Infinite Loop

• A loop that never stops iterating.

Do-While Loop

• A loop construct that first executes the loop body's statements, then checks the loop condition.
• Useful when the loop should iterate at least once.

Sentinel Value

• A special value indicating the end of a list.
• Example: A list of positive integers ending with 0, as in 10 1 6 3 0.

For Loop

• A loop with three parts at the top: loop variable initialization, a loop expression, and a loop variable update.

Nested Loop

• A loop that appears in the body of another loop.
• The nested loops are commonly referred to as the inner loop and outer loop.

Incremental Program Development

• Creating a simple program version, and then growing the program little-by-little into successively more-complete versions.

FIXME Comment

• Commonly used to indicate program parts to be fixed or added.
• Some editor tools automatically highlight the FIXME comment to attract the programmer's attention.

Break Statement

• Causes an immediate exit of the loop.

Continue Statement

• Causes an immediate jump to the loop condition check.

Scope

• A declared name is only valid within a region of code.

Block

• A brace-enclosed {…} sequence of statements, such as found with an if-else, for loop, or while loop.
• A variable name's scope extends from the declaration to the closing brace }.

Enumeration

• Type that declares a name for a new type and possible values for that type.

State Machine

• Any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change.

Array

• A special variable having one name but storing a list of data items, with each item being directly accessible.

Element

• Each item in an array or vector.

Index

• In an array, each element's location number.

Vector

• An ordered list of items of a given data type.

Angle Brackets, Braces

• Angle brackets: < >
• Braces: { }

Vector Operations

• Get index of vector: .at()
• Get size of vector: .size()
• Constant array: const (array) - prepended to an array variable declaration to prevent changes to the array
• Vector resize: .resize()
• Append to vector: .push_back()
• Return last element of vector: .back()
• Remove last element of vector: .pop_back()

String Copy Functions

• strcpy(destStr, sourceStr): Copies sourceStr (up to and including null character) to destStr.
• strncpy(destStr, sourceStr, numChars): Copies up to numChars characters.
• strcat(destStr, sourceStr): Copies sourceStr (up to and including null character) to end of destStr (starting at destStr's null character).
• strncat(destStr, sourceStr, numChars): Copies up to numChars characters to destStr's end, then appends null character.

Function

• A named list of statements.

Function Definition

• Consists of the new function's name and a block of statements.

Function Call

• An invocation of a function's name, causing the function's statements to execute.

Parameter

• A function input specified in a function definition.

Argument

• Value provided to a function's parameter during a function call.

Return Statement

• A function may return one value.

Return Type of Void

• Indicates that a function does not return any value.

Modular Development

• Process of dividing a program into separate modules that can be developed and tested separately and then integrated into a single program.

Incremental Development

• A process in which a programmer writes, compiles, and tests a small amount of code, then writes, compiles, and tests a small amount more (an incremental amount), and so on.

Function Stub

• A function definition whose statements have not yet been written.

Unit Testing

• The process of individually testing a small part or unit of a program, typically a function.

Testbench

• Also known as a test harness, which is a separate program whose sole purpose is to check that a function returns correct output values for a variety of input values.

Border Cases

• Test vectors that represent any extreme inputs that might cause the method to fail. Examples: 0, 999999999, negative numbers.

Program

• Consists of instructions executing one at a time.

Input

• A program gets data, perhaps from a file, keyboard, touchscreen, network, etc.

Process

• A program performs computations on that data, such as adding two values like $x + y$.

Output

• A program puts that data somewhere, such as to a file, screen, network, etc.

Variables

• Refers to data, like x, y, and z below. The name is due to a variable's value varying as a program assigns a variable like x with new values.

Computational Thinking

• Creating a sequence of instructions to solve a problem.

Algorithm

• A sequence of instructions that solves a problem.

Semicolon

• Each statement typically appears alone on a line and ends with a semicolon (;).

Program Start

• A program starts at main().

Code

• The textual representation of a program.

Cin

• Short for "characters in".
• Gets an input value and puts that value into a variable.

Cout

• Construct supports output.

String Literal

• Text in double quotes "".

Endl

• Outputs a new line.

Single-Line Comment

• Starts with // and includes all the following text on that line.
• Commonly appears after a statement on the same line.

Multi-Line Comment

• Starts with /* and ends with /, where all text between / and */ is part of the comment.
• Also known as a block comment.

Whitespace

• Refers to blank spaces (space and tab characters) between items within a statement and blank lines between statements (called newlines).
• A compiler ignores most whitespace.

Syntax Error

• Violates a programming language's rules on how symbols can be combined to create a program.
• A type of compile-time error.

Logic Error (Bug)

• An error that occurs while a program runs.
• The program would compile but would not run as intended.

Compilation Practice

• Good practice for compiling code is to compile after writing only a few lines of code, rather than writing tens of lines and then compiling.

Warning

• Doesn't stop the compiler from creating an executable program but indicates a possible logic error.

Bits

• 0s and 1s.

Processor

• Processes (aka executes) a list of desired calculations, with each calculation called an instruction.

Instruction

• Specified by configuring external switches.

Memory

• A circuit that can store 0s and 1s in each of a series of thousands of addressed locations, like a series of addressed mailboxes that each can store an envelope (the 0s and 1s).

Machine Instructions

• Instructions represented as 0s and 1s.

Executable Program

• A sequence of machine instructions together.

Assembly Language

• Programming language that has the same structure and set of commands as machine languages but allows programmers to use symbolic representations of numeric machine code.

High-Level Languages

• Machine independent and part of the third-generation of computer languages.
• Many languages are available, and each is designed for a specific purpose.

Compilers

• Are programs that automatically translate high-level language programs into executable programs.

Disk

• Stores files and other data.

RAM

• Temporary holding area for information and software.

Clock

• A processor's instructions execute at a rate governed by the processor's clock, which ticks at a specific frequency.

Transistors

• Small electrical devices that could receive and amplify radio signals.

Integrated Circuit

• A thin slice of silicon that contains many solid-state components.

Moore's Law

• The number of transistors per square inch on an integrated chip doubles every 18 months.

C Programming Language

• Created by Brian Kerighan and Dennis Ritchie in 1978.

C++

• Created by Bjarne Stroustrup in 1985.

Problem Solving

• Creating a methodical solution to a given task.

Variable

• A named item such as x or numPeople used to hold a value.

Assignment

• Assigns a variable with a value.

Increment

• Increase.

Variable Declaration

• A statement that declares a new variable.

Assignment Statement

• Assigns the variable on the left-side of the = with the current value of the right-side expression.

Identifier

• A name created by a programmer for an item like a variable or function.
• Identifiers are case-sensitive.

Reserved Word (Keyword)

• A word that is part of the language, like int, short, or double.

Expression

• A combination of items, like variables, literals, operators, and parentheses, that evaluates to a value, like 2 * (x + 1).

Literal

• A specific value in code like 2.

Operator

• A symbol that performs a built-in calculation, like +, which performs addition.
• Common programming operators: +, -, *, /

Unary Minus

• An exception is minus used as negative.

Compound Operators

• Provide a shorthand way to update a variable, such as userAge += 1 being shorthand for userAge = userAge + 1.

Incremental Development

• The process of writing, compiling, and testing a small amount of code, then writing, compiling, and testing a small amount more (an incremental amount), and so on.

Floating-Point Number

• A real number, like 98.6, 0.0001, or -666.667.

Floating-Point Literal

• A number with a fractional part, even if that fraction is 0, as in 1.0, 0.0, or 99.573.
• Good practice is to always have a digit before the decimal point, as in 0.5, since .5 might mistakenly be viewed as 5.

NaN

• Indicates an unrepresentable or undefined value.
• Printing a floating-point variable that is not a number outputs nan.

Constant Variable

• An initialized variable whose value cannot change.

Define Macro

• #define MACROIDENTIFIER replacement instructs the processor to replace any occurrence of MACROIDENTIFIER in the subsequent program code by the replacement text.

Function

• A list of statements executed by invoking the function's name.

Divide-by-Zero Error

• Occurs at runtime if a divisor is 0, causing a program to terminate.

Modulo Operator

• $$
• Evaluates the remainder of the division of two integer operands.

Type Conversion

• A conversion of one data type to another, such as an int to a double.

Implicit Conversion

• The compiler automatically performs several common conversions between int and double types, such automatic conversion.

Type Cast

• Explicitly converts a value of one type to another type.

Static_cast

• Converts the expression's value to the indicated type.

Binary Number

• A number written in the binary system, a system that uses only two digits, 0s and 1s.

Decimal Number

• Each digit must be 0-9, and each digit's place is weighed by increasing powers of 10.

Character Literal

• Surrounded with single quotes.

Escape Sequence

• A two-character sequence starting with \ that represents a special character.

Overflow

• Occurs when the value being assigned to a variable is greater than the maximum value the variable can store.

Long Long

• Used for integers expected to exceed about 2 billion.

Unsigned

• The programmer can prepend the word "unsigned" to inform the compiler that the integers will always be positive.

Rand()

• In the C standard library, returns a random integer each time the function is called, in the range 0 to RAND_MAX.

Time()

• Returns the number of seconds since Jan 1, 1970.

Debugging (Troubleshooting)

• The process of determining and fixing the cause of a problem in a computer program.

Branch

• A program path taken only if an expression's value is true.

If Branch

• A branch taken only if an expression is true.

If-Else Structure

• The first branch is taken if an expression is true, else the other branch is taken.

Braces

• { }, sometimes redundantly called curly braces, represent a grouping, such as a grouping of statements. Note: { } are braces, [ ] are brackets.

Brackets

• [ ]

Equality Operator

• $==$
• Evaluates to true if the left side and right side are equal.

Nested If-Else Statements

• A branch's statements can include any valid statements, including another if-else statement.

Boolean

• A type that has just two values: true or false.

Relational Operator

• Checks how one operand's value relates to another, like being greater than.

Logical Operators

• Treats operands as being true or false and evaluates to true or false.
• Logical operators include AND, OR, and NOT.

Precedence Rules

• The order in which operators are evaluated in an expression.

Bitwise Operators

• Used to manipulate individual bits of values.

Switch Statement

• Can more clearly represent multi-branch behavior involving a variable being compared to constant values.

Case

• Whose constant expression matches the value of the switch expression.

Default Case

• If no case matches, then the default case statements are executed.

Break Statement

• A statement that terminates a loop or switch statement.

Index

• Each string character position.

.at()

• The notation someString.at(x) accesses the character at index x of a string.

.size()

• The function s1.size() returns s1's length. Ex: If s1 is "Hey", s1.size() returns 3.

.append()

• The function s1.append(s2) appends string s2 to string s1. Ex: If s1 is "Hey", s1.append("!!!") makes s1 "Hey!!!".

Exception

• A detected runtime error that commonly prints an error message and terminates the program.

cctype Library

• Provides access to several functions for working with characters.

find()

• find(item) returns index of first item occurrence, else returns string::npos (a constant defined in the string library).
• Item may be char, string variable, string literal (or char array).

substr()

• substr(index, len) returns substring starting at index and having len characters.

push_back()

• push_back(c) appends character c to the end of a string.

insert()

• insert(indx, subStr) Inserts string subStr starting at index indx.

replace()

• replace(indx, num, subStr) replaces characters at indices indx to indx+num-1 with a copy of subStr.

String Concatenation

• str1 + str2 returns a new string that is a copy of str1 with str2 appended.

Conditional Expression

• Has the form condition ? exprWhenTrue : exprWhenFalse.

Ternary Operator

• An operator that takes three arguments.

Epsilon

• The difference threshold indicating that floating-point numbers are equal.

Short Circuit Evaluation

• Skips evaluating later operands if the result of the logical operator can already be determined.

Object

• A grouping of data (variables) and operations that can be performed on that data (functions).

Abstraction

• Means to have a user interact with an item at a high-level, with lower-level internal details hidden from the user (aka information hiding or encapsulation).
• Ex: An oven supports an abstraction of a food compartment and a knob to control heat. An oven's user need not interact with internal parts of an oven.

Abstract Data Type (ADT)

• A data type whose creation and update are constrained to specific well-defined operations.
• A class can be used to implement an ADT.

Class Construct

• Defines a new type that can group data and functions to form an object.

Public Member Functions

• Indicate all operations a class user can perform on the object.

Member Access Operator

• Is used to invoke a function on an object.
• Ex: favLunchPlace.SetRating(4) calls the SetRating() function on the favLunchPlace object, which sets the object's rating to 4.

Private Data Members

• Variables that member functions can access but class users cannot.
• Private data members appear after the word "private:" in a class definition.

Function Declaration

• Provides the function's name, return type, and parameter types, but not the function's statements.

Function Definition

• Provides a class name, return type, parameter names and types, and the function's statements.

Scope Resolution Operator

• A member function definition has the class name and two colons (::), preceding the function's name.

Inline Member Function

• A member function's definition may appear within the class definition.

Mutator Function

• May modify ("mutate") a class' data members.

Accessor Function

• Accesses data members but does not modify a class' data members.

Private Helper Functions

• Help public functions carry out tasks.

Constructor

• Called automatically when a variable of that class type is declared and which can initialize data members.

Default Constructor

• A constructor callable without arguments.

Header File

• Contains the class definition, including data members and member function declarations.
• Sufficient to allow compilation.

CPP Class File

• Contains member function definitions.

Struct

• Defines a new type, which can be used to declare a variable with subitems.

Data Member

• Each struct subitem.

Testbench

• A program whose job is to thoroughly test another program (or portion) via a series of input/output checks known as test cases.

Unit Testing

• Means to create and run a testbench for a specific item (or "unit") like a function or a class.

Regression Testing

• Means to retest an item like a class anytime that item is changed; if previously-passed test cases fail, the item has "regressed".

Overload a Constructor

• Defining multiple constructors differing in parameter types.

Constructor Initializer List

• An alternative approach for initializing data members in a constructor, coming after a colon and consisting of a comma-separated list of variableName(initValue) items.

Implicit Parameter

• The object variable before the function name.

This

• Within a member function, the implicitly-passed object pointer is accessible via this.

Sort()

• Defined in the C++ Standard Template Library's (STL) algorithms library, can sort vectors containing objects of programmer-defined classes.

Static Keyword

• Indicates a variable is allocated in memory only once during a program's execution.
• Static variables reside in the program's static memory region and have a global scope.
• Thus, static variables can be accessed from anywhere in a program.

Ostream

• Short for "output stream," is a class that supports output, available via #include and in namespace "std".

Istream

• Short for "input stream," is a class that supports input.
• Available via #include , istream provides the >> operator, known as the extraction operator, to extract data from a data buffer and write the data into different types of variables.

Manipulator

• A function that overloads the insertion operator << or extraction operator >> to adjust the way output appears.
• Manipulators are defined in the iomanip and ios libraries in namespace std.
• fixed: Use fixed-point notation.
• scientific: Use scientific notation.
• setprecision: If stream has not been manipulated to fixed or scientific: Sets max number of digits in number.
• showpoint: Even if fraction is 0, show decimal point and trailing 0s. Opposite is noshowpoint. From
• setw: Sets the number of characters for the next output item only (does not persist, in contrast to other manipulators).By default, the item will be right-aligned and filled with spaces.From
• setfill: Sets the fill to character c. From
• left: Changes to left alignment. From
• right: Changes back to right alignment. From
• flush: Informs the system to flush the buffer. From

Istringstream

• Reads input from an associated string instead of the keyboard (standard input).

eof()

• End of file that returns true or false depending on whether or not the end of the stream has been reached.

Ostringstream

• Insert characters into a string buffer instead of the screen.

Stream Error

• Occurs when insertion or extraction fails, causing the stream to enter an error state.
• Ex: If a file has the string two but the program attempts to extract an integer, the extraction will fail and the stream will enter an error state.

Linear Search

• A search algorithm that starts from the beginning of a list and checks each element until the search key is found or the end of the list is reached.

Runtime

• The time the algorithm takes to execute.

Big O Notation

• A mathematical way of describing how a function (running time of an algorithm) generally behaves in relation to the input size.
• In Big O notation, all functions that have the same growth rate (as determined by the highest order term of the function) are characterized using the same Big O notation.

Worst-Case Runtime

• The runtime complexity for an input that results in the longest execution.

Sorting

• The process of converting a list of elements into ascending (or descending) order.

Selection Sort

• A sorting algorithm that treats the input as two parts: a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part.

Binary Search

• A faster algorithm for searching a list if the list's elements are sorted and directly accessible (such as an array).
• Binary search first checks the middle element of the list. If the search key is found, the algorithm returns the matching location.
• If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element).

Insertion Sort

• A sorting algorithm that treats the input as two parts: a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part.

Nearly Sorted List

• Only contains a few elements not in sorted order.
• Ex: {4, 5, 17, 25, 89, 14} is nearly sorted having only one element not in sorted position.

Pointer

• A variable that contains a memory address.
• This section describes a few situations where pointers are useful.

Linked List

• Consists of items that contain both data and a pointer—a link—to the next list item.

Reference Operator (&)

• Obtains a variable's address.

Dereference Operator (*)

• Is prepended to a pointer variable's name to retrieve the data to which the pointer variable points.
• Ex: If valPointer points to a memory address containing the integer 123, then cout << *valPointer; dereferences valPointer and outputs 123.

New Operator

• Allocates memory for the given type and returns a pointer to the allocated memory.

Delete Operator

• Deallocates (or frees) a block of memory that was allocated with the new operator.

Array-Based List

• A list ADT implemented using an array.
• An array-based list supports the common list ADT operations, such as append, prepend, insert after, remove, and search.

Prepend Operation

• Operation for an array-based list inserts a new item at the start of the list.

InsertAfter Operation

• Operation for an array-based list inserts a new item after a specified index.

Search Operation

• Returns the index for the first element whose data matches that key, or -1 if not found.

Remove-At Operation

• Removes the item at that index.

The Heap

• The region where the "new" operator allocates memory and where the "delete" operator deallocates memory.
• The region is also called free store.

The Stack

• The region where a function's local variables are allocated during a function call.
• A function call adds local variables to the stack, and a return removes them, like adding and removing dishes from a pile; hence the term "stack."
• Because this memory is automatically allocated and deallocated, it is also called automatic memory.

List Node

• A class is defined to represent each list item.

Destructor

• A special class member function that is called automatically when a variable of that class type is destroyed.
• C++ class objects commonly use dynamically allocated data that is deal located by the class's destructor.

Memory Leak

• Occurs when a program that allocates memory loses the ability to access the allocated memory, typically due to failure to properly destroy/free dynamically allocated memory.

Garbage Collection

• A program's executable includes automatic behavior that at various intervals finds all unreachable allocated memory locations.

Copy Constructor

• A constructor that is automatically called when an object of the class type is passed by value to a function and when an object is initialized by copying another object during declaration.

Deep Copy

• The copy constructor makes a new copy of all data members.

Shallow Copy

• Creating a copy of an object by copying only the data members' values creates a shallow copy.

Rule of Three

• Describes a practice that if a programmer explicitly defines any one of those three special member functions (destructor, copy constructor, copy assignment operator), then the programmer should explicitly define all three.
• For this reason, those three special member functions are sometimes called the big three.