Data Structures and Algorithms using JAVA

A data structure is a named location that can be used to store and organise data. An algorithm is a collection of steps to solve a particular problem. Data structures provide a means to manage large amounts of data efficiently.

• In the first week of this course, you will learn:
  
  • Stack memory vs heap memory in Java
  • Physical vs logical data structure
  • Abstract data types and data structures
  • Complexity analysis
  • Asymptotic analysis, comparison of functions, recurrence relations
    
    • Time complexity
    • Space complexity
    • Master theorem
    • Amortized analysis
    • Iteration Vs recursion
  • Recursion - Factorial, Fibonacci, finding nCr, tower of Hanoi problem.

Arrays are used to store multiple values in a single variable, instead of declaring separate variables for each value. A string is a sequence of characters like - "hello".

• In this session, we will learn about:
  
  • Arrays
    
    • Static arrays
    • Dynamic arrays
    • 2D arrays, row-major and column-major mapping, matrices
    • Strings
  • LinkedList
    
    • Singly LinkedList and its operations
    • Doubly LinkedList and its operations
    • Circular LinkedList and its operation

The stack is a linear data structure that is used to store a collection of objects. It is based on Last-In-First-Out (LIFO).

• In this session, we will be discussing about:
  
  • Stacks
    
    • Implementations- using arrays, using linked lists
    • Operation
    • Applications
  • Queues
    
    • Implementations- using arrays, using a LinkedList, using two stack
    • Circular queues
    • Priority queues

A tree is a non-linear data structure where data objects are organised in terms of hierarchical relationships. In this week's session, we’ll be discussing them one by one.

• In this week, we will discuss about
  • Trees.
    
    • Binary trees, their representations
    • Pre-order, In-order, post-order traversal
    • Binary search trees
    • AVL trees

Heap and Trie are special cases of trees. A heap is a special tree-based data structure in which the tree is a complete binary trees.

• In the session, we will discuss about
  • How to solve the longest word in the dictionary problem using tries.
  • Heaps
    
    • Min Heap
    • Max Heap
    • Find K largest (or smallest) elements in the array
  • Tries
    
    • Longest Word in Dictionary Problem

A graph is a data structure that consists of a finite set of vertices, also called nodes and a finite set of ordered pairs of the form (u, v) called edges.

• In this week's session, We will be discussing different types of algorithms, like:
• Graphs
  
  • Types of graphs
  • Breadth-first search, depth-first search
  • Topological sort
  • Shortest path problem
• Algorithms
  
  • Dijkstra's algorithm
  • Bellman–Ford algorithm
    
    • Minimum spanning tree problem
    • Prim's algorithm
  • Kruskal's algorithm

• In this week, we will discuss about
  • Sorting-
    
    • Types of sorting techniques
      
      • Bubble sort
      • Insertion sort
      • Selection sort
      • Quick sort
      • Merge sort
      • Heap sort
      • Count sort
      • Bucket sort
      • Radix sort
      • Shell sort

Searching is probably one of the most common actions performed in a regular business application. This involves fetching data stored in data structures like arrays, lists, and maps. Hashing is the process of converting a given key into another value. A hash function is used to generate the new value according to a mathematical algorithm.

• During this week we will be discussing the following:
  
  • Searching
    
    • Linear search
      
    • Binary search
      
  • Hashing
    
    • Hash function
      
    • Collision handling
      
  • Chaining
    
  • Open addressing
    
    • Linear probing, primary clustering
      
    • Quadratic probing, secondary clustering
      
  • Double hashing

A greedy algorithm is a simple, intuitive algorithm that is used in optimization problems.

• The topics discussed in this session will be-
  
  • The strategy of greedy algorithms
  • Elements of greedy algorithms
  • Advantages of greedy algorithms
  • Disadvantages of greedy algorithms
  • Applications of greedy algorithms
  • Knapsack problem
  • Job sequencing with deadlines
  • Huffman coding

The divide and conquer approach is pretty straightforward, the problem at hand is divided into smaller subproblems and then each problem is solved independently. As we keep dividing the subproblems into even smaller problems, we eventually reach a stage where no more division is possible.

• In the session this week, we will discuss:
  
  • The strategy of divide and conquer techniques
  • Advantages of divide and conquer techniques
  • Disadvantages of divide and conquer techniques
  • The master theorem of divide and conquer techniques
  • Applications of divide and conquer techniques
  • Find the median of two sorted arrays
    

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally.

• We’ll discuss two methods used to backtrack.
  Backtracking-
  
  • Brute force approach
  • N queens problem
• After backtracking, we will be studying how Java 8 collections framework is implemented. We will be covering the following,
  
  • Set
  • List
  • Queue
  • PriorityQueue
  • Map
  • HashSet
  • TreeSet
  • ArrayList
  • LinkedList
  • Vector
  • Dictionary
  • Stack

Dynamic Programming is also an algorithmic technique for solving optimization of problems. It is done by breaking the problem down into simpler subproblems, and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

• During this session, we will be covering the following:
  
  • Dynamic programming-
    
    • The strategy of dynamic programming
    • Properties of dynamic programming
    • Approaches of dynamic programming
    • 0/1 knapsack
    • Travelling salesman problem
    • Floyd Warshall
  • In the end, we will conclude and summarize the course by having a brief discussion on
    • Greedy vs Divide & Conquer vs Dynamic
    • Programming examples