Day 4

[githubdudu]

Review:

1. Time complexity of DLL operations:
   getFirst, getLast, removeFirst, removeLast, addFirst, addLast, getSize, isEmpty : O(1)
   the rest of methods: O(N)
   We just put the conclusion here. After we learn React hooks: useEffect, useState and so on, we will revisit this.
2. Some reading resource about the feature of linked-list : https://javascript.info/recursion#linked-list

TODAY

1. Two function coding practices.
   1.1 function combineTwoSingleLL
   1.2 function combineTwoDoubleLL
   1.3 function merge
   The code link is here: https://github.com/githubdudu/react-study-group/tree/master/day4.
   You can git clone & git pull to practice them.

This is for:

• Test your understanding of reference type and value type
• Test your understanding of the structure of SLL or DLL
• Improve your coding skill

2. Continue with previous dll.js code.
   add the code: console.log(dll), and console.log(dll.__proto__)
   2.1 try to run dll.js on the console (terminal on your computer/ node environment)
   2.2 try to run dll.js on the browser (client environment)
   Is there any difference in the output? How to explain it?

3. A prototype version of dll.js has been provided. Read the code.

4. Read and study all these:
   https://javascript.info/prototype-inheritance
   https://javascript.info/function-prototype
   https://javascript.info/native-prototypes
   https://javascript.info/prototype-methods

[githubdudu]

5. Recall we learnt the map function of array.

      const array1 = [1, 4, 9, 16];
   
      // Pass a function to map
      let map1 = array1.map((x) => x * 2);
   
      console.log(map1);
      // Expected output: Array [2, 8, 18, 32]
   

   Let's try code below on the console of the browser.
   Execute the code below on the console.

      Array.prototype.map = function(){
          console.log("this array map function has been hacked")
      };

   Then run this line of code again on the console: let map1 = array1.map((x) => x * 2);

   Again, Execute the code below on the console.

      Array.prototype.map = function(){
          this.forEach(() => console.log("this array map function has been hacked, too"));
      };

   Then run this line of code again on the console: let map1 = array1.map((x) => x * 2);

   Explain the output.
   Explain why changing the prototype of a built-in type is not recommended.
   If we have to change the prototype of Array in the project temporarily and then change back to the original prototype, are we able to change it back? If we can, how?
   Another case like above, when Zephyr was learning the JS, he accidentally changed the original map to a wrong function. The original map function has been lost forever. Help him write a version of map function that works just as the original one.
   (this exercise need knowledge of high-order function)

6. Some materials of time complexity.

[githubdudu]

7. Some practice of time complexity estimation. Now you have to learn what is Big Theta (Θ) notation before starting to finish the exercises.

[jinwookuk]

Q1. published to branch "jin_day_4"

Q2. browser shows circular reference of each node (recursion) and details of all prototype methods whereas terminal (Node.js) shows circular reference in simplified way using <ref*1> notation.

...

Q5: *After the first modification, when running map1, instead of performing the usual map, it will show the log "this array map function has been hacked" because the original map function is overridden with console.log("this array map function has been hacked"); After the second modification, when running map1, again, instead of performing the usual map, it will show the log "this array map function has been hacked, too" for each element of the array because forEach() method iterates through all array elements and run the overridden function of console logging "this array map function has been hacked, too".
**This is why changing the prototype of built-in types is not recommended. It can cause unexpected errors and it is really hard to figure out where it's coming from, as developers usually expects built-in types to work as they normally would do. ***We can change the prototype back if the original was saved as a variable like const backedUpMap to assign it back later on, Array.prototype.map = backedUpMap; Otherwise, it can't be restored as the original gets deleted from the memory once overriding function occurs.
****Array.prototype.map = function(callback){ const output = []; for (let i = 0; i <this.length; i++){ output.push(callback(i, this[i], this)); //don't know what the callback function will require as it's parameters, so I included i and this as well.. } return output; }

Q7:
Asymptotics
a. O(1), O(log n), O(n), O(n log n), O(n^2 log n), O(n^3), O(2^n)O(n)^n, O(n!)
b.

1. False, f(n) \in \Theta(g(n))
2. False, f(n) \in O(g(n))
3. False, f(n) \in \Theta(g(n))
4. True
5. False, f(n) \in O(g(n))
6. True
7. False, f(n) \in \Omega(g(n))
   c. Worst case: O(NM), best case: O(N)

Asymptotics Introduction
f1, \Theta(N^2)
f2, \Theta(N)

Asymptotics is Fun!
a) g(N, 1) : \Theta(N),
g(N, 2) : \Theta(N^2)
b) g(N, 2) : \Omega(1), O(2),
g(N, N) : \Omega(1), O(N)

[tiff777]

1. Published to my branch
2. They seem no difference on my view for console.log(dll). However, for console.log(dll.proto), terminal just show a summary for dll ({constructor: ƒ, add: ƒ, addFirst: ƒ, addLast: ƒ, get: ƒ, …}) and cannot be expandable while browser will show an expandable list with detailed function of ddl.
3. First .map can work properly and console log the result as expected. However, after running Array.prototype.map, console log the message and default .map is changed. So when we run let map1 = array1.map((x) => x * 2) again, as function of .map is changed and only log message in the function, undefined will be returned. Similar result is outputted after third time modify.

Based on the above result, it is not recommended to modify the prototype of a built in type. It is because doing this can break the built in method and cause significant issues to existing code. If we need to change the prototype of built in type, I would suggest storing the original method in a reference or temporary variable before making any changes. Then, use this reference for restoring when needed.

7. tbd

[githubdudu]

To Tiffani, Re 3:

My point of view. The capability of modification of the prototype during runtime is a nuclear-level tool. We can utilize this flexibility to perform powerful actions on code that Java couldn't do. Otherwise, like a nuclear weapons, improper use may cause big catastrophes.

[githubdudu]

Hi all, here are answers to the exercise 7: