Comprehensive Study Guide: C++ Programming Fundamentals, Data Structures, and Algorithm Analysis

Introduction to Programming, Algorithms, and Efficiency

Programming is used to solve different types of problems that deal with data. To code in any programming language, a programmer must understand the flow or behavior of data to formulate the algorithm required to complete the program.
Program efficiency must be considered based on the structure of data used. According to the foundational rule of data structures, the less main memory used in code, the more efficient the program is.
Memory Management and Efficiency Comparison:
- Generating numbers from $1$ to $50$ manually using explicit output lines (e.g., writing individual statements for $n+1$ , $n+2$ , etc., up to $n+29$ ) produces the exact same output as generating numbers using a for loop.
- Utilizing a for loop (e.g., for (n = 1; n <= 50; n++)) is far more efficient because it consumes significantly less main memory and drastically reduces the lines of code required.
Definition of Algorithm:
- An algorithm is a step-by-step procedure for making a flow from initializing data, input, processing, to output to accomplish a computational task.
- Example Step-by-Step Flow:
- Step 1: Initialize $n$ as an integer.
- Step 2: Enter $n$ .
- Step 3: Compute $n \bmod 2$ (where $\bmod$ is the operation used to obtain the remainder of division).
- Step 4: If the remainder is equal to $0$ , print Even; otherwise, print Odd.
Learning Objectives in Data Structure and Algorithm Analysis:
- Explain the importance of Data Structures and Algorithms in developing C++ programs.
- Build interest in learning Data Structure and Algorithm Analysis.
- Formulate and solve simple machine problems using data structures and algorithms.

History and Foundations of C++

C++ was originally invented in the year $1979$ by Danish developer Bjarne Stroustrup.
The first official version of C++ was released to the public in the year $1983$ .
It rapidly gained worldwide popularity among programmers and was widely adopted across industrial and software enterprise contexts.
Instructor / Author attribution details: Prepared by JOHN M. MURILLO, CpE, MSCS.

Data Structures and Abstract Data Types (ADTs)

Definition of Data Structure:
- A data structure is a way of organizing or managing data in a program so that it can be used effectively. It allows easier processing of data and assists in designing efficient algorithms.
Abstract Data Types (ADT):
- An ADT is defined as a set of values and operations.
- ADTs are essential in computational logic, but they cannot be used directly inside programs without computer implementation.
- Implementing an ADT requires two components:
1. Data stored in computer memory that represents the values in the carrier set of the ADT.
2. The operations of the ADT to realize computational mechanisms.
- The relationship between data structures and algorithms is direct: data structures represent the values of an ADT carrier set, while algorithms work with these data structures to implement their operations.
Examples of ADTs, Carrier Sets, and Operations:
- Boolean: Carrier set of $\{\text{true}, \text{false}\}$ . Operations include conjunction, disjunction, negation, conditional, and others.
- Integer: Carrier set of positive and negative whole numbers, such as $\{1, -2, -200\}$ . Operations include standard arithmetic operations.
- String: Carrier set of a finite sequence of characters. Operations include concatenation, length calculation, substring extraction, index identification, and others.
- BitString: Carrier set of a finite sequence of bits, such as $\{0, 011, 100\}$ . Operations include complement, bit shifts, conjunction, disjunction, and concatenation.

Structural Classification and Characteristics of Data Structures

Basic Categorization:
- Primitive Data Structures: Integer, Float, Boolean, Char, String.
- Abstract Data Structures: Linked List, Tree, Graph, Stack, Queue.
Comprehensive Taxonomy of Data Structures:
- Built-in Data Structures:
- Integer
- Float
- Character
- Pointer
- User-Defined Data Structures:
- Arrays
- Files
- Lists:
  - Linear Lists: Stacks, Queues
  - Non-Linear Lists: Trees, Graphs
