Join Raghavendra Dixit for an indepth 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 wellspecified 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 welldefined 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 leftmost 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.
Author
Raghavendra DixitReleased
11/20/2017Note: 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
 Recursion
 Binary search trees
 Representing heaps using arrays
Skill Level Intermediate
Duration
Views
Related Courses

Learning Java
with Peggy Fisher3h 9m Beginner 
Java 8 Essential Training
with David Gassner6h 4m Beginner

1. Introduction to Algorithms

Introduction1m 8s

Euclid's algorithm4m 49s

Bubble sort algorithm2m 52s

Correctness of an algorithm1m 35s


2. Analysis of Algorithms

Introduction3m 20s

The Big O notation3m 26s


3. Basic Sorting and Search Algorithms

Selection sort2m 48s

Selection sort: Pseudocode2m 34s

Insertion sort: Pseudocode2m 38s

Stable vs. unstable sorts3m 46s

Sorting any type of object1m 33s


4. Linked Lists

What is a linked list?3m 21s

Inserting a new node5m 25s

Length of a linked list2m 11s

Deleting the head node2m 11s

Searching for an item3m 11s

Doubly ended lists3m 5s

Doubly linked list6m 28s

Insertion sort revisited10m 32s


5. Stacks and Queues

Stacks2m 41s

Queues2m 32s

Queues using arrays5m 29s

Doubleended queues1m 58s


6. Recursion

Introduction4m 32s

Understanding recursion3m 4s

Tail recursion2m 48s

Tower of Hanoi8m 24s

Merge sort4m 9s

Merge sort: Pseudocode4m 24s

Merge step: Pseudocode4m 32s


7. Binary Search Trees

The tree data structure3m 41s

Binary trees3m 34s

Binary search trees2m 1s

Deleting an item: Case 16m 5s

Deleting an item: Case 22m 58s

Deleting an item: Case 33m 44s

Tree traversal: In order3m 19s

Tree traversal: Pre order1m 58s

Height of a binary tree1m 34s


8. More Sorting Algorithms

Introduction1m 27s

Quicksort4m 53s

Shell sort5m 27s

Shell sort example3m 28s

Counting sort4m 50s

Radix sort2m 27s

Bucket sort3m 11s


9. Heaps

Deleting the root1m 53s

Inserting an item in a heap1m 59s

Heaps as priority queues2m 30s

Heap sort2m 30s

Building a heap4m 7s

Introduction4m 6s


10. Hashtables

Introduction2m 40s

Direct access tables2m 4s

Hashing1m 37s

The hash function6m 16s

Conclusion59s

 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.
CancelTake 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.
Share this video
Embed this video
Video: Euclid's algorithm