Forem: Chet Chopra

Recursion

Chet Chopra — Thu, 10 Oct 2019 19:34:58 +0000

To understand recursion you must first understand recursion

Hopefully this joke makes sense by the end of this!

A bit of background

Before we dive into recursion let’s go over some concepts that you’ll need.

What happens when you call a function?

When a function is called an execution context is placed on the call stack.

What is the call stack?

The call stack is a pretty deep topic but for our purposes just know that it keeps track of what function is being executed.

What is an execution context?

Don’t worry about it. Just know that when you call a function you are putting instructions, variables, and parameters onto for that function call onto the call stack.

What is a Stack?

A stack is a data structure that follows the first in last out procedure. Imagine, that you have a stack of plates. You can place one plate on top of the other and to remove a plate there must be no plates on top of it. With that in mind we know that the first plate we put down will be the last one we get we get out because we have to remove the plates on top of it first.

# Ruby
def speak
  sayWords
end
def sayWords
  return "Hello there"
end
puts speak
#output --> "Hello there"

#Call Stack
#1. sayWords --> Speak calls sayWords so that gets placed on the stack as #well
#0. speak --> Our program begins by calling speak so it gets placed on #the stack

The thing to note is that we call speak which calls sayWords but speak doesn't finish until sayWords finishes.

Recursion

Recursion is the repeated application of a procedure. In software we see this concept in recursive functions.

A recursive function is a function that calls itself…Let's play with that idea.

# Ruby 
def addUp
  addUp
end
#output --> Stack Overflow Error

We get an error here because the function is endlessly calling itself creating an infinite loop. This loop continues until the call stack is full and throws you a stack overflow error.

At this point this idea seems pretty useless. Buts lets say we add a condition or a base case to this behavior.

# Ruby 

def count_down(num)
  if num == 0
    return
  else
    puts num
    count_down(num - 1)
  end
end
count_down(3)

#output 
#--> 3
#--> 2
#--> 1
#Call Stack
#3. count_down(0)
#2. count_down(1)
#1. count_down(2)
#0. count_down(3)
#What's going on
#Call to count_down(3)
#puts 3 

# Note that count_down(3) still isn't done because its waiting for #count_down(2) 
#Call to count_down(2)
#puts 2
#Call to count_down(1)
#puts 1
#Call to count_down(0)
#Base Case Hit
#return to count_down(0)
#count_down(0) execution complete
#count_down(1) execution complete
#count_down(2) execution complete
#count_down(3) execution complete
#COMPLETE!

Let’s do the same without recursion.

# Ruby 

def count_down(num)
  while num != 0
    puts num
    num -= 1
  end
end
count_down(3)

#output 
#--> 3
#--> 2
#--> 1
#Call Stack
#0. count_down(3)

Why should you use recursion?

You probably shouldn’t. In most situations you can accomplish the same with a loop. Also, since recursion leverages the call stack the program could run into a stack overflow error.

However recursive solutions can be more elegant to read. It’s said that recursive solutions divide and conquer the problem by turning a large problem into a series of smaller ones. Let’s take a look at an example.

Example

The function we want to write takes in two numbers, multiplies them, and returns the value. The catch is that you can’t use the * operator.

So our large problem is multiplication and we will use a series of additions to solve it.

Regular Function

def multiply(num1, num2)
  result = 0
  num1.times do
    result += num2
  end
  return result
end
multiply(5, 4)

#output --> 20
#Call Stack 
#0. multiply(5, 4)

Recursive Function

def multiply(num1, num2)
  if num1 == 0
    return 0
  else 
    return (num2 + multiply(num1 - 1, num2))
  end
end
multiply(3, 2)
#output --> 30

#Call Stack
#3. 2 + multiply(0, 2)
#2. 2 + multiply(1, 2)
#1. 2 + multiply(2, 2)
#0. multiply(3, 2)
#What's going on
#Call to multiply(3, 2)
#Call to 2 + multiply(2, 2)
#Call to 2 + multiply(1, 2)
#Call to 2 + multiply(0, 2)
#Base Case Hit
#0 returned to 2 + multiply(0, 2) --> 2 + 0
#2 returned to 2 + multiply(1, 2) --> 2 + 2
#4 returned to 2 + multiply(2, 2) --> 4 + 2
#6 returned to multiply(3, 2)

