Question # 1. Write a function template to find the maximum of two values. Quest
ID: 3635931 • Letter: Q
Question
Question # 1.Write a function template to find the maximum of two values.
Question # 2.
Give an example of an algorithm with complexity O(1).
Question # 3
Write a function to find the reach-ability matrix of a diagraph using Warshall's algorithm.
Question # 4:
Write an insertion sort algorithm that is appropriate for a linked list.
Question # 5.
Demonstrate that Morse code is not immediately decodable by showing that the bit string 100001100 can be decoded in more than one way.
Question # 6.
what are the variants of standard linked lists that make algorithms for some of the basic list operation simpler and efficient?
Explanation / Answer
1.
#include <iostream>
using namespace std;
inline int const& max (int const& a, int const& b)
{
return a < b ? b : a;
}
// maximum of two values of any type
template <typename T>
inline T const& max (T const& a, T const& b)
{
return a < b ? b : a;
}
// maximum of three values of any type
template <typename T>
inline T const& max (T const& a, T const& b, T const& c)
{
return ::max (::max(a,b), c);
}
int main()
{
cout <<" " <<::max(7, 42, 68); // calls the template for three arguments
cout <<" " <<::max(7.0, 42.0); // calls max<double> (by argument deduction)
cout <<" " <<::max('a', 'b'); // calls max<char> (by argument deduction)
cout <<" " <<::max(7, 42); // calls the nontemplate for two ints
cout <<" " <<::max<>(7, 42); // calls max<int> (by argument deduction)
cout <<" " <<::max<double>(7, 42); // calls max<double> (no argument deduction)
cout <<" " <<::max('a', 42.7); // calls the nontemplate for two ints
}
2.
A simple example of O(1) might be return 23; -- whatever the input, this will return in a fixed, finite time.
A typical example of O(N log N) would be sorting an input array with a good algorithm (e.g. mergesort).
A typical example if O(log N) would be looking up a value in a sorted input array by bisection.
3.
The constructor for class GraphTC computes the transitive closure of G in the private data field T so that clients can use GraphTC objects to test whether any given vertex in a digraph is reachable from any other given vertex. The constructor initializes T with a copy of G, adds self-loops, then uses Warshall's algorithm to complete the computation. We use a DenseGraph object for the transitive closure T because the algorithm needs an efficient implementation of the edge existence test (see Section 17.5).
4.
5
Hand sent CW telegraphy is now mostly an amusement for those of us who like 'pounding brass', and is no longer used commercially. High speed error-correcting codes, sent via UHF links to satellites where the large bandwidth is not a problem since there is plenty of spectrum space at UHF, have long superseded the brasspounder's art. Statements at the beginning of 1999 that Morse code is 'no longer used' were not however true. Oddly, there is one high-tech industry where Morse code is still used: airline pilots have to know it. Admittedly it is only at about 5 wpm, and only three letters at a time. Beacons which radiate in the medium wave region of the spectrum use three-letter identifiers sent very, very slowly in Morse.
Different versions of Morse code
Morse's original code was not quite the same as the one in use today. In particular C, O, R, Y and Z contained spaces within the letter codes which must have been tricky to handle, and the numbers were different. This ‘American’ morse code was in wide use until the 1920’s. For international use it was modified as a result of a conference in Berlin in 1851; this regularised the code on a more rational basis and eliminated the spaces within the letters, but equally important from a European point of view it provided codes for accented letters.
Both the original code and the current International Code use the same principle, that the commonest letters have the shortest codes. How to find out what the letter incidence is? Difficult now, from scratch, but Morse had a marvellous idea. He went to his local newspaper. There he found compositors making up pages by hand from individual letters; capital letters were in one case or tray of type, and this was set above the case of small letters. This is the origin of 'upper and lower case' letters. Morse simply counted the number of pieces of type for each letter, thinking, soundly enough, that this must be related to the number needed. Thus 'e' has the shortest code, 'dit', whereas 'z' is (now) 'da-da-di-dit' and 'q' (now) 'da-da-di-dah'. Notice that I write them as they sound; morse was a visual code in the early days, but it is now an aural one. An intriguing question: the symbol for V, di-di-di-dah, is also the opening phrase of Beethoven’s Fifth (V’th) Symphony. Morse was 20 years younger than Beethoven - was he a fan of the composer?
Morse can be decoded by computer, but that can't be much fun. Some of the earliest telegraphs used with land-lines employed an inked stylus which was moved sideways when a signal was received and which wrote on a moving paper tape.
Da-da-di-di-dit di-di-di-da-da da-di-dit dit
di-da-dit da-da-dah da-di-dit
di-da-di-da-dit di-di-di-da-di-dah
[73 de Rod AR SK:
best wishes (73) from (de) Rod, end of message (AR), end of work (SK, i.e. closing down).]
Morse Codes
American
International
SOS!
The apparently well-known SOS distress call is not quite what it seems. Fancifully represented as 'Save Our Souls', it actually means no such thing. It isn't even SOS; it is a procedural signal, and the three dots - three dashes - three dots are sent as a single signal without the gaps that would be present if three separate letters were being sent. The distress call is
di-di-di-dah-dah-dah-di-di-dit
and not
di-di-dit dah-dah-dah di-di-dit
The International use of the signal was proposed at the Second International Radio Telegraphic Convention in Berlin on November 3rd 1906; "SOS" had been part of the German Radio Regulations since April 1st 1905. The first Conference had been held in 1903, but the nature of procedural signals was not part of its remit. The 1906 Conference made the "SOS" signal obligatory from July 1st 1908.
Prior to the 1906 Conference there was no standard signal. Marconi operators used "CQD" from February 1904, the D being an extension to the standard CQ signal to signify distress. In 1906 the Navy suggested "NC", this being the equivalent flag signal, but by this time "SOS" was more or less in place.
Marconi operators were rather resistant to adopting "SOS" - one result was that distress signals from the Titanic were sent by its Marconi operators using both "CQD" and "SOS".
6.