Oh wow. It's been a long while since I've blogged here. It's been a long time too, since I've belonged to an academia, or even dared to dream of university. Back in highschool, when geometry honors and pre calc were easy and full of joy to explore, I wanted to go to MIT. Everything I kept up on, was happening in MIT. AI, Robotics, all the things that were cutting edge were seemingly happening at MIT. Brilliance was what I thought of them.

Fastforward and I'm a community college drop out with school debt living on government benefits struggling to understand the basic concepts of ACE or really any Object Oriented Language assisted Engine (like Unity, and so on).

I had known about MIT open coarse-ware since I was enrolled in physics at a community college. I would watch a lecture on Electromagnetism every night, amazed with the content, thinking how cool it would be to use the information to build an electronic device never before seen. I ended up making a aluminium foil capacitor that held 2 volts for .25 seconds

 

Now I'm here, finishing some reading on a MIT press book, Introduction to Algorithms.

 

It's great. It talks about how the book is meant for not only a student teacher relationship, but also a reference manual for professional programmers, to help in creation/learning to create algorithms that always produce a given output from a provided input, are time efficient based on the resources available to execute the information, and without error. It's also a huge plunge into parts of math that remain unexplored for me. Like Weirmer functions, or newtons method, and some of finite math that's since slipped my mind after having tutored university students in the field.

 

The first hurdle was getting the text book. It could not just be an ebook, I want to read it anywhere, and the entire planet isn't guaranteed to have the internet. And as I have learned, it may take me a long while to read all of what the book has to offer, the coarse I am following only has 25 lectures that cover a handful of chapters, wheras the book has a lot more chapters to offer. mainly the exploration of mathematics in it is of firm intrigue to me, should it suffice to be able to construct a method in ruby of it's principles, I should have no problem with the contents.

 

Mom got me the book for an early birthday present. It's very well over 1200 pages. Just the preface alone was cause for me to desire to read chapter 1 the very next morning. All with the delighted hope of learning to craft algorithms that could solve and explore new aspects of reality for me.

 

I began reading, and writing the exercises.

 

Quote

Exercises:

1.1-1

Give a real-world example that requires sorting or a real-world example that requires computing a convex hull

 

 

1.1-2

Other than speed, what other measures of efficiency might one use in a real-world setting?

 

 

1.1-3

Select a data structure that you have seen previously and discuss its strengths and limitations.

 

1.1-4

How are the shortest-path and traveling-salesman problems given above similar? How are they different?

 

1.1-5

Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is ‘approximately’ the best is good enough.

 

I couldn't help be so excited about the idea of learning once more, in a field so vastly unlearned and yet so rewarding, that I upset a contact in a discord server. They ended up giving me a link to another discord server that focused on programming in general. I couldn't help but ignore the feeling of total devistation in having pissed someone off, for having found people that could help me grade myself as I progressed, so that I could correct myself and better apply my knowledge on the subjects in the book.

Things checked out on my end for the answers.

 

Such a short section with so much useful information, I had to keep going.

 

Quote

1.2-1

Give an example of an application that requires algorithmic content at the application level, and discuss the function of algorithms involved.

 

 

1.2-2

Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion runs 8n² steps, while merge sort runs in 64n lg n steps. For which values of n does insertion sort beat merge sort?

 

 

1.2-3

What is the smallest value of n such that an algorithm whose running time is 100n² runs faster than an algorithm whose running time is 2ⁿ on the same machine?

 

 

after more principles, I had failed to realize something that should have been obvious, involving the direction of the book.

 

regardless, I did my first problem of the book:

Quote

Problems

1-1            Comparison of running time

For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

I probably totally failed it, in that microsecond does not constitute 1000 of itself into a second. Had I paid attention in the non-existent weights and measures class they call elementary science, I would have known. But that's kind of a scaling issue as I found out from my implications.

So one of the functions of f(n) was f(n) = log2(n)

It wasn't so easy to solve. My first assumption was to create real values for n, and not some representative formula. My first attempts did not posses efficiency, because I am so under-educated about RUBY for one. After talking it over with ruby programmers on the server, I had arrived at this method for the solution
 

Quote

def solve(t, factor)
  t = t / factor
   #n1 = 2**t
  n1 = (1..t).inject(1) {|product| product * 2}
  n2 = Math.log2(n1).to_i
  n2 *= factor
  n1 = Math.log10(n1).to_i
  n1 *= factor
  return n1, n2
end

My first thoughts are, why does that work. I still don't know. but if t is say, 2, the answer is 4, and so on, until we have a value where t = 1 second, it becomes large quickly. For a day the number n1 became so large that it was unmanageable for modern RUBY, so I had to introduce a factor. and being a decimal starting with 1 and having no other digit seems to have worked perfectly, scaling according to the t value.

I did this sort of process for all 64 cells of the 8x8 table.

 

Then I woke up and read chapter 2. And immediately was presented with a real world application for insertion_sort. An algorithm that mimics taking a handful of cards, and aligning them in a sequential order such that the elements are from least to greatest or greatest to least. It was also the first time I had seen pseudo code and attempted to use it as a structure for RUBY code.

 

Quote

Insertion sort

for j = 2 to A.length

  key = A[j]

  insert A[j] into the sorted sequence A[1..j-1]

  i = j -1

  while i > 0 and A > key

    A[i+1] = A

    i = i -1

A[i+1] = key

 

I toyed around with it for ages. Before reading the book further, and had hit a dead end. All of my debugging techniques couldn't make sense of the garbled mess of the array my method had made. When I read further, it explained that i = j = e. And its use of A[1..j-1] was saying what would happen in the next loop.

 

def insertion_sort(an_array)
  size = an_array.length
  i = 0
  while i < size
    current = an_array
    j = i
    while j > 0 and an_array[j-1] > current
      an_array[j] = an_array[j-1]
      j -= 1
    end
    an_array[j] = current
    i += 1
  end
  return an_array
end

def insertion_sort(an_array)
  size = an_array.length
  i = 0
  while i < size
    current = an_array[i]
    j = i
    while j > 0 and an_array[j-1] > current
      an_array[j] = an_array[j-1]
      j -= 1
    end
    an_array[j] = current
    i += 1
  end
  return an_array
end

this produced this result:

And what I had mentioned earlier, of this being so obvious now. I had made this function before when I was making Classical Age World. It was my sort method for arranging the NPCs in a 2d array into family trees with relationships. I know on my walmar machine it will bog down on 10K entries. It might be more efficient now with the latest RUBY. the time coefficient being defined as:

* insertion sort – c₁n²

Just from the table I had made, I know that N**2 is really not that great, but isn't the worse efficient coefficient algorithm. The worst on the table being, N!

I went and did the method in GML, and it worked eventually.

 

Now I can happily say I know an algorithm with it's application and relevance in programming. The book had me write an algorith to return Nil when a value is not in the array. To be honest I am not sure I understand the problem thorough.

Quote

Consider the searching problem:

Inuput: A sequence of n number A = (a1,a2,…,an) and a value v.

Output: An index I such that v = A or the special value NIL if v does not appear in A

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties

this was my guess at it

Linear search:
For j = 0 to A.length
	V = A[j]
	If A[j+1].defined? j = j + 1 else 
		V = nil
		Break

Anyways, I thought people would like to know about this particular journey as it develops.