Javascript is easy, algorithms are harder…
Tell us about something you learned this week.
This week we went over search and sorting algorithms. These are useful for accessing specific parts of data that you’d like to manipulate, or more specifically sort.
What are the pros and cons of immutability?
The definition of an immutable object is one that cannot be changed once it has been created. So the obvious pros are that you can use immutability to create things that cannot be altered on accident. The cons seem to fall in line with the pros where you have objects that cannot be changed so if you are creating an immutable object without intending to do so, it could cause some code breaking bugs.
How can you achieve immutability in your own code?
You could use Classes to create instances of the objects you have designed. This way the initial blueprint never mutates and the new objects all can share the properties of their ‘parent’ object.
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?
Algorithms designed based on multi-branched recursion. They work by recursively breaking down an argument into two or more sub-problems, and continuing this until the problem can be solved directly. This could be used when manipulating an immense amount of data and having to organize it a specific way.
How do insertion sort, heap sort, quick sort, and merge sort work?
Insertion sort is a comparison algorithm that compares the current value you are trying to place with others values within the same array. It does this by working with one item at a time, and iteratively places each item into the right order in the array.
Heap sort is a comparison based sorting technique based on a Binary Heap data structure. A Binary Heap is a complete Binary Tree where where items are stored in a special order such that the value in a parent node is greater than the value of its two children nodes. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Quick sort divides elements into smaller parts based on some condition and performing the sort operations on those divided smaller parts. It is one of the most commonly used sort algorithms in javascript.
Merge sort compares entire arrays as opposed to individual elements in the arrays. It works to break the sorting down into sub-problems and recursively continue to break those down until we have a lot of simple problems that we can easily put back together.
What are the key advantages of insertion sort, quick sort, heap sort and merge sort? Discuss best, average, and worst case time and memory complexity.
The key advantages are the time complexity they provide for specific instances. If you are trying to achieve big O notation, choosing the correct sort algorithm is key. These concepts are daunting as someone unfamiliar with computer science and take a lot of practice to grasp the intricacies, even though they make sense as a concept. Time and memory complexity refer to the amount of time and the amount of memory taken to complete a function. They range from Linear Time, O(n), Constant Time, O(1), and Quadratic time, O(n²).
Explain the difference between mutable and immutable objects.
If an item is mutable, modifying the copy will also modify the original. Immutable objects do not modify the original if a change is made to the copy.
What are the three laws of algorithm recursion? Describe them in your own words and what they mean to you.
A Recursion Algorithm:
- They must have a base case.
- Must change its state and move towards the base case
- Must call itself, recursively
A base case is just a condition that allows the algorithm to stop recursing, an escape route or end condition.
The second change state refers to the idea that some sort of data must change within the recursion that allows us to move towards the base case, maybe a number incrementing down to 0.
The final law is just the definition of recursion, it must call itself.
