These notes pickup where CS1 left off, building this time more on programming patterns, design, etc., less focused on syntax of C++, more advanced topics.
//Abstract Data Types
//8/19/25
//Caleb Magill
/*NOTES
In brief; the idea of abstract data types is that, for a given implementation,
of a class or whatever framework you're creating, the focus is on the behavior,
and the properties, rather than the implementation details. These details are,
usually hidden from the user as they are unnecessary.
- Abstraction is the core concept; the idea that the internal implementation,
details are hidden from the user
An ADT has three things;
- Data, some memory
- Operations of Data, a set of methods/functions that work on data
- Rules of Usage, set of usage rules that must be obeyed for ADT to work
- An example of an ADT is the boolean variable, we don't know what is going,
on under the hood, though it contains the three possessions above
Example; type int
Data = two words (the significand and base (the two properties of the int))
Operators = +, -, /, *
Rules = floating-point arithmetic
- A class is a construct that allows the addition of functionality in C++,
via new types (ADTs)
Why Are Classes ADTs?
- Include encapsulation, keeping data and operations in one place
- Has information hiding, access modifiers dictate what the user has,
direct access to
- Contains objects, instances of the class
Using Classes as ADTs
- Using a class requires 2 files; the .hpp & the .cpp
- The .hpp is the info about the behavior that the user interacts w/
- The .cpp is the info hidden from the user and the bts of how it,
actually works, which in this case is unimportant to the developer
- The 'Make' build tool is an automation tool that compiles the newly,
created ADT that packages the two files together, & for future use w/ a,
given developer, they only need the .hpp file
Including the Proper Guards W/ ADT Creation (in header file);
The guards are crucial, these are prefixed with the '#' (denoting preprocessor,
directive) to define the methods of a class within the library of a newly,
created program for the user.
#include - Used to reference external libraries, tells the compiler to,
search a given location for a given file(s)
- #include "library.hpp" - syntax is used for user-defined headers,
compiler searches same directory as the source file
- #include - syntax for system-defined headers, will,
search the predetermined folders w/ associated system files
#ifndef - Always comes second, is used to first check whether another,
ADT already exists w/ that name
#define - Assuming the newly created ADT isn't already defined, the,
define statement is used to define that ADT within the system in the scope,
of the referenced file
#endif - Always put at the end, used to tell the compiler we are done
//ALWAYS PUT AN EXTRA LINE AT THE END OF AN ENDIF (last line of .hpp file)
*/
//-------------------------------------------------------------------------------
/*EXAMPLES*/
// In brief; he went through and created an ADT as an example following the rules,
// of including the proper guards and such from the notes above.
//Point.hpp-----------------
#include
#ifndef CS2_POINT_HPP_
//^Recall ifndef check comes before the def
#define CS2_POINT_HPP_
//^never use a leading underscore in name of define (reserved)
class Point{
public:
Point();
Point(double, double);
void init(double, double);
void setX(double);
void setY(double);
double getX();
double getY();
void print(std::ostream&);
Point add(Point);
Point sub(Point);
double distance(Point);
private:
double x;
double y;
};
#ENDIF
//IMPORTANT TO INCLUDE THIS LAST BLANK LINE
//Point.cpp-----------------
#include "point.hpp"
//^This is the line we want to include w/ the quotations since we created it,
//not system
Point::Point(){
x = 0;
y = 0;
}
void Point::init(double newX, double newY){
x = newX;
y = newY;
}
void Point::setX(double newX){
x = newX;
}
void Point::setY(double newY){
x = newY;
}
double Point::getX(){
//^Remember to use const for non-mutators
return x;
}
double Point::getY(){
return y;
}
void Point::print(std::ostream& out){
out << "(" << x << "," << y << ")";
}
Point Point::add(Point rhs){
Point result;
result.x = x + rhs.x;
result.y = y + rhs.y;
return result;
}
//fileWithMainLoop.cpp------
#include "point.hpp"
//^Same inclusion as w/ the .cpp file for 'Point' ADT
int main(){
Point a, b, c;
a.init(4, 5);
b.setX(3);
b.setY(7);
b.print(std::cout);
c = a.add(b);
}
//-------------------------------------------------------------------------------
/*SUMMARY
- Recall the difference between (#include "NewADT.hpp") & (#include )
- When using the include w/ quotations, any include statements within the,
.hpp file will additionally be included w/ the associated .cpp file, so don't,
have to respecify things like "#include " if already within .hpp file
- From now on, think of the classes that we create as ADTs
- ALWAYS include guards on .hpp files
- ALWAYS have default constructors for ADTs
- ALWAYS skip ending line after '#endif' of .hpp file
*/
//-------------------------------------------------------------------------------
//adtsWithSets.cpp
//8/25/25
//Caleb Magill
/*NOTES
In Brief;
The general idea w/ ADTs is understanding how to use data types,
and how the efficiency of C++ can really be honed through the,
creation of proprietary data types context-specific to a program.
Additionally, through the efficiency of code, we can localize bugs,
so that, when debugging, it is easier to identify where they are.
(Don't give a given method more permission than it needs)
Understanding Operator Overloading;
The Core Cocept of operator overloading is you are creating a custom,
implementation for a given operator in the scope of objects of your,
created class. The term 'overloading' comes from the idea that you,
are literally adding a proprietary meaning to an existing operation,
for use with objects of your class within a program that uses it.
Think back to CS1 and the "operator overload" assignment of the big 3.
Typically formatted as overloading the "=" sign, this was done in,
order to allow you to set an object of a class's values equal to that,
of an already-existing object using the "=" symbol, and normally,
without the assignment-overload defined, the syntax for setting one,
object of a class equal to that of another class would otherwise be,
impossible.
This proprietary definition of an operator through an operator overload,
allows us to define a new set of rules for how that operator will be,
handled by the compiler in the context of dealing with objects of our class.
Relevant Learned Concepts;
Reviewing the Use of 'const';
Const Function;
*/
bool booleanFunc(int intArgVar) const;
/*^This use-case denotes the function will not modify the object for,
which called the function, this is represented as accessors, however,
the argument may be modified.
Const Argument;
*/
bool booleanFunc(const int intArgVar);
/*^This means the argument passed to the function may not be modified,
within the function, however the object for which the function was called,
upon may be.
Importance of Pass-By-Reference;
With pass-by-reference, the argument is a reference to an existing object,
or variable, this means, in contrast to pass-by-value, a new object or variable,
will not be created, but instead an already-existing one will be used.
When dealing with large variables, in our case of dealing with ints hundreds,
of place values long, it is important to not make a new instance of such a large,
variable, and instead pass-by-reference. By using the idea of a const arg,
this ensures the integrity of the already-existing object outside the context,
of the function.
Assignment Overloading Operators;
Remember why it's called operator overloading.
*/
//Given class 'Set'
Set operator+(const Set &rhs) const;
/*^This operator overload is overloading operator '+', keyword 'operator',
followed by desired symbol (could be any) to use. This means, when dealing with,
objects of the 'Set' class, this newly defined operator can be used. The rules,
of use with this operator are defined within the function. This is an example,
of an ADT.
Now,
*/
//Assuming in main()
Set setObj1, setObj2;
Set setObj3 = setObj1 + setObj2;
/*^Before, this second line wouldn't work as you can't inherently use a built-in,
operator to deal with objects of a class, but since we operator overloaded with,
this defined symbol '+', the syntax works.
*REMEMBER: the symbol is arbitrary and user-defined, the '*' may not be defined,
to perform a multiplication operation on some object's member value.
Member Functions Versus Free Functions;
Understanding lhs v. rhs
lhs
Is the target of an assignment operation;
*/
int a = 5;
/*^'a' is the lhs because it is the target whose being assigned the value 5
rhs
The source or value being assigned;
*/
int a = 5;
/*^The 5 is the rhs as it is the value for which the 'a' is being assigned
Member Functions
A member function is a function located within the definition of a class.
Its first unique property is the ability to access private members of the class, as it is,
a member itself, it has this capability.
The second property unique to member functions in contrast to free functions is its,
implicit understanding of the 'this' pointer
*/
class AClass{
public:
AClass operator*(AClass obj);
};
/*^As you can see, the operator overload statement is defined within the definition,
of the class. This means we ONLY have to specify the 'rhs' since it is known the lhs will,
be an object of type 'AClass'.
With this knowledge, it is important to note operator overload statements should be,
used as member functions if the lhs will be an object of that class.
Note: ALL methods' lhs is implicitely an object of its class.
'This' Pointer
Understanding the 'this' pointer and how it operates in C++ is key to understanding,
the internal behavior of classes.
*/
//Given class "AClass" & member, method, aMethod();
AClass obj;
obj.aMethod();
/*^In the above example, this line can also be interpreted as;
*/
MyClass* this = &obj;
this->doSomething();
/*^Since 'aMethod()' is a method, apart of class as a member, the pointer is implicit,
however under the hood, these two lines explain what is actually going on.
Free Functions
A free function is a function located outside the definition of a class. These are,
used in such cases whereas the lhs isn't necessarily an object of the type class.
*/
AClass operator*(AClass objLhs, AClass objRhs);
/*^In such case, the function will return an object of type 'AClass', however,
both the lhs and rhs of the operation must be specified.
Should be used when the lhs isnt to be an object of type class, also syntatctically,
clearer to see what's going on even if both lhs and rhs are to be members of class.
*/
//============================================================
//CODE
//set.hpp
#ifndef SET_HPP
#define SET_HPP
#include
#include
//A set of integers from {0, 1, ... DOMAIN-1}
//So all elements must be between 0 and DOMAIN -1 (6399)
const int DOMAIN = 6400;
class Set{
public:
Set();
Set(int);
Set(int, int);
Set(std::initializer_list);
//^Don't worry about for right now
int card() const;
//^Returns # of elements in set, cardinality
//^Const as we don't want to modify w/ method
bool operator[](int) const;
Set operator+(const Set &rhs) const;
//^The 'const' is added as prefix of arg,
//to make unnecessary copy
Set operator*(const Set &rhs) const;
Set operator-(const Set &rhs) const;
//^Compare between (const Set rhs&) & (const Set &rhs)
//SOLVED: "const Set &rhs" calls const of object Set and gives,
//it name "rhs" vs. pass-by-reference.
bool operator==(const Set &rhs) const;
bool operator<=(const Set &rhs) const;
//^operator followed by operator is MOST LIKELY used as an ADT,
//relative to our program to define its behavior
private:
bool element[DOMAIN]; [0,...,DOMAIN-1]
};
//Free functions are located outside class
std::ostream& operator<<(std::ostream&, const Set&);
Set operator+(int, const Set&);
Set operator*(int, const Set&);
Set operator-(int, const Set&);
bool operator<(const Set&, const Set&);
bool operator>=(const Set&, const Set&);
bool operator==(int, const Set&);
#ENDIF
//------------------------
//============================================================
/*SUMMARY
We learned operator overloading and why it matters. This knowledge can be,
used to work through future projects involving performing operations,
on objects of a given class. Also a shorthand way to perform operations,
as instead of defining a function for every operation and having to call it,
we can more simply just use an operator defined by us.
Note: ALL methods' lhs is implicitely an object of its class.
W/ free functions by contrary, the lhs must be specified
*/
//compilingTestingAndNaming.cpp
//8/28/25
//Caleb Magill
/*NOTES
In Brief;
Walkthrough of the compilation process for COMPILED LANGUAGES and,
how they work.
Compiled Languages vs. Interpreted Languages;
These two categories are reflective of languages encompassed and,
each have their own unique way of code execution.
Compiled Languages:
Such as C++, are first converted into low-level machine code,
format first, the compiler being the one to handle this,
translation.
Steps we learn today cover "compiled languages".
Interpreted Languages:
Rather than conversion via compiler, source code is instead,
read and executed line-by-line by an interpreter at runtime.
We will not cover compilation process of interpreted languages.
Steps of Compilation of Compiled Languages;
Preprocessing:
Preprocessing is the process of preparring the code for the,
compilation stage.
The preprocessor directives, in C++ denoted w/ '#' are handled,
first. Compiler just identifies all necessary included files,
and literally copies the library/header files into your source,
code for later use.
Compilation:
Compilation has three main steps it performs sequentially:
Lexical Analysis:
Scans the code and uses tokens to understand the lines of,
code;
*/
int x = 5;
/*^May be interpreted as;
int = a keyword
x = an identifier
= = an operator
5 = a literal
; = a punctuator
Literally breaks down each line into machine-interpretable,
symbols.
Also removes whitespaces and comments as these are unnecessary.
Syntactic Analysis:
Responsible for syntax error detection
This takes the tokens produced from the previous step and,
verifies whether the sequence is valid or not per-line.
If a token sequence is invalid, it returns SYNTAX ERROR.
Semantic Analysis:
Responsible for semantic error detection
This step is responsible for taking the syntactically-correct,
token sequences and analyzing each to determine whether,
is logically correct;
*/
int x = "hello" + 5;
/*^Is syntactically correct, however isnt semantically correct,
this would produce an error despite passing the syntactic,
phase.
Populates a symbol table for next step of compilation w/ valid,
sequences.
If a token sequence is invalid in this stage, it returns,
a SEMANTIC ERROR.
Code Generation:
The code-generation step is responsible for taking the verified,
valid code and converting it into assembly for an assembler,
to further handle and convert to machine code.
LLVM is a compiler framework that serves to take code passed,
to it and convert it into a platform-independant intermediate,
representation, which could be used by different languages to,
compile to various target architectures.
(LLVM is pretty cool)
LLVM assembly code is then converted into object files (.o),
which will then be passed onto the linker.
Linking Phase:
Input is ojbect files, takes both these object files and,
libraries (determined by preprocessor directives) and,
links them together.
"Linking them together" involves taking the afformentioned,
files and assembling them together into a final executable file,
which then can be ran.
Overall:
Due to all these steps, and the reason this process is all,
automated, is because even just a few lines of code in a,
program can produce an executable file tens of thousands,
of lines long. :O
//------------------------------------------------------------
Software Testing;
In brief:
It is important to understanding good software-testing,
habits as this is a large percentage of the work you'll,
be doing on your program as it is important to TEST!!!
- Objective is to cause failures, to find faults/errors
- Failure is defined as syntax errors
- Fault is defined as semantic errors
- The best test cases are the ones that have the highest,
likelihood of producing the most errors
(We want to find errors so we can fix them!!!)
Scope of Testing:
Unit Tests - Testing each method
Module Tests - Testing each class in full
System Test - Whole program tested
- We want to take a bottom-up approach when testing,
starting w/ smaller scope first then working into bigger,
scope.
Types of Testing:
Blackbox Testing:
Blackbox testing is the practice of testing code,
by interacting w/ it as if you're the end-user.
Independant of any knowledge of how the system,
actually works, just test to try and produce,
errors with the output.
Only uses i/o specs.
Typically tests are performed by QA People (non-developers).
Glassbox Testing:
Testers have full knowledge of the system's internal,
structure.
Testing with this knowledge in-mind, the goal is to,
find issues with how it is written and what issues,
may incur.
Typically tests are performed by the developers.
- GOAL is to test a union of cases both between blackbox,
and glassbox test cases.
- Can make comments whilst parsing through code via glassbox,
to make sense of where errors might occur.
Important Vocab w/ Testing;
Assertions (ASSERT) - A statement that is true at a,
specific point in the program.
Pre-Condition (REQUIRES) - A statement that must be true,
BEFORE a method/function is executed.
Post-Condition (ENSURES) - A statement that is true AFTER,
a function or method is executed.
INVARIANTS (INV) - A statement that is always true,
(think global vars).
- Any time a change is made to program code, RE-RUN all,
prior test-cases to ensure cogency.
- Goal is to determine a sensical range of inputs to,
account for issues that may arise rather than testing ALL,
cases (Smart choices).
*/
//============================================================
/*SUMMARY
"We're Software Poets."
- Understand main steps and general functionality w/ compilation
- Understand distinction between blackbox and glassbox testing
- Understand general good habits for naming variables
*/
//everythingLinkedLists.cpp
//Caleb Magill
//10/10/25
/*NOTES;
Overview;
Linked lists are a collection of items whereas the elements of the list are,
connected to eachother in some way. Singly linked lists traditionally store,
both some value and a pointer to the next immediate element in the list infront,
of it. On the contrary, doubly linked lists contain both a pointer to the,
element immediately behind it AND immendiately infront of it. Linked Lists are,
an ADT that can be implemented practically in terms of either a stack, a queue,
or other such (unlearned at this time) data structures.
Singly-Linked Lists v. Doubly-Linked Lists;
Singly-Linked Lists:
Contains some data value & a pointer to the NEXT NODE IN THE LIST,
(Whether this is sorted back-to-front or visaverse is up to creator.).
Doubly-Linked Lists:
Contains some data value & both a pointer to the NEXT node in the list,
AND the previous node in the list.
Linked Lists w/ Stack;
Recall the stack is FILO, meaning the newestmost element added to the stack,
is the first one resolved.
Insert at head:
The 'tos' always points to the head of the linked-list, for each push(),
operation, node is created which points to formerly topmost node on,
stack, then 'tos' begins pointing to said newlymost created element.
Steps:
1 - create new node
2 - Set new node's next ptr to point to current head
3 - Update head ptr (tos) to point to newly created node
Remove from head:
'tos' points to current head's 'next' ptr and current head is deleted.
Steps:
1 - Point to current head node with a temp ptr
2 - Update head ptr (tos) to point to head's next node
3 - Delete temp ptr's ptr (the head now deleted)
Linked Lists w/ Queue;
With queue, it is FILO, which means 'head' of queue cannot be deleted,
unless it is the only node in the queue.
Insert at Tail(enqueue):
Newly created elements are created at tail of queue "first in",
and are only able to be resolved if they're the tail of queue.
Steps:
1 - Create a new node
2 - Set current tail's 'next' ptr to point to new node
^(ptr of now former tail now pointing at new node)
3 - Update tail's 'current' ptr to new node
Delete at Head(dequeue):
We delete from front, creating a temp to help handle this.
Steps:
1 - Create temp ptr to point to current head node
2 - Update head ptr to point to current head node's 'next'
3 - Delete temp ptr (former head node)
*/
//stackNotes.cpp
//9/30/25
//Caleb Magill
/*NOTES
In Brief;
Overview of stack and how it works w/ program/application.
The stack is an ADT w/ proprietary attributes
Defining the Stack;
- The stack is a collection of items (containers)
- Follows FILO, first-in-last-out
- Can only remove elements from top of stack
Operations of Stack;
Pop;
Removes topmost element from stack.
Push;
Adds an element topmost to stack.
- When performing algabraic operations, stack typically,
handles via either prefix or postfix notation (operands,
before/after operator)
Executing Functions;
Since we're always basically within a function, when a new,
function is called within program, the state of the parent,
func is saved & child func is invoked, upon exit from child,
func, we return to place we left off on in parent func.
Program Counter - Register that points to location in,
program that is to-be-executed (keeps track of where we left,
off in parent func)
Stack Pointer - ptr that always points to top of stack
Stack Frame - Block of memory that is pushed onto stack
Upon call of child func, stack frame child func is pushed,
onto top of stack, completes child func, then stack frame,
is removed & the program counter is used to determine where,
we left off on in parent func & returns to that location.
Recursive Functions;
Definition;
A recursive func is a func that invokes itself to solve,
problem
Two Attributes;
Base Case - The stopping condition, condition in,
which function stops calling itself and returns result.
Recursive Step - Case in which func calls itself,
but with an altered input that moves problem closer,
to base case.
Interaction w/ Stack;
Everytime new recursive step is invoked, a new stack,
frame is invoked & put ontopmost of stack.
Implementation;
A stack is typically implemented as a linked-list, like in,
the examples from class, stack is ruleset that can be applied,
to underlying ADT such as linked list.
*/
//queues.cpp
//10/9/25
//Caleb Magill
/*NOTES;
In brief;
Queues are an adt that follow FIFO, with queues,
the idea is it holds some nodes, hypothetically,
as many as memory constraints allow, and as a new,
node is added to the structure, it (the recentmost,
addition) is resolved first. Resolves nodes topdown.
General Notes;
- Linear data structure;
elements are arranged sequentially
- FIFO
Means entry and exit are at opposite ends.
- Insertion point is the end
- Deletion point is the front
- Elements are added at the END of the queue
- Elements are removed from the FRONT of the queue
Analogy Understanding;
Imagine a line of people at the checkout of a,
grocery store, whoever gets in the line first is,
serviced first, people are served in the order in,
which they joined the line, the sooner you joined,
the queue, the quicker you're serviced.
Operations of Queue;
Enqueue:
Adds a new element to the back/end of the queue
Dequeue:
Removes an element from the front of the queue
Visualization of the Structure;
Overview:
Each element in the queue can be expressed as a,
node, queue is typically expressed as a linked list,
with each node having two properties; a value and,
a pointer to the next node.
Enqueue:
An element is added to the queue at the back of the,
queue, it now points to the already-existing node,
immediately infront of it.
Dequeue:
An element is removed, if top-of-stack, or whatever,
pointer is keeping track of topmost node, it would,
be modified to now point to the node immediately,
behind the to-be-deleted node.
Implementation;
A queue may be implemented as a linked-list, think of a queue,
as a ruleset for which a linked-list can be implemented and,
such.
*/
//templates.cpp
//Caleb Magill
//9/24/25
/*NOTES;
In Brief;
With templates, we can more dynamically create ADTs,
by creating a generic structure & setup then simply,
specifying the type of data later on.
This can be done with single functions to entire classes.
General Structure;
*/template /*
^General setup of template;
- The 'typename' will be changed to some type later,
on (int, char, bool, etc.)
- The 'T' is the placeholder name for the type, so,
instead of 'bool' or 'int', we'll say 'T'
For Classes;
The */template /* must be right above the,
class definition in the cpp file for the func prototypes,
AND present in the cpp file above EVERY member func,
definition.
For Functions;
The */template /* must be right above the,
definition for the func.
Misc.;
- Always test & code out originally w/o template,
implementation, this is because template can produce,
a lot of errors so its hard to test functionality of,
code initially w/ generic
- Simply implement template after bug-free &,
tested
*/
//trees.cpp
//Caleb Magill
//10/29/25
/*NOTES;
In Essence:
A tree is a data structure which is known for quick lookup,
and generally how database info is stored. It may be,
structured in any way use-case sees fit, generally seen as,
a binary search tree.
General Structure:
Root - The parentmost vertex(node), all subsequent nodes,
are child to some degree of root.
Branch - Path connecting parent with children
Leaf - Node that has no children.
Binary Search Tree:
Type we care about. Node may have either 0, 1, or 2 children,
no other possibility is possible.
Implementation (As Binary-Search Tree):
A root will be a node w/ a left & right child ptr which points,
to corresponding children. This is a one-way ptr as child has,
no handle on parent.
It can be implemented such that the tree is itself a class and,
there is another class that handles iteration (would dictate,
how it iterates(preorder, postorder, etc.)).
In class implementation, there is a class 'btree' that handles,
general functionality w/ member 'root' which is a node class obj,
of which has itself a left & right child ptr that may be set.
Traversal Types:
Inorder:
Left() * temp = right;
right = 0;
delete this;
return temp;
}
//Case 2, Subcase 2: One child, value less than parent
if(left && !right){
dnode* temp = left;
left = 0;
delete this;
return temp;
}
//Case 3: Two children
data = left->predecessor();
//^First find predecessor (replacement data value for to-be-deleted node)
left = left->bremove(data);
//^Find afformentioned predecessor node whose data we've copied, then delete it
//RECALL; we're deleting the predecessor, not the marked-for-deletion node
}
//Cases where we've not found it
else if(keybremove(key);
}
else right = right->bremove(key);
return this;
/*
*/
//recursiveFunctions.cpp
/*NOTES;
Overview;
Recursive functions are functions that call themselves,
during execution, they are a simple way to handle,
operations in which the argument is the result of a,
previous iteration, for example fibbonacci sequence,
or factorial.
Two Key Properties of Recursive Function;
Base Case:
The base case can be thought of as the floor, the,
point at which the function returns a value,
without making another function call. This is an,
essential property, as without it, the func. would,
loop infinitely.
Recursive Case:
The case in which the function invokes itself,
typically expressed as a while() loop, while,
the base case is not met.
Typical Structure;
*Example of factorial, a standard recursive function:
*/factorial(int n){
//Assuming n>=0
if(n==0){
//^Our base case, will stop recursive call,
//when this condition is met
return 1;
}
if(n>0){
//^Our recursive step; while the base case,
//isnt met, call recursion to get closer,
//to it
return n*factorial(n-1)
}
}/*
How Recursive Call Works;
Behind-the-scenes, pretend given func above we want,
to find factorial(3); we first invoke our recursive,
step which now enters the invocation of that func,
whilst still within our initial function invocation.
This occurs as many times as needed, finally, childmost,
case is returned, and each parent is resolved bottom to,
topmost.
^Key idea: parent function is never returned until,
end of ALL recursive steps.
Recursive Func Relationship w/ Stack;
Given our understanding of stack and how it works,
basically, for every invocation of recursive step,
a new stackframe is added to the top of stack, however,
parent instance of func stackframe still exists, until,
childmost instance of func is resolved, all parent,
stackframes also remain on stack. FILO
*/
//brieflyOnBacktrackingAlgorithms.cpp
//11/17/25
//Caleb Magill
/*NOTES;
In Brief:
Backtracking Algorithms are algorithms that iterate through each scenario,
to a given problem in order to find the appropriate solution. Essentially,
incrementally building candidates to a solution, then abandoning candidates,
who don't correctly arrive at the solution, continuing this process until,
an appropriate candidate who achieves the solution is reached.
Motivating Example:
Imagine being tasked with coloring the countries on a map one of four colors,
in such a pattern whereas no two neighboring country may have the same color.
In such a case, we have to iterate through all the possible combinations,
until we arrive at a scenario in which this requirement is satisfied.
Process:
The foundation for backtracking algorithms are recursive functions in which,
many nested invocations of a function exist. As these functions return, parent,
invocation can iterate through different child invocation 'candidates' until,
the candidate that satisfies all conditions is reached.
Example Algorithm:
*/
bool MapColor(int country, map& world){
if(country == world.numberOfCountries()){
return true;
}
bool doneColoring = false;
bool aColorRemains = true;
color c = red;
while(aColorRemains && !doneColoring){
if(world.isValidColoring(country, c)){
world.colorCountry(country, c);
doneColoring = MapColor(country+1, world);
}
if(c == yellow){
aColorRemains = false;
}
c++;
//^Here, we increment the argument for our next child invocation,
//this creates a new candidate which will be tried.
}
if(!doneColoring){ //Here, the backtracking step is reached;
//in this case, the parentmost iteration then increments through,
//its remaining candidates before next child invocation can proceed,
//with process, becoming itself a parent and finding the appropriate,
//candidate.
world.colorCountry(country, none);
}
return doneColoring;
//^Finally stopping condition, only reached in case (assuming conditions,
//being met are possible) where the correct candidate is reached.
}
//inheritenceAndVirtuals.cpp
//11/17/25
//Caleb Magill
/*NOTES;
Overview:
Inheritence and virtuals covers the way class inheritence works, the new,
'protected' accessor for classes, and virtual methods in a base class,
and their use.
Class Inheritence:
Why?:
We use inheritence w/ classes in instances where a sort of 'subclass',
is warranted; consider this example;
Base class 'car' where members are things like four wheels, windows,
four doors, etc. Every class has these things, an appropriate subclass,
would then be 'Chevy' or 'Hyundai' or 'Nissan' for example.
Overview of Structure:
Base Class - Also referred to as the 'Parent' class, other classes,
will inherit from it, this provides the general structure and behavior.
Derived Class - Also called 'Child' class, will inherit parent, adds,
additionally its own unique members.
^Key relationship may be summarized as an "is-a" relationship with parent-,
child, a Kia for example is a car.
Example of Inheritence:
*/class base_class{
public:
//^Directly accessible to classes that inherit it.
protected:
//^Treated like private when it comes to objects,
//is publicly accessible to classes that inherit it.
private:
//^Not accessible directly to classes that inherit it.
};
class inherit_class : public base_class{
//^'inherit_class' inherits publicly 'base_class'
};
/*
'Protected' Access Modifier:
The 'protected' access modifier is used to denote members as 'protected',
of a class. This access modifier is only really ever applicable in regard,
to class inheritence. For objects of a class with 'protected' members, the,
object cannot directly access 'protected' members, and 'protected' members,
should thus be treated as private in this context. 'Protected' members are,
publicly accessible to classes that inherit it.
You should denote a member as 'protected' if you intend to inherit the class,
and would like to have said members be directly accessible by said class whilst,
also maintaining the flexibility such that objects of class cannot directly access.
Example
*/class aClass{
protected:
int wheels;
//^'wheels' is publicly accessible to classes that inherit 'aClass', for,
//objects, 'wheels' remains directly inaccessible.
};/*
Virtuals:
Why?:
In essence, we use virtuals to achieve 'polymorphism'; this means to treat,
objects of different derived classes uniformely through a signle interface,
the base class.
Using Virtuals:
We prefix a method of the BASE CLASS with 'virtual' to denote this, virtuals,
may not be used for constructors.
Example:
*/class base{
public:
virtual void aVirtualMethod();
virtual ~base();
//^ALWAYS must have an additional destructor for virtuals
};
class aDerivedClass : public base{
//^Inherits class 'base' publicly
void aVirtualMethod() override;
//^We use 'override' to create a local definition,
//of the inherited method (every derived class,
//will individually override this method)
};
/*
Application in Main:
Given above definitions;
*/int main(){
base baseObjs[4];
baseObjs[0] = new aDerivedClass;
}/*
*/