Download the Visualization.jar from DS/MyCourse/Christ Website and run, by double clicking the jar file from the folder you download you can see how most of the algorithim in this course in an animated mode
Includes all sorts, bst,linked list, graph etc
This was made by a professor along with his students
David Galles
Department of Computer Science
University of San Francisco
Saturday, November 27, 2010
Thursday, November 25, 2010
Class 9 Summary: Nov 25 : Merge Sort
Blogged By: Jibrael Jos
Merge Sort works on the principle that we can Merge two sorted arrays by looping thru it once
But then even if we could merge two sorted arrays, how does this strategy help in sorting unsorted array ?
Lets take an array
7,23,12,8,6,9,2,76,13,19 and call mergeSort(arr,0,9)
Lets divide array into two half and sort each side somehow like this
Step 1: Divide : 23,7,12,8,6 9,2,76,13,19
Step 2: Sort : 6,7,8,12,23 and 2,9,13,19,76
Step 3: Now Simple Merge them using a merge function and get
2,6,7,8,9,12,13,19,23,76
But wait a sec ? How did Step 2 happen what method did we use to Sort?
Well !!
Lets divide array into two half and sort each side somehow like this
Step 1: Divide : 23,7 12,8,6
Step 2: Sort : 7,23 and 6,8,12
Step 3: Merge to get 6,7,8,12,23
Big Deal ..... how did you do second step here ?
Lets divide array (23,7) into two half and sort each side somehow like this
Step 1: Divide : 23 7
Step 2: Sort : Now 23 is sorted in itself (since only 1 number)
Step 3:Merge to get 7,23
This is the beauty of a recursive algo like towerOfHanoi .... the logic is simply stated as
MergeSort(lowerBound,upperBound)
MergeSort(lowerBound,middle)
MergeSort(middle+1,upperBound)
Merge(lowerBound,middle+1,upperBound)
But don't forget every recursion should stop somewhere so add a condition in the beginning
if(lowerBound==upperBound)
return;
So how many times does recursive call take place for 8 numbers?
MergeSort(0,7);
------------------------ MergeSort(0,0) ... now returns
------------------------MergeSort(1,1) ... now returns
------------------------Merge() the very first merge after 6 calls to MergeSort ??
------------MergeSort(2,3)
------------------------MergeSort(2,2) ... now returns
------------------------MergeSort(3,3) ... now returns
------------------------Merge()
------------Merge()
------------------------MergeSort(4,4) ... now returns
------------------------MergeSort(5,5) ... now returns
------------------------Merge()
------------MergeSort(6,7)
------------------------MergeSort(6,6) ... now returns
------------------------MergeSort(7,7) ... now returns
------------------------Merge()
------------Merge()
Check out wiki link : Merge Sort or the SortExplain Workbook in Excel
Merge Sort works on the principle that we can Merge two sorted arrays by looping thru it once
But then even if we could merge two sorted arrays, how does this strategy help in sorting unsorted array ?
Lets take an array
7,23,12,8,6,9,2,76,13,19 and call mergeSort(arr,0,9)
Lets divide array into two half and sort each side somehow like this
Step 1: Divide : 23,7,12,8,6 9,2,76,13,19
Step 2: Sort : 6,7,8,12,23 and 2,9,13,19,76
Step 3: Now Simple Merge them using a merge function and get
2,6,7,8,9,12,13,19,23,76
But wait a sec ? How did Step 2 happen what method did we use to Sort?
Well !!
Lets divide array into two half and sort each side somehow like this
Step 1: Divide : 23,7 12,8,6
Step 2: Sort : 7,23 and 6,8,12
Step 3: Merge to get 6,7,8,12,23
Big Deal ..... how did you do second step here ?
Lets divide array (23,7) into two half and sort each side somehow like this
Step 1: Divide : 23 7
Step 2: Sort : Now 23 is sorted in itself (since only 1 number)
Step 3:Merge to get 7,23
This is the beauty of a recursive algo like towerOfHanoi .... the logic is simply stated as
MergeSort(lowerBound,upperBound)
MergeSort(lowerBound,middle)
MergeSort(middle+1,upperBound)
Merge(lowerBound,middle+1,upperBound)
But don't forget every recursion should stop somewhere so add a condition in the beginning
if(lowerBound==upperBound)
return;
So how many times does recursive call take place for 8 numbers?
MergeSort(0,7);
- MergeSort(0,3);
------------------------ MergeSort(0,0) ... now returns
------------------------MergeSort(1,1) ... now returns
------------------------Merge() the very first merge after 6 calls to MergeSort ??
------------MergeSort(2,3)
------------------------MergeSort(2,2) ... now returns
------------------------MergeSort(3,3) ... now returns
------------------------Merge()
------------Merge()
- MergeSort(4,7);
------------------------MergeSort(4,4) ... now returns
------------------------MergeSort(5,5) ... now returns
------------------------Merge()
------------MergeSort(6,7)
------------------------MergeSort(6,6) ... now returns
------------------------MergeSort(7,7) ... now returns
------------------------Merge()
------------Merge()
- Merge() .. final two merge the two halves
Check out wiki link : Merge Sort or the SortExplain Workbook in Excel
Monday, November 22, 2010
Class 7: Nov 19
Blogged by: Tinu Lawrence
Today in class we learnt about the Tower of Hanoi algorithm and how to solve the problem when 4 discs are used.
http://webcache.googleusercontent.com/search?q=cache:xA-NRvipzAYJ:www.towerofhanoi.net/+tower+of+hanoi&cd=9&hl=en&ct=clnk&gl=in
http://webcache.googleusercontent.com/search?q=cache:CfWV2h-cFL4J:en.wikipedia.org/wiki/Tower_of_Hanoi+tower+of+hanoi&cd=1&hl=en&ct=clnk&gl=in
http://webcache.googleusercontent.com/search?q=cache:FEL19xlmhl8J:www.cut-the-knot.org/recurrence/hanoi.shtml+tower+of+hanoi&cd=2&hl=en&ct=clnk&gl=in
Today in class we learnt about the Tower of Hanoi algorithm and how to solve the problem when 4 discs are used.
http://webcache.googleusercontent.com/search?q=cache:xA-NRvipzAYJ:www.towerofhanoi.net/+tower+of+hanoi&cd=9&hl=en&ct=clnk&gl=in
http://webcache.googleusercontent.com/search?q=cache:CfWV2h-cFL4J:en.wikipedia.org/wiki/Tower_of_Hanoi+tower+of+hanoi&cd=1&hl=en&ct=clnk&gl=in
http://webcache.googleusercontent.com/search?q=cache:FEL19xlmhl8J:www.cut-the-knot.org/recurrence/hanoi.shtml+tower+of+hanoi&cd=2&hl=en&ct=clnk&gl=in
Summary: 18 Nov
Blogged by: L N Aggrawal
Today we have discussed about lab work. Suppose if the program is of bubble sort. The question
will be divided in five parts i.e
1. Display the content of array.
Here, Array can be globally or locally initialized. Create a function which display the values of
array.
2. Swap the two values of array.
Here, You have to pass two position of array in a swap function. With using temp variable you
can simply swap the values.
3. One pass of bubble sort.
Here, by using loops and swap function you can perform this operation. The operation is done in
a function onepassbubblesort.
4. Bubble Sort.
Here , in bubblesort function write the code I this function using swap function and loops.
5. Optimization or Switch Flag.
Even we discussed about the if condition concepts. You have to look every aspects of the condition
applied to the expression. Later at the end we discussed about quick sort i.e
1. If there is three arrays. One contains the complete array array1. The other two arrays i.e higher
array which store greater value as compared to first element of array1. The other array lower
contains value less that the first element. How this can be done?
2. How the above will be done using one additional array?
Today we have discussed about lab work. Suppose if the program is of bubble sort. The question
will be divided in five parts i.e
1. Display the content of array.
Here, Array can be globally or locally initialized. Create a function which display the values of
array.
2. Swap the two values of array.
Here, You have to pass two position of array in a swap function. With using temp variable you
can simply swap the values.
3. One pass of bubble sort.
Here, by using loops and swap function you can perform this operation. The operation is done in
a function onepassbubblesort.
4. Bubble Sort.
Here , in bubblesort function write the code I this function using swap function and loops.
5. Optimization or Switch Flag.
Even we discussed about the if condition concepts. You have to look every aspects of the condition
applied to the expression. Later at the end we discussed about quick sort i.e
1. If there is three arrays. One contains the complete array array1. The other two arrays i.e higher
array which store greater value as compared to first element of array1. The other array lower
contains value less that the first element. How this can be done?
2. How the above will be done using one additional array?
Wednesday, November 17, 2010
Which Textbook to buy ?
Review By: Pooja Jaiswal
I was asked to refer three books
Book analysis for the topics- quick sort, linked list and exercises
QUICK SORT-
For the topic quick sort, after referring three books - best
explanation in schaum’s series.
Schaum’s series, has a good example explaining the process of sorting. It also has clearly mentioned the directions to scan the elements of an array to be sorted .it also explain about the positions of interchanged elements. Even the algorithm explained is understandable, if once gone through.
In the other reference, forouzan the topic is explained good as well. it will be useful to refer it if one wishes to look on more details on quick sort method. This book explains about the method of finding the median of three, median left.
A figure 11-16 –quick sort operation explains gives a idea of dividing the array and then comparing the elements with pivot element and then again dividing into sub lists.
While in yeshwant kanitakar, the explanation of quick sort is merely explained in words but no supportive example.
LINKED LIST-
In forouzan, the linked list is given in a good manner . it has first, a short description of all algorithms and then explaining them in details. Algorithms to create list, insert node, delete node, empty list etc. are given .it proves to be a useful reference.
In kanitakar,linked list is given in such a way that it explains about the various operations on linked list by giving programs for each operation while the algorithms are explianed only through figures.
Linked list in schaum’s series is also given good. It has algorithms on various operations. No programs are given for it but .
EXERCISE –
looking for the exercise on linked list ,it can be said that forouzan holds different type of questions based on different situation in linked list. And the programming questions are also given. And similarly in schaum’s series the exersices are equally good . it covers figure based questions, programs for different operations on linked list .
so , the conclusion is , the choice is yours..but I recommend forouzan to refer the data structures for this semester . I feel this book will be useful in every aspect .
I was asked to refer three books
- Forauzan and Gilberg
- Schaum’s Series
- DS by Yeshwant Kanitkar
Book analysis for the topics- quick sort, linked list and exercises
QUICK SORT-
For the topic quick sort, after referring three books - best
explanation in schaum’s series.
Schaum’s series, has a good example explaining the process of sorting. It also has clearly mentioned the directions to scan the elements of an array to be sorted .it also explain about the positions of interchanged elements. Even the algorithm explained is understandable, if once gone through.
In the other reference, forouzan the topic is explained good as well. it will be useful to refer it if one wishes to look on more details on quick sort method. This book explains about the method of finding the median of three, median left.
A figure 11-16 –quick sort operation explains gives a idea of dividing the array and then comparing the elements with pivot element and then again dividing into sub lists.
While in yeshwant kanitakar, the explanation of quick sort is merely explained in words but no supportive example.
LINKED LIST-
In forouzan, the linked list is given in a good manner . it has first, a short description of all algorithms and then explaining them in details. Algorithms to create list, insert node, delete node, empty list etc. are given .it proves to be a useful reference.
In kanitakar,linked list is given in such a way that it explains about the various operations on linked list by giving programs for each operation while the algorithms are explianed only through figures.
Linked list in schaum’s series is also given good. It has algorithms on various operations. No programs are given for it but .
EXERCISE –
looking for the exercise on linked list ,it can be said that forouzan holds different type of questions based on different situation in linked list. And the programming questions are also given. And similarly in schaum’s series the exersices are equally good . it covers figure based questions, programs for different operations on linked list .
so , the conclusion is , the choice is yours..but I recommend forouzan to refer the data structures for this semester . I feel this book will be useful in every aspect .
Thursday, November 11, 2010
Class 5 : 11-Nov
Blogged By: Joshy Joseph
In today’s class we discussed singly linked and the doubly linked list. And also the ways of deleting and freeing the memory space of such elements without extensive traversal within the list.
In today’s class we discussed singly linked and the doubly linked list. And also the ways of deleting and freeing the memory space of such elements without extensive traversal within the list.
Wednesday, November 10, 2010
Class 4 : 10-Nov
Blogged By: Makrand Ballal
Today we have discussed about various methods of sorting. Basically these methods are the unconventional methods of sorting. We discuss these as a part of developing the logic for the programming. Today we have discussed many questions of sorting numbers in an array.
Q. In how many steps (condition and swap) can you sort three numbers
Q. How can we sort 4 numbers in 5 steps.
Q. We use a coin toss to decide between two choices. How many times do we have to toss do decide between 4 choices.
Q. We use a coin toss to decide between two choices. How many times do we have to toss do decide between 3 choices and how.
Q. Next we discussed one question in which there is an array which has numbers from 1025901 to 1025964 in random order. How to sort this array in O(n) ?
Q. If an array contains 100 numbers with only 3 distinct values. How to sort this array in O(n) ?
Students were able to device ways to solve the problems given. Some students also found ways to Solve the 3 way tossing problem in a completly out of box way in which Sir had also not envisaged
Today we have discussed about various methods of sorting. Basically these methods are the unconventional methods of sorting. We discuss these as a part of developing the logic for the programming. Today we have discussed many questions of sorting numbers in an array.
Q. In how many steps (condition and swap) can you sort three numbers
Q. How can we sort 4 numbers in 5 steps.
Q. We use a coin toss to decide between two choices. How many times do we have to toss do decide between 4 choices.
Q. We use a coin toss to decide between two choices. How many times do we have to toss do decide between 3 choices and how.
Q. Next we discussed one question in which there is an array which has numbers from 1025901 to 1025964 in random order. How to sort this array in O(n) ?
Q. If an array contains 100 numbers with only 3 distinct values. How to sort this array in O(n) ?
Students were able to device ways to solve the problems given. Some students also found ways to Solve the 3 way tossing problem in a completly out of box way in which Sir had also not envisaged
Class 2 : 8-Nov
Blogged By : Tincy T Mannoor, Minnu Jose
This day we learnt about the various types of sorting techniques which included Selection sort, Insertion Sort, Bubble Sort and Binary Search.
This day we learnt about the various types of sorting techniques which included Selection sort, Insertion Sort, Bubble Sort and Binary Search.
Sunday, November 7, 2010
Why Learn Data Structures
Blogged By : Jibrael Jos
Are you planning to be in Software Development line ? Do you plan to code ?
Every program you will ever write does requires some memory usage, may it be simple variables, arrays, structs or maybe even complicated structures like Adjacency List.
Are you planning to be in Software Development line ? Do you plan to code ?
Every program you will ever write does requires some memory usage, may it be simple variables, arrays, structs or maybe even complicated structures like Adjacency List.
Subscribe to:
Comments (Atom)