This course introduces the basics of algorithms and data structures with examples in C++. This course focuses on what the working programmer should know about algorithms and data structures without getting bogged down in mathematical formalism.
Learning Objectives
Introduction
- start the course
- recognize the definition of a data structure and its importance in computer science
- define what an algorithm is informally and discuss a few aspects of algorithms we need to consider as programmers
- define the complexity of an algorithm in terms of Big O notation
- define and use static arrays in C++
- define and use dynamic arrays in C++
- use a recursive binary search in C++
Standard Containers
- implement a fixed-size stack of integers in C++
- implement a fixed-size queue of integers in C++
- implement a linked list in C++
Binary Trees
- construct and destruct a Binary Search Tree (BST) in C++
- perform a search using recursion on a BST in C++
- insert elements into a BST in C++
- delete elements from a BST in C++
Sorting
- implement a Bubble sort to sort a list of integers in C++
- implement a Merge sort in C++
- implement a Quicksort in C++
Graphs
- define a graph as an adjacency list in C++
- define a graph as an adjacency matrix in C++
- perform a Breadth First Search (BFS) on a graph represented by an adjacency list in C++
- perform a Depth First Search (DFS) on a graph represented by an adjacency matrix in C++
- implement a Topological Sort in C++ to sort a graph represented by an adjacency list
Hashed Data Structures
- define a hashed data structure and discuss when to best use them
- implement a custom hash function in C++
- discuss the difference between perfect and non-perfect hashing, and implement a perfect hash in C++
- discuss the method of handling collisions using separate chaining
Practice: Using Algorithms and Data Structures
- learn the use of the fundamental basics of algorithms and data structures