This course introduces some basic data structures (arrays, linked lists, stacks, queues, trees and heaps) and algorithms (various sorting algorithms, and algorithms for operations on binary search trees and heaps). We will also cover recursion in this course. Use of graphics and animations makes the lectures very easy to understand and digest. After taking this course, you will loose your fear for data structures and algorithms.
Analysis of Algorithms
Basic Sorting and Search Algorithms
Linked Lists
-
17Selection Sort
-
18Selection Sort : Pseudocode
One of the problems that people face in writing algorithms is how to translate their thoughts into a programming language. Many people cannot even start writing the very first statement of an algorithm. I suggest that if you are having such trouble, don't try to solve the whole problem together, rather break it down into smaller, easier parts. For e.g. try doing the following in writing code for the selection sort algorithm -
- First try to write a method, which just finds the minimum number in the data array. Don't think about anything else, just that method. If you write it in a different method, then you may need to pass the data array as a parameter to that method. Return the index of that minimum element from this method.
- Now change the method to find the minimum number STARTING FROM A PARTICULAR INDEX. So you will need to pass this index as a parameter.
- Write another method which can swap items in an array, located at two different indexes. What parameters should be passed to this method?
Hopefully, by this time you will have enough clarity on completing the sorting algorithm, if you understood the pseudo code.
-
19Introduction to Insertion Sort
-
20Applying Insertion Sort algorithm to cue balls
-
21Insertion Sort: Pseudocode
-
22O(n²) sorting algorithms - Comparison
-
23In place sorting
-
24Stable Vs Unstable Sorts
-
25Searching elements in an un ordered array
-
26Searching elements in an ORDERED array
-
27Searching elements in an ORDERED array - contd.
-
28Inserting and Deleting items in an ORDERED array
-
29Sorting any type of object
Try to write generic sort methods, like shown in the InsertionSortWithGenerics.java, for Bubble sort and Selection sort algorithms as an exercise. But if you don't want to get into generics at this point, you may choose to skip this section.
-
30Chapter Quiz
-
31Assignment
Stacks and Queues
-
32What is a Linked List?
-
33Implementing a Linked List in Java
-
34Inserting a new Node
-
35Length of a Linked List
-
36Deleting the head node
-
37Searching for an Item
-
38Using java generics to parameterize the LinkedList
-
39Doubly Ended Lists
-
40Inserting data in a sorted Linked List
-
41Doubly Linked List
-
42Insertion Sort revisited
-
43Chapter Quiz
-
44Assignment
Recursion
Binary Search Trees
More Sorting Algorithms
-
65The Tree Data structure
-
66Binary Trees
-
67Binary Search Trees
-
68Finding an item in a Binary Search Tree
-
69Implementing the find method
-
70Inserting an item in a Binary Search Tree
-
71Deleting an Item : Case 1
-
72Deleting an Item - Case 2
-
73Deleting an Item - Case 3
-
74Deleting an Item - Soft Delete
-
75Finding smallest & largest values
-
76Tree Traversal : In Order
-
77Tree Traversal : Pre Order
-
78Tree Traversal : Post Order
-
79Unbalanced Trees Vs Balanced Trees
-
80Height of a Binary Tree
-
81Time Complexity of Operations on Binary Search Trees
-
82Chapter Quiz
-
83Assignment