Data-Structures-and-Algorithms

My notes from an online C++ course

---

Project maintained by jfspps Hosted on GitHub Pages — Theme by mattgraham

Data Structures and Algorithms in C++

The stack and the heap

Essential C and C++

• Enumerations
• Structures
• Pointers
  • Storing data on the heap with pointers in C and C++
  • Pointers, Arrays and Pointer Arithmetic
  • Pointers to char
  • Pointers and Structures
• References (C++ only)
• Functions and parameter passing
  • Passing pointers and function overloading
  • The main() method
  • Passing by reference (C++ only)
  • Passing arrays
  • Passing read-only addresses
  • Passing structures
• Static variables
• Returning pointers and references
• Pointers to functions
• Functions as arguments of other functions
• Array of pointers to functions
• Default arguments

Classes in C++

• Instantiation, members and constructors
• Scope resolution and inline methods
• Friend functions
• The this pointer
• Constant class instances
• Pointers and references to objects
• The copy constructor
• Destructors
• Copy constructors revisted
• Operator overloading
• Overloading prefix and postfix operators
• Templates (function and class)
• Inheritance
• Protected access specifier
• Friend Classes
• Early and Late Binding
• Virtual Functions and Polymorphism
• Pointers and References of derived class instances
• Abstract classes
• Nested classes

Types of data structures

• Physical and logical data structures
• Abstract data types

Time and space complexity

• Order and degree
• Calling and returning phase of recursive functions
• Excessive recursions and memoization

Recurrence relations and recursion

• Designing recursive functions
• Recurrence relations

Static variables and methods

Types of recursion

• Tail and head recursion
• Indirect recursion
• Nested recursion

Applications of recursion

• Taylor’s series
• Fibonacci series
• nCr recursion and Pascal’s triangle
• Tower of Hanoi

Array representations

• Static and dynamic arrays
• Multi-dimensional arrays
• Row-major and column-major mappings

Array operations

• Displaying arrays
• Appending to arrays
• Insertion and deletion
• Reversing arrays and inserting into sorted arrays
• Merging sorted arrays
• Sets as arrays: union, intersection and difference

Array searching

• Linear search
• Binary search

Algorithm exercises on arrays

• Finding missing element(s) in sorted arrays
• Finding duplicated elements
• Summing pairs of elements
• Finding min and max elements

Strings in C and C++

• Arrays of characters
• Printing and scanning strings
• Reversing strings
• Finding duplicate characters with hash tables and bitwise operations
• Deducing string permutations

Matrices

• Diagonal matrices
• Lower-triangular matrices with row- and column-major mappings
• Upper-triangular matrices
• Symmetric matrices
• Tridiagonal and Toeplitz matrices

Sparse matrices and polynomials

• Representing sparse matrices and summing sparse matrices
• Representing polynomials with matrices and summing different polynomials

Linked Lists

• Nodes and keys
• Linked list traversal
• Displaying linked lists
• Initialising linked lists
• Node count and summing key values
• Min and max keys
• Linear searching
• Inserting nodes and creating linked lists
• Sorted linked list verification and inserting into sorted lists
• Deleting nodes and duplicated keys
• Interchanging elements and updating node links
• Merging linked lists
• Looped/circular linked lists (display, insertion, deletion)
• Doubly linked lists (insertion, deletion, reversal)
• Linked lists compared to arrays

Sparse matrices and polynomials as linked lists

The stack

• Implementing stacks with arrays
• Push(), Pop(), Peek(), StackTop(), isEmpty(), isFull() and Display() methods
• Implementing stacks with linked lists
• Linked list based methods
• Stack applications
  • Checking paired parentheses
  • Prefix and postfix operations (meaning of operator precedence)

The Queue

• Implementing queues with arrays
• Enqueue and Dequeue methods
• Circular queues
• Implementing queues with linked lists
• Doubled ended queues, DEQueues
• Priority queues (an overview)
• Implementing queues with stack ADTs

Trees

• Terminology
• Binary trees
• Node count and height deduction
• Strict binary trees
• m-ary trees
• Array and linked list representations of binary trees
• Full and complete binary trees
• Pre-, post- and in-order traversal of binary trees
• Building binary trees
• Recursive binary tree traversal
• Iterative binary tree traversal
• Level traversal
• Building trees from traversals

Binary Search Trees BSTs

• Searching with BSTs
• Inserting into BSTs
• Deleting from BSTs
• Building BSTs from pre-order traversals

AVL trees

• Balance factors
• Insertions and rotations
• Principles of BST balancing
• Building and deleting from AVL trees
• Height and node count analysis

Search trees

• 2-3 search trees
• 2-3-4 search trees
• Red-black trees
• Deleting from red-black trees

Binary Heaps

• Min and max heaps
• Inserting into binary heaps
• Creating heaps and deleting nodes
• Binary heap sort
• Heapify method
• Binary heaps and priority queues

Sorting methods

• Comparison based sorting methods
  • Bubble sort
  • Insertion sort
  • Selection sort
  • Heap sort
  • Merge sort
  • Quick sort
  • Tree sort
  • Shell sort
• Index based sorting methods
  • Bin/bucket sort
  • Count sort
  • Radix sort

Hashing techniques

• Hash tables, keys and collisions
• Open hashing
  • Chaining
• Closed hashing
  • Linear probing
  • Quadratic probing
  • Double hashing

Graphs

• Directed and undirected graphs
• Breadth first search
• Depth first search
• Spanning tree
• Prim’s programming
• Kruskal’s minimum cost spanning tree
• Disjoint subsets
• Kruskal’s program

Exceptions and error-handling