← back to the schedule


Assignment #2
First C++ Program



For this assignment you are required to implement a naìˆve matrix multiplication algorithm using C++. For more information about matrix multiplication go to: Multiplying Matrices

The idea of this assignment is to expose you to C++ and to design your first algorithm. Make sure that you compile and run your program using the terminal (or the command line). This assignment will required for you to figure out things on your own, such as compiling and running a C++ program using gcc, taking execution times, and so on.

Instructions for the Report

As part of this assignment you will write a report that will contain the following:

  • Describe the design of your algorithm. Remember this is a sequential algorithm.
  • Provide a brief time complexity analysis of this algorithm.
  • Build a table or figure with the running times of your algorithm showing how the execution time behaves as the matrix size doubles.
  • Since you are implementing a naïve version of the matrix multiplication algorithm, research and add to your report other algorithms that can solve this problem faster than the naïve version. Hint: Strassen algorithm
  • 3 pages max.

Instructions for the Code

For your code you will:

  • Write the C++ sequential program that executes this algorithm. Name your file matmult.cpp
  • Run this program using a 4x4, 16x16, 128x128, and a 1024x1024 matrices.
    • You could fill these matrices with random numbers.
  • Collect the sequential execution time of the algorithm for each matrix size. Try to execute several times for each matrix size, so you can have an average execution time that is more accurate.

Format and Due Date

Submit a PDF version of your report together with the matmult.cpp code (zip these two files) Monday of Week 5 by 11:59PM via Kit (there will be a space where you can submit your PDF document). Make sure to include your name, the submission date, and course code both in the PDF and the matmult.cpp file.


EVALUATION

Assignment #2 is worth 15 points and will be submitted individually.

Have fun! And if you have any questions remember my email or contact me via Teams!



← back to the schedule