algorithm and problem solving
Page 1 of 114 Replies  1471 Views  Last Post: 15 August 2012  10:18 PM
#1
algorithm and problem solving
Posted 15 August 2012  07:34 AM
im a first year computer science student. I found really tough to solve algorithm and problem solving questions. Do you have any idea or even a good resources. thanks
Replies To: algorithm and problem solving
#2
Re: algorithm and problem solving
Posted 15 August 2012  07:52 AM
#3
Re: algorithm and problem solving
Posted 15 August 2012  07:56 AM
thanks
#4
Re: algorithm and problem solving
Posted 15 August 2012  07:59 AM
#5
Re: algorithm and problem solving
Posted 15 August 2012  07:59 AM
#6
Re: algorithm and problem solving
Posted 15 August 2012  08:08 AM
As logic  just grab any 'intro to logic' and learn. That's an easy memorization part. Truth tables and such.
You are a freshman comp sci student.. this stuff shouldn't be too easy else why are you paying to learn it? Ha!
#7
Re: algorithm and problem solving
Posted 15 August 2012  08:09 AM
You have a bag with three types of object.
Each turn you remove 2 objects of different types and replace them with an object of the third type.
1.For what starting conditions can we finish with exactly one object in the bag?
2.clearly identify the problem(notation)
start state.
end or goal state.
operators
constraints and
any eventual assumptions
3. identify the invariants
4. look for thw symmetry.
5. look for the ways to sub divide the problems.
For me the hardest part is to show the question 1 answer and 5 part.
#8
Re: algorithm and problem solving
Posted 15 August 2012  08:31 AM
http://www.amazon.co.../dp/1876462639/
As for that problem  write down what you know and work backwards!
You know there are three objects that can exist... A, B, C.
You want only one object.. so start there.
You also know that two different objects have to be removed to get a third different one..
So you start with object C.
To get C you needed to have removed A and B, right?
C A  B
To get A you would have needed B and C... and to get that second level B you needed A and C.
C AB  C   BA C
On and on and on.. then you can extrapolate that into an equation once you start seeing a pattern.
#9
Re: algorithm and problem solving
Posted 15 August 2012  08:38 AM
thanks a lot
#10
Re: algorithm and problem solving
Posted 15 August 2012  08:48 AM
#11
Re: algorithm and problem solving
Posted 15 August 2012  08:55 AM
#12
Re: algorithm and problem solving
Posted 15 August 2012  08:56 AM
#13
Re: algorithm and problem solving
Posted 15 August 2012  09:01 AM
#14
Re: algorithm and problem solving
Posted 15 August 2012  09:06 AM
If it has already been done then you should have the answer.. and work back from there.
#15
Re: algorithm and problem solving
Posted 15 August 2012  10:18 PM
1. Prove the opposite. Rather than find starting conditions that succeed, I tried to find starting conditions that fail.
 obvious situations are sets of 2 or more of only one type.
 back track to see what can reduce to such cases. Make sure alternate paths do not produce a solution.
examples: AA < ABC and any operation on ABC leaves 2 of the same type so ABC is not solvable.
AAA < AABC but this is solvable because AABC > ACC > BC > B
2. One of the patterns I noticed from my various trials in 1 is that if you have any number of A's you can eliminate them all so long as you have one of the other types. I visualize this as a stack of A's in which a B is fired into the top. The collision results in a C. The C then boomerangs back and knocks of the top of the A's producing a B (hey, visuals help). Repeat until the stack of A's is gone. In this case, an odd number of A's results in a C when all is said and done. An even number would leave a B.
3. Once I had the stack visual, I decided to arrange all items into their 3 respective stacks. I treat the pattern in 2 as a sort of goal state because from there I can solve the problem trivially. For example, if we have 20 A's, 3 B's and 2 C's, then we just perform BC>A twice leaving us with 22 A's and 1 B. The boomerang then solves the problem.
Pursuing 3, I was able to identify exactly the conditions for which we can reduce the objects to a single item. Proving it was the only condition is a whole other can of worms. I leave both of those exercizes for you to play with.
