Monthly Archives: November 2015

pointer array parameter passing

Create a new Array on the Heap

Creating a new array on the heap basically means:

1) we create a row of new objects that are next to each other
2) We then have an index pointer pointing to it. A index pointer is a pointer pointing to the FIRST element of the array. That way, we can access the rest of the array. If there is no index pointer, we wouldn’t know how to access the rest of the array elements.

1) We create the row of new objects like so:

2) Then we create the index pointer and point to it like so:

That’s it, and what this looks like in memory is this:

ptr_to_array

The index pointer by default is pointing to the 1st, or 0th element of the array.
The reason why we have an index pointer is so that we can reference the whole array like so:

0th element *(arrayA)
1st element *(arrayA + 1)
2nd element *(arrayA + 2)
nth element *(arrayA + n)

Thus, you can display all the elements in an array via an for loop and simply using the index i to display whatever element you’d like. That is the most important purpose of the index pointer.

Binary Array Search

Pre print recursion

ref – http://shanghaiseagull.com/index.php/2015/11/16/simple-recursion/

note: recFunc is a placeholder name for any recursive function name that you are running.

a) we write the push of the function for recFunc( 3 ) onto the main stack
b) We begin for the start of line for recFunc( 3 ) at comment #1
c) We check the base case at comment #2, it is false so we move down to comment #5. Its a print statement so we print n, which is 3.

We need to remember to write 3 in the output as shown on the top right hand side of the image.

pre-1

Then we hit comment #6, which is a call to the recursive function. This means we are going to push recRunc( 2 ) onto the stack. Thus:

a) we for visual clarity, we tab some spaces, then write out recFunc( 2 )
b) we reach comment #1 which is the Start Of Line for recFunc( 2 )
c) We check the base case at comment #2, it is false so we move down to comment #5. Its a print statement so we print n, which is 2. Remember to write it in your output section.

Reaching the base case

We continue this fashion until we hit recFunc( 0 ). Once we get to recFunc( 0 ), we write out SOL at comment #1, then when we reach the base case at comment #2. It evaluates to true, so we print out the “happy new year” at comment #3, and the function returns at comment #4.

Whenever a return or end of function is reached, we pop the stack frame. In our case we pop the stack frame for recFunc( 0 ). On our paper for visual clarity, make sure you draw a line connecting SOL 0 to EOL 0. This tells us that the stack frame for rechFunc has been popped and completed.

pre-2

In code, we then continue where we left off at comment #6 for recFunc( 1 ). We then go down to comment #7. Its the EOL for recFunc( 1 ), so on our paper, we write out —– EOL 1 —–.

In code, we reach end of function, so that means we pop the stack frame for recFunc( 1 ). Make sure you draw the connecting line from SOL 1 TO EOL 1 to clarify this.

We continue where we left off at comment #6 for recFunc( 2 )…

We keep doing this until all the stack frames have been popped, and we finish running recFunc( 3 ).

pre-3

Thus, in the output, you should see: 3 2 1 Happy New Year!

Recursion Concepts

ref – https://www.cs.drexel.edu/~mcs172/Su04/lectures/07.3_recursion_intro/Dangers.html?CurrentSlide=7
https://en.wikipedia.org/wiki/Recursion_termination

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. In other words, when a function calls itself from its body.

The power of recursion lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.

A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method;

Pros

Less Code – Recursion is generally known as Smart way to Code
Time efficient – If you use recursion with memorization, Its really time saving

For certain problems (such as tree traversal ones) – it’s more intuitive and natural to think of the solution recursively.

Cons

Recursion takes up large amounts of computer resources storing return addresses and states.
In other words, if left unbounded, and fed a data set which leads it deep enough, the function call overhead will accumulate, sucking up system resources rapidly and eventually overflowing the stack.

It is fairly slower than its iterative solution. For each step we make a recursive call to a function, it occupies significant amount of stack memory with each step.

May cause stack-overflow if the recursion goes too deep to solve the problem.
Difficult to debug and trace the values with each step of recursion.

Recursion vs Iteration

Now let’s think about when it is a good idea to use recursion and why. In many cases there will be a choice: many methods can be written either with or without using recursion.