That was a brief intro into recursion!

Resources

https://en.wikipedia.org/wiki/Call_stack?source=post_page-----5156e152a608----------------------

https://www.freecodecamp.org/news/recursion-is-not-hard-858a48830d83/?source=post_page-----5156e152a608----------------------

https://www.valentinog.com/blog/context/?source=post_page-----5156e152a608----------------------

https://www.geeksforgeeks.org/recursion/?source=post_page-----5156e152a608----------------------

NAtUrE CaN prOgRAM

Chet Chopra — Sat, 05 Oct 2019 18:25:54 +0000

My hope is that by the end of this you will believe that nature can program. I had originally picked one topic for this post but I quickly realized that I had gone all over the place. So please join me on this directionless journey.

Problem Solving

There are many different ways to solve the same problem. But let's talk about the problem solving framework or process in an extremely general sense. The framework below demonstrates an indirect problem solving process.

From this we can see that we have a problem, and through analysis we can come up with a representation of a problem. Then, from this representation of a problem we can design a representation of a solution. If we implement then hopefully we will have a working solution!

This seems like a pretty simple process but it holds a lot of power. Because this is so general and abstract we can mix problems and solutions from different fields of study. One field of study in particular is biology or the natural world.

“Nature is the most complex system known to man and it contains countless designs in the form of the biological species and environmental phenomena that make our world unique.”- (( Steven A. Korecki, 2008))

Biomimicry

“Biomimicry is a maturing science of studying the designs, processes, and phenomena in nature as a source of inspiration for human creations. It acknowledges nature as a model for us to imitate, a measure for us to evaluate our designs, and a mentor from which we can learn.” - ((J. M. Benyus, 2002))

So in a simpler sense, the core idea behind biomimicry is that nature has already come up so solutions or processes for solving problems. Why not apply them to how we engineer things today.

Let’s look at some examples

In 1989 Japan’s Shinkansen bullet train had a problem. The issue was that it was really fast which is great if you want to get to work on time but bad if you’re coming out of a tunnel. The train would exit the tunnel with a sonic boom which could be heard from 400 meters away. This is bad for dense residential areas. So an engineering team was brought in to design a quieter, faster, and more efficient train. Luckily the general manager of this team, Eiji Nakatsu, was a bird watcher.

Different components of the redesigned bullet train were modeled after different birds.

Owls inspired the pantograph, the rig that connects the train to the electric electric wires above. The new pantograph was modelled after their feathers. Using the same serrations and curvature that allows Owls to catch prey quietly.

The Adelie Penguin, whose smooth body allows it to swim effortlessly, inspired the pantographs supporting shaft lowering wind resistance.

The kingfisher, whose unique beak shape allows it to catch prey in the water without a splash, inspired the nose of the new train.

Sourced from Vox on YouTube.com https://www.youtube.com/watch?v=iMtXqTmfta0

In the end the engineering team had made a train that was 10% faster, used 15% less energy, and stayed under the noise limit in residential areas.

All information regarding the bullet train was sourced from the Vox Channel
https://www.youtube.com/watch?v=iMtXqTmfta0

How does this relate to programming?

Much like the engineers of the train used nature to solve their problems, we as programmers can do the same.

The study of Evolutionary Computing

Genetic Algorithms

Genetic algorithms mimic the process of natural selection. Which means that those who adapt best to their environment will survive. Aka survival of the fittest.

How they work?

Individuals in a population compete for resources and mate
Those individuals who are successful (fittest) then mate to create more offspring than others
Genes from “fittest” parent propagate (trickle down) throughout the generation
Then each successive generation is more suited for their environment

Genetic Algorithm Example

Let’s say that you’re working in an environment where animals are represented as strings. Let’s call them string animals and the king (fittest) of all strings is the (Representation of the behavior you want to achieve) target = “Puffin”. Each character in the string correlates to a specific trait that that string animal has. Traits can be repeated and the order of the traits matters.

