C++ Help please!!!!

[Joseph A.]

Hi, I have to take a prelim exam for my work dealing with c++. I am
VERY RUSTY so I need some help. They gave me a study sheet to prepare
for the exams, and I've done most of it but cannot figure out how to do
the following. I just need help, thank you very much.


1. Write a function in C++ called secMaxElement that takes an input a
vector<double>& and returns the second largest in the array. How fast
is your algorithm (in big O notation). What if we wanted the 5th
largest element, or the 15th largest, or more generally the kth largest
(i.e. if we made k an argument to maxElem). Don't write any code but
explain how you would solve the more general problem. How fast is your
algorithm now?

2. Write a C++ function that takes as input a double and returns its
square root (you may not use any standard library math functions of
course). There is more than one way to go here - just pick one. Write
this as a complete program (that includes a main) that takes the double
as an input at the command line.

 

[wwwolf]

Hi,
2. Write a C++ function that takes as input a double and returns its
square root (you may not use any standard library math functions of
course). There is more than one way to go here - just pick one. Write
this as a complete program (that includes a main) that takes the double
as an input at the command line.

Sounds like you just need to completly define your own homemade sqrt function in
the program.

I'm only a one-week novice but I do understand the question and the process.
note: The people on this forum will usually help you a great deal if you show
your work. At the very least, you should post your attempt. I would be
interested in seeing the other questions you supposedly finished.

 

[John Guo]

1. Write a function in C++ called secMaxElement that takes an input a

vector<double>& and returns the second largest in the array. How fast
is your algorithm (in big O notation). What if we wanted the 5th
largest element, or the 15th largest, or more generally the kth largest
(i.e. if we made k an argument to maxElem). Don't write any code but
explain how you would solve the more general problem. How fast is your
algorithm now?

This is an algorithm question, you should check out some textbook like
"Intro to algorithm, MIT press", for selection problem.

If select 2nd largest, need only one pass to the array to keep track of
the largest and 2nd largest, then it's O(n).

For general K-th selection problem, three ways to do:
1. selection selection do k times, then it's O(kn) , for any k, it's
O(n2).
2. Sort the array, and look at position k, which is O(nlogn) if you use
merge sort or heap sort (these O(nlogn) sorting algorithms.
3. There is an algorithm called BIG5 algorithm, which take linear time
O(n) for K-th selection. But it's hard to implement, and might only
have theoretical interest.

 

[Phil Staite]

1. Write a function in C++ called secMaxElement that takes an input a

vector<double>& and returns the second largest in the array. How fast

See partial_sort in STL.

2. Write a C++ function that takes as input a double and returns its
square root (you may not use any standard library math functions of

I'd use an iterative approach with an initial estimate of the root, and
halt the iteration when the root value was changing less than some very
small delta per iteration.

 

[Thomas Matthews]

Hi, I have to take a prelim exam for my work dealing with c++. I am
VERY RUSTY so I need some help. They gave me a study sheet to prepare
for the exams, and I've done most of it but cannot figure out how to do
the following. I just need help, thank you very much.


1. Write a function in C++ called secMaxElement that takes an input a
vector<double>& and returns the second largest in the array. How fast
is your algorithm (in big O notation). What if we wanted the 5th
largest element, or the 15th largest, or more generally the kth largest
(i.e. if we made k an argument to maxElem). Don't write any code but
explain how you would solve the more general problem. How fast is your
algorithm now?

I'd sort the vector then access the nth largest one.
I'd spend the rest of my time getting the program working correctly
and only worry about the speed of the code when it becomes an issue.

2. Write a C++ function that takes as input a double and returns its
square root (you may not use any standard library math functions of
course). There is more than one way to go here - just pick one. Write
this as a complete program (that includes a main) that takes the double
as an input at the command line.

I'd use an algorithm from a book that explains the square root
function. I'd use the rest of my time getting the program
finished.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library