Yeah, use goto. :P

I'm very interested in hearing your thoughts on this. Would the solution I presented not work for multicore systems? I asked my teaching about this during yesterdays class but he couldn't really give a good answer and referred me to the lecture slides provided by the teacher. They didn't really explain this fully either.

Anyway, I got a similar problem to the one I posted earlier that is due tonight. I'll post it tomorrow as well as my solution (in spoilers ) for those that might be interested in trying to solve it or in seeing the solution

Thanks!

I am at a complete loss here with this. I'm supposed to write a non recursive function to do a postorder traversal of a binary search tree.



The pseudocode makes no sense whatsoever. Value 0? what? the implementation doesn't make much sense to me either but I can't seem to make anything even close to working here.

The "value" it's referring to is a mechanism to save off state information as you traverse through the tree that tells you which parts of it have been visited and which haven't.

At a high level, as you dive into lower nodes and then pop back up to process their parent nodes (which you do after the children, according to the instructions), if you're just keeping track of nodes alone you'll run into an infinite loop that will basically go like:

- process parent of leftmost node
- node has a left child, process it
- process leftmost node
- no left child, no right child, DoSomething() on this node
- go back to parent
- process parent of leftmost node
- node has a left child, process it
- process leftmost node
etc etc etc

Every time you visit a new node, you essentially are starting with a clean slate for your knowledge about it and you won't know if you've already visited its children or not; thus, your options are to never visit any children or to repeat visiting the same children forever.

By using the value the algorithm talks about as a flag to track your progress, that would instead go like:

- process parent of leftmost node, value is 0 so we've processed no children yet
- node has a left child, save off this node + value of 1
- process leftmost node, value is 0
- node has no children, DoSomething() on this node
- go back to parent
- process parent of leftmost node, value is 1 so we've processed the left child already
- node has a right child, save off this node + value of 2
- process right child
- node has no children, DoSomething() on this node
- go back to parent
- process parent of leftmost node, value is 2 so we've processed both children already
- DoSomething() on this node
- go back to parent

0/1/2 are kind of confusing ways to frame it, if you were doing this in C++ then you'd be better off using an enum (0=NotVisited, 1=VisitedLeft, 2=VisitedRight) so it's clearer what they mean.

I ran into several of the problems you mentioned and came up with a far simpler algorithm than what she recommended.

I just use 1 and 2: 1 for left subtree being visited, 2 for right subtree being visited. if i run into a leaf that has not had the right subtree visited yet, i visit it and go to the right subtree. if the right subtree has been visited then parent can be printed.

took me like 2 hours and i hand traced this but it works fine.

the whole point of this exercise was to show us how much easier recursion is for traversing binary search trees but she never gave us any recursive functions to write so FU lady

Yes your program would work with the caveat as long as the OS implemented mutual exclusion correctly because implementing the mutual exclusion resource at the OS level is more complicated. In multicore systems where memory is shared hardware wise between cores and each core has cache presents some interesting challenges for the OS.

Yes post the problem. FWIW from what I can tell, this is a very good and relevant course you are taking. Processor clock speeds have maxed out for the foreseeable future and thus parallel algorithmic type solutions are going to be necessary to bring about more processing throughput in solving more complex software problems. Starting with C++ 11, C++ has a concurrency model that is very interesting and is geared to parallel algorithm development in my view.

Not a binary tree expert but isn't one of the concepts regarding traversing binary trees related to the type of traversal: pre order, in order, post order? Of course they all use recursion. Thinking she showed you one way and you just traversed it a different way. Binary Tree Traversal

Probably didn't give you any recursive code to write because it's either 1) in the book, 2) only three lines of code, or 3) both

For clarity: bolludagur is an annual event, where bakers produce a whole lot of bolla, which is a kind of pastry. It is often made out of three things, the plain bolla itself, chocolate and cream.

I'm not sure if this requires more explanation. You can refer to my solution for the swimmers problem to see semaphores being used. Remember they have a value, which essentially tells us how many processes can pass the semaphore, and then they have two operations wait(), that decrements the semaphore value and then checks if the process can pass the semaphore (is the value >= 0), and signal() that increments the semaphore value, and checks if there is a process waiting to pass the semaphore (is the value <= 0).

The wikipedia page on semaphores has some useful information, as well as a library analogy that does a decent enough job of explaining the concept.
The following is a snippet from the wikipedia page: Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available) are called binary semaphores. And a small hint is that we should only use binary semaphores to solve this (i'm not sure if a solution using counting semaphores is possible, it might be, but the most straight-forward solution uses only binary semaphores)

That problem i posted was supposed to be a non recursive function to post order traverse a BST. The recursive algorithm is in the lecture notes but unless I sit down and try to write it I'm not gonna get it. After I posted last night I wrote it on a whiteboard and figured it out which was a helpful exercise.

nvm, I'm blind

@Mavoor - do a google search on counting semaphores, they are not used for mutual exclusion.

re: recursive code for jmakin's problem

Does this work? I wanted to write code like gaming_mouse. Building an array seemed like a convenient way to avoid having to actually use an if statement to see if nodes are undefined, but I'm new at this so I may have missed something better.

I believe he is going to use binary semaphores.

I haven't tested it, but the idea looks right to me. And I officially endorse the number of lines of code, the DI with the callback, and purely functional approach

how do you write code with out if for and for? Just use while every time? Whats the logic behind that? and how can you not have conditional statements?

I think he's referring to functional programming. See goofyballer's example above

(Which, face it, also uses if and for statements, just in a functional manner and called something else)

god no, not while :P

the logic is just a fun way of saying: program in a functional style. if and for are imperative constructs.

in the case of for, you should be using appropriate declarative alternatives like map, reduce, and so on. they make your code more readable by avoiding silly low level details like the "i" counter that has nothing to do with what you are trying to express 99% of the time. also, this will greatly promote reuse by encouraging a compositional style. Check out Rambda.js and some of their videos if you want to see practical examples of what I mean.

you avoid "if" for similar underlying reasons: because state is evil and hard to reason about (see "Out of the tar pit," currently my favorite treatise on programming, for more).

In the small, it doesn't really matter, and it may appear as a trivial difference in syntax. But there's a larger issue at play in the way you are thinking about organizing your program. Of course, rewriting all your ifs into ternary expressions won't magically make your programs any better. But if you understand the deeper reasons why expressions and immutability are better than branching logic and state manipulation, you will write better programs.

while true in the most technical sense -- all programming is just turing machines, it's implemented on registers and stacks, and so on -- this is really a misleading equivalence.

As I said in my last post, "Out of the tar pit" makes the best case for the merits of functional programming that I've seen, so I'll just let that be my argument for the reasons why, but the one sentence version is that human beings can't reason about state, but we do ok with the concept of inputs and outputs that always work the same way.

Im not very experienced, so this is no doubt ignorance, but that last line to me is EXACTLY the same thing as in if statement, just different syntax. I will read "out of the tar pit", thanks for the recommendation!

Im dumb, I should have realized you were talking about functional programming, I took a whole class on that, oops.

in the first version, there is a statement that *may* get executed depending on the the value of some other variable. in the second, an expression that is always executed. the difference would be clearer written like this:

that is, we're setting the value of myStyle to the result of a function, and that result (assuming the function is pure) depends only on the value of stateIsEvil.

the difference is extremely subtle and unimportant in such a trivial example, but as the number of things that style depends on grows, and the complexity of the logic expands, the functional code will remain clear, while the imperative code becomes impossible to reason about.