Super Star Challenge 2
Challenge 02-01: Splay Trees:
Implement a Splay Tree in Java. Feel free to use the Wikipedia Splay tree entry as a reference. Please do not make the code as unreadable as the example on the Wikipedia page, and please do not just port that example to Java. Please do not refer to or copy any Java implementation on the web. Write Unit tests that test the functionality well. Write a JUnit test that verifies the runtime performance bound that performing a sequence S of m accesses in a splay tree containing n elements is O(m(1+log n) + n log n).
Challenge 02-02: Math Challenges:
These math challenges you should be able to do on paper and pencil, then implement in Java where asked. You should be able to answer them yourself without having to surf the web or ask for help.
- There are n people in a room. p are chosen at random. What are the odds that at least one of those p people have the same birthday as at least one of the non-selected people? Demonstrate that your answer is probably correct by simulating it with a Java program.
- Write a Java program that determines the prime factorization of a number. Test it on 6,646,094
- Write a Java program to determine the Least Common Multiple and Greatest Common Divisor of two integers. For example for 20 and 28 the GCD is 4 and the LCM is 140.
- Derive a set of equations for projecting a 3D point onto a 3D line.
- Derive a set of equations for determining the intersection of two 2D lines.
- Derive a set of equations for testing whether or not a 2D point lies in the inside of a 2D polygon defined by its vertices ordered in clockwise order.
- Given two 2D polygons, each defined by its vertices ordered in clockwise order, determine an algorithm for checking whether or not the two polygons are equivalent, though possibly translated and/or rotated. Note that the ordering of the two polygons may be different (even though the polygons may be equivalent, the first vertex of the first polygon may not correspond with the first vertex of the second polygon.)
- Why do humans use a base 10 number system and computers use a base 2 number system? What are advantages that base 10 has over other number systems?
- A bicycle rider can ride one mile in three minutes with the wind and one mile in four minutes against the same wind. How long would the mile take him to ride if there was no wind?
- Given a shuffled normal 52-card deck of cards with no jokers, what’s the odds that there will be a full house (2 of one card, 3 of another) in the first 5 cards?
Challenge 02-03: Relative Importance:
What’s more important: Fast Software, Readable Software, or Correct Software? Elaborate.
Challenge 02-04: Logic Problems
Come up with a new logic problem. Try not to just rephrase one you’ve heard previously. Write it out clearly.
Challenge 02-05: Clean Code
Find some Java code that smells. Could use a public package, or a friend’s code. Refactor it, including the API, to make it clean. Submit before and after versions of the code.
If you’ve gotten to this point and are still enjoying the challenges, it’s time to get personal. The next challenge page will get us information on your programming and life philosophies. Grab your hat and whip and here we go to Challenge Page 03.