Q: Is the recursive version usually faster?
A: No — it’s usually slower (due to the overhead of maintaining the stack)

Q: Does the recursive version usually use less memory?
A: No — it usually uses more memory (for the stack).

Q: Then why use recursion??
A: Sometimes it is much simpler to write the recursive version (for trees)

  • Use recursion for clarity, and (sometimes) for a reduction in the time needed to write and debug code, not for space savings or speed of execution.
  • Remember that every recursive method must have a base case (rule #1).
  • Also remember that every recursive method must make progress towards its base case (rule #2).
  • Sometimes a recursive method has more to do following a recursive call. It gets done only after the recursive call (and all calls it makes) finishes.
  • Recursion is often simple and elegant, can be efficient, and tends to be underutilized.

Examples

Every recursive function has 2 basic parts:

1) A base case return
2) a recursive function.

The base case stops the recursion, and the recursive function keeps it running. Our base case would be comment #2. Recursive case would be at comment #5.

In order to properly understand how a simple recursion work, whenever a function is called, on your paper, write out the function name with its parameter. In the pictorial, you will see recFunc(3)

simple-1

Then on the next line, you want say SOL (start of line). This signifies that you’ve entered the function. In the pictorial, you see —– SOL 3 ——-. Doing this will clarify that you’ve entered the frame for that function.

After the SOL for recFunc(3), we come to base case ( comment #2 ) to see if parameter n is 0.

We see that the base case is not true, so we continue down the code. We come to the recursive case with parameters n – 1 ( comment #5 ). Hence we start a new function stack.

In our paper, we skip a new line and write recFunc(2). This means we’ve entered recFunc( 2 )’s frame ( comment #1 ).

We then do —- SOL 2 —— because we’ve entered the stack for recFunc( 2 ) ( comment #1 ). We then evaluate the base case, to see if parameter n is 0. Its not so we continue on the function call recFunc(1)….

We continue on until we reach recFunc(0).

We see that the base case is true, so we go to comment #3, where you would write out the printf. Then at comment #4, we hit the return for the base case. The return means we pop the stack frame for recFunc( 0 ).

Note: Whenever a stack frame is popped, make sure you connect the lines from SOL to EOL. This can visually help you to see where the function frame has been completed.

simple-2

By popping recFunc( 0 ), we continue where we left off at comment #5 of recFunc( 1 ).
We step through the code and hit EOL ( comment #6 ). So in our diagram, we connect the SOL to its EOL to show that we’ve concluded recFunc( 1 ) frame.

We pop the stack for recFunc( 1 ) and we then come to comment #5 for recFunc( 2 ). That is where we left off. We continue down, and we see EOL for recFunc( 2 ) at comment #6. We then draw the end of stack for recFunc( 2 ).

simple-3

We pop the stack for recFunc(2), and we are then on recFunc(3) at comment #5. We step down, see EOL at comment #6, and in our notes, we draw the end of stack for recFunc( 3 ).

Risks of Recursion

In computing, recursion termination is when certain conditions are met and a recursive algorithm stops calling itself and begins to return values. This happens only if, with every recursive call, the recursive algorithm changes its state and moves toward the base case.

Recursive programs can fail to terminate – This error is the most common among novice programmers. Remember that your subprogram must have code that handles the termination conditions. That is, there must be some way for the subprogram to exit without calling itself again. A more difficult problem is being sure that the termination condition will actually occur.

Stack Overflow – Remember that every subprogram is a separate task that the computer must keep track of. The computer manages a list of tasks that it can maintain, but this list only has a limited amount of space. Should a recursive subprogram require many copies of itself to solve a problem, the computer may not be able to handle that many tasks, causing a system error.

Out of Memory Error – All of the subprograms we have shown here have used pass by value. That means that every time a subprogram is called it must allocate computer memory to copy the values of all the parameter variables. If a recursive subprogram has many parameters, or these parameters are memory intensive, the recursive calls can eat away at the computers memory until there is no more, causing a system error.

List Insertion Sort

download source

A note on passing Arrays to functions

Given an array of Node pointers…..each element is a pointer to a Node object.

1) We get a random int

2) Create a Node object
3) assign the random into to the Node object

4) then point the array element to the Node object

So now, we have a full array of Node pointers, pointing to Node objects with random integers.

What we’re trying to do is to pass this array into a class SortedLinkedList so that it can process this list.
It processes this list by taking each Node and inserting it into its own data structure. The insert will sort it. Then it will pop the element back onto an array, and thus, we sort it this way.

However, the passing of a whole array into a parameter is done by passing the pointer of pointer of the 1st element in the array. It is designated simply by the array name linkArray.

We know that each array element has an address. The first element’s address has its own address. That address of the address of the 1st element is designated simply by the variable itself, or linkArray.

Let’s display the address of our 1st element’s address in 2 different ways. One through star, and the other through bracket access. Both of which are the same, just different ways of accessing elements in C++. Notice that linkArray, has the same address as them:


output:
linkArray: 0x7fff5fbff6d0

&linkArray[0]: 0x7fff5fbff6d0
&(*linkArray): 0x7fff5fbff6d0

Therefore, that’s how we pass whole arrays into a function.

Create unsorted Array

Create the sort list and pass the unsorted array in

When we pass in the unsorted array, the linked list’s insertion will sort it

Then, because the list was already sorted via insertion, we simply pop the elements from the list and assign it onto the array.
This ensures that what we pop is in sorted order.

Sorted Linked List

download source
The key to understanding sorted insertion is to have 2 pointers.

One is current, the other is trailer.

sorted-linkedlist

While the current is not NULL, and the incoming data to be inserted is larger than the current’s data, then we move forward

We move forward by having the trailer and current move forward. Trailer take on current. Current take on current’s next.

When we do find a node data, where the incoming node’s data is not larger, we stop. We have the trailer’s next point to the new node. The new node’s next take on current.

If the list empty, we simply use the first to point.

Queue Linked List

download source

Queue is First In First Out, FIFO.
This means that Nodes are processed in order. They get in line, and each node is taken care of in the order added (or received).

In order to do this, we have a first and a last pointer. The first pointer points to the beginning of the list, which represents the next node to be processed and removed first.

The last pointer points to the end of the list, which represents the newest node that comes in, and thus, must wait its turn for the list to process and remove it.

The first pointer points to the node TO BE processed and thus removed.

queue-remove

The last pointer points to the position where new, incoming nodes come in.

queue-add

Stack Linked List

source download

Stacked list is all about having ONE head pointer.

Pop is O(1)
Push is O(1)

The head pointer is used to add and remove.

For append:

1) We have head point to NULL in the beginning

