Trivial Computer Science

Want a challenge? Then this is the forum for you. Partake in contests or trivia games for a chance to win Tokens.

Trivial Computer Science

Postby Gigafrost » Fri Jun 18, 2004 5:44 am

Just a trivia with some simple Computer Science concepts. You might have even heard of all of them without even taking any Computer Science classes, hehehe. I imagine that Terrafrost should be able to easily answer these questions, hehehe. :)

1 week, 1 guess, 1 medal.

Special rule: If you make a guess and you get some questions wrong, yet you get at least one question right, I'll let you have another try at the questions you got wrong. (Why? To encourage participation, of course.)

1.
x := x ^ y
y := y ^ x
x := x ^ y

If := means that the variable on the left takes on the value on the right, and ^ represents a bit-wise XOR, what does this well known code snipet do?

2.
In what ways are Mergesort and Quicksort similar\different?

3.
A Red-Black tree is a kind of Binary Tree. What does it aim to do?

4.
If you design a program to search through a string, looking for all occurances of some smaller string within that bigger string, it is possible to achieve sub-linear times. How do you do this?
User avatar
Gigafrost
Frost Weapon
Frost Weapon
 
Posts: 4900
Joined: Wed Dec 04, 2002 5:09 pm
Location: Here

Postby TerraFrost » Fri Jun 18, 2004 6:05 am

I imagine that Terrafrost should be able to easily answer these questions, hehehe. :)


i think all of them, save for #3 (and possibly #2), are from CS337, actually! :)

although that said, i'll give others a chance, first :)
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Postby TerraFrost » Thu Jun 24, 2004 3:26 am

well... it's almost six days later, so i'll bite...

1. performs a swap.

2. quicksort has a similar big-o efficiency to mergesort, and both use a divide and conquer approach. they differ in what they do immediatly after a divide. a mergesort will, immediatly after a divide, select another midpoint, and do another divide around that midpoint, if it can, whereas a quicksort will select a "midpoint" and partition about that midpoint (ie. put elements greater than the "midpoint" after the "midpoint", and put elements less than it before it). there are other differences, but that's they key one.

3. it aims to stay balanced.

4. yes - by not examing every single character.
TerraFrost
Legendary Guard
 
Posts: 12357
Joined: Wed Dec 04, 2002 6:37 am

Postby Gigafrost » Thu Jun 24, 2004 5:01 am

Yup. That's pretty much everything I was looking for, and then some. :)
User avatar
Gigafrost
Frost Weapon
Frost Weapon
 
Posts: 4900
Joined: Wed Dec 04, 2002 5:09 pm
Location: Here

Postby Megafrost » Thu Jun 24, 2004 2:13 pm

*awards Terrafrost with token and ice cubes*
The universe is mine and all shall bow before the might of Megafrost, master of Orion, master of the universe...
User avatar
Megafrost
Frost Blacksmith
Frost Blacksmith
 
Posts: 5249
Joined: Thu Dec 05, 2002 4:15 pm
Location: The planet of Cybertron


Return to Contest Cooler

Who is online

Users browsing this forum: No registered users and 1 guest

cron