NYU POLY CS2134 HW 1a

CS2134 Homework 1A
Fall 2014
Due 11:59 p.m. Monday, September 8, 2014
September 2, 2014
Your rst assignment includes a programming portion and a written portion. The programming
portion should consist of a single le called hw01.cpp, and the written portion should consist of a
single le called hw01written in a standard format (.txt, .doc, .htm., or .pdf). Be sure to include
your name at the beginning of each le! You must hand in both les via MyPoly.
Programming Part:
1. (a) Write a function (or 3 seperate functions) to return the minimum item in a vector
containing:
i. chars
ii. ints
iii. strings
(b) Write a function (or 3 seperate functions) to return the maximum item in a vector
containing:
i. chars
ii. ints
iii. strings
2. Using the linked list class
class Node
{
public: // These member variables are made public to simplify your coding.
// Of course these member variables should be private!
chNode( char ch, Node * ptr = nullptr):data(ch),next(ptr){}
char data;
Node * next;
};
1
and a pointer to the class Node * nodePtr; write the code to perform the following:
create a linked list of three nodes containing the items B, D, E.
add a node containing A to the front of your linked list
print out the memory locations of A, B, C D, E and nodePtr (and hand in this
information with the written part).
delete the node containing A, (nodePtr now points the the nodes containing B, C
D, E )
3. For an array, int * intPtr = new int[5];, using only pointers (no array indexing) write
the code to perform the following:
insert items 2, 3,4, 5 into the rst three positions (positions 0,1,2,3).
add item 1 to the front of your array; (you need to move the other items)
Print out the memory locations of 1, 2, 3, 4, 5 and intPtr (and hand in this information
with the written part).
delete the array pointed to by intPtr
2
Written Part:
1. Write each of the following functions in Big-Oh notation:
(a) T(n) = 12n log(n) + 10n
0.5
log
3
(n) + 12
(b) T(n) = n log(n) + n log
2
(n) + 12n
(c) T(n) = 22 log(n
12
) + 12 log(4 n)
(d) T(n) = 1000 n log
5
(n) + 0.002n
3
+ 8n
2
(e) T(n) = (4n
2
+ 4 n) 11n
(f) T(n) = n log(n
12
) + 8n
2
(g) T(n) =
log(n)(12nlog(n)+n
2
)
n
(h) T(n) =
n
2
(This means n choose 2)

(i) T(n) =
n
3
(This means n choose 3)

2. For each of the following code fragments, determine the worst case running time using Big-Oh
notation as a function of n.
(a) int sum = 0;
for (int i = 0; i < n; i++)
sum += i;
for (int j = 0; j < n; j++)
sum += j;
for (int k = 0; k < n; k++)
sum += k;
(b) int sum = 0;
for (int i = 0; i < n; i++)
{
sum += i;
for (int j = 0; j < n; j++)
sum += j;
}
3
(c) int sum = 0;
for (int i = 0; i < n; i++)
{
sum += i;
for (int j = 0; j < n; j++)
{
sum += j;
for (int k = 0; k < n; k++)
sum += k;
}
}
(d) int sum = 0;
for (int i = 0; i < n; i*=2)
{
sum += i;
}
(e) int sum = 0;
for (int i = 0; i < n; i*=2)
{
sum += i;
for (int j = 0; j < n; j++)
{
sum += j;
}
}
(f) int sum = 0;
while (n>0)
{
cout<< n%2;
sum += n%2;
n/=2;
}
3. Suppose a program takes 0.05 seconds to run on input size of 2048. Estimate how long it
would run for an input size of 2
13
if:
(a) the program had an O(n) running time.
(b) the program had an O(n
2
) running time.
(c) the program had an O(n
4
) running time.
4
4. Arrange the following in increasing order: O(n
2
log(n)), O(2
n
), O(n
3
), O(n (log(n))
2
), O(n),
O(n
0.5
log(n)), O(n log(n)), O(n
2
), O(log
2
(n)). Indicate if any two have the same rate.
5. Suppose you had a very complicated code that was dicult to analyze. To get a quick idea
of your algorithms running time you ran your program on dierent sized inputs. Suppose
the following are the timing results for your algorithm. Using the timing results below,
indicate the most likely running time in big-Oh notation; choose one from the following list.
O(1), O(n), O(n
2
), O(n
3
), O(n
4
).
n time
2^7 0.002094
2^8 0.00834
2^9 0.033412
2^10 0.133054
2^11 0.532501
2^12 2.12835
6. Using the denition of Big-Oh, show that 3n + 17 log(n) + 5 = O(n).
5

NYU POLY CS2134 HW 1a

Uploaded by

Copyright:

Available Formats

NYU POLY CS2134 HW 1a

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

NYU POLY CS2134 HW 1a

Uploaded by

Copyright:

Available Formats

CS2134 Homework 1A

(This means n choose 2)

(This means n choose 3)

You might also like