— — — — — — — — — — — — P→ “ Polite ” — — — — — — — — — — — — — —
— — — — — — — — — — — — U→ “ Understanding ” — — — — — — — — — —
— — — — — — — — — — — — F→ “ Fun ” — — — — — — — — — — — — — —
— — — — — — — — — — — — F→ “ Fun ” — — — — — — — — — — — — — —
— — — — — — — — — — — — I→ “ Intelligence ” — — — — — — — — — — —
— — — — — — — — — — — — N→ “ Nice ” — — — — — — — — — — — — — —

All of a sudden the environment changes and the fittest string is no longer the Puffin and it is now the target= “Rabbit”. So the rest of the string animals must evolve into Rabbit’s as well. We can use natural selection modeled by a genetic algorithm to do this.

Terms

A Population is a group of string animals.
A Chromosome is a string animal.
A Gene is one letter/characteristic of the string animal

Selection Operator

The fittest (best fitness score) individuals are selected to pass on their genes. So our string animals will get a ranking based on how close they are to matching the exact string of “Rabbit”. The best will be selected.

Crossover Operator

Mating happens. Two string animals are chosen and chunks, crossover points, or sub-strings are randomly selected. The selected chunks will recombine into a new string animal child.

Mutation Operator

Random genes are inserted. Nature has randomness. We want this randomness to maintain genetic diversity among all the string animals.

Algorithm Summary

Randomly initialize population
Determine fitness of population
Until convergence (isRabbit?) repeat:

Select parents from population
Crossover and generate new population
Perform mutation on new population
Calculate fitness for new population

You may be thinking “what a stupid way to change a string”. This is true, but we didn’t change the string. We modeled a process that generates a string based on a target.

Genetic Algorithm Usage

Copies image to its left

You can watch a video about this project on Cody Husky on YouTube.
https://www.youtube.com/watch?v=Q-CDOHkQWBw

Here is another one where someone used evolution to drive a car in unity
https://www.youtube.com/watch?v=FKbarpAlBkw&t=196s

So while nature can’t pick up a computer and start programming. We as programmers can and have taken inspiration from nature to solve problems.

References

https://scholarworks.gvsu.edu/cistechlib/?utm_source=scholarworks.gvsu.edu%2Fcistechlib%2F44&utm_medium=PDF&utm_campaign=PDFCoverPages

https://www.geeksforgeeks.org/genetic-algorithms/?source=post_page-----cb393da0e67d----------------------

https://biomimicry.org/?source=post_page-----cb393da0e67d----------------------

A Brief Intro to Multi-Threaded Programming

Chet Chopra — Wed, 25 Sep 2019 21:30:04 +0000

Of course before we start talking about multithreaded programs we need some background information. Even though there is a lot of background information for this concept, we will only discuss the bare minimum.

What is a Thread?

A thread is a sequential flow of control in a program. So it's essentially a sequence a program instructions that are managed by the scheduler so they can be executed.

What is a scheduler?

Don't worry about it for now. Just know that it's a part of the operating system. There is a link in the references section if you want to know more.

Let's say your working on a system with multiple physical cores or multiple virtual cores in a hyper threaded environment. Multi-Threading is a way of telling your operating system that these are the different threads or chunks of instructions that I want to run on my computer. The operating system (scheduler) is responsible for choosing which thread gets time on the CPU cores whether they are physical or virtual. So if you have a single program running on multiple threads that proposes some interesting issues and some very powerful advantages.

Issue

Take the same code below for example.

Bad Multi-Threaded Code

# include <stdio.h>
# include <stdlib.h>
# include <pthread.h>
# include <unistd.h>
volatile long int a = 0;
void threadOne(void *arg) {
  int i;
  for (i = 1; i < 500000; i++) {
    a = a + i;
  }
}
void threadTwo(void *arg) {
  int i;
  for (i = 500000; i <= 1000000; i++) {
    a = a + i;
  }
}
int main (int argc, char **argv) {
  pthread_t one, two;
  int i;
  pthread_create(&one, NULL, (void*)&threadOne, NULL);
  pthread_create(&two, NULL, (void*)&threadTwo, NULL);
  pthread_join(one, NULL);
  pthread_join(two, NULL);
  printf("%ld\n", a);
}

