B215 Practical exercises – Week 7
ICT283 (not assessed but must be attempted)
Objectives:
· More practice with use of an STL map
· Continue with the data structures requirements of assignment 2
· Start work on specific assignment 2 requirements
· Experiment with sorting and do empirical comparisons of their performance
· Make us of the pointer to function concept
· Think critically about the problem solving approaches that you use and the relevant theory
It is very important not to fall behind with these exercises. You should complete this lab to prepare for assignment 2.
Specific Assignment 2 requirements start in this lab.
Exercises
a.
This question enables you to practice using the STL map if you feel you need more programming practice with the STL map (see Lab 7). Such maps are needed in assignment 2. For this exercise, you would need to refer back to the practice exercises from labs 2 to 5.
Use an STL map to relate a student with his/her results. The student id is the map key. Write a test program to demonstrate that your map works.
b.
Create two arrays of 1000 (try 10,000 too) numbers each. Populate both arrays with random numbers or use your data reading routine from the assignment. Use library routine qsort (http://www.cppreference.com/wiki/c/other/qsort) and sort (http://www.cppreference.com/wiki/stl/algorithm/sort) in turn to sort both the arrays. You will need to write a function for doing comparisons. The function is passed to qsort as a function pointer. The library routine qsort will “callback” your function when it needs to compare two items in the array.
Using the idea above, can the BST insert and traversals routines take in function pointers to functions that you write? See the textbook chapter on Binary Trees, section on Binary Tree Traversal Algorithms and Functions as Parameters.
Use a profiler to time how long it takes to do the sort. Try a few other sort routines and time them. If you have a compiler IDE which provides profiling tools, you might try it out. Otherwise, you may want to use the very sleepy profiler (http://www.codersnotes.com/sleepy/). Run your program and then run the profiler and select your programs process to profile. If the program runs too fast because you have got a fast processor, increase the size of the arrays. Alternatively, you can do the timing yourself. See the example http://en.cppreference.com/w/cpp/chrono. Alternatively see http://en.cppreference.com/w/cpp/chrono/c/time or http://en.cppreference.com/w/cpp/chrono/c/clock (has code example).
Put each part in separate subroutines, so that profiler can tell how much time was spent in each subroutine. See how the Fibonacci subroutine is timed at http://en.cppreference.com/w/cpp/chrono.
Implement the merge algorithm given in lecture 25. The two arrays to be merged are the ones from above. They need to be pre-sorted using one of the sorting algorithms (sort, qsort) above. Profile your code. You can use the timing routine as used to time the fibonacci routine reproduced below from http://en.cppreference.com/w/cpp/chrono.
c.
In the example at http://en.cppreference.com/w/cpp/chrono, there is a call, fibonacci(42), that will return the 42nd Fibonacci number. Time this call, and find out what time values are obtained when the parameter 42 is increased by 1 each time (43, 44, 45, .. etc) you change, build and run. Try larger numbers. What can you say about the nature of the fibonacci routine? How does the time complexity
increase as n is increased? Is it possible to make this routine more efficient?
// Code from http://en.cppreference.com/w/cpp/chrono
#include
#include
#include
// returns the nth Fibonacci number
// Does this fibonacci code represent a complex algorithm?
// Is it possible to make this routine more efficient?
unsigned long fibonacci(unsigned n)
{
if (n < 2) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
auto start = std::chrono::system_clock::now();
std::cout << "f(42) = " << fibonacci(42) << '\n'; // LINE 1
auto end = std::chrono::system_clock::now();
std::chrono::duration
std::time_t end_time = std::chrono::system_clock::to_time_t(end);
std::cout << "finished computation at " << std::ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "s\n"; } Comment out the call to Fibonacci at LINE 1 – i.e. comment out the entire line and then build and run the program. This will give you a base line time value showing time taken when the Fibonacci routine is not called. Then uncomment and try different parameter n values, build and run. Record the value n and the time taken. What observation can you make about the relationship between n and the running time for this recursive implementation of Fibonacci. d. (needed for assignment 2) Convert your BST from laboratory 9 into a minimal and complete BST. Use function pointers in the traversal routines. See the files testTree.cpp and BinarySearchTree.h When putting data into the BST, what methods or operators must exist for the data itself? Test the BST to make sure all methods work. In particular make sure that you can pass the tree to other routines by value and reference. Check that data values are as expected on pass/return to/from routines. e. (needed for assignment 2) Use the modified form of assignment 1 that reads from multiple data files. (exercise. 5 of Lab 8). Do not attempt to code this question until you have completed exercise 5 of Lab 8 and exercise d above. Your BST must be completed and fully tested. The major design/programming requirements of Assignment 2 are as shown below. Think of how you can use your BST and the STL map in the modified assignment 1 to store data for processing as required by the menu options. The use of BST and map is *mandatory* for assignment 2, so think very hard and do not start coding until you have thought through the issues. Hint: There are issues that you have to resolve before you incorporate the BST and map. The write up of these issues and your resolution is part of the rationale for taking a particular approach. Don’t make things up as you go along as you now have access to sufficient theory to guide the thinking process needed for assignment 2. Cite the theory in your rationale for your particular approach. You will not be told how to incorporate the BST or the STL map in your assignment 1 to make it into assignment 2, so whatever approach you come up with will require written justification that will be assessed. *Vector is optional*. If you decide to use Vector as well, written justification is needed for that too. You will need to explain the rationale for use of these data structures in *your* particular way. The data structures can be used in many ways and so we want to know the thinking behind your choice of usage. Write down what you are thinking and the relevant theory you have used to guide your thinking. Add the BST to the UML of assignment 1. Are you planning to continue using Vector? Update the data dictionary. Add the BST to the data dictionary of assignment 1. Read the lecture notes and the assignment 1 QandA to find out about how to write the data dictionary. Ask your tutor if you are not sure. Stress test your assignment by loading a dozen copies of the same file. The file data/met_index.txt will have the same file name listed 12 times. Another stress test would be having all the csv data files in data listed multiple times in data/met_index.txt. For bonus marks, you will need to add an extra menu option to the modified assignment 1. Make sure all other menu options are working before you start on this extra menu option. This bonus is not available if any of the other menu option requirements is not working. Your Time class is needed for this option. New menu option: Given a Date in the form d/m/yyyy, show the times for the highest solar radiation for that Date. Output to screen in this format: (There can be one or more time values that are output.) Date: 11/1/2019 High solar radiation for the day: 1046 W/m2 Time: 10:40 11:30 Add the test plan of the above menu option to your assignment 1 test plan. Make you sure you have manually checked the expected output. This manual checking applies for all the menu options. e. Please read the QandA files for both assignments 1 and 2 (when available). The QandA file for assignment 2 can get updated very close to submission time, if someone asks a question then. Internal students should demonstrate progress on their assignment to their tutor. This means code too. A good approach to take would be to always have a running version of the assignment. It may not fulfil all the requirements of the assignment, but at any point in time, some requirements would be completed. Remember the incremental approach covered in the lectures at the start of semester. Use stubs for functionality that is incomplete. You must demonstrate progress on the assignment (lab 11) before the assignment is submitted. You will want to do this demonstration to get quick feedback and to avoid academic misconduct accusations later on. If you have questions, ask early in class or by email. Don’t expect turnaround time to be quick in the last week of semester/trimester, so all questions need to be asked by the second last week of semester/trimester. � See the section on “Asymptotic Notation: Big-O Notation” in the textbook chapter on Searching and Sorting Algorithms. PAGE 1 Lab10.doc