Mastering Data Structures & Algorithms using C and C++

Before we Start
1 Instructor’s Note
2 Introduction

Essential C and C++ Concepts
3 Arrays Basics
4 Practice Arrays Basics
5 Structures
6 Practice Structures
7 Pointers
8 Practice Pointers
9 Reference in C++
10 Practice Reference
11 Pointer to Structure
12 Practice Pointer to Structure
13 Functions
14 Practice Functions
15 Parameter Passing Methods
16 Practice Parameter Passing Methods
17 Array as Parameter
18 Practice Array as Parameter
19 Structure as Parameter
20 Practice Structure as Parameter
21 Structures and Functions (Must Watch)
22 Converting a C program to a C++ class (Must Watch)
23 Practice Monolithic Program
24 Practice Modular Program
25 Practice Structure and Functions
26 Practice Object-Oriented Program
27 C++ Class and Constructor
28 Practice C++ Class
29 Template classes
30 Practice Template Class

Required Setup for Programming
32 Setup Dev-C++ and Settings
33 Setup CodeBlocks and Settings
34 Debugging using Dev-C++
35 Debugging using CodeBlocks
36 Setup Visual Studio
37 Debugging using Visual Studio
38 Setup Xcode

Introduction
39 Introduction
40 Stack vs Heap Memory
41 Stack vs Heap. Continued
42 Physical vs Logical Data Structures
43 ADT
44 Time and Space Complexity
45 Time and Space Complexity from Code

Recursion
46 How Recursion Works ( Tracing )
47 Generalising Recursion
48 How Recursion uses Stack
49 Recurrence Relation – Time Complexity of Recursion
50 Lets Code Recursion
51 Static and Global Variables in Recursion
52 Let’s Code Static and Global in Recursion
53 Tail Recursion
54 Head Recursion
55 Tree Recursion
56 Let’s Code Tree Recursion
57 Indirect Recursion
58 Let’s Code Indirect Recursion
59 Nested Recursion
60 Let’s Code Nested Recursion
61 Sum of Natural Number using Recursion
62 Let’s Code Sum of N using Recursion
63 Factorial using Recursion
64 Let’s Code Factorial using Recursion
65 Power using Recursion
66 Let’s Code Power Recursion
67 Taylor Series using Recursion
68 Let’s Code Taylor Series using Recursion
69 Taylor Series using Horner’s Rule
70 Let’s Code Taylor Series Horner’s Rule – Recursion
71 Let’s Code Taylor Series Iterative
72 Fibonacci Series using Recursion – Memoization
73 Let’s Code Fibonacci
74 nCr using Recursion
75 Let’s Code nCr using Recursion
76 Tower of Hanoi Problem
77 Let’s Code Tower of Hanoi
78 Quiz 1 Solutions

Arrays Representations
79 Introduction to Array
80 Declarations of Array
81 Demo – Array Declaration
82 Static vs Dynamic Arrays
83 Demo – Static vs Dynamic Array
84 How to Increase Array Size
85 Demo – Increasing Array Size
86 D Arrays
87 Demo – 2D Array
88 Array Representation by Compiler
89 Row Major Formula for 2D Arrays
90 Column Major Formula for 2D Arrays
91 Formulas for nD Arrays
92 Formulas for 3D Arrays
93 Solutions for Quiz 2

Array ADT
94 Array ADT
95 Demo – Array ADT
96 Inserting in an Array
97 Let’s Code Insert
98 Deleting from Array
99 Let’s Code Delete
100 Linear Search
101 Improving Linear Search
102 Let’s Code Linear Search
103 Binary Search
104 Binary Search Algorithm
105 Let’s Code Binary Search
106 Analysis of Binary Search
107 Average Case Analysis of Binary Search
108 Get( ) Set( ) Avg( ) Max( ) functions on Array
109 Let’s Code Get() Set() Max() on Array
110 Reverse and Shift an Array
111 Lest’s Code Reversing an Array
112 Check if Array is Sorted
113 Let’s Code to check if Array is Sorted
114 Merging Arrays
115 Let’s Code to Merge Arrays
116 Set operations on Array – Union, Intersection and Difference
117 Let’s Code Set operations on Array
118 Let’s Code a Menu Driver program for Arrays
119 Let’s convert C program for Array to C++
120 Let’s Put all together in C++ program for Array
121 Student Challenge Finding Single Missing Element in an Array
122 Student Challenge Finding Multiple Missing Elements in an Array
123 Student Challenge Finding Missing Element in an Array Method 2
124 Student Challenge Finding Duplicates in a Sorted Array
125 Student Challenge Finding Duplicates in Sorted Array using Hashing
126 Student Challenge Finding Duplicates in a Unsorted Array
127 Student Challenge Finding a Pair of Elements with sum K
128 Student Challenge Finding a Pair of Elements with sum K in Sorted Array
129 Student Challenge Finding Max and Min in a single Scan
130 Solutions for Quiz 3

Strings
131 Introduction to Strings
132 Finding Length of a String
133 Changing Case of a String
134 Counting Words and Vowels in a String
135 Validating a String
136 Reversing a String
137 Comparing Strings and Checking Palindrome
138 Finding Duplicates in a String
139 Finding Duplicates in a String using Bitwise Operations
140 Checking if 2 Strings are Anagram (distinct letters)
141 Permutation of String