All this program does is add up all of the numbers from 1 to 190009000. But the catch is that it does it using two threads of execution. So one thread will add up the numbers from 1 to 500,000 and the other from 500,000 to 1,000,000.

Let's run this code multiple times and observe.

Run #1 Output - 370752617319
Run #2 Output - 336751282108
Run #3 Output - 250846382315
Run #4 Output - 314774608001

Hmmm… why do we get different answers every time we run this code? In theory, we should get the right answer in half the amount when compared to using a single thread.

Here is another program that does the same thing but uses only one thread.

Single Thread

# include <stdio.h>
# include <stdlib.h>
# include <unistd.h>
volatile long int a;
int main (int argc, char **argv) {
  int i;
  a = 0;
  for (i = 1; i <= 1000000; i++) {
    a = a + i;
  } 
  printf("%ld\n", a);
}

As expected we get the same value every time. So what is the multithreaded program doing that makes it produce different incorrect answers?

Each thread loads the variable A from memory, makes a local copy, adds a value to it, and then stores it back into A. The issue is that both threads are using the global variable A to add up their numbers but they aren't they aren't working in sync. They could both load variable A at the same time add a value to it then store it back into A. Depending on which one stores the value back to A first, one update will be overwritten by the other.

The solution to this issue would be to synchronize these two threads so that they don't try to operate/access A at the same time. One way to do this would be to use a mutex (mutual exclusion). You can use tokens as an analogy. Let's say that now each thread can only access A if it has the token. This means that if thread one has the token and is working with A, then thread two can not access A and is forced to wait until thread one releases the token.

Let's look at some code

Better but still bad Multi-Threaded Code

# include <stdio.h>
# include <stdlib.h>
# include <pthread.h>
# include <unistd.h>
pthread_mutex_t a_mutex = PTHREAD_MUTEX_INITIALIZER;
volatile long int a = 0;
void threadOne(void *arg) {
  int i;
for (i = 1; i < 500000; i++) {
    pthread_mutex_lock(&a_mutex);
    a = a + i;
    pthread_mutex_unlock(&a_mutex);
  }
}
void threadTwo(void *arg) {
  int i;
  for (i = 500000; i <= 1000000; i++) {
    pthread_mutex_lock(&a_mutex);
    a = a + i;
    pthread_mutex_unlock(&a_mutex);
  } 
}
int main (int argc, char **argv) {
  pthread_t one, two;
  int i;
  pthread_create(&one, NULL, (void*)&threadOne, NULL);
  pthread_create(&two, NULL, (void*)&threadTwo, NULL);
  pthread_join(one, NULL);
  pthread_join(two, NULL);
  printf("%ld\n", a);
}
Run #1 Output - 500000500000
Run #2 Output - 500000500000
Run #3 Output - 500000500000
Run #4 Output - 500000500000

You can see that there are some new lines that lock and unlock the resource from being accessed. Now we get the correct output! But there is still a problem since using threads this way is pointless. It's pointless because while thread one is working with A thread two is forced to wait until thread one releases the resource. In theory this is as slow as using a single thread.

Time to fix it!

Advantage

Good Multi-Threaded Code

# include <stdio.h>
# include <stdlib.h>
# include <pthread.h>
# include <unistd.h>
pthread_mutex_t a_mutex = PTHREAD_MUTEX_INITIALIZER;
volatile long int a = 0;
void threadOne(void *arg) {
  int i;
  long int localA = 0;
  for (i = 1; i < 500000; i++) {
    localA = localA + i;
  }
  pthread_mutex_lock(&a_mutex);
  a = a + localA;
  pthread_mutex_unlock(&a_mutex);
}
void threadTwo(void *arg) {
  int i;
  long int localA = 0;
  for (i = 500000; i <= 1000000; i++) {
    localA = localA + i;
  }
  pthread_mutex_lock(&a_mutex);
  a = a + localA;
  pthread_mutex_unlock(&a_mutex);
}
int main (int argc, char **argv) {
  pthread_t one, two;
  int i;
  pthread_create(&one, NULL, (void*)&threadOne, NULL);
  pthread_create(&two, NULL, (void*)&threadTwo, NULL);
  pthread_join(one, NULL);
  pthread_join(two, NULL);
  printf("%ld\n", a);
}

