Binary trees

Assume: let T = nonempty binary tree let n = number of nodes let n_e = number of external nodes let n_i = number of internal nodes let h = height of T Then, T has following properties: height of the nonempty binary tree + 1 is less than or equal to the number of nodes in the binary tree is less than or equal to 2^(height of the nonempty binary tree + 1) — 1 1 is less than or equal to number of external nodes in the nonempty binary tree is less than or equal to 2^(height of the nonempty binary tree) height of the nonempty binary tree is less than or equal to number of internal nodes of the nonempty binary tree is less than or equal to 2^(height of nonempty binary tree) — 1 log of...

Continue Reading →

Unless otherwise mentioned in the post, those projects are side projects which I work on on weekends and evenings, and are not affiliated with my work or employer.

Tags: software engineering   |   Report a bug via Twitter

Position vs index

Have you ever wondered why you sometimes see index and sometimes position keywords in code fragments? … numeric indices are not a good choice for describing positions within a linked list because, knowing only an element’s index, the only way to reach it is to traverse the list incrementally from its beginning or end, counting elements along the way. … position, which formalizes the intuitive notion of the “location” of an element relative to others in the list. To provide a general abstraction for the location of an element within a structure, we define a simple position abstract data type. Be mindful that this is described within the context of Java. This all stemmed from my reading of The Positional List Abstract Data Type. At the same time, this text was fun to read because it got linked to graphs...

Continue Reading →

Unless otherwise mentioned in the post, those projects are side projects which I work on on weekends and evenings, and are not affiliated with my work or employer.

Tags: software engineering   |   Report a bug via Twitter

Stacks October 25 2018

On “Implementing a Stack with a Singly Linked List” In designing such an implementation, we need to decide if the top of the stack is at the front or back of the list. There is clearly a best choice here, however, since we can insert and delete elements in constant time only at the front. With the top of the stack stored at the front of the list, all methods execute in constant time. The Adapter Pattern One general way to apply the adapter pattern is to define a new class in such a way that it contains an instance of the existing class as a hidden field, and then to implement each method of the new class using methods of this hidden instance variable. By applying the adapter pattern in this way, we have created a new class that...

Continue Reading →

Unless otherwise mentioned in the post, those projects are side projects which I work on on weekends and evenings, and are not affiliated with my work or employer.

Tags: software engineering, javascript   |   Report a bug via Twitter

October 20 2018

From Object Oriented JavaScript (Part the First) var literalDog = { // declaration AND instantiation name: "Vincent", // object property speak: function() { // object method return this.name + " says woof"; } }; literalDog.speak(); // "Vincent says woof" Inside of the speak method the this variable will refer to the current context of the function execution. This is an important distinction with classically object oriented languages: the value of this can (and often does) change! In most cases, this inside of a method like the one above will refer to the current object or instance. Without some other influence, if a method is called with “dot” syntax as in the last line above, then you can generally expect this inside the function to be whatever is on the left side of the dot. Inside of literalDog.speak() the this variable...

Continue Reading →

Unless otherwise mentioned in the post, those projects are side projects which I work on on weekends and evenings, and are not affiliated with my work or employer.

Tags: software engineering, javascript, personal development   |   Report a bug via Twitter