Programming tutorials
The Art Of Programming
The art of programming goes beyond writing code. It involves our thinking process, problem-solving approach, and the impact we make on the world. Programming is a creative language that brings ideas to life and allows us to express ourselves through technology. It challenges us to think innovatively, find unconventional solutions, and expand our understanding of the world and ourselves. This video explores fundamental programming concepts, from basic syntax and data structures to advanced algorithms and programming paradigms. Let's begin.
When it comes to editing code, there are two main types of tools: text editors and IDEs. While text editors focus on editing plain text, IDEs provide additional features. However, for most purposes, the distinction between the two doesn't matter much, and the terms can be used interchangeably. Popular options for text editors and IDEs include Vim, Atom, Sublime Text, Eclipse, IntelliJ, PyCharm, and Visual Studio Code. Visual Studio Code, in particular, is highly customizable and widely recommended.
To run code, we need to compile it into machine code, which computers understand. This requires installing a language compiler or runtime. Different languages have their own compilers or runtimes, such as GCC, Java SDK, Python interpreter, Node.js runtime, and .NET SDK. Understanding the details of these tools is not necessary; all you need to know is to install a language to run your code.
Running code involves using the terminal, which provides access to the command line interface. Commonly used terminals include Powershell and Bash. The terminal allows us to execute commands like creating directories, listing files, and running programs. Package managers, such as npm for Node.js and pip for Python, can be used to install software from repositories through the command line. Git, a version control system, is essential for managing code changes and collaborating with others.
To start coding, you need a suitable text editor or IDE, a language compiler, and basic knowledge of terminal commands. Visual Studio Code is a recommended choice for a text editor or IDE. Installing a programming language and familiarizing yourself with terminal commands will enable you to write and run code. Learning programming languages involves understanding their syntax, environment, and conventions. Different languages have varying levels of complexity, but they all share similarities in structure and concepts.
Printing output in different programming languages can be done using functions or methods specific to each language. For example, Python has the built-in print function, JavaScript has the console.log method, and Java and C++ have their own syntax for printing to the standard output.
Variables are used to store values of different data types. Variables are declared, defined, and initialized with values. Programming languages can be statically typed or dynamically typed, and they have different syntax for variables. Static typing requires explicit declaration of the variable type, while dynamic typing does not. Variables have scope, which determines where they can be accessed and used in a program. Scope can be global or local, and it allows for better organization and prevention of errors.
Data types represent different kinds of data, such as strings, booleans, integers, floating-point numbers, characters, and arrays. Data structures provide a way to organize and manipulate data. Popular data structures include arrays, stacks, heaps, trees, linked lists, hash tables, hash maps, and graphs. Arrays and maps are two commonly used data structures with various applications.
In summary, programming is an art that encompasses thinking, problem-solving, and shaping the world through code. It involves using text editors or IDEs, running code through compilers or runtimes, and understanding terminal commands and version control. Learning programming languages requires grasping syntax, variables, data types, and data structures. The video provides a high-level overview of these concepts to get you started on your programming journey.
The Art Of Programming
- 2023.05.11
- www.youtube.com
In this video, we'll explore the basics of programming, including the different programming paradigms such as procedural, object-oriented, and functional pro...
The Art of Writing Software
Computers, like musical instruments, are meticulously crafted machines designed to perform specific tasks based on the instructions they receive. These instructions, written in code, are the software that guides their operations. Just as musical notation is the code used by composers, computer programmers use software code to create programs.
Programming can be a source of joy and satisfaction, akin to the feelings experienced by poets or musicians. Early computers were fascinating and empowering to those who enjoyed problem-solving and complexity. They operated at astonishing speeds, capable of solving a wide range of problems as long as they were expressed using the computer's native commands.However, computers are inherently dumb and require precise instructions to understand what to do. Early programmers had to write machine language using numbers that represented binary commands. This process was tedious and error-prone, leading to the development of more human-friendly programming languages.
The introduction of higher-level languages, such as Fortran and COBOL, made programming more accessible. Programmers could express their instructions using familiar scientific formulas or logical statements that made sense to them. Compilers were then used to translate these instructions into the computer's binary language. This breakthrough unlocked the software revolution, as programmers no longer needed to learn each computer's specific machine language.
Over the years, hundreds of programming languages have been developed to cater to different needs. The gap between these languages and the machine language has widened, allowing programmers to focus on what they want to achieve rather than the low-level details. As computing became more personal, programming languages became more diverse and user-friendly. People now routinely communicate with computers by telling them what to do, such as calculating averages or organizing data. Programming has become a tool for empowering individuals, allowing them to customize and adapt computer systems to their needs.
Writing software involves not only coding but also defining how data is represented and organized. Data can be organized into strings, lists, tables, trees, and more, depending on the requirements. The choice of language and data structure is crucial in solving programming problems effectively. Programmers create step-by-step procedures known as algorithms to solve problems. These algorithms specify the operations needed to achieve the desired outcomes. However, finding the most efficient algorithm for a given problem can be a complex task. It requires careful thinking, concentration, and sometimes extensive knowledge in specialized fields.
Software development is a challenging and creative endeavor that requires keeping numerous aspects in mind simultaneously. Programmers constantly adapt to advancements in technology, pushing the boundaries of what computers can achieve. They strive for elegance and coherence in their code, creating software that is both functional and aesthetically pleasing. Through their efforts, software programmers have expanded our capabilities, allowing us to harness the vast amounts of information and interact with the world in ways that were once considered magical. Programming is the driving force behind making computers work and shaping the high-tech world we live in today.
The Art of Writing Software
- 2014.11.17
- www.youtube.com
CHM Exhibition "Revolution: The First 2000 Years of Computing"Software is more than obscure computer code. It’s an art form: a meticulously-crafted literatur...
C++ Tutorial for Beginners - Full Course
C++ Tutorial for Beginners - Full Course
00:00:00 - 01:00:00 This video is a tutorial for beginners who want to learn how to code in C++. It covers the basics of working with strings, numbers, and variables. It also introduces the concept of importing code from other files.
01:00:00 - 02:00:00 This C++ tutorial for beginners covers how to build a four function calculator. The tutorial explains how to input data, check for operator equality, and execute code based on that condition.
02:00:00 - 03:00:00 This video provides a basic introduction to C++ programming, with a focus on using for loops to calculate a specific result. The function being demonstrated calculates the result of a number raised to a specific power.
03:00:00 - 04:00:00 In this C++ tutorial for beginners, the instructor demonstrates how to use inheritance to extend functionality in a class hierarchy. Inheritance allows a class to have the same functionality as another class, while extending that functionality with additional features. The instructor also demonstrates how to override inherited functions in order to change the behavior of a class.
Part 1
- 00:00:00 This video tutorial teaches beginners how to write basic c++ code. The first step is to install a text editor and a c++ compiler, which are both included in the codeblocks package. Then the tutorial shows how to set up a simple project in codeblocks.
- 00:05:00 This tutorial provides a brief introduction to the C++ programming language and the tools needed to write and run C++ programs. The first part of the tutorial shows how to install the necessary tools on a Mac, and the second part covers how to create a new C++ project in code blocks.
- 00:10:00 In this video tutorial, the presenter walks through the basics of writing a c++ program. He covers the need for a c++ project and file, explains functions, and shows how to build and run a program.
- 00:15:00 This tutorial explains how to write basic code in C++, and how to use print statements to output information to the console.
- 00:20:00 In this video, the presenter shows how variables are useful in programming, by providing an example of a program that prints out a story. The presenter then demonstrates how to create and assign a value to a variable named "character name" which stores the character's name. Next, the presenter demonstrates how to create and assign a value to a variable named "age" which stores the character's age. Finally, the presenter demonstrates how to use a variable to store multiple pieces of data.
- 00:25:00 In this video, the presenter introduces the concept of variables and shows how to use them to store data in a program. They demonstrate how to access and manipulate the data stored in variables using print statements. Finally, they show how to include a variable inside of a print statement so that the data is printed in a separate string.
- 00:30:00 This video introduces the concept of variables and data types in C++. A variable is a container that stores data, and you can use it to store any type of information. Strings are a common type of variable, and they are a sequence of characters. You can also use integers to store whole numbers, or negative integers to store negative numbers. You can also store decimal numbers in integers.
- 00:35:00 This tutorial covers the basics of programming with C++, starting with simple text and numbers, and moving on to more complex data types like strings and booleans.
- 00:40:00 This video covers how to use the C++ string functions length and string indexing to print strings and determine the location of specific characters in a string, and how to modify specific characters in a string.
- 00:45:00 The video covers the basics of working with strings in C++, including how to pass arguments to functions, and how to use different mathematical functions to manipulate strings.
- 00:50:00 In this C++ tutorial, the basics of numbers, addition, subtraction, multiplication, and division are covered. The modulus operator is also introduced, which is useful for dividing two numbers and calculating the remainder. Finally, storing numbers in variables is demonstrated.
- 00:55:00 This C++ tutorial for beginners explains how to use math functions to solve problems. The functions include square root, pow, and round. Importing code from other files is also explained.
Part 2
- 01:00:00 In this C++ tutorial for beginners, the user is prompted to enter their age and name. The program then stores the information in a variable called age, and prints the user's name and age.
- 01:05:00 This video tutorial shows how to create a basic calculator in c++, and how to build a Mad Libs game.
- 01:10:00 This video explains how to create and use arrays in C++. Arrays are similar to variables, but can hold multiple values.
- 01:15:00 This video tutorial explains the basics of arrays in C++. An array is a container that can store multiple pieces of data, and you can access individual elements by index or by assigning a value to the array's "size" property.
- 01:20:00 In this tutorial, the author demonstrates how to create a function in C++. A function is a block of code that performs a specific task and can be reused throughout a program. The function's return type can be either void or an integer. The author also demonstrates how to call a function.
- 01:25:00 In this video, the author explains how functions work and how they can be reused. He also shows how to create a function signature and how to call a function using its signature. Finally, he discusses returns in c++, which is when a function returns information to the caller.
- 01:30:00 The video discusses how to create functions in C++ and how to use the return keyword to indicate that the function is finished executing. The video also demonstrates how to use the cube function to return the result of cubing a number.
- 01:35:00 In this tutorial, the author teaches beginners about the if statement in C++. An if statement is a programming structure that allows a program to respond to different situations. The author demonstrates how to use an if statement to check conditions, and how to create more complex if statements.
- 01:40:00 This video tutorial explains how to use the and and or operators in C++ to check two conditions. If either condition is false, the entire if block will be false and the code will not be executed.
- 01:45:00 In this tutorial, the author teaches beginners about if statements, explaining how to use comparisons to create true or false values. The function will take two numbers as input, and will return the largest.
- 01:50:00 This video explains how comparisons work in C++, and how to use greater than, less than, and equal to to check if two numbers are equal or greater than or equal.
- 01:55:00 This C++ tutorial for beginners teaches how to build a four function calculator, including how to input data, check for operator equality, and execute code based on that condition.
Part 3
- 02:00:00 In this video tutorial, a function to convert an integer number to a day of the week is demonstrated. The function is created, and an if statement is used to determine if the day number given is one or greater. If it is one, the function returns "Sunday"; if it is not one, the function returns "Monday".
- 02:05:00 This video explains how a switch statement can be used to make code in an if statement more efficient. The video goes on to explain how to create a switch statement for each day of the week, and demonstrates the function by printing the day of the week for a number passed in as an input.
- 02:10:00 This video provides an overview of the video "C++ Tutorial for Beginners - Full Course." The video demonstrates how to use a while loop to iterate through a block of code, while a condition is met.
- 02:15:00 This C++ tutorial for beginners covers the basics of loops, including how to create a while loop and a do while loop. The video also discusses an infinite loop and how to avoid them. Finally, a for loop is demonstrated.
- 02:20:00 This tutorial shows how to create a guessing game using a while loop and a do while loop. The game is initially unfair in the sense that the user gets unlimited guesses, but the tutorial shows how to make the game more fair by imposing a guess limit.
- 02:25:00 In this video, the author explains how for loops work and how they can be used in C++. He also shows an example of how for loops can be used to solve a problem.
- 02:30:00 In this video, the author explains the while loop, a looping construct in which a variable changes each time it is executed. The for loop is a similar construct, but it includes a variable declaration, initialization, and looping condition.
- 02:35:00 This video tutorial demonstrates how to use for loops to iterate through the contents of arrays, as well as how to build a function that takes a number to a specific power.
- 02:40:00 This video tutorial provides a basic introduction to C++ programming, with a focus on using for loops to calculate a specific result. The function being demonstrated calculates the result of a number raised to a specific power.
- 02:45:00 In this tutorial, the author shows how to create and use a two-dimensional array and discusses how to access elements within it.
- 02:50:00 This video tutorial introduces the C++ language and demonstrates how to use for and int iterators to loop through arrays of data. The nested for loops allow for easy iteration of data within arrays.
- 02:55:00 This video explains what a pointer is, how they are useful, and how to create them in C++.
Part 4
- 03:00:00 This video provides a beginner-friendly introduction to C++ programming, with examples of how to use variables and constants to store information. The video also demonstrates how to access memory addresses to retrieve information stored inside them.
- 03:05:00 This video provides an overview of the video "C++ Tutorial for Beginners - Full Course". In the video, the presenter demonstrates how to access memory addresses of variables using pointers. A pointer is just a memory address that is just a type of data, and you can use it to store a pointer to a different variable.
- 03:10:00 This tutorial explains how to use pointers in programming, and demonstrates how to dereference them to access the value stored at a particular memory address. Additionally, the tutorial discusses classes and objects in c++, and demonstrates how to create and use a class.
- 03:15:00 In this video, a c++ tutorial for beginners, the author creates a class to represent books. The class has two attributes, the title and the author. The author then creates a book object and sets the title and the author.
- 03:20:00 This video teaches beginners how to create and work with objects in C++. An object is an actual instance of a class, and a class is the template for a data type. Objects can be printed and have their values changed.
- 03:25:00 This video explains how Constructors work in C++ and how they can be used to initialize objects with default values.
- 03:30:00 This video tutorial explains how to create a C++ constructor that accepts title, author and pages as input values. Once initialized, the constructor can be used to create a new object without having to pass in the values each time.
- 03:35:00 This video explains how to use functions in C++ to determine whether a student has honors or not. Functions are templates that each object can use to return true or false depending on the object's own GPA.
- 03:40:00 This video will teach beginners how to use getters and setters in c++ classes. Getters and setters allow you to control the access to attributes and elements in your classes. This example shows how to enforce a valid rating for a movie using getters and setters.
- 03:45:00 In this C++ tutorial for beginners, the author demonstrates how to use getters and setters to restrict the ratings that can be assigned to a movie object. If the rating passed in is not one of the valid ratings, an error is thrown or the rating is not set.
- 03:50:00 In this video, the author explains how to set ratings for videos using C++. First, they explain how ratings are represented in C++, with a rating being equal to a positive value such as 13, or a negative value such as -3. Next, they demonstrate how to set a rating for a video using a function named set rating. This function takes one parameter, which is a string that represents the rating. If the rating entered is invalid, the function will return a string representing the not rated rating. Lastly, the author demonstrates how to print out the rating for a video using a function named get rating. This function takes no parameters and simply returns the rating for the video.
- 03:55:00 In this C++ tutorial for beginners, the instructor demonstrates how to inherit functions and how to override them in a class hierarchy. This allows a class to have the same functionality as another class, while extending on that functionality with additional features.
C++ Tutorial for Beginners - Full Course
- 2018.08.24
- www.youtube.com
This course will give you a full introduction into all of the core concepts in C++. Want more from Mike? He's starting a coding RPG/Bootcamp - https://simula...
Introduction to Programming and Computer Science - Full Course
Introduction to Programming and Computer Science - Full Course
This video is a beginner's guide to programming and computer science for those with little to no background in coding. It covers fundamental concepts and techniques that apply to any programming language. The video explains the basics of writing code in an integrated development environment (IDE) and emphasizes the importance of programming grammar.
Topics covered in the video include:
- Introduction to programming and computer science, including syntax and programming rules.
- Using the console to output text from a program.
- Basic mathematics operations and the modulus operator in programming.
- Printing strings to the console.
- Understanding variables, data types, and naming conventions.
- How variables are defined, referenced, and manipulated in programs.
- Exploring if statements, elsif statements, and else statements for conditional execution.
- Introducing arrays as a way to store related variables.
- Basics of loops, including for loops, while loops, and do-while loops.
- Understanding different types of programming errors: syntax errors, runtime errors, and logic errors.
- Debugging techniques, such as using print statements, breakpoints, and comments.
- Strategies for avoiding errors in programming.
- Working with functions to organize code and reduce repetition.
- Importing functions from libraries and naming conventions for functions.
- Different types of functions and their purposes.
- Introduction to dictionaries as a flexible data storage option.
- Overview of searching algorithms, including linear search and binary search.
- Recursive programming and its use cases, including the base case concept.
- Soft skills for computer science, such as problem-solving and planning.
- Using pseudocode as a planning tool for writing code.
- Different methods for planning and writing code, including flowcharts and chronological planning.
- Overview of programming languages and available resources for learning.
The video provides a comprehensive introduction to programming and computer science, offering viewers the necessary foundation to begin their coding journey. It also suggests additional resources and websites to further explore the topic.
- 00:00:00 This video covers the main points of the video, which is meant for those who are interested in computer science and programming but have no idea where to start and have little to no background information on coding. The video covers the basics of computer programming, which can be applied to any and all programming languages you might want to learn.
- 00:05:00 This video discusses the basics of programming, how to write code in an integrated development environment (IDEs), and the importance of programming grammar.
- 00:10:00 This video introduces programming and computer science, and covers the basics of syntax and programming rules. The main use of the console is to output text from the program.
- 00:15:00 This video covers basic mathematics, including arithmetic, addition, subtraction, multiplication, and division, as well as modulus, a basic operator in many programming languages. It also covers printing strings to the console.
- 00:20:00 This video introduces programming and computer science concepts, including variables, types, and names. Primitive variables include integers, Booleans, floats, and doubles. String variables store strings of characters. Char variables hold one character. Variables are essential for storing information in a format that can be easily referenced.
- 00:25:00 This video discusses what happens when we define or create variables, how to reference them, and how to manipulate them for our programs. The main points to take away are that variables are simply spaces in memory that store a certain value, and that we can update the numbers and their place will remain constant throughout the code.
- 00:30:00 A variable is a place where you can store information while programming. Naming conventions for variables are important for readability. If a condition in an if statement is true, the code within the curly braces will run. There are two additional statements, elsif and eltons, that work similarly to if statements. If the condition in elsif is true, the code following elsif will run. Otherwise, the code following elsif
will be skipped. If the condition in elsif is not true, the code following elsif will be skipped and the code following the if statement will run. - 00:35:00 An array is a list of variables that are related to each other. They are useful when a programmer wants to store a lot of variables containing information that is all related to each other.
- 00:40:00 An introduction to programming and computer science course covers arrays, indexes, size, and arrays inside of arrays. Loops are also covered.
- 00:45:00 This video covers the different types of loops, for, while, and do while loops. It explains how to set up a condition for a loop and how to avoid an infinite loop.
- 00:50:00 This video covers the three types of errors that can occur during programming: syntax errors, runtime errors, and logic errors. Syntax errors are the easiest to fix, since they are usually something that can be fixed within seconds. Runtime errors are caused by statements in your code that seem logically sound but the computer physically has no way of completing the task in a reasonable amount of time. Logic errors are the most furying and difficult to debug, as they can often lead to programs not working as intended. To debug your code, you should test it incrementally and look for syntax and runtime errors.
- 00:55:00 If you're encountering an error in your code, you can use print statements and the console to determine where the code is going wrong, use breakpoints to track down the cause of the error, and use comments to mark out code that is meant for you and not the computer. Finally, strategies for avoiding errors are discussed.
- 01:00:00 In this video, the instructor covers the basics of programming and computer science, including errors and functions. He goes on to explain how arguments work in a function and how to use functions to reduce repetition in code.
- 01:05:00 This video introduction to programming and computer science discusses the four different types of functions, their purposes, and how to use them in your code. Functions can be helpful for organizing code, saving time, and making large changes to code without having to go through the entire program.
- 01:10:00 In this video, the basics of programming and computer science are introduced. Importing functions from libraries is explained, and rules for naming functions are discussed. Rules for creating functions based on type and number of arguments are also introduced.
- 01:15:00 In this video, the instructor explains the basics of programming and computer science, including functions, scope, and argument passing. He also covers how to create functions that do not return any values.
- 01:20:00 In this video, the presenter reviews arrays, functions, and dictionaries. Arrays are like lists of values that are stored together, and functions return a variable depending on the path taken. One small detail to note is that you can't return one type of variable if you've already defined the function to return another type. Array lists grow themselves when the size of the list exceeds 10 elements, and dictionaries store multiple values.
- 01:25:00 A computer stores data in different ways, which can be difficult to understand. A dictionary is a type of data storage, which is more fluid and easier to organize than traditional arrays. Searching algorithms are used to quickly find a specific piece of data in a list of values.
- 01:30:00 This video introduces the concept of searching algorithms and their efficiency. Linear search is a good basic algorithm for unsorted lists, but is inefficient in the worst case scenario. Binary search is an efficient search algorithm for sorted lists, taking advantage of the fact that the list is sorted.
- 01:35:00 The binary search algorithm is faster and more efficient than a linear search for finding an item in a sorted list. The recursive function is an example of a recursive programming statement. The base case for a recursive statement is a definite value that all recursive statements must meet. If n is not less than or equal to one, the recursive statement will return the sum of n and then the returning value of the recursive sum method minus one.
- 01:40:00 This video introduces programming and computer science and explains why recursion is a useful technique. The soft skills needed for computer science include problem solving and planning. Pseudocode is a simplified form of programming that can help with this planning.
- 01:45:00 Pseudocode is a visual way of planning out computer code, similar to constructing an outline for a paper. Flowcharts and writing out what you want the program to do chronologically are two common methods.
- 01:50:00 This video introduces programming and computer science concepts, including the different methods for planning and writing code, and the importance of pseudocode. It also covers different programming languages and their uses.
- 01:55:00 In this series, the author covers the basics of programming, which include syntax and rules, and teaches how to learn a specific language. He also provides websites and resources to help you get started.
Introduction to Programming and Computer Science - Full Course
- 2020.04.21
- www.youtube.com
In this course, you will learn basics of computer programming and computer science. The concepts you learn apply to any and all programming languages and wil...
C++ Programming Course - Beginner to Advanced
C++ Programming Course - Beginner to Advanced
The course covers different aspects of C++ programming.
The topics covered:
-
Setting up a C++ development environment: The videos provide an overview of how to set up a C++ development environment on various platforms. This includes installing different compilers and configuring Visual Studio Code to use the compilers and the C++ standard library. The instructions cover platforms like Windows, Mac, and Linux.
-
Basics of programming in C++: The videos cover fundamental concepts such as variables, data types, functions, and flow control statements. They explain how to declare variables, define functions, and use control structures like loops and conditional statements. The videos also introduce concepts like comments and the main function in C++.
-
String manipulation: Specific videos focus on working with strings in C++. They explain how to compare and concatenate strings using functions like strcmp and strcat. The videos also demonstrate how to copy strings using the strcpy function.
-
Arrays: The videos introduce the concept of arrays in C++. They cover topics like declaring and initializing arrays, accessing elements using pointers, and printing character arrays.
-
Dynamic memory allocation and pointers: These videos explain how memory is managed in C++ and how to use dynamic memory allocation techniques to allocate additional memory for a program. They cover the concepts of pointers, memory maps, and memory management units. The videos also discuss how to safely use pointers, avoid crashes, and handle multiple pointers pointing to the same memory location.
-
Function templates and lambda functions: The videos explain how to create generic functions using function templates in C++. They demonstrate how the compiler can generate function definitions based on the types of parameters passed in. Additionally, the videos cover lambda functions, which are anonymous functions that can be called without giving them a name. They explain the syntax and return type specification for lambda functions.
-
Classes and inheritance: These videos introduce the concept of classes in C++ and explain how to define member variables and functions within a class. They cover topics like constructors, destructors, access specifiers (protected and private), and the use of static and dynamic binding to achieve polymorphism. The videos also demonstrate how to create and use derived classes based on pre-existing classes using inheritance.
-
Debugging and error handling: The videos provide guidance on debugging C++ programs. They explain how to set breakpoints, examine variables in local scope, and handle errors related to uninitialized pointers and memory leaks. The videos also cover concepts like object slicing and overriding base class constructors.
-
Interfaces and polymorphism: Some videos focus on interfaces and polymorphism in C++. They explain how to use dynamic binding, references, and the override keyword to achieve polymorphic behavior in programs. The videos also discuss the final specifier, which can be used to mark a virtual method as final and prevent it from being overridden in derived classes.
-
Other topics: Additional topics covered include default parameters, stream insertable interface for automatic output stream printing, and utilizing interfaces to create more readable code.
The video provide step-by-step instructions, demonstrations, and explanations to help beginners learn C++ programming from installation and configuration to more advanced concepts like object-oriented programming, memory management, and polymorphism. The content is suitable for both beginners who want to learn the basics of C++ programming and experienced programmers who want to refresh their skills or explore specific topics in depth.
Code: https://github.com/rutura/The-C-20-Masterclass-Source-Code
Chapter 1: Setting up the tools
- 00:04:32 C++ Dev Tools
- 00:11:06 Installing C++ Compilers On Windows
- 00:24:27 Installing VS Code On Windows
- 00:28:00 Configuring Visual Studio Code For C++ On Windows
- 00:57:27 Installing C++ Compilers On Linux
- 01:04:02 Installing Visual Studio Code On Linux
- 01:07:40 Configuring Visual Studio Code For C++ On Linux
- 01:22:45 Installing C++ Compilers On MacOS
- 01:28:07 Installing Visual Studio Code On MacOS
- 01:30:16 Configuring Visual Studio Code For C++ On MacOS
- 01:35:37 Online Compilers
Chapter 2: Diving In
- 01:43:01 Your First C++ Program
- 01:55:56 Comments
- 02:01:56 Errors And Warnings
- 02:13:12 Statements And Functions
- 02:31:34 Input Output
- 02:49:57 C++ Program Execution Model & Memory Model
- 02:56:42 C++ Core Language VS Standard Library VS STL
Chapter 3: Variables And Data Types
- 03:00:47 Variables And Data Types Introduction
- 03:05:05 Number Systems
- 03:21:52 Integers
- 03:40:44 Integer Modifiers
- 03:54:00 Fractional Numbers
- 04:16:39 Booleans
- 04:24:49 Characters And Text
- 04:32:05 Auto
- 04:38:06 Assignments
- 04:45:42 Variables And Data Types Summary
- 04:46:45 Operations On Data Introduction
- 04:47:31 Basic Operations
- 04:58:01 Precedence and Associativity
- 05:12:06 Prefix And Postfix + & -
- 05:23:22 Compound Operators
- 05:31:43 Relational Operators: Comparing Stuff
- 05:40:51 Logical Operators
- 05:56:09 Output formatting
- 06:33:26 Numeric Limits
- 06:41:10 Math Functions
- 06:54:23 Weird Integral Types
- 06:59:41 Operations On Data Summary
- 07:01:58 Flow Control: Conditional Programming Introduction
- 07:03:30 If Statement
- 07:20:49 Else If
- 07:28:46 Switch
- 07:42:44 Ternary Operator
- 07:52:20 Flow Control: Conditional Programming Summary Chapter 6: Loops
- 07:53:49 Loops Introduction
- 07:55:20 For Loop
- 08:25:20 While Loop
- 08:36:54 Do While Loop
- 08:47:08 Arrays Introduction
- 08:48:45 Declaring And Using Arrays
- 09:15:53 Size Of An Array
- 09:26:44 Arrays Of Characters
- 09:46:46 Bounds Of An Array
- 09:53:23 Pointers Introduction
- 09:56:03 Declaring And Using Pointers
- 10:14:48 Pointer To Char
- 10:27:26 Program Memory Map
- 10:36:30 Dynamic Memory Allocation
- 11:05:45 Dangling Pointers
- 11:24:15 When New Fails
- 11:38:00 Null Pointer Safety
- 11:45:18 Memory Leaks
- 11:55:44 Dynamic Arrays
- 12:11:04 References Introduction
- 12:11:58 Declaring And Using References
- 12:22:28 Comparing References To Pointers
- 12:37:25 References And Const
Chapter 10: Character Manipulation And Strings
- 12:44:29 Character Manipulation And Strings Introduction
- 12:46:24 Character Manipulation
- 13:09:28 C-String Manipulation
- 13:41:42 C-String Concatenation And Copying
- 14:01:19 Introducing std::string
- 14:03:38 Declaring And Using std::string
- 14:12:47 One Definition Rule
- 14:28:25 First Hand On Functions
- 15:00:50 Function Declaration & Definition
- 15:15:30 Functions Across Multiple Files - Compilation Model Revisited
- 15:42:30 Pass By Value
- 15:50:30 Pass By Pointer
- 15:57:46 Pass By Reference
Chapter 12: Getting Things Out Of Functions
- 16:03:20 Getting Things Out Of Functions Introduction
- 16:03:58 Input And Output Parameters
- 16:17:54 Returning From Functions
Chapter 13: Function Overloading
- 16:49:00 Lambda Functions Introduction
- 16:49:38 Declaring And Using Lambda Functions
- 17:20:25 Capture Lists
- 17:34:24 Capture All In Context
Chapter 15: Function Templates
- 17:40:08 Function Templates Introduction
- 17:41:45 Trying Out Function Templates
- 18:19:52 Template Type Deduction And Explicit Arguments
- 18:35:47 Template Type Parameters By Reference
- 18:48:55 Template Specialization
Chapter 16: Concepts
- 19:04:31 Concepts Introduction
- 19:06:47 Concepts
- 19:25:32 Concepts: Building Your Own
- 19:42:45 Requires Clause: Zooming In
- 19:59:53 Logical Combinations Of Concepts
- 20:09:39 Concepts And Auto
Chapter 17: Classes
- 20:15:40 Classes Introduction
- 20:16:33 Your First C++ Class
- 20:38:03 Constructors
- 20:53:35 Defaulted Constructors
- 20:59:42 Setters And Getters
- 21:10:06 Class Across Multiple Files
- 21:30:49 Managing Class Objects Through Pointers
- 21:42:48 Destructors
- 22:05:44 Constructor & Destructor Call Order
- 22:11:03 The This Pointer
- 22:33:33 Struct
- 22:42:37 Size Of Class Objects
Chapter 18: Inheritance
- 22:52:43 Inheritance Introduction
- 22:55:59 Your First Try On Inheritance
- 23:21:10 Protected Members
- 23:32:06 Base Class Access Specifiers: Zooming In
- 23:36:49 Base Class Access Specifiers: A Demo
- 24:07:42 Closing In On Private Inheritance
- 24:26:36 Resurrecting Members Back In Scope
- 24:46:59 Default Arg Constructors With Inheritance
- 24:57:37 Custom Constructors With Inheritance
- 25:26:56 Copy Constructors With Inheritance
- 25:51:53 Inheriting Base Constructors
- 26:06:00 Inheritance With Destructors
- 26:12:20 Reused Symbols In Inheritance
Chapter 19: Polymorphism
- 26:21:03 Polymorphism Introduction
- 26:26:54 Static Binding With Inheritance
- 26:55:24 Polymorphism (Dynamic Binding) With Virtual Functions
- 27:14:31 Size Of Polymorphic Objects And Slicing
- 27:26:37 Polymorphic Objects Stored In Collections
- 27:45:42 Override
- 27:52:45 Overloading, Overriding And Hiding
- 28:07:35 Inheritance And Polymorphism At Different Levels
- 28:33:03 Inheritance And Polymorphism With Static Members
- 28:49:13 Final
- 29:07:42 Virtual Functions With Default Arguments
- 29:23:18 Virtual Destructors
- 29:35:38 Dynamic_cast<>()
- 30:08:17 Don't Call Virtual (Polymorphic) Functions From Constructors & Destructors
- 30:24:45 Pure Virtual Functions And Abstract Classes
- 30:43:37 Abstract Classes As Interfaces
GitHub - rutura/The-C-20-Masterclass-Source-Code: Source code for the C++ 20 Masterclass on udemy
- rutura
- github.com
Source code for the C++ 20 Masterclass on udemy . Contribute to rutura/The-C-20-Masterclass-Source-Code development by creating an account on GitHub.
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer (parts 1-4)
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer
Brief summary:
00:00:00 - 01:00:00 The instructor explains data structures and their importance in creating faster and more powerful algorithms. The tutorial covers Big O notation and how it's used to standardize how much time and space an algorithm requires, and concrete examples are provided for different time complexities. The tutorial also covers the implementation of static and dynamic arrays, including their advantages and disadvantages, and delves into creating and inserting nodes in singly and doubly linked lists. Finally, the tutorial provides an introduction to the stack data structure and briefly explains its primary operations.
01:00:00 - 02:00:00 This section of the "Data Structures Easy to Advanced Course" tutorial provides comprehensive coverage of various data structures and their functionalities. The tutorial guides the audience on the working principles of stacks and queues, their implementations using arrays and linked lists, and their importance in different applications, including graph traversal and managing server requests. The tutorial also explores priority queues and their implementation using heaps, clarifying the difference between priority queues and heaps as well as the types of heaps. The tutorial ends by providing a step-by-step demonstration of how to add and remove elements from a binary heap.
02:00:00 - 03:00:00 The Google Engineer presents a full tutorial on data structures, explaining how to remove nodes from a binary heap data structure, how to maintain the heap invariant in a priority queue, and how to swim and sink nodes in a binary heap data structure. The video also covers the union find data structure, which is used to track elements divided into disjoint sets and to merge two groups together, with an example about magnets to illustrate how the data structure works. Additionally, Kruskal's algorithm for finding a minimum spanning tree in a graph is explained, and the concept of path compression is introduced to make the union find data structure more efficient.
03:00:00 - 04:00:00 This tutorial covers various data structures, starting with the union-find data structure and its methods, including find, connected, parent, size, and unify. The tutorial then moves on to trees, including definitions for trees, rooted trees, binary trees, and binary search trees. The video provides examples of inserting and removing nodes from binary search trees, as well as different traversal algorithms, including pre-order, in-order, post-order, and level order, and explains how to implement these constructs in Python and Java. Additionally, the video introduces hash tables and discusses the importance of hash functions and popular collision resolution methods.
04:00:00 - 05:00:00 The section covers various aspects of hash tables and their implementation. It discusses the importance of hash functions, which map keys to values, and how to handle hash collisions using techniques such as separate chaining and open addressing. The tutorial also covers methods for inserting, removing, and searching for entries in hash tables, as well as resizing and managing load factors. The speaker emphasizes the importance of choosing an appropriate probing function and table size to avoid infinite loops and performance issues. Practical examples are used throughout the tutorial to illustrate the concepts.
05:00:00 - 06:00:00 This section provides a comprehensive overview of hash tables, double hashing, and quadratic probing in collision resolution. The video covers the concepts of resizing and growing a hash table, handling collisions and deletion, and implementing hash tables using quadratic probing. The video also introduces the Fenwick tree, a data structure that supports range queries and point updates in logarithmic time with linear construction time. The video provides a step-by-step explanation of how to perform prefix sums and range queries using the Fenwick tree.
06:00:00 - 07:00:00 The video tutorial covers various topics, including the concept of a Fenwick tree for quick range queries and point updates, using suffix arrays and LCP array for finding unique substrings and longest common substrings, and solving the longest common substring problem using a sliding window technique. The tutorial also explains how to find the longest repeated substring efficiently using the LCP array and explores the properties and importance of balanced binary search trees, specifically AVL trees, and how they can be kept balanced by using tree rotations. The video provides detailed explanations, examples, and source code in Java available on GitHub.
Part 1
- 00:00:00 The speaker introduces the concept of data structures as a way of organizing data efficiently and how they are essential in creating faster and more powerful algorithms. The speaker talks about the importance of understanding how and when to use the appropriate data structure for the task at hand and how data structures can make code cleaner and easier to understand. The concept of abstract data type is also explained along with examples of how an abstract data type provides only the interface and not the specific details on how the data structure should be implemented. Additionally, the video briefly touches on computational complexity in order to understand the performance of data structures.
- 00:05:00 The concept of Big O notation is introduced as a way of standardizing how much time and space is required for an algorithm to run based on the worst possible arrangement of input. Big O only cares about what happens when inputs become really large and removes constant values added to big O notation. The concept of a function f is also introduced, and it's stated Big O of f of n is just n cubed, which is the biggest, most dominant term in that function.
- 00:10:00 The Google Engineer provides concrete examples of how Big O notation is used. The examples are categorized based on their time complexities—constant time, linear time, quadratic time, logarithmic time. He also provides a step-by-step breakdown of how a logarithmic time complexity is achieved using the example of binary search. Additionally, he demonstrates how to calculate the time complexity of a more complicated algorithm and explains the rule for determining an algorithm's complexity.
- 00:15:00 The speaker discusses the complexity analysis of a nested loop with an outer loop and an inner loop. The inner loop has a constant amount of work and the outer loop has a variable amount of work. The big O of the function is O(n^4) as n^3 is the dominant term. The speaker then introduces static arrays, which are a fixed-length container containing indexable elements that are contiguous chunks of memory. Static arrays are used everywhere, from temporarily storing objects to storing information from an input or output stream. The speaker outlines the basic structure of an array, common operations that can be performed on them, and their complexity analysis.
- 00:20:00 The instructor discusses the use of arrays in programming, including as a workaround for languages that only allow one return value and in dynamic programming. He explains that arrays have constant access time due to their indexable property, but searching may take up to linear time in the worst-case scenario. Insertion, appending, and deletion from a static array are not feasible, but with a dynamic array, resizing the internal array for appending results in a rare but constant time operation. Finally, he notes that elements can be iterated over using a for-each loop, and that array indexing in computer science starts at zero, which can be confusing for some beginners.
- 00:25:00 The video discusses the concept of indexing in arrays, where a square bracket denotes indexing, and how dynamic arrays can grow and shrink as needed, allowing for similar get set operations as static arrays. To implement a dynamic array, a static array is used, and when capacity is exceeded, the array size is doubled, and all elements are copied into the new static array. The video also shows the source code for the array class, which supports generics of type T and has instance variables for the internal static array, length, and capacity.
- 00:30:00 The instructor goes through the implementation of several methods for a dynamic array, including size, inset, clear, add, remove, index of, contains, and toString. The add method involves resizing the array by doubling its size when the capacity is reached, and the remove method uses two indices to copy all elements of the array except for the removal index. The instructor also demonstrates how to create an iterator for the dynamic array and talks about the benefits of using an iterator for iterating over the elements of an array. Overall, the tutorial provides a simple yet comprehensive introduction to implementing dynamic arrays.
- 00:35:00 The instructor provides an introduction to singly and doubly linked lists, explaining that they are a sequential list of nodes that hold data and point to other nodes containing data. Linked lists are used in the implementation of lists, stacks, and queues, as well as circular lists, hash table separate chaining, and for adjacency lists and graphs. The instructor also covers some useful terminology for creating linked lists. Additionally, the advantages and disadvantages of singly and doubly linked lists are discussed, with singly linked lists being more memory efficient but lacking the ability to access previous elements, while doubly linked lists can be traversed backwards and allow for easy removal of a node.
- 00:40:00 The instructor explains the implementation details of creating and inserting nodes in a singly linked list and a doubly linked list. To insert a node in a singly linked list, a new pointer is created, and the traverser pointer is advanced to the desired position, following which the new node is created and linked to the other nodes. On the other hand, a doubly linked list has both next and previous pointers, and when inserting a new node, both pointers of the adjacent nodes and the new node need to be updated. Removing a node from a singly linked list involves using two pointers to advance to and remove the desired node, and then deallocating its memory later.
- 00:45:00 The speaker covers how to remove nodes from a doubly linked list, which is easier than removing nodes from a singly linked list since we don't have to manually maintain references to the last node. The speaker shows an implementation in Java and discusses the complexity of various operations in linked lists, such as searching and removing elements from the head or tail. While searching in a linked list is linear in the worst case scenario, inserting to the head or removing the head is constant time. Removing from the tail takes linear time in a singly linked list, but not in a doubly linked list because it has a reference to the previous node.
- 00:50:00 In this section of the video, the presenter explains the implementation of a doubly linked list with methods to clear the list, get size and check if empty, and add nodes to the beginning and end of the list. He also explains how to peek at the first or last element of the list, remove the first or last element, and remove an arbitrary node in the middle of the list. The presenter emphasizes the importance of deallocating memory properly, and sets the node class as private to prevent users from accessing it directly.
- 00:55:00 In this section of the video, the tutor explains how to remove a node of a particular index from a linked list, even though the nodes are not explicitly indexed. The Remove method supports removing an arbitrary value from the linked list and searching for null values. The tutor also explains the index of method for getting the index of an object within a linked list and the iterator method. Lastly, the tutor introduces the stack data structure and briefly provides an overview of its primary operations, push and pop. The tutor also highlights that the upcoming videos in the series will cover stack implementation, problems solved using stacks, and the time complexity associated with stack operations.
Part 2
- 01:00:00 The video discusses how a stack data structure functions and its various uses in programming. The video provides a detailed example of how operations are added and removed from a stack and explains how stacks are used in text editors, compilers, and supporting recursion. Additionally, the video highlights how a stack can be used to perform a depth-first search on a graph and presents a cool example problem of how to determine whether a bracket sequence is valid or not using a stack. Lastly, the video includes a complexity analysis of stacks and how they function as a linked list.
- 01:05:00 The Google engineer demonstrates how to check if a bracket sequence is valid using a stack data structure. He goes through the algorithm step-by-step, pushing left brackets onto the stack and popping them off when encountering right brackets, and checks if they match. He also explains how the Tower of Hanoi game can be related to stacks, as each peg represents a stack and the discs represent elements that can only be moved under certain conditions. Finally, he discusses how stacks can be implemented using arrays or linked lists.
- 01:10:00 We learn about creating a stack using a singly linked list and popping elements off of the stack in a simple implementation of a stack data structure in the Java programming language. The stack is created by pointing the head to a null node which means that the stack is empty. New elements are inserted before the head, and popping elements is done by moving the head pointer to the next node and deallocating the last node. Memory leaks in data structures can cause problems, so it is important to watch out for them in all data structures, and to correct them when necessary.
- 01:15:00 The instructor discusses queues, a linear data structure used to model a real-world queue with two primary operations: enqueuing and dequeuing. The front and the back of the queue are used to insert and remove elements, respectively. The instructor also explains the various terminologies surrounding queues, with enqueuing sometimes referred to as adding, and dequeuing as polling or removing from the front of the queue. A classic example of a queue is a line at a movie theater or restaurant, and queues can be useful for keeping track of the x most recent elements in a sequence.
- 01:20:00 The video explains how queues are used to manage server requests and to conduct a breadth first search traversal on a graph. The concept of queuing requests is introduced, where an idle server can only handle a certain number of requests at a time and any excess requests are put into a queue. The video also covers the basics of breadth first search, in which nodes of a graph are visited in order of their distance from a starting node. The video concludes by explaining the implementation of n-queuing and dequeuing elements using a queue data structure.
- 01:25:00 The tutorial delves into queues and explains how the queue abstract data type can be implemented using either arrays or different kinds of linked lists - singly linked lists and doubly linked lists. The tutorial provides an example of how the singly linked list implementation of a queue can work and also discusses the implementation of various queue methods like peak, poll, and offer using Java programming language. The tutorial also shares a link to the source code of the queue implementation on github.com.
- 01:30:00 In this section of the tutorial, the Google Engineer explains the concept and implementation of data structures, specifically queues and priority queues. He discusses how a priority queue operates similar to a normal queue with the only difference being that each element has a certain priority, and elements with a higher priority come out of the queue first. He also emphasizes that priority queues only support comparable elements, meaning that the data we insert into the priority queue must be ordered. Furthermore, he provides an example to explain the operations of polling and adding elements into a priority queue. In the next sections of the tutorial, he will go into more detail about the common operations performed on priority queues, turning min priority queues into max priority queues, complexity analysis, and ways of implementing priority queues.
- 01:35:00 The Google Engineer explains how priority queues are implemented using heaps. A heap is a tree-based data structure that satisfies the heap invariant, which means that the value of the parent node is always greater than or equal to the value of the child node for all nodes, resulting in two types of heaps: Max heaps and min heaps. Heaps are important as they form the canonical underlying data structure for priority queues. The Google Engineer then shows examples of structures and asks the audience if they are heaps or not, demonstrating that all heaps must be trees and satisfy the heap invariant.
- 01:40:00 The importance of priority queues in algorithms such as Dijkstra's shortest path algorithm and Huffman encoding is discussed. Priority queues are useful in situations where there is a need to dynamically fetch the next best or worst element. The main focus is on priority queues implemented as binary heaps, and the operations, including adding an element, removing an element, checking containment, and changing min priority queues to max priority queues. Hash tables can be used to improve the removing time complexity to be logarithmic, while a linear scan is performed for all the elements for the naive method. The section concludes with a hack to convert min priority queues to max priority queues.
- 01:45:00 The Google engineer explains how to use negation as a simple way to implement reverse heaps in priority queues. He provides examples of both numerical and string manipulation using a min priority queue with the standard lexicographic comparator as well as a negated comparator. The engineer also introduces the concept of binary heaps and how to add elements to them.
- 01:50:00 The instructor explains the important terminology and concepts necessary for understanding how to add elements effectively to a priority queue using a binary heap. He clarifies that a priority queue is not a heap but an abstract data type that defines the behavior a priority queue should have, and that heaps are just the data structure that lets us actually implement that behavior. He also discusses the types of heaps, including binary heaps, and explains the complete binary tree property and how to represent a binary heap using an array construct.
- 01:55:00 The Google Engineer explains how to add nodes to a binary heap and maintain the heap invariant by using a technique to easily access a node's children and parent nodes. They illustrate with the example of inserting values into a min heap and demonstrate how to bubble up the nodes to satisfy the heap invariant. In the next section, the engineer covers removing elements from a binary heap and emphasizes the importance of removing the root value, which is the node of interest with the highest priority.
Part 3
- 02:00:00 The Google engineer explains the process of removing nodes from a binary heap data structure using the pull method. Pulling is done in two cases, when removing the root node and when removing a specific node. When removing the root node, the node is swapped with the last node in the array, and the heap invariant is ensured through bubbling down. When removing a specific node, the node is searched for linearly, swapped with the last node in the heap, and then the heap invariant is ensured through bubbling up or down depending on the value of the swapped node. The engineer concludes that pulling takes logarithmic time for the root node and linear time for a specific node.
- 02:05:00 In this section of the tutorial, the Google Engineer explains how to remove nodes in a heap with improved time complexity by making use of a hash table. Instead of doing a linear scan to find the index of the node to remove, each node is mapped to the index it is found at. When we want to remove a particular node, we just look up its index to start doing it. The video also covers how to deal with the problem of multiple values in the heap and how to keep track of the positions of the values in the tree. The Engineer explains that as long as we satisfy the heap invariant, it does not matter which node we remove. The tutorial includes examples of adding, pulling, and removing elements with the new scheme proposed.
- 02:10:00 The speaker explains how to insert, remove, and maintain the heap invariant in a priority queue using a heap data structure. Then he dives into the source code and highlights some important instance variables and constructors necessary for implementing the priority queue. He explains that the elements allowed in the priority queue must implement the comparable interface and that logging and removals can be tracked using a map that maps an element to a set of integers representing the positions of the element in the heap.
- 02:15:00 In this section of the tutorial, the Google Engineer discusses different ways to create a priority queue, including creating an initially empty queue with a set capacity, creating a queue with a defined initial capacity, and constructing a queue in linear time using the heapify operation. The engineer also goes over some simple methods of a priority queue, including empty, clear, size, peek, poll, and contains. The add method is also discussed, with details on how to add elements to the queue and the importance of keeping track of the elements in a map. The swim function is also highlighted as a necessary step after adding an element to the end of the list.
- 02:20:00 In this section of the video, the Google engineer explains the methods for swimming and sinking nodes in a binary heap data structure. The swimming method involves swapping nodes with its parent and moving upwards until the node is in the correct position based on its value. The sinking method is similar but involves comparing the node with its child nodes and swapping with the smaller one until it reaches the correct position. The engineer also explains the swap, remove, and remove add methods implemented in the binary heap. The remove add method involves swapping the removed node with the last element in the heap and sinking or swimming the new node to the appropriate position.
- 02:25:00 In this section of the tutorial, the instructor explains how to remove a node from a heap data structure and ensure that the minimum heap's integrity is maintained using a method to sink or swim nodes depending on whether the swap affects the heap's order. The section also introduces the union find data structure and its two primary operations, find and union, which are used to track elements divided into disjoint sets and to merge two groups together, respectively.
- 02:30:00 The speaker uses the example of magnets to explain how the union find data structure works. The union find efficiently merges items or groups of items, assigning them an arbitrary color. The union find data structure is used in various algorithms, such as the minimum spanning tree algorithm and grid percolation. The union find has excellent complexity, and its construction is linear time, while its count components function can determine the number of components in constant time, making it a great data structure to have around.
- 02:35:00 In this section of the tutorial, the Google engineer explains Kruskal's algorithm for finding a minimum spanning tree in a graph. The algorithm involves sorting edges by ascending edge weight and then unifying nodes that do not belong to the same group, until all vertices are unified into one group. The union find data structure is used to efficiently merge groups and prevent cycles. The engineer provides an example graph and walks through the steps of the algorithm to illustrate how it works.
- 02:40:00 The tutorial explains the union find data structure and how it works internally. The first step is to create a mapping between the objects and the integers in the range of zero to N non-inclusive, where N is the number of elements. Then an array is constructed, and each index has an associated object, which is done through the mapping. The value in the array's position is initially the index it's at, and each node is a root node mapping to itself. As instructions are performed to unify objects into groups, the values in the array have changed to map to other objects. Smaller components are merged into larger ones, and the root nodes are used to unify groups.
- 02:45:00 The speaker talks about how to merge elements into different groups using the union find data structure. By finding and following the parent nodes of each component's root node, we can determine which component an element belongs to. To unify two components, we make one of the root nodes point to the become the parent of the other root. The number of components is equal to the number of root nodes remaining, and the number of root nodes only decreases as we unify components. The speaker also notes that the implementation of this structure currently does not have an amortized time complexity without the use of path compression, an optimization to be discussed in the next video.
- 02:50:00 The concept of path compression is introduced to show how it makes the union find data structure more efficient. Path compression involves compressing all nodes along the path to the root node, thus allowing for constant time lookup of the root node for any given component. The example of unifying groups with and without path compression is given to compare and contrast the two methods, demonstrating the efficiency gained through path compression.
- 02:55:00 The instructor discusses how path compression and union find work together to create an efficient data structure. He demonstrates how path compression dynamically compresses paths along the way until reaching a final state. The union find code is presented in the video, with explanations of the use of arrays for indexing and tracking parent-child relationships. Additionally, the code includes methods to check for the root node and compress the path to it. The instructor emphasizes the importance of watching other videos on union find to gain a full understanding of the topic.
Part 4
- 03:00:00 The instructor introduces a union-find data structure and its methods, including find, connected, parent, size, and unify. He demonstrates how the root nodes of the structure contain the size of each connected component, and the unify method merges smaller groups into larger ones. Moving on to trees, the instructor gives a brief overview of trees as undirected graphs and introduces binary trees and binary search trees. He promises to cover how to insert and remove nodes in binary search trees, tree traversals, and how they can be applied to general trees in later tutorials.
- 03:05:00 The concept of trees is introduced, with multiple definitions provided. A tree can be defined as a non-directed graph that is connected and acyclic, as a graph with n nodes and n-1 edges, or as a graph where there is only one path between any two vertices. A rooted tree is introduced as well, where any node can become the root and child and parent nodes are defined. The parent of the root node is itself, and leaf nodes are defined as nodes with no children. The concept of a subtree is also introduced, denoted by triangles within a tree. Additionally, the definition of a binary tree is explained as a tree in which every node has at most two children.
- 03:10:00 The video covers binary search trees, which are binary trees that satisfy the binary search tree invariant. This means that the left subtree always has values smaller than the current node and the right subtree has larger values. The video presents various examples of binary search trees and challenges viewers to determine if they satisfy the invariant. Binary search trees are useful in many implementations of abstract data types and are used in balanced binary search trees and syntax trees. They also have a logarithmic time complexity in the average case for operations like insertion and search on random data.
- 03:15:00 In this section of the tutorial, the Google engineer discusses binary search trees and how to insert elements into them. Binary search trees have logarithmic behavior on average, which makes them easy to implement and efficient for most cases. However, in the worst case, a binary tree can become a linear data structure, which is not ideal. To insert an element in a binary search tree, the element must be comparable, and one of four cases may occur: recurse down the left subtree, recurse down the right subtree, handle duplicate values, or insert a new node. Finally, the engineer demonstrates inserting values into a binary search tree using animations.
- 03:20:00 The Google engineer explains the worst-case scenario when inserting values into a binary search tree, which causes it to become a linear structure. This behavior is undesirable because it slows down operations such as searching for nodes or deleting values. The engineer then explains how to remove elements from a binary search tree in two steps: first finding the node to remove, and then replacing it with its successor to maintain the binary search tree invariant. The video provides an example of how to search for values in a binary search tree to help understand the process.
- 03:25:00 The Google engineer explains the four cases of the Remove phase when dealing with a binary search tree. The first case is when the node to remove is a leaf node the second and third cases occur when there is only one subtree either to the left or to the right. The fourth case occurs when the node has both a left and right subtree, and the question is in which subtree will the successor of the node be? The answer is that the successor can be either the largest value in the left subtree or the smallest value in the right subtree, and there can be two possible successors.
- 03:30:00 In this section of the course, the instructor explains how to remove nodes from binary search trees using the concept of a successor node. The successor is either the smallest node in the right subtree or the largest node in the left subtree. The instructor demonstrates the removal of nodes through several examples, emphasizing the importance of rebalancing the tree after removal. The section concludes with an overview of different tree traversals, including pre-order, in-order, post-order, and level order.
- 03:35:00 The instructor explains the concepts of pre-order, in-order, and post-order traversals in binary trees. He explains that pre-order prints the current node's value followed by its left and right subtrees, and then provides an example of how pre-order traversal works in a binary tree, maintaining a call stack to keep track of which nodes are visited. Similarly, he explains how in-order traversal works, which involves traversing the left subtree, printing the value, and then traversing the right subtree. The instructor uses a binary search tree as an example and highlights the order in which the nodes are visited and printed during traversal.
- 03:40:00 The tutorial discusses different traversal algorithms for binary trees. First, the inorder traversal, which prints the values of the nodes in increasing order. Next, the post order traversal, which traverses the left subtree, then the right subtree, and only after both of those are traversed, prints the value of the node. The tutorial goes on to explain breadth first search and how it can be used for level order traversal, which prints the nodes one layer at a time. A queue is used to keep track of the nodes to be explored, and nodes are added to the queue as their parent nodes are visited.
- 03:45:00 In this section of the video, the instructor explains how to perform breadth-first search using a queue data structure. He demonstrates the process of exploring nodes and adding their children to the queue according to their order. He emphasizes the importance of using a queue instead of a stack when performing level-order traversal. The video then shifts focus to the implementation of a binary search tree in Java, with the instructor explaining the class structure, instance variables, and methods used to add elements to the tree. He also highlights the importance of choosing a comparable type when working with binary search trees.
- 03:50:00 The instructor explains the process of removing nodes from a binary search tree. They begin by discussing the public method for removing nodes and explaining that they will only remove the node if it exists within the tree, which is checked first. Then, they delve into the recursive method used to remove the node, which involves finding the node to be removed and then actually removing it based on whether it has left and/or right subtrees. The instructor explains three different cases for removal, which involve either a left or right subtree, or both a left and right subtree. They also provide helper methods for traversing the tree to find the successor node.
- 03:55:00 The Google engineer explains how to implement a binary search tree in Python, including inserting a new node, searching for a specific element, and calculating the height of the tree. He also shows how to implement binary tree traversals iteratively using a custom method called "traverse," which takes a tree traversal order as input and returns an iterator for that order. Next, he introduces hash tables and discusses the importance of hash functions, as well as popular collision resolution methods like separate chaining and open addressing.
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer
- 2019.09.19
- www.youtube.com
Learn and master the most common data structures in this full course from Google engineer William Fiset. This course teaches data structures to beginners usi...
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer (parts 5-8)
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer
Part 5
- 04:00:00 The instructor introduces the concept of hash tables and its implementation using hashing techniques. Hash tables are used to construct a mapping from keys to values, where each key is unique and is associated with a value. To map the keys to values, a hash function is used, which maps the keys to a whole number in some fixed range. The instructor shows how to define hash functions for arbitrary objects, such as strings, using the ASCII values of characters in the string. Hash tables are often used to track frequencies of values and construct mappings between key-value pairs, provided the keys are hashable. The section ends with a mini challenge to define a hash function for a database of people with three fields.
- 04:05:00 The instructor discusses hash functions and their properties. The hash function is defined arbitrarily and can have an infinite number of possibilities. The instructor emphasizes that hash functions must be deterministic to avoid screwing up the hash table. The uniformity of hash functions is also important to minimize hash collisions which occur when two objects hash to the same value. The instructor also illustrates how hash values can speed up object comparisons, and goes on to explain that sophisticated hash functions such as cryptographic hash functions and checksums are used for files instead of the hash functions used for hash tables.
- 04:10:00 The tutorial explains what makes a key of type 't' hashable and how a hash table works using a uniform hash function to index into it. It mentions that hash functions need to be deterministic and enforce immutable keys that are fixed and constant, such as immutable strings and integers. By using the hash function as a way to index into a hash table, we can achieve quick insertion, look-up, and removal times in constant time. The tutorial also provides an example of inserting key-value pairs into a table that eventually leads to a hash collision and explains how to handle collisions.
- 04:15:00 The speaker discusses hash collision resolution techniques, specifically separate chaining. Separate chaining is a way of dealing with hash collisions by maintaining an auxiliary data structure, usually a linked list, to hold all the different key-value pairs which hash to a specific value. The time complexity of a hash table can achieve constant time insertion, removal, and search on average, but with a terrible hash function that's not uniform, it could be linear time. The speaker also provides an example of how separate chaining works and how we can use it to handle collisions within our hash table by maintaining a linked list data structure for each index in the array.
- 04:20:00 The speaker explains how lookups work in a hash table with separate chaining, which uses linked lists to handle collisions. With a given key, the speaker demonstrates how to find the corresponding value by hashing the key and searching the linked list in the corresponding bucket of the hash table. The speaker also addresses some common questions about maintaining constant time complexity, removing key-value pairs, and using different data structures to handle buckets in the hash table. Finally, the speaker shares some source code for a hash table implementation using separate chaining.
- 04:25:00 The video introduces hash tables and how they are implemented in Java. The entry class is first discussed, with a focus on generics, hash codes, and equals method. The hash table itself is then explained including instance variables like maximum load factor, capacity, threshold and the table itself, which is an array of linked lists. Various methods such as size, empty, clear, contains key, and hash are also discussed along with their implementation details. Finally, the normalized index method is explained, which is used to convert a hash value into an index for lookup in the hash table.
- 04:30:00 In this section of the video, the speaker explains the methods involved in implementing a hash table such as insert, get, remove, seek entry, and resize table. The insert method adds a new entry to the hash table or updates an existing one, while get retrieves the value associated with a specific key. Remove removes the key value pair from the hash table, and seek entry method helps in finding the entry at a given bucket index. Lastly, resize table resizes the table by doubling its capacity and then creates a new table with the new capacity, moves the data from the old table to the new table, and removes the old data.
- 04:35:00 The instructor discusses the open addressing technique for resolving collisions in hash tables. This method stores the key-value pairs in the table itself instead of an auxiliary data structure. Therefore, it is crucial to manage the size of the hash table and the number of elements in it. The load factor, which is the ratio of items to the size of the table, needs to be kept below a certain threshold to prevent it from becoming exponentially bad. When inserting a new key, the hash function gives an original position for the key, but if there is a collision, a probing sequence is used to find the next open spot. The linear probing sequence is one of many to choose from.
- 04:40:00 The instructor discusses open addressing, a method of handling collisions in hash tables where the item is placed in a different location when the original hash index is already occupied. Various probing functions are introduced, such as linear probing, quadratic probing, double hashing, and pseudo random number generator probing function, each of which uses a different mathematical formula to find the next slot. However, the main difficulty with open addressing is the potential for producing cycles that are shorter than the size of the hash table, which can lead to an infinite loop. A practical example is given to illustrate this problem.
- 04:45:00 The speaker discusses the issue of cycles in probing functions used in hash tables and how to handle it. The speaker explains that techniques such as linear probing, quadratic probing, and double hashing are all subject to this issue of cycles but can be redefined to produce a cycle of length to avoid being stuck in an infinite loop while inserting an element. The constant "b" in linear probing is considered obsolete, and the speaker mentions that some linear functions may be unable to produce a full cycle of order "n." The solution to this problem is to choose probing functions that produce a cycle of exactly "n" by making sure that the constant "a" and the table size "n" are relatively prime to each other.
- 04:50:00 The instructor discusses hash tables and how they work, including probing functions, table size, load factor, and resizing. He uses an example with linear probing to demonstrate how to insert key value pairs into a hash table and avoid infinite loops caused by hash collisions. However, he points out that the choice of probing function and table size can significantly impact performance, and selecting a function whose greatest common denominator with the table size is not one can lead to cycles and cause problems.
- 04:55:00 We see an example of using a probing function to insert key-value pairs into a hash table without any collisions. If a collision does occur, the probing function will keep probing until an empty spot is found to avoid any cycle occurring. Once the number of elements exceeds the table's threshold, the table size is doubled while maintaining the GCD of N. The old elements are then placed in the new table using the new table size while keeping the same probing function. Finally, a new key-value pair is inserted, and if the spot is free, there are no issues.
Part 6
- 05:00:00 The instructor discusses quadratic probing in hash tables, which is used to address collisions in open addressing. This involves probing according to a quadratic formula using a selecting a random probing function. The instructor explains that not all quadratic functions are viable because they don't produce a cycle of order which results in getting stuck in an infinite loop, but most randomly selected quadratic functions will end up producing a cycle. The instructor provides three most popular ways to select a probing function, and focuses on the second one where p of x equals x squared plus x divided by two and the table size is a power of two.
- 05:05:00 The speaker discusses the process of inserting elements into hash tables using the double hashing and open addressing collision resolution technique. They explain the importance of the table size being a power of two and how to handle collisions using probing. The speaker also demonstrates the process of resizing the table when the load factor exceeds a certain threshold. They go on to discuss how to update existing elements and how to insert new ones into the table.
- 05:10:00 The instructor explains the concept of double hashing, which is a probing method used to handle collisions in hash tables. The double hashing scheme involves probing according to a constant multiple of another hash function, called the secondary hash function. The instructor warns about the issue of infinite cycles that can occur in the case of double hashing and provides a strategy to fix it, which involves picking a prime number for the table size and constructing a value called delta. He also discusses the systematic way of generating new hash functions for different data types using the same fundamental building block.
- 05:15:00 The speaker explains the concept of hash functions and how they can be combined to create a new hash function. They mention the use of Universal hash functions and provide an example using double hashing. They discuss the process of inserting key-value pairs into a hash table while also handling hash collisions and updates. The example uses a table size of seven and a max load factor of 0.75, and the hashing function uses integers and real numbers as building blocks.
- 05:20:00 The tutorial explains the process of resizing and growing a hash table with double hashing, which involves doubling the table size, finding the next prime number above that value, allocating a new table, and inserting the old elements into the new table. The tutorial provides an example where the original table has reached its maximum threshold after inserting five elements, and the table is resized to a new size of 17. The tutorial also explores the issues that arise when removing elements from a hash table using the open addressing scheme, and the importance of avoiding collisions during insertion and deletion operations.
- 05:25:00 The video explains how to handle hash collisions and deletion in a hash table. The naive method of deletion, which simply clears the contents of the bucket, is shown to be flawed because it impacts the ability to find elements in the hash table properly. Instead, the video recommends placing a unique marker called a tombstone in place of the deleted element. This marker can later be replaced with a new key-value pair or removed during hash table resizing. The video provides an example using quadratic probing to show how tombstones are used during hash table lookup.
- 05:30:00 The Google engineer provides an overview of hash tables that use open two addresses as a collision resolution scheme. The engineer discusses lazy deletion or lazy relocation, which involves relocating key value pairs to avoid hitting a bunch of tombstones when probing. The engineer also provides a walk-through of the code for a hash table that uses quadratic probing, which involves storing key value pairs directly inside an array rather than having one array with a wrapper class for an entry. The engineer explores the constructor and default constants for the hash table, which allows users to initialize it without any parameters.
- 05:35:00 In this section of the course, the instructor explains the implementation of the hash table using quadratic probing. The method involves computing the threshold, normalizing the index and initializing the tables. The insert method info is provided where key-value pairs are inserted into the hash table or updated if the key already exists. The instructor also discusses key count, hash table's empty check, and put addition before moving onto the insertion method. The do-while loop for the insertion of a key is explained in detail.
- 05:40:00 The instructor explains the contains key, has key, get, and remove methods of a hash table implementation. The contains key and has key methods check whether a key exists in the hash table by calling the get method, which returns a true or false value for the contains flag. The get method finds the hash index and looks for the key. If the key exists, the contains flag is set to true, and the value is returned. The remove method is simpler, where a key is first found in the hash table, then decremented, and a tombstone is dumped in its place. The resize table method is called when new elements are being inserted to grow the table size, where a new table is allocated, and the current table is swapped with the new table to call the insert method.
- 05:45:00 The Fenwick tree, also known as the binary index tree, is introduced as a data structure to efficiently compute range queries on an array and perform point updates. The motivation behind the Fenwick tree is the inefficiency of linear queries when computing ranges in an array. By computing all prefix sums for the array, range queries can be calculated in constant time. However, updates to the array require recomputing all prefix sums, making the process inefficient. The Fenwick tree was created to solve this problem by supporting range queries and point updates in logarithmic time with linear construction time. The Fenwick tree works by having each cell responsible for a range of other cells based on the value of its least significant bit.
- 05:50:00 In this section of the video, the instructor discusses Fenwick trees and how they work for range queries. He shows a diagram with a one-based array and the binary representation of each number. The diagram shows the least significant bits responsible for themselves, and all other cells responsible for a range of 2, 4, 8, or 16 cells. To perform a range query, the instructor explains how to calculate the prefix sum up to a certain index by cascading downwards until reaching zero. He demonstrates how to find the prefix sum for a specific index and how to do an interval sum between two given indices.
- 05:55:00 We learn about calculating prefix sums using a cascading down effect and how to perform a range query algorithm using Fenwick trees. The prefix sum calculation involves starting at a given index and subtracting the least significant bit from the value until it reaches zero, and then adding all the values during each subtraction. The range query algorithm uses Fenwick trees where we take the difference between prefix sums for range queries. The algorithm requires bit manipulation and provides a neat little algorithm for faster computation. The video author recommends checking out the previous Fenwick tree range query video for more context on how the tree is set up and how operations are performed on it.
Part 7
- 06:00:00 The concept of point updates and Fenwick tree construction are explained by the Google Engineer. Point updates involve adding values to the tree at a specific index and finding the cells responsible for that range of responsibility. Meanwhile, the linear construction of the Fenwick tree involves updating the immediate cell responsible for a value by propagating the values throughout the tree in place, resulting in a fully functional Fenwick tree. The propagation process relies on the cascading idea of updating the parent responsible for a specific value.
- 06:05:00 In this section of the tutorial, the concept of a Fenwick tree is explained in detail. A Fenwick tree is a data structure that is used to quickly perform range queries and point updates on an array of values. The data structure utilizes a type of binary indexing in which each cell is responsible for propagating its value to its parent and so on. The construction algorithm for a Fenwick tree is also discussed, which involves turning an array of values into a Fenwick tree by cloning the original array and computing the parent cell for each element in the new tree structure. The source code for a Fenwick tree implementation in Java is shown and is available in a GitHub repository.
- 06:10:00 The instructor explains how to create a Fenwick tree class and its different constructors. He also explains the prefix sums, which allows to compute the prefix sum from one to i both inclusive. The video also covers how to add from a point update and an additional method to set the index equal to k. The instructor emphasizes the importance of using binary manipulation and the suffix array data structure, which is very useful in string processing.
- 06:15:00 The concept of suffixes and suffix arrays are introduced, with an example of constructing a suffix array for the word "camel". The suffix array is an array of sorted indices that allows for a compressed representation of the sorted suffixes without storing the suffixes themselves, making it a space efficient alternative to a suffix tree. The longest common prefix (LCP) array, which stores how many characters two sorted suffixes have in common with each other, is also introduced as an important piece of information associated with the suffix array, with an example of constructing the LCP array for a given string.
- 06:20:00 The video discusses the application of suffix arrays and LCP arrays in finding and counting unique substrings in a more efficient manner than the naive algorithm which requires a lot of space. By using the information stored inside the LCP array, it provides not just a quick but a space-efficient solution. The LCP array represents the shared number of characters between two adjacent suffixes of the original string. By examining the LCP values, one can determine which substrings are repeated and eliminate them to count all unique substrings effectively.
- 06:25:00 The speaker discusses the problem of finding the longest common substring shared between at least k out of n given strings. One approach to solving this problem is dynamic programming, but it can quickly become unwieldy. A better approach is to use a suffix array, which can find the solution in linear time. To do this, the speaker explains that we first concatenate all the strings into a larger string, adding unique sentinel values in between each string to avoid any intermingling of suffixes. Then, we construct the suffix array for this concatenated string, which allows us to find the longest common substring of K strings by looking for K strings with different colors that share the largest LCP value.
- 06:30:00 The video tutorial discusses how to find the longest common substring of k different colors within a string using a sliding window technique. The approach is to adjust the window size to contain k suffixes of different colors and to query the minimum LCP value within that range. The minimum range query can be solved using a linear solution or a minimum range query data structure such as a segment tree. The tutorial also recommends using a hash table to keep track of the colors in the window. The sliding window expands downwards to capture missing colors and shrinks when the criteria are met.
- 06:35:00 In this section of the video, the instructor demonstrates an example of solving the longest common substring problem with a suffix array. The window LCP and window LCS values help track the longest common prefix and longest common substring values for the current window, while the LCS length and LCS set track the best values so far. The example uses four strings and a minimum of two strings of the pool of four to share the longest common substring. The instructor demonstrates how to expand and shrink the window while searching for the longest common substring, and hints at a challenge for viewers to check out on the cast website and provides a link to an implementation of the algorithm on GitHub.
- 06:40:00 The video explains the process of solving the longest common substring problem using the sliding window technique. By expanding and shrinking the window size and using the longest common prefix array to identify the common substrings, the algorithm finds a solution with a linear time complexity. The video then introduces the longest repeated substring problem and explains how to use the longest common prefix array to efficiently find the longest repeated substring in a given string, compared to the naive approach that requires N squared time and lots of memory.
- 06:45:00 The Google engineer teaches about using a suffix array and an LCP array to find the longest repeated substring. The LCP value at an index gives the length of the longest common prefix between two adjacent suffixes. The maximum value in the LCP array gives the length of the longest repeated substring. In the case of ties, all the possible longest values must be found. Then the engineer explains the importance of balanced binary search trees and how they differ from traditional binary search trees in terms of being self-adjusting to maintain a logarithmic height relative to the number of nodes they hold, making insertion and deletion extremely fast. The key concept to achieve this is tree rotations, and they will be discussed further in the video.
- 06:50:00 The concept of tree invariant and tree rotations in balanced binary search trees is explained. A tree invariant is a rule imposed on a tree to be met at the end of every operation, which is ensured by applying a series of tree rotations. Tree rotations are legitimate transformations that move around nodes in a tree without breaking the binary search tree invariant if the ordering and placement of nodes are maintained. The process of right rotation is explained in detail, and the steps involved in updating pointers when nodes have references to both the child and parent nodes are discussed.
- 06:55:00 The video tutorial focuses on demonstrating how to insert nodes into an AVL tree using the tree rotation technique while also explaining the properties that keep AVL trees balanced. First, the video explains what an AVL tree is and its significance as the first type of balanced binary search tree. Then, the video introduces the balance factor, which is the difference between the height of the right subtree and the left subtree. The video emphasizes that the balance factor of every node should be either minus one, zero, or plus one to maintain the balance of the AVL tree. The tutorial then proceeds to discuss how to handle cases when this is not true, which can be resolved with tree rotations.
Part 8
- 07:00:00 The instructor explains the four distinct cases of rotations needed to balance a left-heavy tree in an AVL tree. The instructor also provides pseudocode for inserting a node into an AVL tree and explains the update and balance methods. The update method calculates the height and balance factor of a node, while the balance method checks if the balance factor of a node violates the AVL tree property and determines the appropriate rotation to rebalance the tree. The left-right and right-left cases are also explained as they reduce to left-left and right-right cases after the first rotation.
- 07:05:00 The video explains how to remove elements from an avielle tree, which is very similar to removing elements from a regular binary search tree. The removal process can be broken down into two steps: finding the element and replacing it with a successor node to maintain the binary search tree invariant. Finding the node involves comparing the target element with nodes in the tree until a match is found or the search reaches the end of the tree. The replacement process depends on whether the node to remove is a leaf node or has only a left or right subtree, with the successor node being the immediate child in the latter two cases.
- 07:10:00 The instructor explains how to remove a node from a binary search tree and provides examples for the three cases of deletion. The first case is when the node to remove has no children, the second is when it has one child, and the last is when it has two children. The instructor also explains how to augment the binary search tree removal method for AVL trees by simply adding two lines of code to ensure that the tree remains balanced and that the balance factor and height values stay up to date. Finally, the instructor provides a link to their GitHub repository where viewers can find the source code for the AVL tree and a live demonstration of the AVL tree in action.
- 07:15:00 The instructor provides an explanation of the source code for a recursive AVL tree implementation in Java. The AVL tree accepts a generic type argument and stores the value inside the node, which must be comparable. The node subclass stores the left and right child pointers, and the height and balance factor of the node. The tree can be displayed on the terminal using the tree printer interface, and public methods such as size, is empty, and set contains are provided in the code. The insert method is also explained using base cases and comparative values to determine whether an insertion was successful or not.
- 07:20:00 The private insert method in the AVL tree is explained, which inserts new nodes either to the left or the right subtree, while updating the balance factor and height of the nodes accordingly. The update method updates the height and balance factor of a node, and the balance method calls the necessary rotation methods to maintain the balance of the tree. The left-left, left-right, right-right, and right-left cases are explained, and the order of the update methods after rotation is emphasized as crucial for the AVL tree to maintain its balance.
- 07:25:00 The instructor discusses the remove method of the binary search tree data structure. He explains that to remove an element, the method first checks if the element exists in the tree and subsequently calls the private remove method. The instructor outlines the four cases that can arise during removal and proposes a heuristic to determine which subtree to remove from when attempting to remove a node with both subtrees. Finally, he reminds viewers to call the update and rebalance method on the callback of the remove method to ensure the tree remains balanced despite node removals.
- 07:30:00 The Google engineer introduces the indexed priority queue, a data structure that supports quick updates and deletions of key-value pairs. It solves the problem of being able to quickly look up and dynamically change the values in a priority queue, which can be useful in various situations such as a hospital waiting room where patients need to be served by the highest priority first. The engineer provides an example of patients with different priorities and how the indexed priority queue can help in updating priorities on the fly.
- 07:35:00 The video discusses index priority queues which allow for the efficient dynamic updating of priorities for certain items. The first step in using an index priority queue is to assign index values to all keys, creating a bi-directional mapping. This mapping should be bi-directional and can be facilitated with a bi-directional hash table. The reason for using index values on keys is to enable indexing into arrays, which is often how priority queues are implemented.
- 07:40:00 The speaker introduces the concept of an index priority queue and explains the operations it should support, including deleting keys, getting the value associated with a key, checking if a key exists in the priority queue, getting the key index with the smallest value, getting the smallest value in the index, being able to insert and update key value pairs, and the specialized update operations increase and decrease the key. The time complexity for all these operations is either constant or logarithmic. The speaker also provides a refresher on the traditional priority queue data structure, including how binary heap works, how to insert a new value into the priority queue, and how to remove items from it.
- 07:45:00 How do we implement an indexed priority queue with a binary heap? The first step is to assign each item a unique index value and an initial value for the index priority queue. Then, we use a min indexed priority queue to sort by the lowest value first, and we maintain a position map to tell us the index of a node in the heap for any given key index. Additionally, we maintain an inverse lookup table to find the key for a given node. This information enables us to efficiently access and manipulate the priority queue for a variety of applications, such as prioritizing patients in a hospital or customers in a restaurant.
- 07:50:00 The video discusses how to perform useful operations, such as inserting, updating, and removing key-value pairs in an index priority queue. The process for insertion is similar to a regular priority queue, but with the added step of updating the position and inverse maps. The video provides pseudocode for the insertion process, showing how the node is moved up through the heap until the heap invariant is satisfied. The swapping process involves updating the position and inverse maps, but not the values array, which remains indexed by the key index rather than the node index. The video also briefly touches on polling and removing key-value pairs, which involve similar steps as insertion but in reverse.
- 07:55:00 The video explains how removing elements from an indexed priority queue is improved from linear time complexity to logarithmic time complexity, making use of node position lookups that are now constant time. The video gives a step-by-step example of how to remove nodes, including swapping nodes, storing key value pairs before removal, cleaning up removed nodes, and restoring the heap invariant by moving the swapped node up or down. Additionally, pseudocode for removing key-value pairs is provided, showcasing a short five-line implementation and three-line cleanup process. Finally, the video describes the sync method and how it works, as well as key-value pair updates, which are similar to remove but also take logarithmic time.
Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer
- 2019.09.19
- www.youtube.com
Learn and master the most common data structures in this full course from Google engineer William Fiset. This course teaches data structures to beginners usi...
C Programming Full Course for free
C Programming Full Course for free
00:00:00 - 01:00:00 The "C Programming Full Course for free" video teaches viewers how to install the gcc compiler, set up an IDE, and write C code. The video covers the basics of C programming, including how to use printf statements, comments, escape sequences, and format specifiers to display different data types. The instructor explains how to create and initialize variables, and how to use arithmetic and increment/decrement operators. Additionally, the video covers accepting user input using scanf and formatting output using printf. The instructor also discusses useful math functions in C and how to use them to calculate the circumference and area of a circle based on user input for the radius. The video emphasizes that although C is a difficult language, anyone can learn it with persistence and effort.
01:00:00 - 02:00:00 The "C Programming Full Course for free" YouTube video teaches programming concepts in C language. In this video section, the instructor covers topics such as if/else statements, switch statements, logical operators, functions, and loops. The instructor explains conditional statements, allowing the program to make choices based on conditions, and how the switch statement is a more efficient version of the else if statement. Furthermore, the instructor goes in-depth to show how to convert temperature units, create a simple calculator program, use logical operators to improve program efficiency, and how to use functions to minimize code redundancy. Finally, the instructor explains the ternary operator and how string functions can aid program creation.
02:00:00 - 03:00:00 This C Programming Full Course covers a wide range of topics, starting with explaining the difference between a while and do-while loop, and how to use nested loops to create shapes. The video then proceeds to cover the basics of arrays and how to loop through and display elements in a one-dimensional array, before moving on to two-dimensional arrays and how to create a 2D grid or table of data. The instructor then introduces the concept of swapping variables, sorting algorithms such as bubble sort, and teaches about structs and typedef in C, as well as generating random numbers and making a number guessing game. Overall, this course provides a comprehensive and in-depth understanding of C programming concepts.
03:00:00 - 04:00:00 This YouTube video titled "C Programming Full Course for free" covers a comprehensive range of C programming topics, including creating games such as number guessing and quiz games, and covers concepts such as memory, pointers, bitwise operators, and file I/O. Additionally, the video explains how to create a Tic Tac Toe game that uses nested for loops and if statements to check for a winner and generate random moves for the computer player. The instructor provides clear explanations and demonstrations throughout the video, making it a valuable resource for anyone interested in learning C programming.
04:00:00 - 04:00:00 The instructor continues building the Tic-Tac-Toe game in C, adding a check to ensure the chosen spot is empty before placing a move and creating a function to print the winner. They then add a "play again" option using a do while loop and reset the variables at the beginning of each loop. The code will be shared in the comments section for users to use.
Part 1
- 00:00:00 The author explains the importance of learning C, which is a middle-level language that acts as a bridge between high-level software and low-level hardware. C originated in the 1970s and is widely used for various purposes, including writing compilers, operating systems, and databases. The YouTuber also provides instructions on how to set up an IDE and install the necessary extensions and compiler to get started with writing C code. However, the YouTuber cautions that C is a difficult language for beginners, but with persistence and effort, anyone can learn it.
- 00:05:00 The video explains how to install gcc on a Mac or Linux system and how to add the path to the gcc compiler underneath environment variables. Once gcc is installed, the video proceeds to explain how to configure the default build task so that VS Code knows how to compile the program. The video recommends increasing the font size and enabling autosave to save headaches later in the future. The video also goes over the basics of C programming and includes important functions such as hashtag include, std for standard io input/output, and print f parentheses. Finally, the video emphasizes the need to add the return 0 statement at the end of the main function to check for any errors.
- 00:10:00 In this section of the C programming tutorial, the instructor shows how to use printf statements to print out text and how to add a new line character using an escape sequence. He also demonstrates how to compile and run a C file using command prompt, and explains the purpose of comments in C programming. The video covers the basics of programming in C and provides helpful tips for beginners.
- 00:15:00 In this section of the video tutorial on C programming, the instructor explains how to use comments and escape sequences in your code. Comments are used for explanation, description or notes for anyone reading the code. Single-line comments are made using two forward slashes, while multi-line comments are made using forward slash followed by an asterisk and ending with an asterisk followed by a forward slash. Escape sequences, on the other hand, are character combinations that specify actions within a line of text or a string. The most commonly used escape sequences are for creating new lines and tabs within strings of text. The instructor also demonstrates how to display quotes, single quotes, and backslashes using escape sequences.
- 00:20:00 the video discusses how to create variables in C programming. First, you must declare a variable and assign a name and data type to this variable. Next, you must initialize this variable by setting it equal to some value. The video gives examples of different data types including integers, floating points, characters, and arrays. The video also explains how to display the value stored within a variable using a printf statement and a format specifier.
- 00:25:00 In this section of the video, the instructor explains how to use format specifiers to display different data types in C programming. For example, to display a character array, use the percent sign followed by 's' for string. To display a character variable, use percent c, and to display a floating-point number, use percent f. The instructor also discusses data types such as chars, floats, integers, and doubles, with doubles having 64 bits of precision and retaining more significant digits than floats. Booleans are also introduced, storing true or false and using one byte of memory. Different format specifiers and ways to customize them will be discussed in the next video.
- 00:30:00 We learn that Booleans can be displayed using percent d with one referring to true and zero to false. Characters can store integers within negative 128 to positive 127 range, with their representations being shown using percent d or percent c format specifiers. Unsigned variables double our range of positive numbers for both characters and shorts, so char can store numbers between 0 and 255, while shorts can store digits from negative 32,768 to positive 32,767 if signed, and 0 to 65,535 if unsigned. We learn you can use short instead of short int as shorthand. Integers can store whole numbers that can be either positive or negative values.
- 00:35:00 It is important to note that there are different format specifiers for different data types and using the wrong one can result in errors or unexpected output. While there are many data types available in C programming, we will mainly be focusing on chars, arrays of chars, doubles, booleans, and integers in this course.
- 00:40:00 The instructor explains format specifiers, which define and format types of data to be displayed in a specified manner. To set a minimum field width for displaying the output, a number is added after the percent sign to allocate specific spaces. Using a negative sign after the percent sign left aligns the data. The video also covers constants, which are fixed values that cannot be altered by the program during its execution. To convert a variable into a constant, the data type is preceded by the keyword 'const,' and uppercase convention is followed for naming the constant. Arithmetic operators such as addition, subtraction, multiplication, and division are also covered, where division with integers can truncate decimal portions, requiring the use of float or double for storing the result, and modulus operator is used to obtain the remainder of any division.
- 00:45:00 The instructor explains arithmetic operators in C programming, including modulus, which can be used to quickly determine if a number is even or odd by finding the remainder when divided by 2. The video also covers increment and decrement operators, which can be used to increase or decrease a variable by 1, and augmented assignment operators, which allow users to perform an arithmetic operation on a variable and assign the result back to the same variable using a shortcut. Finally, the instructor provides an overview of accepting user input with scanf function and prompts in C programming.
- 00:50:00 The instructor explains how to accept user inputs in C programming using the scanf function with the appropriate format specifier for the type of variable being used. The section covers accepting integers and strings, with the caveat that accepting strings with spaces requires the fgets function instead of scanf because of white spaces. The instructor also explains how to format the string after using fgets to get rid of new line characters. The section ends with an overview of printf statement formatting to improve readability.
- 00:55:00 In this section of the video, the instructor discusses useful math functions in C when including the math header file. Square root, power, rounding (using ceiling and floor), absolute value, logarithms, and trigonometry functions are explained with examples of how to use them in code. Later, the instructor demonstrates how to write a program that calculates the circumference of a circle based on user input for the radius, and goes further to calculate and display the area of the circle using pi times the radius squared formula.
Part 2
- 01:00:00 In this section of the video, the instructor demonstrates how to calculate the circumference and area of a circle using C programming language, and how to find the hypotenuse of a right triangle, which requires the use of the square root function from the math.h header file. The instructor also introduces if statements and how they are used to add choices to a program by checking conditions and executing code accordingly. He demonstrates how to use the greater than or equal to condition and the double equal signs comparison operator, as well as how to use else statements to provide a different output when a condition is false.
- 01:05:00 the video discusses if statements and else if statements in C programming. These statements allow the program to check if a condition is true and perform a specific subset of code if it is, and if not, the program will move down to the next block to check another condition. If all conditions evaluate to be false, then the program will execute the code that is within the else block. Additionally, the video introduces the use of a switch statement as a more efficient alternative to using multiple else if statements. The switch statement allows a value to be tested for equality against many cases using the case keyword. Finally, the video stresses the importance of adding a break statement after each case in a switch statement to exit out of the switch once a matching case has been found.
- 01:10:00 In this section of the video, the instructor teaches how to create a program that converts temperature from Celsius to Fahrenheit or vice versa. The program accepts user input for the unit of measurement (Celsius or Fahrenheit) and the current temperature, and then uses if/else statements and the appropriate formulas to perform the conversion. The instructor also demonstrates how to use the to_upper function to handle case sensitivity and how to use scanf to accept floating point numbers. The program prompts the user for input and displays the converted temperature.
- 01:15:00 In this section of the course, the instructor demonstrates how to create a program in C that converts temperature units (Celsius to Fahrenheit and vice versa) based on user input. The program prompts the user to enter the temperature and unit of measurement, accepts the input using scanf, and then uses a series of conditional statements to convert the temperature units as needed. The instructor explains the use of format specifiers, the Celsius to Fahrenheit conversion formula, and the switch statement to handle different types of operations in the program's flow. The final program is posted in the comments section for download and review.
- 01:20:00 In this section of the video, the instructor demonstrates how to create a simple calculator program in C that can perform addition, subtraction, multiplication, and division. The program uses a switch statement to determine which operation to perform based on the user's input. Additionally, the use of logical operators is explained, specifically the "and" operator, which checks if a set of conditions is true. The instructor provides examples of how to use logical operators to check if a temperature falls within a certain range, and how to include boolean variables in the condition checks.
- 01:25:00 The or logical operator and the not logical operator are discussed. The or logical operator checks if at least one condition is true, while the not logical operator reverses the state of a condition. The or operator can be used to check multiple conditions by adding more vertical bars. On the other hand, the not operator can offer more options for the way in which a program is written. These logical operators can help create more complex conditions and improve the efficiency of a program.
- 01:30:00 The instructor teaches about using functions in C programming to avoid repeating the same code. By creating a new function, code can be written once and then reused multiple times simply by calling the function. The instructor then moves on to discuss arguments and parameters, with an example of passing character arrays and integers as arguments to a function. The parameters need to be declared in the function declaration to make the function aware of the variables being passed to it. Without a matching set of parameters, the function cannot be called.
- 01:35:00 In this section of the transcript, the speaker explains the concept of the return statement and how it can return a value back to the calling function. They demonstrate an example of a function called "square" that will accept one argument, square that argument, and then return the result back to the calling function. They also discuss the syntax of the trinary operator, a shortcut to using an if-else statement when assigning or returning a value, and show an example of how it can be used to find the maximum of two integers. The speaker also emphasizes the importance of matching the data type when using the return keyword within the function declaration.
- 01:40:00 We learn about the ternary operator, which serves as a shortcut for using an if-else statement when assigning or returning a value. The operator consists of a condition, followed by a question mark, a value to return if the condition is true, a colon, and the value to return if the condition is false. We also discuss function prototypes, which ensure that calls to a function are made with the correct number and type of arguments. By adding a function prototype before the main function, we can avoid unexpected behavior and receive errors if incorrect arguments are used.
- 01:45:00 In this section of the video, the instructor explains function prototypes in C and their advantages, as well as introducing some useful string functions that are already written in C, such as string length, string compare, string lower, string upper, and string cat. The instructor gives examples of how each of these functions work and demonstrates their outputs. The string compare function returns zero if the two strings being compared are the same, and other numbers if they are not. The instructor ends the section by including a code snippet that uses these string functions.
- 01:50:00 The instructor covers for loops, which repeat a section of code a limited number of times. He provides an example of counting from 1 to 10 using a for loop and explains the three statements required for a for loop: declaring an index, defining a condition for how long to repeat the code, and a way to increment or decrement the index. He also demonstrates different ways of incrementing and decrementing the index. The instructor then moves on to explain while loops, which repeat a section of code possibly unlimited times as long as a certain condition remains true, and gives an example of prompting users for their name until the user inputs a valid response.
- 01:55:00 In this section of the video, the instructor demonstrates how to use fgets instead of scanf for user input in C programming. They then use a while loop to prompt the user to enter their name and yell at them if they did not enter their name properly. The instructor then transitions to discussing the do-while loop and provides a demonstration of a program that asks the user to enter as many numbers as they want, provided they are greater than zero, and calculates the sum of those numbers.
Part 3
- 02:00:00 In this section of the C Programming Full Course, the instructor explains the difference between a while loop and a do-while loop in C. While a while loop checks the condition first and then executes the code if the condition is true, a do-while loop executes the code once and then checks the condition to see if it's true before continuing. The instructor demonstrates this with an example code and explains how to modify a while loop to a do-while loop. The section also covers nested loops, which is a loop inside of another loop, and demonstrates an example of using nested loops to print a rectangle of symbols based on user input values for rows, columns, and symbols.
- 02:05:00 In this section of the video, the instructor demonstrates how to create rectangle shapes using nested loops in C. He allows the user to enter a symbol and the number of rows and columns for the rectangle, but he also shows how to clear input buffer to allow for proper user input. The instructor also explains the difference between the continue and break statements within the context of C loops, where continue will skip the rest of a section of code and force the next iteration of a loop, while break will exit out of a loop entirely. Finally, the instructor defines the concept of arrays as a data structure that can store many values of the same data type and shows how to turn a variable into an array.
- 02:10:00 The video covers the concept of arrays in C programming language. Arrays are a way to store multiple values of the same data type in a fixed-size data structure. The video demonstrates how to initialize an array and access specific elements using index numbers. There are various ways to initialize an array, such as assigning values immediately or assigning values later in the program. The video also explains how to loop through and print all the elements of an array using a for loop.
- 02:15:00 The video covers how to loop through and display the elements of an array in C programming. The instructor demonstrates using a for loop and a printf statement, with the index of the for loop being used to access the elements of the array. They also show how to calculate the number of times the loop should iterate using the size of operator, which will automatically update if elements are added or removed from the array. The instructor then moves on to create a two-dimensional array, which is an array where each element is itself an array. They demonstrate how to initialize and organize a two-dimensional array, using the example of a simple grid or table of data.
- 02:20:00 The instructor goes over how to declare and assign values to a two-dimensional array in C programming. They also explain how to display the elements of a two-dimensional array using nested loops and the format specifier "d". The instructor then shows how to calculate the number of rows and columns of a two-dimensional array by using the size of operator and the size of one of the rows, and by using the size of one of the elements found within the first row. The section concludes with an example of how to test the code with a new row added to the 2D array.
- 02:25:00 In this section of the video, the instructor explains how to create a two-dimensional array in C, which is an array of arrays where each element is an entire array. Two indices are used to access one of the elements - one for the row and one for the column. The instructor also shows how to create an array of strings, which is a 2D array of individual characters, except each element is a string. To display an array of strings, a for loop can be used. Finally, the instructor explains how variables can be swapped in C by introducing a third variable as temporary storage for the value. Swapping variables is important in sorting algorithms, which will be covered in the next topic.
- 02:30:00 The instructor teaches how to swap the values of two variables in C, both for integer and character arrays. Using temporary variables and the string copy function, the instructor shows how to swap values and avoid unexpected behavior with character arrays if the length of the second argument is less than the first. The instructor also suggests imagining variables as glasses containing fluid to better understand swapping values, and provides sample code in the comments section. Following this, the instructor explains how to write a program to sort elements within an array, first with an array of integers and then with an array of characters. The instructor declares a separate function for sorting and uses nested for loops to iterate through the array and compare values for sorting.
- 02:35:00 The speaker discusses how to sort elements of an array in C using the bubble sort algorithm. They explain the use of temporary variables and if statements, and how the size of the number being sorted affects its final position in the array. The speaker also demonstrates how to sort an array of characters by changing the data type and print function. They then introduce the concept of structs as a way to organize related members in one block of memory, with the ability to mimic real-world objects. A struct is defined using the struct keyword followed by a tag name and a set of curly braces to represent its members.
- 02:40:00 In this section of the video, the instructor teaches about structs and typedef in C programming language. Structs allow a programmer to group related values under one name in a block of memory, and these can be used to assign values to members with different data types. The typedef keyword gives an existing data type a nickname, which makes it easier to use the data type in the code. The instructor also shows an example of creating a struct with three members and assigning values to them. The video provides a sample code for users who would like to use it.
- 02:45:00 The struct is created outside of the main function and given a tag name, "student", and contains a character array for the name and a float variable for the GPA. An array of four students is initialized and then placed within an array called "students". Using a for loop, the program loops through the array and prints out each student's name and GPA using the dot member access operator. Finally, the video explains that if we use the "typedef" keyword with a struct, we no longer need to use the struct keyword to create the struct and can instead use the nickname we assigned to it.
- 02:50:00 The instructor teaches about creating arrays of structs in C, where each element in the array is a struct containing data for each student such as name and GPA. The instructor also goes over using enums, which are user-defined types of named integer identifiers that can make a program more readable by replacing integer values with associated names, making the code easier to understand for the programmer and anyone reviewing the code. The structure of enums is outlined, and the instructor demonstrates how to use enums in if-else statements to print different output based on the value of an enum variable.
- 02:55:00 In this section of the video, the instructor demonstrates how to generate random numbers in C programming. The current time is used to generate a seed for the rand function, which generates a random number between 0 and 32767. To obtain a random number within a given range, the modulus operator can be used. The instructor provides an example of generating a random number between 1 and 6 (for rolling a dice) and for rolling three dice. A number guessing game is also introduced using the knowledge of generating random numbers. Constants for the minimum and maximum range are set and the user is prompted to guess the number. The program uses the rand function to generate a random number between the given range, and the user gets feedback to adjust their guess until the correct number is entered.
Part 4
- 03:00:00 The instructor teaches how to create a number guessing game in C, where the program generates a random number between two specified values, prompts the user to guess the number, and provides feedback if the guess is too high, too low, or correct. The program uses a do-while loop to ensure at least one guess is made and counts the number of guesses made by the user. The instructor also adds some text decorations to make the output more visually appealing. This example demonstrates the use of conditionals, loops, user input, and random number generation in C.
- 03:05:00 The instructor shows how to create a quiz game in C. The game uses a two-dimensional character array to store the questions and a separate two-dimensional character array to store the options. The correct answers are stored in a one-dimensional character array. The game calculates the number of questions it has and uses a for loop to cycle through them one by one, displaying them along with their possible options. To do this, the instructor uses a nested for loop that begins with every fourth string within the options array. This for loop cycles four times, displaying the four possible options for each question.
- 03:10:00 The instructor walks through how to create a simple quiz game in C that prompts the user with questions and checks their answers. The code uses a nested for loop to display the questions and options, accepts user input using scanf, and converts lowercase characters to uppercase using the "toupper" function. The program then checks if the user's guess matches the correct answer and increments the score accordingly. Once all questions have been answered, the program displays the final score. The instructor also briefly explains bitwise operators and demonstrates how to use five different bitwise operators in C.
- 03:15:00 We learn about bitwise operations in C programming. We start with the AND operator, which, when applied to two binary numbers, assigns a one to our result only if both corresponding bits are one. We then move on to the OR operator, which assigns a one to our result if any of the corresponding bits are one. The exclusive-OR operator assigns a one to the result if only one corresponding bit is one. We also learn about left and right shift operators that shift bits in a binary number to the left or right. Shifting the bits to the left effectively doubles the number, while shifting it to the right has the opposite effect.
- 03:20:00 The video explains memory in C programming, which is an array of bytes within RAM, with each unit being a memory block that can hold a value. A memory address points to where a memory block is located within RAM, and it is like a street address. When declaring a variable, it sets some memory blocks aside to hold a value that is associated with a memory address. Each variable uses a memory block of one byte, and the video displays the memory addresses and sizes of various characters as examples. The video also briefly explains hexadecimal values, which use numbers from 0 to 9 and letters from a to f to create 16 possible values for each digit. Finally, the video covers short data types, which use two bytes of memory.
- 03:25:00 The instructor explains the basics of memory in C programming, including how variables use up memory blocks and how arrays use up multiple memory blocks based on their size and data type. He also introduces the concept of pointers, which hold a memory address as a value to another variable, and explains how they can be used to perform certain tasks more easily. The instructor demonstrates how to display the value and address of a variable and how to create a pointer of the same data type as the variable it is pointing to.
- 03:30:00 We learn about pointers in C programming. Pointers are declared using an asterisk as the indirection operator and a common naming convention is using a lowercase "p" followed by the variable name with the first letter capitalized. The value of a pointer is an address, and we can access the value stored at that address by using the indirection operator. It is important to make sure the data types of the pointer and the variable it is pointing to are consistent. Pointers can also be passed as arguments to functions, allowing the function to access and modify the value stored in the pointed-to variable. Additionally, pointers can be declared and initialized in two steps, but assigning a value right away is good practice.
- 03:35:00 The instructor explains pointers in C programming. A pointer is a variable that holds a memory address to another variable, array, and more. To declare a pointer, you use the indirection operator. To assign a value to a pointer, you use the same operator. The instructor shows how to write to a file in C using pointers, fopen, fwrite, and fclose. To write to a file, you need to create a pointer to a file and use `fprintf` to write to the file. The instructor also demonstrates file I/O by deleting a file and writing to a file in a specific location on a computer's directory.
- 03:40:00 The instructor shows how to read the contents of a file in C programming by creating a pointer with the data type "file" and using the fopen function to open the file. The instructor demonstrates how to use a buffer to contain an array of characters to hold one line of the text document at a time and how to read a single line from the file using the fgets function. The section also includes how to display all the lines from a file using a while loop and how to add file detection to check if the file exists before attempting to read it.
- 03:45:00 In this section of the video, the instructor goes over the function prototypes that will be used in the program, including functions to reset the board, print the board, check free spaces, player move, computer move, check winner, and print winner. After declaring these functions, the instructor discusses some global variables to be used, including a 2D array of characters named board, as well as constants for the player and computer characters. The main function is discussed next, where it declares a local variable for the winner, sets it to an empty space, resets the board, and prints it. The video also includes details on nested for loops used in the reset board function and a printf statement used in print board.
- 03:50:00 In this section of the C Programming Full Course, the instructor explains how to create a while loop in the main function that will surround the print board function. The while loop condition is that if the winner is an empty space and the returned value from invoking the check free spaces function does not equal zero, the loop will continue. The check free spaces function is also created using two nested for loops to loop through the 2D array of characters and decrement the free spaces local variable if any spot is occupied. The player move function is explained which prompts the user to enter row and column numbers to make a move, and checks to see if the spot is occupied or not. The check winner function is also created to check each row for a win condition and to check each column for a win condition.
- 03:55:00 The instructor goes over the code for checking the rows, columns, and diagonals for a winner in a Tic Tac Toe game. They explain the use of for loops and if statements to iterate through the elements in the game board and check for matches. If there is a winner, the function returns the character value of the winning element. If not, an empty character is returned. The instructor then provides code for the computer's move, which involves generating random coordinates to place its symbol on the board. Before generating random numbers, the program checks if there are any available spaces on the board.
- 04:00:00 The instructor continues building the Tic Tac Toe game in C. They add a check to make sure the spot generated is an empty space before placing a move. If there are no more spaces available, then the "print winner" function is invoked with an empty space, meaning the game is a draw. They explain that this function is fairly easy as it prints "You win" if the winner is the player, "You lose" if the winner is the computer, and "It's a tie" if there is no winner. The instructor implements a "play again" option using a do while loop and resets the winner and response variables at the beginning of each loop. The game is run and tested multiple times, with the instructor explaining each step. Finally, they mention that the code will be posted in the comments section for users to use.
C Programming Full Course for free 🕹️
- 2021.10.07
- www.youtube.com
C tutorial for beginners full course#C #tutorial #beginners⭐️Time Stamps⭐️#1 (00:00:00) C tutorial for beginners 🕹️#2 (00:12:36) compile and run a C pro...
Fundamental Concepts of Object Oriented Programming
Fundamental Concepts of Object Oriented Programming
The four fundamental concepts of object-oriented programming are abstraction, encapsulation, inheritance, and polymorphism. Before delving into their meanings, it is important to understand what an object is. An object represents something from the real world, which can be physical, like a car or a book, or non-physical, like a dental appointment or a bank account.
In the context of object-oriented programming, an object refers to anything of interest to the software application being developed, where data needs to be stored and processed. Objects are also known as entities.
Abstraction is the first fundamental concept, which involves simplifying reality by focusing only on the relevant data and tasks related to an object. When designing an application to process data about a person, for example, only the necessary data and operations are considered.
To create objects programmatically, a class is required. A class serves as a template for creating objects and is written by a programmer to define the attributes (also known as fields or properties) and operations (also known as behaviors or methods) of an object. Attributes describe the object's data, while operations represent the actions that can be performed by the object.
Encapsulation is the second fundamental concept and involves hiding the complexity of an object's inner workings from other programs and programmers. It is often referred to as information hiding because the data and functions within an object are bound together and protected from external interference. Experienced programmers often create classes that are used by junior programmers, and compiled class libraries protect intellectual property.
Inheritance is the third fundamental concept, allowing a class to derive its methods and properties from another class. This leads to a hierarchy of classes, where subclasses inherit from a superclass. For example, an employee class inherits from a person class, and a customer class also inherits from the person class. This creates a type of relationship, with subclasses extending the properties and methods of their superclass.
Polymorphism, the final fundamental concept, enables a class to implement inherited methods in its own way. Different subclasses of the same superclass can have different implementations for the inherited methods. Polymorphism allows for different forms of objects with the same interface to behave differently, depending on their specific subclass implementation.
To summarize, abstraction simplifies reality, encapsulation hides complexity, inheritance establishes class hierarchies, and polymorphism allows for diverse implementations of inherited methods. These fundamental concepts form the basis of object-oriented programming.
Fundamental Concepts of Object Oriented Programming
- 2020.11.01
- www.youtube.com
This video reviews the fundamental concepts of Object Oriented Programming (OOP), namely: Abstraction, which means to simplify reality and focus only on the ...
Object Oriented Programming (OOP) in C++ Course
Object Oriented Programming (OOP) in C++ Course
This video provides an overview of object-oriented programming (OOP) in C++. It explains the fundamental concepts of OOP, such as classes, objects, and methods. The instructor demonstrates the creation of a C++ class and its members, emphasizing the importance of declaring variables as user-defined data types. Access modifiers like private, public, and protected are explained in relation to accessing object members.
The video also covers the implementation of OOP principles, including encapsulation, abstraction, inheritance, and polymorphism. It showcases examples of how these principles are applied in code, such as creating constructors and abstract classes. The instructor highlights the benefits of OOP, such as simplifying software development and hiding complexity from users.
Furthermore, the video explores the concept of inheritance, where a derived class inherits properties from a base class. The instructor demonstrates the process of creating derived classes and explains how they can have their own unique properties in addition to the inherited ones.
The video concludes with discussions on virtual functions and polymorphism. It explains how polymorphism allows objects and methods to have multiple forms, enabling a parent class reference to be used with child class objects. The concept of virtual functions is introduced, emphasizing that the most derived version of a function is executed when invoked.
Overall, this video aims to provide a comprehensive understanding of OOP in C++, covering essential concepts, principles, and practical implementations. The instructor encourages viewers to follow her channel, Code Beauty, and welcomes feedback on the videos.
- 00:00:00 This video explains the basics of object-oriented programming and how it works in practice. Classes are a key concept in object-oriented programming, and variables must be declared as user-defined data types in order to use them.
- 00:05:00 In this video, a C++ class is created and members are added. The class has three attributes, name, company, and age. An instance of the class is created and the variable number is assigned to it.
- 00:10:00 In this video, the instructor explains how to access the members of an object in C++. Access modifiers, such as private, public, and protected, determine how members of an object are accessible. A class method can be used to describe a behavior of an object.
- 00:15:00 This video explains how object-oriented programming (OOP) works in C++. A function is created with the return type of void, and the function is called using the same syntax as the function that was introduced. The function is then invoked five times, each time with a different employee name and company. The employee names and company values are then copied to a new employee object, and the employee object's attributes are set to the values of the newly copied values.
- 00:20:00 In this video, the instructor walks through the three rules for creating constructors in C++. The first rule is that a constructor has the same name as the class it belongs to, the second is that a constructor must be public, and the third is that a constructor must be accessible. When creating a constructor, it is important to keep in mind the rules outlined in this video. If a constructor is not following one of these rules, an error will be generated.
- 00:25:00 In this video, the instructor explains the basics of object-oriented programming, including the concepts of classes, objects, and methods. He then goes on to describe four key principles of object-oriented programming: encapsulation, abstraction, inheritance, and polymorphism. Finally, he explains how to implement these concepts in a code example.
- 00:30:00 This video introduces object-oriented programming (OOP) in C++. A class is a structure that encapsulates data and public methods that other classes can invoke to access and modify the data. To provide encapsulation, the class fields are private and the getters and setters are public.
- 00:35:00 In this video, a C++ course instructor discusses the principles of object-oriented programming (OOP). The instructor discusses how encapsulation and abstraction help to hide complex data behind a simplified interface. The instructor also discusses how validation rules can be applied to the setter methods of private properties.
- 00:40:00 In this video, the presenter explains how object-oriented programming (OOP) can make software development simpler by hiding the complexity from users. They use an example of a smartphone to illustrate how OOP can make a complex process look simple. They then demonstrate how to create a contract that makes one side of a system look simple while hiding the complexity of the system from the user.
- 00:45:00 This video explains the object-oriented programming (OOP) concept in C++. The video discusses how to create an abstract class that requires implementation for a virtual function, and how to test the function to see if a particular employee can get a promotion.
- 00:50:00 In this video, the author gets promoted and then if that person is younger than 30, that person is not going to be promoted. This allows us to implement a contract which is actually an abstract class and that abstract class or that contract has only one rule and that rule is this pure virtual function here which is called ask for promotion. So, whichever class signs this contract, whichever class inherits from this abstract employee, which is this class here, will have to provide implementation for this method here. We tested it and as you could see, I didn't get promotion and John did so that is the idea of abstraction. And this ask for promotion method is just that button that we mentioned a button on your smartphone from the beginning of this chapter. The third principle of object oriented programming that I want to talk about is called inheritance. The idea of inheritance is the following: there is this base class also known as super class or parent class and then there is derived class also known as child class or subclass.
- 00:55:00 In this video, a C++ course instructor demonstrates how object-oriented programming works by creating a derived class from an existing base class. The base class properties are then inherited by the derived class, which also gains its own properties specific to the developer class.
- 01:00:00 In this video, the instructor discusses how object-oriented programming works in C++. He explains how a developer class inherits from an employee class, and how the employee class' constructor can be used to initialize certain properties of the developer class. The instructor then shows how a method can be created on the developer class to test if the properties have been set correctly. Finally, he demonstrates how to close the developer class.
- 01:05:00 In this video, the instructor discusses the object-oriented programming (OOP) concepts of inheritance and polymorphism. He demonstrates how to use these concepts to solve a problem with a code example. Finally, the instructor demonstrates how to make a class that inherits from another class.
- 01:10:00 This video provides a brief overview of object-oriented programming (OOP) in C++. The video explains how to create a teacher class that inherits from an employee class and implements a prepare lesson function. The video also discusses some of the problems that can arise when creating and using OOP classes, and how to solve them.
- 01:15:00 In this video, the instructor explains the concept of object-oriented programming (OOP) in C++. Polymorphism refers to the ability of an object or a method to have many forms. One common use of polymorphism in programming is when a parent class reference is used to refer to an object of a child class. This example demonstrates how polymorphism works by returning to the main function and invoking the new work method on the developer and teacher classes, which are both inheriting from the employee class.
- 01:20:00 This video covers the basics of object-oriented programming in C++. The first part of the video covers the history of object-oriented programming and how it differs from other programming paradigms. The second part of the video explains how to create a pointer to a base class, and how to make a work method virtual in an employee class. Finally, the video demonstrates how the pointer works and how the program works as a result.
- 01:25:00 In this video, the instructor discusses the concept of virtual functions and polymorphism in C++. He explains that, when a virtual function is invoked, the most derived version of the function is executed. This means that, if a function is not implemented in a class's derived classes, the class's developer class will be invoked instead. He also notes that, with polymorphism, different types of employees can be treated as if they were one large object, allowing them to be referenced with a base class pointer.
- 01:30:00 This video introduces Object-Oriented Programming (OOP) in C++. It discusses how OOP makes programming more organized and easier to understand. The presenter also recommends that viewers follow her channel, code beauty, and subscribe there. Finally, the presenter encourages viewers to leave feedback on her videos.
You are missing trading opportunities:
- Free trading apps
- Over 8,000 signals for copying
- Economic news for exploring financial markets
Registration
Log in
You agree to website policy and terms of use
If you do not have an account, please register
In our technologically advanced world, programming and computer science have become transformative disciplines that drive innovation and shape society.
Programming, as an art form, combines creativity, logic, and problem solving to create elegant and efficient solutions.
Computer science serves as the scientific basis for programming, covering theories, algorithms, and methodologies for the development and implementation of computer programs. However, programming itself requires imagination and ingenuity. Like a blank canvas artist, a programmer weaves lines of code into complex algorithms, creating digital masterpieces that revolutionize industries, simplify tasks, and enhance the user experience. Object-oriented programming (OOP) is a key paradigm in computer science that allows programmers to manage complexity by organizing code into reusable and modular objects. By encapsulating data and behavior in objects, programmers can creatively design solutions that are easier to understand, maintain, and extend.
Programming goes beyond problem solving and includes designing user-friendly interfaces and engaging user experiences. This aspect combines artistic sensibility with technical knowledge. Programmers design user interface (UI) and user experience (UX) using aesthetics, intuitive navigation, and eye-catching visuals to create software that delights and captivates users. The art lies in seamlessly blending functionality with aesthetic appeal, translating complex features into intuitive and visually pleasing designs. With OOP, programmers can separate tasks and create separate objects that are responsible for different aspects of the software. This modular approach promotes creativity in design by allowing programmers to focus on individual objects, their interactions, and the overall behavior of the system. Using OOP principles such as inheritance and polymorphism, programmers can develop software with an intuitive interface, user-friendly interface, and visually appealing aesthetics.
Software engineering, a discipline of computer science, emphasizes the artistic aspect of programming. It covers the entire software development lifecycle, from requirements gathering to deployment and maintenance. Software engineers approach programming like architects, designing systems and platforms that are reliable, scalable, and maintainable. They consider factors such as code modularity, reusability, and architectural patterns to create software solutions that combine functionality and elegance. The art of software development is to balance technical constraints, user needs, and design goals to create software that is both functional and aesthetically pleasing. OOP plays a key role in software development by providing a structured approach to managing complexity. The separation of code into classes and objects allows software developers to design systems that are modular, reusable, and maintainable. With the right abstraction and encapsulation, software developers can strike a balance that results in software that is both functional and elegant.
The art of programming and computer science goes beyond the technology sector, affecting industries and society as a whole. From healthcare to finance, education to entertainment, programming and computer science are revolutionizing the way we work, communicate and live. Innovations such as artificial intelligence, virtual reality and blockchain technology are changing industries and opening up new horizons. Programmers and computer scientists are playing a key role in these transformative advances, pushing the boundaries of what is possible and turning ideas into reality. OOP allows programmers to create innovative solutions that revolutionize various areas. By managing complexity with the modular and extensible nature of OOP, programmers can develop complex systems such as artificial intelligence algorithms, immersive virtual reality experiences, and secure blockchain applications. These advances are changing industries, increasing productivity and improving the quality of life for people around the world.
Complexity management is a key aspect of software development. As systems become more complex, it becomes necessary to use effective approaches to manage complexity and ensure maintainability and scalability.
The object-oriented paradigm is a powerful approach that offers significant advantages in managing complexity. By encapsulating data and behavior in objects and using concepts such as encapsulation, inheritance, and polymorphism, the object-oriented paradigm provides a solid foundation for managing complexity.
Encapsulation is a fundamental principle of the object-oriented paradigm that promotes the association of data and methods within objects. This encapsulation hides the internal complexities of an object, exposing only the necessary interfaces to interact with it. By hiding implementation details, encapsulation reduces the complexity of other parts of the system, allowing developers to focus on higher-level abstractions. This promotes modularity and improves code readability, making complex systems easier to understand and maintain.
Abstraction is another key concept in the object-oriented paradigm to help manage complexity. This allows developers to represent complex real-world objects as classes, abstracting away unnecessary details. By creating abstract classes and interfaces, developers can define common behaviors and attributes that can be inherited and implemented by multiple subclasses. This hierarchical organization of classes allows developers to manage complexity by breaking down complex systems into smaller, more manageable components. Each class focuses on its specific responsibilities, resulting in a more modular and understandable codebase.
Inheritance is a powerful mechanism provided by the object-oriented paradigm that promotes code reuse and reduces redundancy. This allows new classes to inherit properties and behavior from existing classes by establishing an "is" relationship between them. Inheritance helps manage complexity by allowing developers to define a base class with common attributes and behaviors and then create specialized classes that inherit from it. This hierarchical organization of classes eliminates code duplication, reduces complexity, and improves maintainability.
Polymorphism is a key feature of the object-oriented paradigm that allows objects of different types to be treated interchangeably based on their common interfaces. Polymorphism simplifies complexity management by allowing developers to write code that works with a higher-level abstraction without having to deal with the specific implementation details of each object. Using polymorphism, developers can create more flexible and extensible systems because new classes can be added without affecting existing code. This promotes modular and scalable development, reducing complexity in the long run.
Complexity management is a critical aspect of software development, and the object-oriented paradigm provides a powerful framework for this task.
Through principles such as encapsulation, abstraction, inheritance, and polymorphism, the object-oriented paradigm allows developers to effectively manage complexity and create maintainable, scalable, and modular systems. By encapsulating data and behavior in objects, abstracting away unnecessary details, reusing code through inheritance, and using polymorphism, the object-oriented paradigm offers a comprehensive approach to managing complexity. The use of the object-oriented paradigm greatly improves the software development process and contributes to the creation of reliable and manageable software systems.
The art of programming combines scientific principles with creativity, problem solving and innovation. It is a discipline that requires both technical prowess and artistic vision. Managing complexity with an object-oriented approach is essential in programming, allowing programmers to develop elegant and efficient solutions and improve user experience.
As technology advances, software will continue to shape our digital world and drive future innovation.