In this code we are using a local variable called localA in each function. We do this so that thread one will add numbers from 1 to 500,000 to its own localA and at the same time thread two is adding numbers from 500,000 to 1,000,000 to its own localA. After one thread is done adding it will lock A, update it, then unlock it so the next thread can use it. So now we have significantly reduced the time one thread waits on the other. In theory this should run twice as fast as opposed to using a single thread.

References

This blog is based off of a great video on Youtube made by Computerphile

https://youtu.be/7ENFeb-J75k

https://pdfs.semanticscholar.org/a23b/22fb7bc0286101bdf4794e1e61bcad2fa896.pdf

https://en.wikipedia.org/wiki/Scheduling_(computing)

Technology and Medicine

Chet Chopra — Wed, 25 Sep 2019 21:17:27 +0000

Why

The why here is about why I am choosing to write about this topic. While I feel like this topic has already been pretty well explored. I also feel like many people could benefit from re-exploring how technology has impacted the face of medicine. I hope to give the reader an appreciation for how things have been accelerated and to provide them with hope if needed.

This article will adhere to the following format

Increased Outreach / Communication
3D Printing
Big Data

Increased Outreach and Communication

As we all could've all guessed, by how long we've had to wait to see a doctor, they are very busy people. With that being said before technology really came into play in the medical field it was difficult for doctors to easily reach patients and vice versa. Now through the power of the internet and web applications, technologies focused on improving the link in between patients and doctors have emerged.

In the past one might have had to wait for a letter to come in the mail or a phone call discussing results of tests. With mail the issue is that you have to wait a couple days for it to arrive and with a phone call you can only go into so much detail.

Now, apps like Medici and SoundCare have removed these barriers and improved the overall communication in between patients and doctors. These apps have allowed secure messaging, appointment requests, lab result sharing, documenting personal information, and even voice communication. This has allowed patients to ask health related questions easily and has let doctors answer those questions in less time than before.

Besides of the convenience of being able to reach your doctor via an app technology has also increased outreach and communication within the medical community as well.

Let's play a bit of pretend. You are now a doctor (hooray), and a patient has come in with an issue you just can't seem to diagnose. In the past a doctor may have continued to struggle with diagnosis or just sent the patient home without one. Now, you as a doctor can use medical reference apps such as Epocrates and Medscape to assist with diagnosis. If that also doesn't help you can reach out to a vast community of doctors from all over the world via a forum, blog, or email. Someone somewhere has probably seen something similar and with technology the distance from you and that someone is no longer an issue.

3D Printing

3D printing has an ever growing number of applications in many industries and the medical industry is no exception.

Kaiser Permanente's Los Angles Medical Center is perfecting the use of 3D printing to replicate multidimensional models of problematic areas inside patients. Surgeons can handle the models and simulate a variety of possible operation replicas before performing the actual surgery.

3D printing goes beyond just helping surgeons prepare for surgery, it also helps the handicap-able. A prosthetic hand can cost thousands of dollars; however, a 3D printed prosthesis could be made for as little as $50. 3D printing materials cannot yet replace the long-term durability of traditionally-made prostheses. However, this will soon change. In the meantime, technology is making cost-effective prosthetics a reality and encouraging creative people from all over the world to participate in their design.

Researchers are also working on the ability to 3D print bones and organs as replacements for people. Research is currently being conducted on artificial heart, kidney, and liver structures, as well as other major organs. Some printed organs are approaching functionality requirements for clinical implementation, and primarily include hollow structures such as the bladder, as well as vascular structures such as urine tubes. So its not there just yet, but we can imagine a future where someone could print you a kidney instead of giving you one of theirs.