Six Core Characteristics of Data Structures:
- Linear: Data elements are arranged in a linear or sequential form (e.g., Array).
- Non-Linear: Data elements are not organized sequentially (e.g., Tree, Graph).
- Homogeneous: All stored data elements belong to the exact same data type (e.g., Array).
- Non-Homogeneous: Stored data elements can belong to different data types (e.g., Structure, List).
- Static: The structure occupies a fixed memory allocation determined at compile time (e.g., Array).
- Dynamic: The structure memory allocation is not fixed; it expands or contracts dynamically during program execution, and memory locations change (e.g., Linked List created using pointers).

Algorithmic Properties, Analogies, and Performance Measurements

The Cookbook Analogy:
- An algorithm functions like a cookbook recipe. For example, when cooking Adobo, ingredients such as chicken, soy sauce, vinegar, black pepper, water, onion, and garlic act as the data. Sautéing the garlic, onion, and chicken in step-by-step sequential order acts as the algorithm.
Five Mandatory Properties of an Algorithm:
- Input: Must have $0$ or more inputs supplied to the algorithm.
- Output: Must produce at least $1$ output.
- Definiteness: Every step of the algorithm must be clear, unambiguous, and well-defined.
- Finiteness: The algorithm must terminate after a finite number of steps.
- Correctness: For every valid input, the algorithm must produce the correct output.
Performance Measurements of Algorithms:
- Time Complexity: The total amount of computer time required by the program to execute and run to completion.
- Space Complexity: The total amount of memory space required by the algorithm during execution.

C++ Data Types and Memory Specifications

Data Type Definition:
- A data type is a classification that dictates what type of value a variable or object can hold.
Three Major Data Type Categories:
- Numerical:
- Integers: Represent whole numbers. Divided into three types: int, short, and long.
- Floating Point: Represent real numbers with decimal points. Divided into two types: float and double. Can be written in decimal notation (e.g., $3.1478$ ) or scientific notation (e.g., $2.75e3$ , which equals $2.75 \times 10^3$ ).
- Alphabetic:
- Character: Stores a single character enclosed in single quotes (e.g., 'x', 'A'). Represented by the keyword char.
- String: Stores two or more characters (e.g., "Melissa", "apple"). Represented by the keyword string.
- Logical:
- Stores truth values: true or false. Represented by the keyword bool.
Primitive Data Type Taxonomy:
- Integral Types: char, short, int, long, bool, unsigned.
- Floating Types: float, double, long double.
- Valueless Type: void.
- Wide Character Type: wchar_t.
Complete Data Type Size and Range Table:
- char: Size = $1\text{ byte}$ , Range = $-128$ to $127$ . Description: Stores a single character, letter, number, or ASCII value.
- unsigned char: Size = $1\text{ byte}$ , Range = $0$ to $255$ .
- short: Size = $2\text{ bytes}$ , Range = $-32,768$ to $32,767$ .
- unsigned short: Size = $2\text{ bytes}$ , Range = $0$ to $65,535$ .
- int: Size = $4\text{ bytes}$ , Range = $-2,147,483,648$ to $+2,147,483,647$ . Description: Stores whole numbers without decimals.
- unsigned int: Size = $4\text{ bytes}$ , Range = $0$ to $4,294,967,295$ .
- long: Size = $4\text{ bytes}$ , Range = $-2,147,483,648$ to $+2,147,483,647$ .
- unsigned long: Size = $4\text{ bytes}$ , Range = $0$ to $4,294,967,295$ .
- float: Size = $4\text{ bytes}$ , Range = $-3.4 \times 10^{-38}$ to $+3.4 \times 10^{+38}$ . Description: Stores fractional numbers containing one or more decimals; sufficient for storing $7$ decimal digits.
- double: Size = $8\text{ bytes}$ , Range = $1.7 \times 10^{-308}$ to $1.7 \times 10^{+308}$ . Description: Stores fractional numbers containing one or more decimals; sufficient for storing $15$ decimal digits.
- long double: Size = $8\text{ bytes}$ , Range = $1.7 \times 10^{-308}$ to $1.7 \times 10^{+308}$ .
- bool: Size = $1\text{ bit}$ (or $1\text{ byte}$ ). Description: Stores true or false values.
- void: Valueless.
- wchar_t: Wide character type, Size = $2\text{ or } 4\text{ bytes}$ .

