Study Guide: Algorithms, Data Structures, and
Container Classes
Prepared for Emmanuel
Contents
1 Algorithms 3
1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Core Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Analysis of Algorithms 4
2.1 Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Common Growth Rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Worked Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5 Key Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Abstract Data Types (ADTs) 5
3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Common ADTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 C++ Classes and Object-Oriented Constructs 5
4.1 Classes and Members . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Operator Overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.4 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5 Pointers and Dynamic Memory: Python Perspective 8
5.1 References in Python . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 Copying to Avoid Side Effects . . . . . . . . . . . . . . . . . . . . . . . . 8
5.3 Passing Lists to Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.4 Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1
6 Container Classes 9
6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6.2 Comparison Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.3 Bag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.4 Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.5 Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
7 Summary 11
2
1 Algorithms
1.1 Definition
An algorithm is a finite, unambiguous, and effective sequence of steps designed to solve
a specific problem or perform a computation. It maps input(s) to output(s) and must
terminate after a finite number of steps.
1.2 Core Properties
• Input: Clearly defined set of inputs.
• Output: Clearly defined set of outputs.
• Definiteness: Each step is precise and unambiguous.
• Finiteness: The procedure terminates after a finite number of steps.
• Effectiveness: Each step is basic enough to be carried out in practice.
1.3 Examples
Add Two Numbers
1. Start
2. Read a, b
3. Compute sum = a + b
4. Display sum
5. End
Find Maximum in a List
1. Start
2. Read list L of n numbers
3. Set m = L[0]
4. For each x ∈ L, if x > m then m := x
5. Output m
6. End
3
Euclid’s Algorithm for GCD Given integers a and b (b ̸= 0):
gcd(a, b) = gcd b, a mod b
Repeat until the remainder is zero. Time complexity: O(log(min(a, b))).
2 Analysis of Algorithms
2.1 Purpose
Algorithm analysis studies the time and space requirements of algorithms as functions of
input size n, focusing on asymptotic behavior to assess scalability.
2.2 Asymptotic Notation
• Big-O O(·): Upper bound on growth rate.
• Big-Ω: Lower bound on growth rate.
• Big-Θ: Tight bound (both upper and lower).
2.3 Common Growth Rates
Notation Name Example
O(1) Constant Access array element
O(log n) Logarithmic Binary search
O(n) Linear Single-pass loop
O(n log n) Log-linear Merge sort
O(n2 ) Quadratic Bubble sort
2.4 Worked Examples
Linear search Checks each element; worst-case T (n) = O(n).
Binary search Halves search space each step; O(log n).
Dynamic array insertion Amortized O(1); occasional O(n) on resize.
2.5 Key Considerations
• Correctness proofs (partial and total).
• Space complexity analysis.
4
• Trade-offs: time vs space, preprocessing vs query cost.
• Decidability: which problems admit algorithms.
• P vs NP: verifiability vs solvability.
3 Abstract Data Types (ADTs)
3.1 Definition
An Abstract Data Type specifies a logical model of data and a set of supported operations
without prescribing implementation details. ADTs promote encapsulation, modularity,
and reusability.
3.2 Common ADTs
Stack (LIFO) Operations: push, pop, top, isEmpty. Use cases include function-call
stacks, undo functionality, and expression evaluation.
Queue (FIFO) Operations: enqueue, dequeue, front, isEmpty. Used in task schedul-
ing, buffering, and breadth-first search.
List Ordered collection supporting insertion, deletion, and traversal. Can be array-
based or linked-list–based.
Tree Hierarchical structure. Examples:
• Binary Search Tree: O(log n) search if balanced.
• Heap: efficient priority queue operations.
• Trie: fast prefix-based searches.
Graph Set of vertices and edges (directed/undirected, weighted/unweighted). Appli-
cations: routing, social networks, dependency graphs.
4 C++ Classes and Object-Oriented Constructs
4.1 Classes and Members
A class bundles data members and member functions. Access specifiers:
• private: internal use only.
5
• public: external access.
• protected: access in derived classes.
4.2 Illustrative Example
Listing 1: Encapsulated Person class in C++
# include < iostream >
# include < string >
using namespace std ;
class Person {
private :
string name ;
int age ;
public :
Person () : name ( " Unknown " ) , age (0) {} //
Default
Person ( string n , int a ) : name ( n ) , age ( a ) {} //
Parameterized
Person ( const Person & p ) : name ( p . name ) , age ( p . age ) {} //
Copy
void setData ( const string & n , int a ) {
name = n ; age = a ;
}
void display () const {
cout << " Name : " << name << " , Age : " << age << endl ;
}
};
4.3 Operator Overloading
Listing 2: Overloading + for complex numbers
class Complex {
private :
float real , imag ;
6
public :
Complex ( float r = 0.0 f , float i = 0.0 f )
: real ( r ) , imag ( i ) {}
Complex operator +( const Complex & c ) const {
return Complex ( real + c . real , imag + c . imag ) ;
}
void display () const {
cout << real << " + " << imag << " i \ n " ;
}
};
4.4 Polymorphism
Listing 3: Polymorphism via virtual functions
class Shape {
public :
virtual void draw () const = 0; // Pure virtual
virtual ~ Shape () = default ;
};
class Circle : public Shape {
public :
void draw () const override { cout << " Drawing Circle \ n " ; }
};
class Square : public Shape {
public :
void draw () const override { cout << " Drawing Square \ n " ; }
};
void render ( const Shape & s ) {
s . draw () ;
}
7
5 Pointers and Dynamic Memory: Python Perspec-
tive
5.1 References in Python
Python variables are references to objects. Assigning one name to another binds it to the
same object.
Listing 4: Reference semantics in Python
a = [1 , 2 , 3]
b = a # b refers to the same list as a
b . append (4)
print ( a ) # [1 , 2 , 3 , 4]
Explanation
• Line 1: Create list object and bind to a.
• Line 2: Bind b to the same object; no copy.
• Line 3: Mutate in place via append.
• Line 4: Shows that both names share the same list.
5.2 Copying to Avoid Side Effects
Listing 5: Shallow copy of a list
numbers = [1 , 2 , 3]
copy_numbers = numbers . copy () # or list ( numbers ) or numbers [:]
copy_numbers . append (99)
print ( numbers ) # [1 , 2 , 3]
print ( copy_numbers ) # [1 , 2 , 3 , 99]
Explanation
• copy(): Creates a new list with the same elements.
• Mutation of copy_numbers does not affect numbers.
• For nested objects, use [Link].
8
5.3 Passing Lists to Functions
Listing 6: Lists passed by reference
def modify_list ( lst ) :
lst . append (100)
nums = [1 , 2 , 3]
modify_list ( nums )
print ( nums ) # [1 , 2 , 3 , 100]
Explanation
• Function parameter lst references the same list.
• append mutates the shared object.
• After call, nums reflects the change.
5.4 Dynamic Arrays
Python lists are dynamic arrays that resize automatically. Insertions are amortized O(1).
Listing 7: Dynamic growth of Python list
arr = []
for i in range (10) :
arr . append ( i )
print ( arr ) # [0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9]
Explanation
• Each append may trigger a resize when capacity is reached.
• Resizing doubles capacity, giving amortized constant time per append.
6 Container Classes
6.1 Overview
Container classes store and manage collections of objects. They vary in ordering guaran-
tees, duplication rules, and access patterns.
9
6.2 Comparison Table
Class Type Duplicates Allowed Order Maintained Typical Use Case
Bag Yes No Frequency counting
Sequence Yes Yes Ordered items, indexing
Set No No Uniqueness enforcement
6.3 Bag
A bag (multiset) is an unordered collection that allows duplicates.
Listing 8: Bag behavior using Counter
from collections import Counter
bag = Counter ([ ’ apple ’ , ’ apple ’ , ’ banana ’ , ’ orange ’ ])
print ( bag ) # Counter ({ ’ apple ’: 2 , ’ banana ’: 1 , ’ orange ’:
1})
print ( bag [ ’ apple ’ ]) # 2
Explanation
• Counter: Dictionary subclass to count hashable items.
• Creation via list initializer.
• Indexing returns frequency of element.
6.4 Sequence
An ordered collection that supports indexing and slicing. Duplicates are allowed.
Listing 9: Sequence operations
my_list = [ ’ apple ’ , ’ banana ’ , ’ apple ’ , ’ orange ’]
print ( my_list [0]) # apple
print ( my_list [2]) # apple
print ( my_list [1:3]) # [ ’ banana ’, ’ apple ’]
Explanation
• Indexing: my_list[i] accesses the element at position i in O(1) time.
• Slicing: my_list[1:3] returns a new list containing the elements at indices 1 and 2.
• Properties: Preserves insertion order; supports iteration; supports concatenation;
supports slicing.
10
6.5 Set
An unordered collection of unique elements. Supports union, intersection, and difference.
Listing 10: Set examples
my_set = { ’ apple ’ , ’ banana ’ , ’ orange ’ , ’ apple ’}
print ( my_set ) # { ’ apple ’, ’ banana ’, ’ orange ’}
my_set . add ( ’ grape ’)
my_set . discard ( ’ banana ’)
print ( my_set )
set1 = { ’ apple ’ , ’ banana ’}
set2 = { ’ banana ’ , ’ cherry ’}
print ( set1 . union ( set2 ) ) # { ’ apple ’, ’ banana ’, ’ cherry ’}
print ( set1 . intersection ( set2 ) ) # { ’ banana ’}
Explanation
• Duplicate literals collapse to a single element.
• add: Inserts new element if not present.
• discard: Removes element if present.
• union, intersection: Set algebra operations.
• Set operations are expected O(1) due to hashing.
7 Summary
• Algorithms define precise, finite procedures; analyzed via asymptotic notation.
• ADTs specify operations; concrete implementations manage performance trade-offs.
• C++ classes provide encapsulation, inheritance, and polymorphism.
• Python uses reference semantics and dynamic arrays for flexibility.
• Container classes (Bag, Sequence, Set) differ in order, uniqueness, and use cases.
11