BlogPost_206

• Tell us about something you learned this week.

Learned a few of the different sorting algorithms that exist and made one from scratch.

• What are the pros and cons of immutability?

Advantages:

• Each function is easier to understand because it uses only other public functions and its own private variables.
• The code is easier to parallelize. For example, multiply calls can run in parallel, without the risk of interference. 

Disadvantages :

• It takes more memory. Each function uses its acc accumulator, so the functional version requires twice as much memory as the imperative version.
• The application state is stored in a single object, store, which cannot be edited directly.
• To change the state of the application, you need a function, reducer, which takes as input a state and an action (an object that declaratively describes a change) and returns the following state in return.

• How can you achieve immutability in your own code?

The immutability is a very highly exploited concept in functional programming languages, where the values of the variables do not change when assigned. This has the merit of simplifying the administration of the application state by reducing the number of shared variables.

• What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used?

Divide and Conquer is an algorithmic paradigm. A typical Divide and Conquer algorithm solves a problem using following three steps.

1. Divide: Break the given problem into subproblems of same type.
2. Conquer: Recursively solve these subproblems
3. Combine: Appropriately combine the answers

Quicksort is a sorting algorithm. The algorithm picks a pivot element, rearranges the array elements in such a way that all elements smaller than the picked pivot element move to left side of pivot, and all greater elements move to right side. Finally, the algorithm recursively sorts the subarrays on left and right of pivot element.

Merge Sort is also a sorting algorithm. The algorithm divides the array in two halves, recursively sorts them and finally merges the two sorted halves.

• How do Insertion sort, Heapsort, Quicksort, and Merge sort work?

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

1. Always pick first element as pivot.
2. Always pick last element as pivot (implemented below)
3. Pick a random element as pivot.
4. Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Merge Sort is also a sorting algorithm. The algorithm divides the array in two halves, recursively sorts them and finally merges the two sorted halves.

• What are the key advantages of Insertion Sort, Quicksort, Heapsort and Mergesort? Discuss best, average, and worst case time and memory complexity.

Insertion sort: Simple implementation. Efficient for (quite) small data sets. Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions.

The quick sort is regarded as the best sorting algorithm. This is because of its significant advantage in terms of efficiency because it is able to deal well with a huge list of items. Because it sorts in place, no additional storage is required as well

Efficiency. The Heap sort algorithm is very efficient. While other sorting algorithms may grow exponentially slower as the number of items to sort increase, the time required to perform Heap sort increases logarithmically. This suggests that Heap sort is particularly suitable for sorting a huge list of items.

Merge sort is not in place because it requires additional memory space to store the auxiliary arrays. The quick sort is in place as it doesn't require any additional storage. Efficiency : Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets.

• Explain the difference between mutable and immutable objects.

Mutable objects have fields that can be changed, immutable objects have no fields that can be changed after the object is created.

A very simple immutable object is a object without any field. (For example a simple Comparator Implementation).

class Mutable{
  private int value;

  public Mutable(int value) {
     this.value = value;
  }

  //getter and setter for value
}

class Immutable {
  private final int value;

  public Immutable(int value) {
     this.value = value;
  }

  //only getter
}

• What is an example of an immutable object in JavaScript?

The Object.freeze() method freezes an object. A frozen object can no longer be changed; freezing an object prevents new properties from being added to it, existing properties from being removed, prevents changing the enumerability, configurability, or writability of existing properties, and prevents the values of existing properties from being changed. In addition, freezing an object also prevents its prototype from being changed. freeze() returns the same object that was passed in.