Explore Commands
Try each of following in a terminal (do a pwd after each):
- cd cs115/lab1
- cd ..
- cd ~/cs115/lab1
- cd
Questions
- What does the cd .. do?
- What do you think the ~ represents?
- What does cd do?
Shortcuts:
- What happens when you press the up arrow?
- What does typing history do?
- How are history and the up arrow related?
- In the history output, numbers precede a command. Try typing an exclamation mark (!) and then a number from the list. What happens?
- What happens when you press the tab key after typing: cd cs115/la
Challenges:
Using the man pages for cat, display a file with line numbers in front.
We will leave the explanation of compiling files until a later lab. Let's learn by example:
Single Files
Compiling a Single File
You might want to perform these in your CS115 directory. You can use the ls command after step 1 and 2 to see what files are being added to your directory.
- First, get the file to be compiled:
cp /net/data/ftp/pub/class/115/ftp/cpp/hello.cpp hello.cpp
- Then, compile:
- You can now run the code:
Explore:
- Try playing around with the order of the arguments after the
g++ in Step 2
- If something happens to your hello.cpp code, don't worry--you can always get it again (from Step 1)
- Try leaving out the
-o hello in Step 2. What is produced? Can you use that to run the code?
- Try replacing
hello with test. Try to run test with or without the ./ in front. Does hello work that way too? If you are curious about why, try man test
Multiple Files
Compiling Multiple Files
You might want to perform these in your CS115 directory. You can use the ls command after step 1, 2, and 3 to see what files are being added to your directory.
- First, get the three files to be compiled:
-
cp /net/data/ftp/pub/class/170/ftp/cpp/SeparateCompile/main.cpp .
cp /net/data/ftp/pub/class/170/ftp/cpp/SeparateCompile/myFunction.cpp . cp /net/data/ftp/pub/class/170/ftp/cpp/SeparateCompile/myFunction.h .
- Then, compile the two
.cpp files:
g++ -c main.cppg++ -c myFunction.cpp
- What two files are created? These are refered to as object files and contain the machine code
- Now, the two object files need to be "linked" or combined together into the "executable" (in other words, the file that will be run)
g++ main.o myFunction.o -o main
- You can now run the code. What will you type?
Notes:
Sequential Search
The idea is to start from either the beginning or end of the array and traverse the array element one by one until the target is located or until all the elements in the array have been visited.
The algorithm might be written something like this:
Starting from the first element to the last element of the array
Compare the current element to the target element (what you are looking for)
Return the index when a match is found
If the target element is not found, return a special value (-1) to indicate it is not found
Get the code from the instructions in the exercise.
Questions
- Is the data sorted?
- How many comparisons will be done to find the last element?
- How many comparison will be done to find the first element?
Selection Sort
There are many kinds of sorting routines. Some are easy to understand and to program, others are very complex. A couple of simple and well known sorts are bubble sort and selection sort. This section introduces selection sort.
Assume we have an array of n elements and we want to sort in descending order. The selection sort algorithm would go like this:
Set Current_Element to the start of the array
Repeat until Current_Element at the end of the array
Linear search from Current_Element to the end of the array for the Largest_Element
If the Largest_Element is not the Current_Element swap them
Move Current_Element to next element
Get the code from the instructions in the exercise.
Question
- If we wanted to sort in ascending order, how would we change the algorithm?
Insertion Sort
Another simple sorting algorithm is the insertion sort.
As with the selection sort, assume we have an array of n elements
and we want to sort in descending order. The
insertion sort algorithm is as follows:
Set Current_Index to the first position in the array
Repeat until Current_Index is at the end of the array
Set x to the element at the Current_Index
Find the insertion location, where x should be inserted in the sorted part of the array
Move all elements between the insertion location and the end of the sorted part down by one
Store x at the insertion location
Let's start with the code for the Selection Sort and then change
it to the Insertion Sort
Question
- Change the InsertionSort files to perform an insertion sort.
- Start by changing the name of the function in all three files to
reflect the new purpose.
- Change the name of the file in the #include in the two .cpp files.
- Following notes from class lectures, change the code in
InsertionSort.cpp to actually perform the insertion sort algorithm.
- Compile and test several times (uses different sets of random numbers each time).
Binary Search
The idea of binary search is to cut an array (sorted) into two parts and discard the part which could not contain our searching target.
// Code for binarySearch
int binarySearch(IntArrayType intArray, int low, int high, int target)
{
int mid, difference;
while (low <= high)
{
mid = (low + high) / 2;
difference = intArray[mid] - target;
if (difference == 0) // intArray[mid] == target
return mid;
else if (difference < 0) // intArray[mid] < target
low = mid + 1;
else
high = mid - 1;
}
return -1; // If reach here, target was not found.
}
Get the code from the instructions in the exercise.
Questions
- Is the data sorted?
- How would you print out the number of times that the Difference is calculated?