Matrices
142 Section Introduction
143 Diagonal Matrix
144 Let’s Code Diagonal Matrix
145 C++ class for Diagonal Matrix
146 Let’s Code C++ class for Diagonal matrix
147 Lower Triangular Matrix Row-Major Mapping
148 Lower Triangular Matrix Column-Major Mapping
149 Let’s Code Lower Triangular Matrix in C
150 Let’s Code Lower Triangular Matrix in C++
151 Upper Triangular Matrix Row-Major Mapping
152 Upper Triangular Matrix Column-Major Mapping
153 Symmetric Matrix
154 Tri-Diagonal and Tri-Band Matrix
155 Toeplitz Matrix
156 Menu Driven Program for Matrices
157 Menu Driven Program for Matrices using Functions
158 How to Write C++ Classes for All Matrices

Sparse Matrix and Polynomial Representation
159 Sparse Matrix Representation
160 Addition of Sparse Matrices
161 Array Representation of Sparse Matrix
162 Let’s Code to Create Sparse Matrix
163 Program for Adding Sparse Matrix
164 Let’s Code to Add Sparse Matrix
165 Let’s Code Sparse Matrix using C++
166 Let’s Code Sparse Matrix using C++ Continued
167 Polynomial Representation
168 Polynomial Evaluation
169 Polynomial Addition
170 Let’s Code Polynomial

Linked List
171 Why we need Dynamic Data Structure Linked List
172 About Linked List
173 More About Linked List
174 Display Linked List
175 Let’s Code Display for Linked List
176 Recursive Display of Linked List
177 Let’s Code Recursive Display for Linked List
178 Counting Nodes in a Linked List
179 Sum of All Elements in a Linked List
180 Let’s Code Count and Sum
181 Maximum Element in a Linked List
182 Let’s Code Max for Linked List
183 Searching in a Linked List
184 Improve Searching in Linked List
185 Let’s Code Searching in Linked List
186 Inserting in a Linked List
187 Let’s Code Insert for Linked List
188 Creating a Linked List using Insert
189 Creating a Linked List by Inserting at Last
190 Inserting in a Sorted Linked List
191 Let’s Code Insert in Sorted Linked List
192 Deleting from Linked List
193 Let’s Code Delete on Linked List
194 Check if a Linked List is Sorted
195 Let’s Code to check if Linked List is Sorted
196 Remove Duplicates from Sorted Linked List
197 Let’s Code to Remove Duplicates from Sorted Linked List
198 Reversing a Linked List
199 Reversing using Sliding Pointers
200 Recursive Reverse for Linked List
201 Let’s Code Reversing a Linked List
202 Concatenating 2 Linked Lists
203 Merging 2 Linked Lists
204 Let’s Code to Concatenate and Merge Linked Lists
205 Check for LOOP in Linked List
206 Let’s Code to Check LOOP
207 Let’s Code a C++ class for Linked List
208 Circular Linked List
209 Display Circular Linked List
210 Let8217s Code Circular Linked List
211 Inserting in a Circular Linked List
212 Let’s Code Insert for a Circular Linked List
213 Deleting From Circular Linked List
214 Let’s Code Delete for Circular Linked List
215 Doubly Linked List
216 Let’s Code Doubly Linked List
217 Insert in a Doubly Linked List
218 Let’s Code Insert for Doubly Linked List
219 Deleting from Doubly Linked List
220 Let’s Code Delete for Doubly Linked List
221 Reverse a Doubly Linked List
222 Let’s Code Reverse for Doubly Linked List
223 Circular Doubly Linked List
224 Comparison of Linked List
225 Comparison of Array with Linked List
226 Student Challenge Finding Middle Element of a Linked List
227 Student Challenge Finding Intersecting point of Two Linked List

Sparse Matrix and Polynomial using Linked List
228 Student Challenge Sparse Matrix using Linked List
229 Student Challenge Polynomial Representation using Linked List
230 Let’s Code Polynomial

Stack
231 Introduction to Stack
232 Stack using Array
233 Implementation os Stack using Array
234 Let’s Code Stack using Array
235 Stack using Linked List
236 Stack Operations using Linked List
237 Let’s Code Stack using Linked List
238 Let’s Code C++ class for Stack using Linked List
239 Parenthesis Matching
240 Program for Parenthesis Matching
241 Let’s Code Parenthesis Matching
242 More on Parenthesis Matching
243 Infix to Postfix Conversion
244 Associativity and Unary Operators
245 Infix to Postfix using Stack Method 1
246 Infix to Postfix using Stack Method 2
247 Program for Infix to Postfix Conversion
248 Let’s Code Infix to Postfix Conversion
249 Student Challenge Infix to Postfix with Associativity and Parenthesis
250 Evaluation of Postfix Expression
251 Program for Evaluation of Postfix
252 Let’s Code Evaluation of Postfix