2) First item is initialized through being supplied with values from its constructor parameters. These parameters are int data, and whatever head is pointing to.

If we’re starting out, head should be pointing to NULL. If there were previous items, then head should be pointing to the latest pushed item.

3) In the case of appending the first node, our first node’s pNext should be to what head is pointing to, which is NULL.

4) our head then re-points to the newly created Node object. Our first object as been appended.

For pop, its about having a temp pointer pointing to the head, then have the head traverse 1 step forward. Then delete the object that temp is pointing to.

Simple Linked List

source code

  • A simple linked list in C++
  • Basic features
  • Running time

Features

– add by appending
– search
– remove
– display

A linked list is a bunch of nodes ‘linked’ together by pointers. Each node has a ‘next’ pointer that points tot he next node. This is what creates the link.

First step is to create the node. The node has data and a next pointer. The next pointer should be of the same type this node because after all, the nodes are of the same type.

You’d want to have 2 constructors for the Node. An default empty one, and another where you can assign new values.

Node.h

Node.cpp

LinkedList.hpp

Append

linkedlist-append

1) We have head point to NULL in the beginning

2) First item is initialized through being supplied with values from its constructor parameters. These parameters are int data, double priority, and whatever head is pointing to.

3) In the case of appending the first node, our first node’s pNext should be to what head is pointing to, which is NULL

4) our head then re-points to the newly created Node object. Our first object as been appended.

In programming, we always execute the inner most first. Then we work our way out.

The inner most is the data parameters.

First, we evaluate data to be a int. We evaluate priority to be a double. Finally, we evaluate head to point to NULL.

