01 Introduction PDF

Preview

Summary

Introduction to Data Structures and Algorithms...

Description

Data Structures and Algorithms Data Structure: Data structure is a collection of values. The values can have relationships among them and they can have functions applied to them. Each one is different in what it can do and what it is best used for. Most important thing to take away is that each data structure is good and is specialized for its own thing. You see can think of data structures as any sort of compartment or container a data structure is simply a file cabinet of different types. You have a backpack a place where you put maybe your school books you have drawers where you pull your clothes fridge where you put your food a folder for your files and a packing box maybe for your toys. Each one of these containers are specific for it's own thing and that's what data structure really is. Algorithm is a collection of steps/ process to manipulate the data structures according to the requirements. Data structures + Algorithms = Programs In order for a computer to run code it needs to keep track of things like variables such as numbers, strings or arrays. These variables are stored in what we call random access memory or RAM for short. CPU does all the jobs for us. It can access RAM faster than that of Storage. RAM is called Random Access Memory because we can access it in random fashion. The memory controller can access the different shelves it requires in random manner. CPU is connected to memory controller and memory controller is connected to RAM. A CPU to access nearby memory shelves is much faster than far shelves. Eg: to access shelves 1 and 2 will be faster than accessing shelves 1 and 1000. In order to optimize these, CPU has a very small memory called cache and it stores all the recent data. Eg is LRU (Least Recently Used) cache.

This shelf is now upto 64 bits. You can define the way you interact with this data and how it is arranged in RAM so some data structures in RAM are organized right next to each other. Some are organized apart from each other and they have different pros and cons on access. Our goal is to minimize the operation that we need to do for the CPU you get the information for you to write information. And that is why data structures are so powerful.

Operations on Data structures: • Access • Insert • Delete • Search • Sort • Traversal Algorithms: Algorithm is a collection of steps/ process to manipulate the data structures according to the requirements. Algorithms are used to improve the performance of the program. Recursion: • • •

A function that refers to itself is called recursive function. It is good for tasks that have repeated tasks to do. It is used in searching, sorting where we do recursive tasks again and again.

Advantage of recursion: •

The code is more readeable.

Disadvantages of recursion: • •

Stack overflow. There might be infinite loops that never end/ crash the program because of stack overflow or no memory. Also we need to hold all the previous calls to the function that makes it not efficient.

To avoid stack overflow, there has to be one condition to stop the recursive function ie., we need to have a base case that can terminate the recursive calls and avoid stack overflow. Recursion vs. Iteratitive: • • • •

If a problem can be solved using recursion, it can also be solved using iteration. It depends on the situation and pros and cons. As programming depends on the principle of DRY (Don’t Repeat Yourself), so it is upto you to choose recursive approach or iterative approach. Recursive approach is more readable. However, it can make stack overflow. Iterative approach is more efficient when compared to that of recursive functions. However they are not readeable.

When to use Recursion:...