CS 1110 h/w 3 ... due Friday 1st August by upload and demo
- Induction proof exercises. Prove each of the following by induction:
- The sum of the squares of the integers from 1 to n equals n(n+1)(2n+1)/6 for n positive.
- The sum of the first n odd numbers equals n^2 for n positive.
- A polygon is said to be convex if every line joining two points of the polygon lies within the polygon (the boundary is treated as part of the polygon). Prove that the sum of the interior angles of a convex polygon with n sides is equal to (n-2)π if n is at least 3.
- Rewrite the following sorting techniques (insertion, selection, quick, merge) to apply to lists (do not use arrays). This should be done intially for lists of integers in the range 0 - 100 (inclusive), but then extended to handle sorting People. (You may make such simplifying assumptions as seem reasonable to limit the population so that bucket sort is viable!) Provide a main method to demonstrate that your sorting methods work.
- Revisit the economy question from hw2, improving and extending your solution.
- Model a transport network (e.g, of roads), using nodes in an intelligent way. You will need classes for vehicles (have at least classes for cars, buses, bicycles, ambulances), using inheritance where possible. You will need a class for the transport network itself (think about how you'd like to model one-way streets as well as regular two-way streets). You should arrange things so that depending on various natural conditions (your reasonable choice, well-commented of course!), priorities can be set (for example, buses win over cars, bicycles win over buses, ambulances win over everything if running in an emergency state). Have your main method input a file to initialise things, and then run a simulation with selective output to the screen (and full output to an output file) to show how transport moves around your system and various levels of congestion are handled. Feel free to use a graphical interface if this helps see what's going on.