Join Raghavendra Dixit for an in-depth discussion in this video Euclid's algorithm, part of Introduction to Data Structures & Algorithms in Java.
- [Narrator] Now, we might get very theoretical in this course, and the purpose of this course is mostly to understand data structures and algorithms. Let's start by looking at the definition of an algorithm. In the introduction to the algorithms book, the authors say that an algorithm is a way to solve a well-specified computational problem. Similarly, Donald Knuth has described an algorithm to be a finite set of rules that give a sequence of operations for solving a specific type of problem.
For example, the recipe to make tea can be considered as an algorithm. You can follow these exact sequence of operations, and once you are done, you can have a cup of tea ready. In mathematical texts, one of the earliest algorithms is to find the greatest common divisor of two numbers, which is due to Euclid, who lived in Alexandria in about 300BC. This algorithm is very simple.
Let's say there are two positive numbers, m and n. Now, to find the GCD of these two numbers, we first divide m by n, and let's say that the remainder is r. If this remainder r is zero, we are done, and the value of GCD is n. But if r is not zero, we set m equal to n, and n equal to r, and then start with step one.
So as you can see, this is a recursive algorithm, because it calls itself over and over. You can try this algorithm using a pen and paper with a few values, just to ensure its correctness and get a feel of how it works. Another interesting problem that we study is the problem of sorting data. Sorting is so common to computers that we hardly realize if it is explicitly happening anywhere, but most of the data that you see on your computer, whether it is from some website or a list of files in a directory, it's all sorted in some way.
Now, we are intelligent beings, and we sometimes do things intuitively without caring for the steps that are involved in dong a task. For example, for making tea, you don't say that we'll boil some water, and milk, and don't forget to put the teabag and the sugar, and when you start making it, you'll figure it out. Well, most people may be able to make tea just by listening to that, but that's not an algorithm. It must be an exact sequence of well-defined instructions.
So in that light, let's consider this problem of sorting these numbered balls according to the ascending order of numbers printed on them. Each of the balls is kept in a bin, and there is one empty bin which you can make use of, but there are some rules that you must follow. You can only pick one ball at a time, that is at no point of time, you will have more than one ball in hand.
So, this means that before picking up another ball, you must drop that already held ball in an empty bin, which is basically the same as rule one. Now, this is not really a rule, but you may want to start from one side, and move towards one direction. So let's say we start from the left-most bin, and move to the right to see what numbers are on the other balls. You can use a stick to keep track of the sorted part.
Now, I want you to think about how would you sort these cue balls given these set of rules, and as a hint, you can compare the numbers on the balls in the first two bins, and if the number on the ball on the right, which is two, is less than that on the left, we can exchange the balls, using the extra bin, which means that we pick ball two up, and drop it into the extra bin, then move the ball with 10 to the empty position, and then move the ball with number two back into the empty bin.
This needs to be done over and over. So now you can try to think how does this way sort the cue balls.
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.