Big Data

Big data has become bigger and bigger in recent years. It seems that in modern times data is everything, especially in the medical industry. It can help diagnose a patient and also provide more accurate diagnosis based on the data collected.

IBM research teams say that the same super-computer that won a game of Jeopardy in 2011 is now being used to help physicians make more accurate diagnoses and recommend treatments.

Resources

https://www.hunimed.eu/news/technology-changing-world-medicine/
https://www.amputee-coalition.org/3d-printed-prosthetics/
https://en.wikipedia.org/wiki/Organ_printing

Be Lazier

Chet Chopra — Wed, 07 Aug 2019 18:40:05 +0000

Lazy Loading

Do you want to increase the performance of your applications without compromising on user experience?

Fast page loads are absolutely critical for web applications. The initial load time of an app effects everything about the users experience.

- Audience Retention - If they'll stay
- Audience Conversion - If they'll come back
- Overall user experience

Over time users have come to expect an increasingly rich and interactive experience. They want more features, more content, and they want it faster. As developers this means more Javascript, more data sent back and forth, but when we're working with so much more how could we possibly make our application faster. Especially when are devices and network conditions are not the same.

So the problem is we want more, faster. But in general if you want to load faster then you simply load less. This is a total contradiction!
While most strategies for speeding up page load include reducing the size of your initial payload this doesn't mean you need to strip features and content from your app.

You can get pretty far by simply reconsidering what is absolutely critical for the initial load. Do you really need everything all at once to make give the user? Defer the non-critical resources for later.

So instead of having one massive file that you send, try splitting up the resources so that you can deliver them on demand. There are several ways you can do this

- Code Splitting
- Lazy Load images and videos
- Lazy load application data

What is Lazy Loading

At this point you can probably guess what lazy loading is all about. But just to reiterate the main idea behind it, Lazy Loading is loading the content as its needed, not all at once.

Here is a simple example to help solidify the concept.

Let's say you're visiting reddit/r/cats, and ofcourse there are thousands if not millions of cat pictures / content. If reddit was to try to send you all of these when you first visited the site you'd be waiting quite some time before you could look at all your favorite cats. Instead what reddit does is it only sends you a limited amount of cats when you first load the page, after that more and more cats are brought in as you scroll down.

Load on Scroll

This kind of lazy loading works off of an event listener that monitors the scroll bar. When you hit the bottom of the page the event fires thus loading more cats giving the user the feeling of being able to infinitely scroll down the page.

Intersection Observers

We take the idea of only loading what's needed even further by trying to only load what the user is looking at. This behavior can be accomplished by using an intersection observer. For example you can find an Intersection Observer API at here.

The Intersection Observer API lets code register a callback function that is executed whenever an element they wish to monitor enters or exits the viewport, or when the amount by which the two intersect changes by a requested amount.

This does mean that you will need placeholders for all of your content and when the viewport intersects with that placeholder then the callback function is fired. In this call back you perform a fetch to quickly retrieve (typically) one resource to populate the placeholder with. In most circumstances it's faster to fetch one resource rather than 10.

Asynchronous Rendering

While a component is loading or fetching the rendering of it is suspended. That means that the component will only show up when it's ready. While its not ready a fallback component takes its place. There are multiple ways to achieve this behavior.

-High Order Components

React Suspense

import React, { Component, lazy, Suspense } from 'react';
import './App.css';;
const MyComp = lazy(() => import('./components/myComp'));

class App extends Component {
  render() {
    return (
      <div className="App">
        <header className="App-header">
          <div>another component</div>
          <Suspense fallback={<div>Loading.....</div>}>
            <MyComp />
          </Suspense>
        </header>
      </div>
    );
  }
}

export default App;

import React from "react";

export default function myComp() {
  return <div>Hi there I am now loaded!</div>;
};

References

YouTube Channel
techsith - https://www.youtube.com/watch?v=tV9gvls8IP8&list=LL-3Wvw55vza7tgX28XooW1Q&index=18&t=288s

Geeks for Geeks
https://www.geeksforgeeks.org/what-is-lazy-loading/