Identifiers, Keywords, Variables, and Constants

Identifiers:
- An identifier is a user-defined name given to denote labels, data types, variables, constants, or functions in a C++ program.
- C++ is strictly case-sensitive. For example, Age is distinct from age, and a1 is distinct from A1.
- Using clear, descriptive, and meaningful identifiers is standard programming practice.
Rules for Naming Identifiers:
- Identifiers can contain uppercase letters, lowercase letters, numeric digits from $0$ to $9$ , and underscores (_).
- The first character of an identifier must be an alphabetic letter or an underscore (_).
- Identifiers cannot contain spaces or special punctuation symbols such as <, >, &, !, %, ^, *, etc.
- Identifiers must not match any reserved C++ keyword.
- Two different variables within the same scope cannot share the exact same identifier.
Reserved C++ Keywords:
- The complete list of reserved C++ keywords includes: alignas, alignof, and, and_eq, asm, auto, bitand, bitor, bool, break, case, catch, char, char16_t, char32_t, class, compl, const, constexpr, const_cast, continue, decltype, default, delete, do, double, dynamic_cast, else, enum, explicit, export, extern, false, float, for, friend, goto, if, inline, int, long, mutable, namespace, new, noexcept, not, not_eq, nullptr, operator, or, or_eq, private, protected, public, register, reinterpret_cast, return, short, signed, sizeof, static, static_assert, static_cast, struct, switch, template, this, thread_local, throw, true, try, typedef, typeid, typename, union, unsigned, using, virtual, void, volatile, wchar_t, while, xor, xor_eq.
Variables:
- A variable is a named location in a computer's memory used to store data that can be retrieved and modified during execution.
- Syntax Declaration: [data type] [variable name] = initial value;
- Declaration Examples:
- int i; (Declaration without initialization)
- int j, k, l; (Multiple variable declaration)
- int n = 10; (Declaration with explicit initialization)
- float x, pi = 3.14159; (Mixed initialization and non-initialization)
- char a = 'A'; (Single character initialization)
- string name = "John"; (String literal initialization)
- bool maybe = true; (Boolean initialization)
Constants:
- Constants represent fixed values that cannot be modified during program run-time.
- Declared using the const keyword modifier.
- Declaration Syntax: const [data type] [name] = initial value;
- Example: const float pi = 3.14159;

Operators, Special Characters, and Escape Sequences

Arithmetic Operators:
- + (Addition): Adds together two numeric values (e.g., x + y).
- - (Subtraction): Subtracts one value from another (e.g., x - y).
- * (Multiplication): Multiplies two numeric values (e.g., x * y).
- / (Division): Divides one value by another (e.g., x / y).
- % (Modulus): Returns the division remainder of integer division (e.g., x % y).
- ++ (Increment): Increases the integer value of a variable by $1$ (e.g., ++x).
- -- (Decrement): Decreases the integer value of a variable by $1$ (e.g., --x).
Assignment / Compound Operators:
- +=: x += 5; is equivalent to x = x + 5;
- -=: y -= 2; is equivalent to y = y - 2;
- *=: z *= 10; is equivalent to z = z * 10;
- /=: a /= b; is equivalent to a = a / b;
- %=: c %= 3; is equivalent to c = c % 3;
Special Characters:
- // (Double slash): Marks the beginning of a single-line comment.
- # (Pound sign): Marks the beginning of a preprocessor directive.
- < > (Opening and closing angle brackets): Encloses a header filename when used with #include directives.
- ( ) (Opening and closing parentheses): Used in defining or calling functions (e.g., int main()).
- { } (Opening and closing braces): Encloses a block of executable statements, such as the body of a function.
- " " (Opening and closing quotation marks): Encloses a sequence of characters forming a string literal.
- ; (Semicolon): Marks the termination of a complete programming statement.
Escape Sequences:
- \n (Newline): Positions the output cursor at the beginning of the next line.
- \t (Horizontal tab): Moves the output cursor to the next tab stop.
- \a (Alarm): Triggers an audio sound/beep from the system sound speaker.
- \b (Backspace): Moves the output cursor left by one position.
- \r (Return): Moves the output cursor to the beginning of the current line without advancing to the next line.
- \\ (Backslash): Outputs a literal backslash character.
- \' (Single quote): Outputs a literal single quotation mark.
- \" (Double quote): Outputs a literal double quotation mark.

