Get Started with your first C++ Program

3. Get Started with your first C++ Program
Let us start writing a simple hello world program in C++. The source code will be created in file
hello.cc in directory ~/fce/hw1 (character “~” in directories is used to refer to the home folder).
Type the following commands:
Type the following code:
The header file <iostream> provides a standard name space std with a pre-defined object cout. This object
can be used with operator “<<” followed by a string in order to dump text into the standard output. We
will present all details in class needed to thoroughly understand this code. For now, we just need to know
that this is the pattern used to write text into the screen. The following command can be used to compile
the code:
This command takes file hello.cc as an input and produces an executable file named hello. The
program can be executed with the following command:
4. A Sorting Example
Once our first program is running correctly, let us implement the insertion sort algorithm presented in
class. This program is composed of a function running the algorithm itself, a function to print the unsorted
and sorted versions of the vector, and a main program calling these functions.
Homework 1 (5pt.)
Submission instruction:
Submit one single pdf file for this homework including both coding problems and analysis problems.
For coding problems, copy and paste your codes. Report your results.
For analysis problems, either type or hand-write and scan.
Question 1 (2 pt.) Coding: write programs of insertion sort, and mergesort. Find the input size n, that
mergesort starts to beat insertion sort in terms of the worst-case running time. You can use clock_t
function (or other time function for higher precision) to obtain running time. You need to set your input
such that it results in the worst-case running time. Report running time of each algorithm for each input
size n.
Question 2 (1pt.) You are given with an array {10, 5, 7, 9, 8, 3}. Show the arrangement of the array for
each iteration during insertion sort. You are given with the same array. Show the arrangement of the array
for each iteration of the Partition subroutine and the result of Partition subroutine.
Question 3 (1pt.) True or False
� + 3 ∈ Ω(�)
� + 3 ∈ O(�))
� + 3 ∈ Θ(�))
2,-. ∈ O(� + 1)
2,-. ∈ Θ(2,)
Question 4 (1pt.) Using the master method, determine T(n) for the following recurrances.
�(�) = 8� 3
�
2
4 + �
�(�) = 8� 3
�
2
4 + �)
�(�) = 8� 3
�
2
4 + �5
�(�) = 8� 3
�
2
4 + �6
Question 5 (extra 1pt.) Draw recursion tree for �(�) = 8� 3
,
)
4 + �. And prove the obtained T(n) by
substitution method.