One Week MP

This MP is a one-week MP to better align due-dates with Fall Break.

This MP is due the Friday before break (Nov. 17). The usual grace period policy applies (and, like the usual grace period policy, there are no office hours on Saturday, Nov. 18 during break).

Due to the one-week nature of this MP, there is no extra credit submission. You will be able to earn +14 points for MP7, making up for the +7 extra credit that you are unable to earn as part of MP6.

Solo MP

This MP, as well as all other MPs in CS 225, is to be completed without a partner.

You are welcome to get help on the MP from course staff, via open lab hours, or Piazza!


In software development, it is rare that you build anything completely “from scratch”. Today, we rely on the work of people before us who built amazing programs that allow us to build ever increasingly complex programs. Here in CS 225, this is no exception:

One of the best metrics to determine the robustness of a piece of software is how long it has been in use. When we updated MP5 for this semester, we knew MP5 had been used for the past seven years (around 15 semesters). With that in mind, MP5 was likely to be robust, well debugged, and suitable for updating for this semester.

With a little exploration as a class, together, we found that was not completely true. When I made my new Facebook profile picture out of my favorite picture from a trip to Disney World, I found:

With Fall Break coming up in less than two weeks, this MP is a reflection on a very common real-world problem: understanding the data structures in code that functionally works and applying your knowledge about data structures to improve the runtime and memory usage of that code.


For MP6, you should take your solution from MP5 and copy it into your MP6 file (that is: maptiles.{cpp,h} and kdtree.{cpp,h}. If you did not complete MP5, you can use a course solution that I have posted here.

The end goal of MP5 was to use a kdTree to create a photo mosaic. In the process of creating that mosaic, there are a couple different inputs that we are going to quantify for MP6:

The goal of MP6 is to explore the API you used in MP5 and improve the algorithms that you used (without even knowing you used them)!


This MP requires that you improve the runtime and memory footprint of MP5. There are only a few technical limitations that are imposed on you for this MP:

You already have a working MP6, so there are no unit tests (it already works)! Instead, you must ensure your program runs in a reasonable amount of memory and time. The following command should both not crash and run in less than 10 minutes on EWS:

./mp6 source.png /class/cs225/mp5_pngs/ 400 5 mosaic.png

It should not be necessary to test this (it takes a while) – we’ll work through some observations about this code.

You will have to commit a mosaic that you generated with your program. It should be named exactly mosaic.png and be located in your mp6 directory.


The following are some observations about the runtime of MP5 that will help you improve the runtime of this code.

Observation 1: Generating a mosaic uses far too much memory!

When generating a large mosaic (eg: by running the command above), the following occurs:

When the mosaic is being populated with tile images, $$w * h * PNG$$ additional memory is allocated. For a large mosaic, this would require over 1 TB of RAM! (w=500, h=500, PNG=5MB results in 1.25 TB of memory allocated.)

Modify the MP to allocate $$w * h * C$$ memory when the mosaic is populated, where C is a small constant (eg: C=8 bytes, if a only a single pointer is needed for each image; with C=8, our example above would require only 2 MB instead of 1,250,000 MB).

Observation 2: Generating a mosaic is far too slow!

After reducing the memory footprint of the program, the following occurs when generating a large mosaic:

When a mosaic is drawing, the running time is effectively a quartic polynomial!

Modify the MP to draw the mosaic in $$O(w * h + n * w’ * h’)$$ time.

Make a Mosaic!

You have spent almost four weeks making an mosaic – you should show off your work! You’ll have to gather some pictures, convert them to PNGs, and generate a mosaic using your mp6 executable.

After generating your mosaic, make sure to commit it to SVN as mosaic.png.

Making a great mosaic: Gathering Pictures

A good mosaic requires a lot of tile images. A baseline for a decent mosaic is ~100 tile images if the images are all different (eg: not all daylight pictures or selfies) and ~1000 for a great mosaic. You probably already have many images:

Making a great mosaic: Converting to PNG

The program you built requires PNG files as input. Often photos are JPEG files and must be converted.

Once you have converted all of the image into PNG, place all of the images into a single directory inside of your mp6 folder. This folder will likely be very large – you should NOT commit it to svn!

Making a great mosaic: Sharing and explaining what you’ve made

A mosaic looks like a fun Instagram “block” transformation at first glance, but becomes even more amazing when someone understands what they’re seeing – an image made entirely from other images.

If you share you image, it’s best if you describe what you’ve done! If you want to share it with your peers, post it with #cs225 so we can find it. :)

Handing in Your Code

Commit your changes in the usual way:

svn ci -m "mp6 submission"

If you add any new files, remember to svn add them.

Please don’t commit your tile images! This could easily amount to hundreds of megabytes of files per student, and EngrIT will probably not like that :)

Grading Information

As specified in the Requirements section above, you are able to modify any/all parts of this MP that you wish. To that end, we will use all files present in your mp6 directory to grade your code. We will use the following commands to test your code:

./mp6 source.png /class/cs225/mp5_pngs/ 400 5 mosaic.png

Don’t forget to commit the mosaic.png that you generate!

If running make doesn’t produce an executable called mp6 or your mp6 executable doesn’t work with the above arguments, you will receive a 0 on this MP.

Good luck!