Project 02 - TimSort

Go back to home page

Executive Summary

• Executive Summary

Implementation

• Implementations:
  • C++
  • Java
  • Python
  • io
    • test input 1
    • test output 1
    • test input 2
    • test output 2
    • test input 3
    • test output 3

Slides

• Instructional Slides
• Presentation Slides

Programming Challenge

• Programming Challenge
  • Solutions:
    • C++
    • Java
    • Python
  • Test Cases:
    • Case 1: programming challenge example
    • Case 1 input
    • Case 1 output
    • Case 2: edge case - every ship along y = x
    • Case 2 input
    • Case 2 output
    • Case 3: edge case - every ship along fixed radius
    • Case 3 input
    • Case 3 output
    • Case 4: edge case - duplicate ship coordinates
    • Case 4 input
    • Case 4 output
    • Case 5: edge case - no ships in query
    • Case 5 input
    • Case 5 output
    • Case 6: edge case - 20 ships provided in sorted polar order
    • Case 6 input
    • Case 6 output
    • Case 7: edge case - 20 ships provided in reverse polar order
    • Case 7 input
    • Case 7 output
    • Case 8: edge case - 20 ships along x = 0
    • Case 8 input
    • Case 8 output
    • Case 9: edge case - 20 ships along y = 0
    • Case 9 input
    • Case 9 output
    • Case 10: runtime: 1,000 random ships and 10 queries
    • Case 10 input
    • Case 10 output
    • Case 11: runtime: 5,000 random ships and 10 queries
    • Case 11 input
    • Case 11 output
    • Case 12: runtime: 10,000 random ships and 10 queries
    • Case 12 input
    • Case 12 output
    • Case 13: runtime: 50,000 random ships and 10 queries
    • Case 13 input
    • Case 13 output
    • Case 14: runtime: 150,000 sorted ships and 10 queries
    • Case 14 input
    • Case 14 output
    • Case 15: runtime: 150,000 reverse sorted ships and 10 queries
    • Case 15 input
    • Case 15 output
    • Case 16: runtime: 150,000 random ships and 10 queries
    • Case 16 input
    • Case 16 output
    • Case 17: runtime: 150,000 sorted ships with 150,000 reverse sorted ships and 10 queries
    • Case 17 input
    • Case 17 output
    • Case 18: runtime: 300,000 sorted ships and 10 queries
    • Case 18 input
    • Case 18 output
    • Case 19: runtime: 300,000 reverse sorted ships and 10 queries
    • Case 19 input
    • Case 19 output
    • Case 20: runtime: 300,000 random ships and 10 queries
    • Case 20 input
    • Case 20 output