Introduction to Data Structures and Algorithms in C++

Introduction to Data Structures and Algorithms in C++

English | MP4 | AVC 1280×720 | AAC 44KHz 2ch | 3h 29m | 434 MB

This introductory course will teach you how to implement some fundamental data structures and algorithms in C++ from scratch, with a combination of theoretical introduction using slides, and practical C++ implementation code.

Knowing some fundamental data structures and algorithms both in theory and from a practical implementation perspective helps you in being a better C++ programmer, gives you a good foundation to understand standard library’s containers and algorithms inner “under the hood” mechanics, and serves as a kind of knowledge that is required in several coding interviews, as well. In this course, Introduction to Data Structures and Algorithms in C++, you’ll learn how to implement some fundamental data structures and algorithms in C++ from scratch, with a combination of theoretical introduction using slides, and practical C++ implementation code as well. No prior data structure or algorithm theory knowledge is required. You only need a basic knowledge of C++ language features. First, you’ll discover how to develop a C++ class to safely use arrays, with automatic memory management using constructor and destructor, and safely accessing array elements with bounds checking. Then, you’ll see how to further improve this array class, overloading the insertion operator to offer a simple nice idiomatic printing syntax for arrays, and optimizing the array class with move semantics. You’ll also learn how to properly copy arrays, and you’ll see the copy-and-swap idiom in action. Then, you’ll learn how to generalize the array class with templates. Next, you’ll learn about the Big O notation in a practical intuitive way, and you’ll apply that knowledge to a couple of search algorithms. You’ll start learning how to search using the simple linear search, and then you’ll see how to improve searching, using binary search. I’ll first introduce these algorithms using slides, and then you’ll see them in action in concrete C++ demo code. Finally, you’ll discover how to implement other common data structures, like the stack with its LIFO policy and push and pop operations, and linked lists, including operations like list node insertion and removal, and searching elements in a linked list. After completing this course, you will be able to implement some common fundamental data structures and algorithms from scratch in C++, you’ll have a practical understanding of the Big O notation to evaluate and compare algorithm performance trends, and you’ll see in action, several interesting C++ coding techniques that you’ll be able to reuse in your own C++ projects as well. Moreover, you will be able to use this foundational knowledge to move forward to more advanced C++ data structures and algorithms topics.

Table of Contents

Course Overview
1 Course Overview

Safely Using Arrays
2 Introduction
3 Prerequisites
4 Module Overview
5 What Is an Array
6 C++ Built-in Arrays and Stack vs. Heap Allocations
7 Starting a Basic Array Class Implementation Journey
8 Spotting a Bug in the Array Class
9 Fixing Memory Leaks with a Destructor
10 Accessing Array Elements with Overloaded operator
11 Granting Read-only Access to Array Elements
12 Bounds-checking for Safe Array Element Access
13 Array Index Bounds-checking in Action
14 Summary

Improve Array Implementation
15 Introduction
16 Conveniently Printing Arrays
17 Demo – Printing Arrays with the Overloaded Insertion Operator
18 Demo – A Subtle Bug When Copying Arrays
19 Analyzing the Subtle Copy Bug – Shallow vs. Deep Copies
20 Safely Copying Arrays with a Custom Copy Constructor
21 Demo – Custom Array Copy Constructor in Action Fixing the Copy Bug
22 Overloading the Assignment Operator
23 The Copy-and-swap Idiom
24 Optimizing the Array Class with Move Semantics
25 Generalizing the Array Class with Templates
26 Summary

Efficiently Searching
27 Introduction
28 A Simple Straightforward Algorithm – Linear Search
29 Demo – Implementing Linear Search in C++
30 Smarter Searching with Binary Search
31 Demo – Implementing Binary Search in C++
32 Introducing the Big O Notation and Asymptotic Runtime Complexity
33 Comparing the Efficiency of Linear Search vs. Binary Search
34 Summary

Implementing a Last-in First-out Pattern with the Stack
35 Introduction
36 What Is a Stack
37 An Important Application – The Call Stack
38 Fundamental Stack Operations
39 Demo – A Basic Stack Implementation in C++
40 Demo – Stack in Action
41 Stack Overflow – What Is It and How to Protect Your Code
42 Demo – Stack Overflow in Action
43 Summary

Introducing Node-based Data Structures – Linked-lists
44 Introduction
45 What Is a Linked List
46 Linked Lists vs. Arrays
47 Inserting a New Node in a Linked List
48 Removing a Node from a Linked List
49 Traversing a Linked List
50 Demo – Implementing a Linked List in C++
51 Demo – Linked List C++ Class in Action
52 Summary and Thank You