CSC 1061 Midterm

RRCC Lakewood, CO

Include Guard (Macro Guard)

A technique in C++ that uses a unique identifier defined at the top of header files (.h) to prevent multiple declarations of the same code.

Header File

These files contain declarations (function prototypes) and are #included, but not compiled

Source Files

These files contain the actual implementation (definitions) of functions and are compiled, but not #included

Preprocessor

The first stage in building a multi-file project where the #include directives are replaced by the content of the specified header or file.

Compiler

The second stage where each source file (.cpp) is checked for syntax errors and, if successful, generates a corresponding object file (.o)

Linker

The final stage in building a multi-file project where all objects are linked together to create the executable file (.exe)

Non-Member Function

A type of function that performs a specific task and operates independently of any class. An example is rand().

Overloaded Function

Functions that share the same name but differ in their argument list (number or data type of arguments), allowing them to perform the same task in different ways.

Pass By Value

A parameter passing type where a copy of the argument’s value is passed to the function, meaning the original cannot be modified. It’s safe and efficient for simple data types.

Pass By Reference

A parameter passing type where the memory address of the argument is passed to the function, allowing the function to modify the original variable.

Abstraction

The process of defining abstraction and explaining its role in the problem-solving process.

Class

A custom data type or Abstract Data Type (ADT) that encapsulates data and functionality, making it reusable.

Encapsulation

The concept of hiding the internal implementation details of an object and only exposing the necessary functionalities to the outside world, typically by declaring data members as private.

Object

An instantiation of a class, which has memory and values based on the class’s blueprint.

Constructor

A special type of function that allows an object to be created and its data members initialized. All classes should have a default one.

Member Function

A function that belongs to a class and performs tasks on the class’s data members. Examples include getters, setters, and other utility functions.

Getters

Member functions that return the value of a data member.

Setters

Member functions that change or modify the value of a data member, often with validation.

This Pointer

A hidden argument passed to all member functions calls that points to the object that invoked the function. It is NOT available in static member functions.

Static Variable

Variables declared as ‘static’ in a class, which are allocated in separate static storage and shared by objects of that class. They cannot be initialized using constructors.

Operator Overloading

The ability of an operator to behave differently based on the data types or classes of the operands involved, defining custom behaviors for existing operators.

Friend Functions

A function or class declared with the ‘friend’ keyword that can access the private and protected members of another class.

New Operators

New creates on the heap and return the address. This is accessed by a pointer, which stores its address. Must be deleted after creation for fear or memory leaks.

Non-Overloadable Operators

Member selector (.), scope-resolution (::), ternary (?:), sizeof, and member pointer selector (.*) cannot be overloaded.

Default Operator Definition

Operators are only automatically defined for simple data types by default. For custom classes, you typically need to overload them.

Relational Operator Rule

If you define one relational operator (e.g., ==), it is good practice to define all six (==, !=, <, <=, >, >=) to ensure completeness and logical consistency.

Assignment Operator Default

The ‘operator=’ is automatically provided by classes for assignment, creating a copy of the object’s values.

Insertion Operator Return Type

When overloading the insertion (<<) operator for output, it typically returns ‘std::ostream&’ to allow for method chaining.

File Stream Operator Guideline

When overloading ‘operator<<’ or ‘operator>>’ for file streams (ofstream/ifstream), do not create, open, check, or close the file object within the operator function. This is handled by the caller.

Static Array

A compiler memory-managed array that is fixed-size at compile time, cannot grow or shrink during run-rime, stores elements of the same data type, and has 0-based indexes for referencing elements.

Data Structure

A specialized means of organizing and storing data in computers to perform operations on the stored data more efficiently.

Big-O Notation

A notation (for ‘operations order’) that provides a useful approximation to the actual number of steps an algorithm takes in computation, characterizing its efficiency independent of specific programs or computer.

Bag Data Structure

An unordered collection of values that may have duplicates.

Container (Data Structure)

A holder object that stores a collection of other objects (elements), manages their storage space, and provides member functions to access and modify the collection.

Subscript Operator ([])

A mechanism to retrieve and manipulate array elements, acting as both a getter and a setter, denoted by [].

append()

A Bag ADT function that adds a new element at the end of the array if there is room.

getSize()

A Bag ADT function that returns the number of actual objects currently held in the array.

removeByIndex() (Bag ADT)

A Bag ADT function that removes an element at a specified index by taking the last indexed element and overwriting the element to remove.

Invariant of data members

A rule or condition that must always be true for the data members of a class, ensuring the data structure’s integrity.

Sorting Algorithm Objectives

To simulate and understand the runtime behavior of various sorting algorithms, and to understand their advantages and disadvantages.

Bubble Sort

A sorting algorithm where adjacent elements are repeatedly compared and swapped if they are in the wrong order, with the largest unsorted element moving to the end of the list after each iteration.

Best: O(n)

Worst: O(n²)

Bubble Sort: First Iteration

In the first iteration of Bubble Sort, you start by comparing the first and second elements. If the first is greater than the second, they are swapped. This process continues, comparing adjacent elements and swapping them if out of order, until the last element is reached.

Selection Sort

A sorting algorithm that repeatedly finds the minimum element from the unsorted part of the list and puts it at the beginning. It builds the sorted list one element at a time.

Best: O(n²)

Worst: O(n²)

Selection Sort: First Element Comparison

In Selection Sort, you set the first element as the minimum. Then you compare this minimum with subsequent elements, updating the minimum if a smaller element is found. This continues until the end of the unsorted list for that iteration.

Selection Sort: Iteration Completion

After each iteration in Selection Sort, the found minimum element is placed at the front of the unsorted list. The process then repeats, starting from the new first unsorted element, until all elements are in their correct positions.

Basic Sorting Algorithms

Bubble Sort, Selection Sort, Insertion Sort.

They generally have less efficient runtime complexities compared to more advanced algorithms for larger datasets.

Shell Sort

A type of sorting algorithm that improves on Insertion Sort by sorting incremental sub-lists, allowing elements to move further distances at once.

Merge Sort

A sorting algorithm that requires additional space for the merging process, as it typically divides the list into halves, sorts them, and then merges the sorted halves back together.

Quick Sort

A sorting algorithm that can degrade in performance if the ‘split points’ (pivots) are not chosen near the middle of the list. It does not require additional space for sorting in-place.

Class ‘has a’ relationship

A class ‘has a’ data member relationship describes composition, where one class contains an object of another class as a member.

Inheritance ‘is a’ relationship

Inheritance describes an ‘is a’ relationship where a derived class is specialized version of a base class, inheriting its properties and behaviors.

Code Reuse

Code reuse is a significant benefit of inheritance, allowing developers to extend existing code rather than rewriting it, which saves time and effort.

Inherited from Base Class (exclusions)

In principle, a publicly derived class inherits access to every member of a base class except for constructors, destruction, assignment operator members, and friend non-member functions, and private members.

Derived Class Constructors

The constructors of a derived class must call the constructor of its base class using an initializer list to properly initialize the base class part of the derived object.

Inheritance Function Overriding

Function overriding occurs when a derived class provides its own implementation of a function that is already defined in its base class.

Polymorphism

Polymorphism (meaning ‘many forms’) allows a parent pointer to call a child method, provided the child class overrides the method of the parent. This often involves base class pointers pointing to the derived class objects.