Then we pass these 3 values into the constructor of Node. Node object gets created with its attributes initialized. The values are initialized to , and the pNext pointer points to what head is.

Finally, when the Node object has been created, we have our head point to this Node object.

Remove

linkedlist-firstitem

temp means the temporary node we’re on. Trailer means the pointer behind temp, so that when we remove, we can use the trailer to connect the link.

The important to notice here is

1) evaluating the first item. When temp and trailer are pointing to the same node, we’re at the first node. When we see a match, we remove the node and repoint head to the next node.

linkedlist-move

2) Moving forward to evaluate the next item involves simply checking to see if we have a match or not. If there NO match we move forward by first, pointing trailer to temp. Then have temp point to temp->next. That way, when temp has a match, then the trailer can link (the node before and after the deleted node) together.

Running Time

Search O(n)
Delete O(n)
Append O(1)

Finding or deleting a specified item requires searching through, on the average, half the items in the list. This requires O(N) comparisons.

An array is also O(N) for these operations, but the linked list is nevertheless faster because nothing needs to be shifted when an item is inserted or removed.

The increased efficiency can be significant, especially if a copy takes much longer than a comparison.

Of course, another important advantage of linked lists over arrays is that the linked list uses exactly as much memory as it needs, and can expand to fill all available memory. The size of an array is fixed when it’s created; this usually leads to inefficiency because the array is too large, or to running out of room because the array is too small.

Vectors, which are expandable arrays, might solve this problem to some extent, but they usually expand in fixed-sized increments (such as doubling the size of the array whenever it’s about to overflow). This use of memory is still not as efficient as a linked list.

Stacks and Queues

In an array, any item can be accessed, either immediately through its index, or by searching through the sequence of cells until its found.

In stacks and queues, however, access is restricted. Only one item can be read or removed at a given time.

Their interface is designed to enforce this restricted access. Theoretically, access to other items are not allowed.

Stacks and Queues are abstract by nature. What I mean by that is that they are defined by their interface. Their underlying workings can be different. For example, A stack may have push, pop, view, etc as its interface. But the underlying mechanism may be an array of a linked list.

Some ways to use Stacks

Reverse a word

Use a stack to reverse a word. When a string of word comes in, push each character into your stack. Then pop the stack onto an empty string, and you will then have the word reversed.

Delimiter Matching

Another common use for stacks is to parse certain kinds of text strings. The delimiters are (, ), [, ], {, }…etc.

You have an empty stack

You have a string say “a{b(c[d]e)f}”

read “a”
“a” != delimiter, go on.
Stack:

read “{”
“{” is opening delimiter, push onto stack.
Stack: {

read “b”
“b” != delimiter, go on.
Stack: {

read “(”
“(” is opening delimiter, push onto stack.
Stack: { (

read “c”
“c” != delimiter, go on.
Stack: { (

read “[”
“[” is opening delimiter, push onto stack.
Stack: { ( [

read “d”
“d” != delimiter, go on.
Stack: { ( [

read “]”
“[” is closing delimiter, pop from stack.
Stack: { (

read “e”
“e” != delimiter, go on.
Stack: { (

read “)”
“)” is closing delimiter, pop from stack.
Stack: {

read “f”
“f” != delimiter, go on.
Stack: {

read “}”
“}” is closing delimiter, pop from stack.
Stack:

Using Queues

Queues are first in first out.

In Arrays, when we insert, we just push onto the array, which is O(1).
When we delete, we remove the 0th element, then push all the elements down, which is O(n).

In linked list, we have head and tail pointer. This would make both adding and removing O(1).

However, search and delete would be O(n) because on average, it takes n/2 where n is number of items. T = k * (n/2) where constants are included T = n. In regards to how fast it is to the number of items, we have T = O(n)

priority queues

0 is highest priority, a larger number means a lower priority.

Thus, when we insert an item, we start at the very end of the array. Use a for loop back to 0th index, and see if the new element is larger than the element at the index.

The new element being a larger element means it has a lower priority. If it is, we shift the array element up. We keep doing this until our priority is properly inserted. Having the smallest number mean we have a higher priority, thus, we append the element at the top.

When we delete, we simply pop the top element.