Queues
253 Queue ADT
254 Queue using Single Pointer
255 Queue using Two Pointers
256 Implementing Queue using Array
257 Let’s Code Queue using Array
258 Let’s Code Queue in C++
259 Drawback of Queue using Array
260 Circular Queue
261 Let’s Code Circular Queue
262 Queue using Linked List
263 Let’s Code Queue using Linked List
264 Double Ended Queue DEQUEUE
265 Priority Queues
266 Queue using 2 Stacks

Trees
267 Terminology
268 Number of Binary Trees using N Nodes
269 Height vs Nodes in Binary Tree
270 Internal Nodes vs External Nodes in Binary Tree
271 Strict Binary Tree
272 Height vs Node of Strict Binary Tree
273 Internal vs External Nodes of Strict Binary Trees
274 n-ary Trees
275 Analysis of n-Ary Trees
276 Representation of Binary Tree
277 Linked Representation of Binary Tree
278 Full vs Complete Binary Tree
279 Strict vs Complete Binary Tree
280 Binary Tree Traversals
281 Binary Tree Traversal Easy Method 1
282 Binary Tree Traversal Easy Method 2
283 Binary Tree Traversal Easy Method 3
284 Creating Binary Tree
285 Program to Create Binary Tree
286 Let’s Code Creating Binary Tree
287 Let’s Code Creating Binary Tree in C++
288 Preorder Tree Traversal
289 Inorder Tree Traversals Functions
290 Iterative Preorder
291 Iterative Inorder
292 Let’s Code Iterative Traversals
293 Level Order Traversal
294 Let’s Code Level Order Traversal
295 Can we Generate Tree from Traversals
296 Generating Tree from Traversals
297 Height and Count of Binary Tree
298 Let’s Code Height and Count
299 Student Challenge Count Leaf Nodes of a Binary Tree

Binary Search Trees
300 BST intro
301 Searching in a Binary Search Tree
302 Inserting in a Binary Search Tree
303 Recursive Insert in Binary Search Tree
304 Creating a Binary Search Tree
305 Let’s code Binary Search Tree
306 Deleting from Binary Search Tree
307 Let’s Code Recursive Insert and Delete on BST
308 Generating BST from Preorder
309 Program for Generating BST from Preorder
310 Drawbacks of Binary Search Tree

AVL Trees
311 Introduction to AVL Trees
312 Inserting in AVL with Rotations
313 General form of AVL Rotations
314 Let’s Code LL Rotation on AVL
315 Let’s Code LR Rotation on AVL
316 Generating AVL Tree
317 Deletion from AVL Tree with Rotations
318 Height Analysis of AVL Trees

Search Trees
319 Trees
320 Trees
321 Re-Black Trees Introduction
322 Red-Black Tree creation
323 Red-Black Trees vs 2-3-4 Trees
324 Creating Red-Black Tree similar to Creating 2-3-4 Tree
325 Red-Black Tree Deletion Cases
326 Red-Black Tree Deletion Examples
327 Red-Black Tree vs 2-3-4 Tree Deletion

Heap
328 Introduction to Heap
329 Inserting in a Heap
330 Program to Insert in a Heap
331 Creating a Heap
332 Deleting from Heap and Heap Sort
333 Let’s Code Heap Sort
334 Heapify – Faster Method for creating Heap
335 Heap as Priority Queue

Sorting Techniques
336 Criteria used for Analysing Sorts
337 Bubble Sort
338 Let’s Code Bubble Sort
339 Insertion Sort
340 Insertion Sort Continued
341 Program for Insertion Sort
342 Analysis of Insertion Sort
343 Let’s Code Insertion Sort
344 Comparing Bubble and Insertion Sort
345 Selection Sort
346 Program for Selection Sort
347 Analysis of Selection Sort
348 Let’s Code Selection Sort
349 Idea behind Quick Sort
350 Quick Sort
351 Analysis of Quick Sort
352 Analysis of Quick Sort Continued
353 Let’s Code Quick Sort
354 Merging
355 Iterative Merge Sort
356 Let’s Code Iterative Merge Sort
357 Recursive Merge Sort
358 Let’s Code Recursive Merge Sort
359 Count Sort
360 Let’s Code Count Sort
361 Bin Bucket Sort
362 Radix Sort
363 Shell Sort
364 Let’s Code Shell Sort

Hashing Technique
365 Introduction to Hashing
366 Chaining
367 Let’s Code Chaining
368 Linear Probing
369 Let’s Code Linear Probing
370 Quadratic Probing
371 Double Hashing
372 Hash Function Ideas

Graphs
373 Introduction to Graphs
374 Representation of Undirected Graph
375 Representation of Directed Graphs
376 Breadth First Search
377 Program for BFS
378 Depth First Search
379 Program for DFS
380 Let’s Code BFS & DFS
381 Spanning Trees
382 Prim’s Minimum Cost Spanning Tree
383 Prim’s Program
384 Let’s Code Prim’s using
385 Kruskal’s Minimum Cost Spanning Tree
386 Disjoint Subsets
387 Kruskal’s Program
388 Let’s Code Kruskla’s Program

Asymptotic Notations
389 Asymptotic Notations Big Oh , Omega , Theta
390 PDF for All Programs