Practical Code Implementations and Programs

Example 1: Hardcoded Arithmetic Sum Program
- Objective: Print the sum of two hardcoded numbers ( $8$ and $9$ ).
- Direct Stream Code Variant:
```
#include<iostream>
using namespace std;

int main()
{
    cout << "The sum of of 8 and 9 is ";
    cout << 8 + 9;
}
&nbsp;&nbsp;&nbsp;&nbsp;```
- *Variable Representation Code Variant*:
```
cpp
include
using namespace std;
int main() { int num1 = 8; int num2 = 9; int sum; sum = num1 + num2; cout << "The sum of " << num1 << " and " << num2 << " is "; cout << sum; } ```
- Console Output: The sum of of 8 and 9 is 17
Example 2: Interactive Arithmetic Sum Program
- Objective: Accept two integer values input from the keyboard and output their computed sum.
- Source Code: ```cpp
include
using namespace std;
int main() { int num1, num2, sum; cout << "Enter first number: "; cin >> num1; cout << "Enter second number: "; cin >> num2; sum = num1 + num2; cout << "The sum of " << num1 << " and " << num2 << " is " << sum; } ```
- Sample Interactive Session:
- Input: Enter first number: 20
- Input: Enter second number: 30
- Console Output: The sum of 20 and 30 is 50
Example 3: User Personal Information Input Program
- Objective: Collect first name, last name, and age, then print formatted greeting strings.
- Source Code: ```cpp
include
using namespace std;
int main() { string fname, lname; int age; cout << "Enter your first name: "; cin >> fname; cout << "Enter your last name: "; cin >> lname; cout << "Enter your age: "; cin >> age; cout << "You are " << fname << " " << lname << endl; cout << "You are now " << age << " years old"; } ```
- Sample Interactive Session:
- Input First Name: Ivanna
- Input Last Name: Alawi
- Input Age: 18
- Console Output: You are Ivanna AlawiYou are now 18 years old
Example 4: Reading Full Line Strings Using getline
- Objective: Accept multi-word input strings containing whitespace using getline(cin, variable).
- Source Code: ```cpp
include
using namespace std;
int main() { string name, subject; cout << "Enter name: "; getline(cin, name); cout << "Enter Subject: "; getline(cin, subject); cout << "Your name is " << name << endl; cout << "Your favorite subject is " << subject; } ```
- Sample Interactive Session:
- Input Name: Mary Ann Dela Cruz
- Input Subject: Data Structure
- Console Output: Your name is Mary Ann Dela CruzYour favorite subject is Data Structure

Comprehensive Study Guide: C++ Programming Fundamentals, Data Structures, and Algorithm Analysis

Introduction to Programming, Algorithms, and Efficiency

History and Foundations of C++

Data Structures and Abstract Data Types (ADTs)

Structural Classification and Characteristics of Data Structures

Algorithmic Properties, Analogies, and Performance Measurements

C++ Data Types and Memory Specifications

Identifiers, Keywords, Variables, and Constants

Operators, Special Characters, and Escape Sequences

Practical Code Implementations and Programs

include

include

include

include