starting computer science in college (advice)

[sam dhillon]

Hi guys well i have finally finished school and heading to college to do computer science (my dream) Im just feeling really nervous about it. The nerves started after i had a taster day, in the taster day there was a logic puzzle ,and i was surprised i couldn't manage to do it.(i feel unprepared now) I love programming,but i feel just programming is not going to cut it. I am definitely not the smartest guy(i feel im at a disadvantage) but i really want to do well. So is their advice u guys have on what to learn for the course, anyways to improve my problem solving skills and theory etc.

[LB]

Two things:
- Do all your learning from free resources online and/or known-to-be-correct textbooks. They are more reliable than a professor who is teaching from memory of what he learned years (possibly decades) ago, unfortunately.
- If your professor and/or his study materials tell you something is correct, then it is correct in his class. It may very well be completely wrong, but the exam key doesn't know that.

I've had plenty of incorrect information taught during my classes and it's not worth it to correct the professor in many cases. As long as you know the real correct answer (and know not to be overly confident) then you should be fine.

Unfortunately, as thedailywtf.com shows, you may encounter much of the same kind of "go with the flow even if it is wrong" environment in the work place.

[Duthomhas]

Also, in real life you are very rarely required to solve new problems you (or anyone else) have never heard of before.

The trick is to learn enough to recognize the kinds of problems you are likely to encounter, so that you can know how to start (re-)learning how to solve it when you need to.

Hope this helps.

[Computergeek01]

I have this to say about logic puzzles; do not get hung up on them or take them for a measure of intelligence. The most sinister of them are difficult because they use logic that is counter intuitive to the thought process that you spend your entire life establishing. So you look at it and immediately think you know the answer, but even after trying it a dozen times you'll never get it to work. It takes years to establish the neural pathways that you need to attack some of these from different angles and nothing but practice the same types of puzzle or logic will suffice.

STORY TIME: There was this one puzzle that I saw in high school and had kept in the back of my head for years. You had to draw this square with an X in the middle, each end of the X was connected to its own corner of the square, and there were loops around the sides of the square connecting the outer corners at the end of each loop. You had to draw this without tracing over a previously placed line or lifting the pencil. There was no limit placed on the number of moves you could take so I knew right away that it would be np hard and that there were no shortcuts to be taken.

It would pop into my head months or years later out of no where, for seemingly no reason and I would immediately become obsessed with it. I spent an absurd amount of time on this thing OP and even missed a day or two of work because I had accidentally stayed up all night and didn't get any sleep. I couldn't Google it because I didn't know what the puzzle was called, I even scanned a picture of it into the PC and tried an image search but I had no luck finding a solution. One day I just said to hell with it, broke out SFML and wrote a program that would solve it for me and record the steps to get the answer so I could see what the heck I was doing wrong. That program took less then a minute to find my answer while running a single thread on an old P4. To this day, even after reading that output dozens of times over, I wouldn't be able to solve that puzzle on paper to save my life.

[abhishekm71]

Agree to the opinion about not to let a puzzle deter you from pursuing a career you wish.

OFF-TOPIC:
@Computergeek01
Wonder how even your program solved the puzzle. If you are talking about Boyd puzzle, it seems unsolvable without resorting to tricks like folding the paper.

[Computergeek01]

@ abhishekm71: That's the satanic little bastard! Honestly it was so long ago that I'm questioning if I would have been able to spot a flaw in my code that would have given me an incorrect answer. It might be time to revisit my old Nemesis.

I remember that I called the intersections 'nodes' and each 'node' was connected to four line segments, and so each line segment was connected to two nodes. I specifically remember breaking the 'X' up into four line segments in order to accommodate this approach. The line segments and the nodes were each objects that held pointers to the the next valid component in their paths. The line segments each had a pointer to a bool that was in this function (I used a pointer so that it could hold three states: true, false and NULL. Don't ask me what I was thinking, I thought I was being clever at the time). The function took a node as an argument and it would systematically go through the line segments for that node, if their bool pointer was NULL, and call it self to test the next node that LS pointed to. If there were no more valid paths but the puzzle was not complete then it would return false, and the previous instance of it would mark that path as false. Otherwise it would continue on with this process until the solution was found.

As you can see there is more then enough room for error here for someone who is self taught and not all that advanced in math.

[helios]

This proves by exhaustion that there's no possible way to traverse all edges of the graph without repetition:

#include <iostream>

struct edge{
	int to_where, *directions;
};

int directions[] = {2, 2, 2, 2, 1, 1};

edge states[][3] = {
	{{1, directions + 0}, {2, directions + 4}, {3, directions + 1}},
	{{0, directions + 0}, {2, directions + 2}, {3, directions + 5}},
	{{0, directions + 4}, {1, directions + 2}, {3, directions + 3}},
	{{0, directions + 1}, {1, directions + 5}, {2, directions + 3}},
};

bool backtracking(int state){
	for (int i = 0; i < 3; i++){
		edge &e = states[state][i];
		if (!*e.directions)
			continue;
		--*e.directions;
		if (backtracking(e.to_where))
			return 1;
		++*e.directions;
	}
	//Edited on 2014-09-18:
	//This part of the proof is incorrect. There's no way for backtracking() to
	//return anything other than false.
	//return 0;
	//Here's the correction:
	for (int i = 0; i < 6; i++)
		if (directions[i])
			return 0;
	return 1;
}

bool backtracking(){
	for (int i = 0; i < 4; i++)
		if (backtracking(i))
			return 1;
	return 0;
}

int main(){
	std::cout <<backtracking()<<std::endl;
}

[Computergeek01]

@ helios: This site needs spoiler tags. I was just working on that. I guess on the other hand a thank you is in order for saving me the time. So thanks.

I'm glad to see that my basic premise was right. Although even my current iteration wasn't nearly this succinct. I really have to lose this "value_initialization = ugly_code" mindset that I have set in.

[abhishekm71]

Another way the unsolvability can be proven is as follows (if I am right):

We want to determine if there is an Eulierian path in the graph or not. The necessary and sufficient condition for the same is that every vertex should have an even degree. However in the puzzle each of the 4 vertices has a degree of 5.

The above reasoning works only for graphs that have at most one edge between any two given vertices.

[Computergeek01]

In hind sight I guess the fact that it's symmetrical and each point had to be intersected twice; but the number of intersections is one less then half of the number of line segments should have clue as well. You guys have no idea how much time I've wasted on this thing.

[sam dhillon]

thanks for the answers guys i also need to keep improving my maths because i dont know what might happen on the course and i feel my maths needs to be improved. But a good thing is i get all microsoft products for free and get to keep them forever.