In your own words describe the ‘knapsack problem’. Further, compare and contrast the use of a brute force and a dynamic programming algorithm to solve this problem in terms of the advantage and disadvantages of each. An analysis of the asymptotic complexity of each is required as part of this assignment.

C++ Functions

There are many reasons why one would want to know the minimum and the maximum of a series of values: fight control, range determinate, even in academia, professors often seek the distribution of grades on homework, exams, and class grades.

For this lab, you will write a program which will include a minimum function and a maximum function. Both functions should take in three values. The minimum function should return the minimum of the three values and the maximum should return the maximum of the three values.

The values should be entered by the user.

So, at the very latest, your program should have three functions:

- main()

- minimum()

- maximum()

Beyond that, feel free to modularize your code as you wish.

Answer in JAVA

Write a program that would prompt the user to enter an integer. The program then would displays a table of squares and cubes from 1 to the value entered by the user. The program should prompt the user to continue if they wish. Name your class NumberPowers.java, add header and sample output as block comments and uploaded it to this link.

Use these formulas for calculating squares and cubes are:

• square = x * x
• cube = x * x * x

Assume that the user will enter a valid integer.

The application should continue only if the user enters “y” or “Y” to continue.

Sample Output

Welcome to the Squares and Cubes table

Enter an integer: 4

Number Squared Cubed
====== ======= =====
1 1 1
2 4 8
3 9 27
4 16 64

Continue? (y/n): y

Enter an integer: 7

Number Squared Cubed
====== ======= =====
1 1 1
2 4 8
3 9 27
4 16 64
5 25 125
6 36 216
7 49 343

Continue? (y/n): n

Write a C++ program that scores a blackjack hand. In blackjack, a player receives from two to five cards. The cards 2 through 10 are scored as 2 through 10 points each. The face cards --- jack, queen, and king ---- are scored as 10 points. The goal is to come as close to a score of 21 as possible without going over 21. Hence, any score over 21 is called “busted”. The ace can count as either 1 or 11, whichever is better for the user. Write a C++ program that scores a blackjack hand. In blackjack, a player receives from two to five cards. The cards 2 through 10 are scored as 2 through 10 points each. The face cards --- jack, queen, and king ---- are scored as 10 points. The goal is to come as close to a score of 21 as possible without going over 21. Hence, any score over 21 is called “busted”. The ace can count as either 1 or 11, whichever is better for the user. Write a C++ program that scores a blackjack hand. In blackjack, a player receives from two to five cards. The cards 2 through 10 are scored as 2 through 10 points each. The face cards --- jack, queen, and king ---- are scored as 10 points. The goal is to come as close to a score of 21 as possible without going over 21. Hence, any score over 21 is called “busted”. The ace can count as either 1 or 11, whichever is better for the user. Write a C++ program that scores a blackjack hand. In blackjack, a player receives from two to five cards. The cards 2 through 10 are scored as 2 through 10 points each. The face cards --- jack, queen, and king ---- are scored as 10 points. The goal is to come as close to a score of 21 as possible without going over 21. Hence, any score over 21 is called “busted”. The ace can count as either 1 or 11, whichever is better for the user.

#Below is a class representing a person. You'll see the
#Person class has three instance variables: name, age,
#and GTID. The constructor currently sets these values
#via a calls to the setters.
#
#Create a new function called same_person. same_person
#should take two instances of Person as arguments, and
#returns True if they are the same Person, False otherwise.
#Two instances of Person are considered to be the same if
#and only if they have the same GTID. It does not matter
#if their names or ages differ as long as they have the
#same GTID.
#
#You should not need to modify the Person class.

class Person:
    def __init__(self, name, age, GTID):
        self.set_name(name)
        self.set_age(age)
        self.set_GTID(GTID)

    def set_name(self, name):
        self.name = name

    def set_age(self, age):
        self.age = age

    def set_GTID(self, GTID):
        self.GTID = GTID

    def get_name(self):
        return self.name

    def get_age(self):
       return self.age

    def get_GTID(self):
        return self.GTID

#Add your code below!

#Below are some lines of code that will test your function.
#You can change the value of the variable(s) to test your
#function with different inputs.
#
#If your function works correctly, this will originally
#print: True, then False.
person1 = Person("David Joyner", 30, 901234567)
person2 = Person("D. Joyner", 29, 901234567)
person3 = Person("David Joyner", 30, 903987654)
print(same_person(person1, person2))
print(same_person(person1, person3))

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

What would the complexity of a brute force approach be? Code an O(nlog(n)) algorithm to count the number of inversions. Hint - piggy back on the merging step of the mergesort algorithm.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Complete the code in the functions indicated to count inversions

// countlnv.cpp file

#include <iostream>
#include <vector>

using namespace std;

int numinv;

void mergeSort(vector<int>& numvec, int left, int right);
int merge(vector<int>& numvec , int left, int mid, int right);

int countInv(vector<int>& numvec) {
numinv = 0;
mergeSort(numvec, 0, numvec.size());
cout << "Sorted output: ";
for (auto ele : numvec)
   cout << ele << " ";
   cout << endl;
return numinv;
  
}

//Sorts the input vector and returns the number of inversions in that vector
void mergeSort(vector<int>& numvec, int left, int right){
// Your code here

}

int merge(vector<int>& numvec , int left, int mid, int right){
// Your code here

}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Use the following test code to evaluate your implementation

// countlnv_test.cpp

/* Count the number of inversions in O(n log n) time */
#include <iostream>
#include <vector>

using namespace std;

int countInv(vector<int>& numvec);

int main()
{
int n;
vector<int> numvec{4, 5, 6, 1, 2, 3};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 9
  
numvec = {1, 2, 3, 4, 5, 6};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 0
  
numvec = {6, 5, 4, 3, 2, 1};
n = countInv(numvec);
cout << "Number of inversions " << n << endl; // Should be 15
  
numvec = {0, 0, 0, 0, 0, 0};
n = countInv(numvec);
cout << "Number of inversions " << n << endl;; // Should be 0
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Thank you for your time and help!

python - needed asap (thank you in advance!!!!)

Using the provided climate_data_Dec2017.csv file, find out how many readings there were across our recorded weather stations for each wind direction on the 26th of December. The file contains data for more than this particular day. To make sure that you only include readings from the 26th, you should use pandas to filter the data. If any wind direction value can still be found for the other days but not 26th, it should still appear in the result with value zero. While we encourage you not to rely on a loop for this part, you are free to do as you see fit. (Hint: pandas can help you find a set of unique values from a series of data) Let your program print out sorted wind directions in ascending alphabetical order.

The output should look like this:

E : 4
ENE : 2
ESE : 1
N : 0
NE : 1
NNE : 1
NNW : 1
NW : 0
S : 0
SE : 3
SSE : 3
SSW : 0
SW : 1
W : 0
WNW : 0
WSW : 0

data file

Date,State,City,Station Code,Minimum temperature (C),Maximum temperature (C),Rainfall (mm),Evaporation (mm),Sunshine (hours),Direction of maximum wind gust,Speed of maximum wind gust (km/h),9am Temperature (C),9am relative humidity (%),3pm Temperature (C),3pm relative humidity (%)
2017-12-25,VIC,Melbourne,086338,15.1,21.4,0,8.2,10.4,S,44,17.2,57,20.7,54
2017-12-25,VIC,Bendigo,081123,11.3,26.3,0,,,ESE,46,17.2,53,25.5,25
2017-12-25,QLD,Gold Coast,040764,22.3,35.7,0,,,SE,59,29.2,53,27.7,67
2017-12-25,SA,Adelaide,023034,13.9,29.5,0,10.8,12.4,SE,43,18.6,42,27.7,17
2017-12-25,QLD,Brisbane,040913,22.5,36.2,0,11.0,10.0,WSW,61,29.5,53,32.3,53
2017-12-25,QLD,Townsville,032040,24.8,32.5,0,,,NNE,41,29.1,55,31.1,48
2017-12-25,QLD,Cairns,031011,20.3,33.3,0,,,E,41,29.2,59,32.4,45
2017-12-25,NSW,Wollongong,068228,15.9,21.3,7.6,,,SSW,48,18.5,80,19.5,70
2017-12-25,NSW,Newcastle,061055,19.8,21.6,0.6,,,S,48,20.2,83,20.9,74
2017-12-25,VIC,Ballarat,089002,8.5,21.4,0,,,SSE,54,13.3,62,21.1,40
2017-12-25,QLD,Sunshine C,040861,20.2,31.5,0,,,NNE,43,28.9,62,28.8,61
2017-12-25,NSW,Canberra,070351,13.4,23.0,0,,,ESE,39,15.0,66,21.9,47
2017-12-25,NSW,Albury,072160,14.7,29.1,0,,,SSE,37,18.7,42,26.6,32
2017-12-25,QLD,Toowoomba,041529,19.5,32.0,0,,,E,61,24.4,68,31.2,39
2017-12-25,VIC,Geelong,087184,14.1,21.6,0,,,S,41,16.7,58,19.9,53
2017-12-25,NT,Darwin,014015,24.0,27.6,20.0,6.6,0.0,NNE,46,25.4,91,27.3,81
2017-12-25,WA,Perth,009021,19.7,33.1,0,11.0,13.3,SW,39,27.8,34,31.1,29
2017-12-26,VIC,Ballarat,089002,10.8,29.1,0,,,SE,56,17.3,59,27.1,30
2017-12-26,NSW,Canberra,070351,10.8,22.4,0,,,E,39,18.3,57,21.8,48
2017-12-26,QLD,Brisbane,040913,19.0,29.7,54.8,12.4,7.5,E,26,25.2,77,28.8,56
2017-12-26,NSW,Newcastle,061055,18.5,22.5,3.8,,,SE,43,21.1,76,21.7,79
2017-12-26,SA,Adelaide,023034,18.0,33.3,0,11.4,12.7,E,43,25.7,23,28.6,28
2017-12-26,QLD,Toowoomba,041529,16.4,28.4,0,,,E,74,23.9,65,22.7,79
2017-12-26,WA,Perth,009021,15.4,27.4,0,9.0,13.2,SW,41,22.3,59,25.7,45
2017-12-26,VIC,Bendigo,081123,12.8,31.3,0,,,SE,41,20.5,50,30.3,27
2017-12-26,QLD,Gold Coast,040764,20.4,27.9,11.6,,,SSE,52,24.7,87,25.8,81
2017-12-26,VIC,Geelong,087184,12.5,26.6,0,,,SSE,31,18.9,69,23.8,50
2017-12-26,VIC,Melbourne,086338,12.5,30.5,0,8.0,12.9,SSE,37,17.4,66,27.0,43
2017-12-26,QLD,Cairns,031011,22.0,33.0,0,,,ENE,33,29.2,61,31.1,56
2017-12-26,NSW,Wollongong,068228,17.8,24.1,0,,,ENE,41,21.3,59,23.9,55
2017-12-26,QLD,Sunshine C,040861,19.9,28.6,7.4,,,ESE,33,28.4,67,27.6,68
2017-12-26,QLD,Townsville,032040,23.4,32.4,0,,,NE,37,29.9,52,30.4,50
2017-12-26,NSW,Albury,072160,14.0,30.7,0,,,NNE,31,21.6,46,29.2,26
2017-12-26,NT,Darwin,014015,24.6,31.6,8.0,4.6,1.4,NNW,56,26.7,90,30.3,72
2017-12-27,WA,Perth,009021,14.5,26.5,0,11.8,12.3,SSW,54,21.4,49,25.5,34
2017-12-27,NSW,Wollongong,068228,18.8,25.1,0,,,NE,43,21.8,77,23.3,72
2017-12-27,VIC,Geelong,087184,14.9,37.2,0,,,N,41,26.4,46,35.9,20
2017-12-27,QLD,Sunshine C,040861,21.5,28.8,1.4,,,SE,33,26.5,73,27.6,66
2017-12-27,NSW,Albury,072160,15.0,32.5,0,,,E,30,23.6,54,30.9,29
2017-12-27,VIC,Ballarat,089002,15.3,32.9,0,,,N,56,22.2,55,30.9,30
2017-12-27,QLD,Toowoomba,041529,16.7,26.9,29.4,,,E,57,20.4,80,26.1,57
2017-12-27,QLD,Gold Coast,040764,20.3,29.4,0.2,,,S,41,26.4,72,27.5,71
2017-12-27,NSW,Canberra,070351,15.8,29.1,0,,,NE,33,18.9,68,26.4,37
2017-12-27,SA,Adelaide,023034,20.6,36.0,0,8.8,3.8,WSW,48,32.9,9,28.9,34
2017-12-27,VIC,Melbourne,086338,17.3,34.5,0,11.8,10.4,NW,46,25.3,45,32.9,32
2017-12-27,VIC,Bendigo,081123,16.3,35.6,0,,,N,46,22.7,54,32.9,30
2017-12-27,QLD,Cairns,031011,22.4,32.6,0,,,NE,35,29.1,59,31.3,55
2017-12-27,QLD,Townsville,032040,23.2,32.8,0,,,NE,37,30.3,52,30.0,59
2017-12-27,QLD,Brisbane,040913,20.7,29.6,3.0,5.6,10.0,E,30,27.3,60,28.2,56
2017-12-27,NSW,Newcastle,061055,20.5,23.5,0,,,E,39,22.1,80,22.9,79
2017-12-27,NT,Darwin,014015,23.5,31.3,8.8,3.0,0.0,NW,15,28.7,77,29.5,73
2017-12-28,NSW,Newcastle,061055,19.8,24.3,0,,,E,41,22.6,76,23.6,81
2017-12-28,QLD,Toowoomba,041529,16.6,27.9,0,,,E,43,21.3,73,27.4,52
2017-12-28,SA,Adelaide,023034,21.1,25.0,0,10.2,1.0,SSE,26,22.1,82,23.8,74
2017-12-28,QLD,Sunshine C,040861,20.4,28.8,24.0,,,E,31,26.0,69,27.6,63
2017-12-28,VIC,Ballarat,089002,20.1,30.4,0,,,NW,31,25.1,42,29.3,31
2017-12-28,NSW,Wollongong,068228,19.8,25.3,0,,,NE,39,23.2,73,23.8,75
2017-12-28,NSW,Canberra,070351,12.9,32.4,0,,,NW,37,20.1,70,32.4,31
2017-12-28,VIC,Bendigo,081123,22.6,34.4,0,,,NNE,24,26.2,43,32.6,29
2017-12-28,QLD,Townsville,032040,26.9,32.6,0,,,ENE,39,30.2,57,31.0,54
2017-12-28,WA,Perth,009021,15.7,28.8,0,11.2,13.2,SSW,52,22.1,44,25.6,40
2017-12-28,VIC,Melbourne,086338,24.0,32.8,0,14.0,4.1,SSW,31,26.4,46,23.9,73
2017-12-28,QLD,Brisbane,040913,20.6,29.4,0.6,7.8,12.5,ESE,24,27.5,60,28.8,57
2017-12-28,QLD,Gold Coast,040764,20.7,28.9,0,,,SSE,35,26.5,75,28.1,64
2017-12-28,NSW,Albury,072160,17.4,32.8,0,,,ENE,35,22.3,63,31.9,39
2017-12-28,VIC,Geelong,087184,22.9,28.0,0,,,S,39,25.7,54,20.7,85
2017-12-28,NT,Darwin,014015,25.6,34.5,1.0,0.8,9.8,WNW,31,31.0,72,33.1,62
2017-12-28,QLD,Cairns,031011,22.6,34.2,0,,,E,39,30.2,58,32.8,46
2017-12-29,NSW,Wollongong,068228,19.4,25.8,0,,,SW,22,22.7,85,23.2,84
2017-12-29,VIC,Bendigo,081123,20.6,30.6,0.8,,,SW,39,23.6,76,29.6,47
2017-12-29,NSW,Newcastle,061055,20.8,26.3,0,,,ENE,41,24.2,78,25.7,68
2017-12-29,SA,Adelaide,023034,18.2,22.7,2.4,2.8,1.9,WSW,33,20.3,70,21.5,64
2017-12-29,QLD,Toowoomba,041529,18.9,28.9,0,,,NNE,39,22.5,81,27.8,48
2017-12-29,NT,Darwin,014015,26.1,33.7,0,5.2,7.4,S,31,30.8,68,32.4,66
2017-12-29,VIC,Ballarat,089002,15.6,26.6,0,,,NNW,44,21.4,83,18.9,99
2017-12-29,QLD,Townsville,032040,26.0,33.2,0,,,NE,35,30.8,55,31.5,49
2017-12-29,NSW,Canberra,070351,18.3,33.4,0,,,NW,46,24.7,56,31.3,33
2017-12-29,QLD,Cairns,031011,24.9,34.3,0,,,E,39,29.8,61,32.6,47
2017-12-29,WA,Perth,009021,15.6,30.0,0,8.8,13.1,WSW,41,22.9,43,27.5,38
2017-12-29,VIC,Melbourne,086338,18.6,24.4,0.2,5.8,1.0,SSW,35,19.5,78,20.0,85
2017-12-29,QLD,Gold Coast,040764,22.4,28.8,10.2,,,NNE,26,26.0,91,27.3,74
2017-12-29,NSW,Albury,072160,21.0,27.3,1.4,,,SSE,33,23.0,82,25.9,66
2017-12-29,VIC,Geelong,087184,17.2,22.6,0,,,SSW,26,19.3,79,18.7,93
2017-12-29,QLD,Sunshine C,040861,21.9,29.9,0,,,NE,26,27.5,65,28.5,62
2017-12-30,NSW,Wollongong,068228,21.6,29.7,0.6,,,SE,46,25.2,73,26.8,69
2017-12-30,QLD,Townsville,032040,25.8,33.6,0.2,,,N,35,30.2,60,31.7,49
2017-12-30,QLD,Brisbane,040913,23.3,32.2,0,8.6,7.8,NE,24,28.9,55,30.4,65
2017-12-30,VIC,Melbourne,086338,15.6,21.3,8.4,4.2,8.1,SSW,65,19.0,60,19.6,71
2017-12-30,VIC,Bendigo,081123,13.6,25.3,0.4,,,SW,43,17.8,60,22.2,47
2017-12-30,QLD,Cairns,031011,22.0,33.9,0,,,ENE,46,29.0,61,31.2,62
2017-12-30,QLD,Sunshine C,040861,21.0,31.3,0,,,NNE,43,29.0,54,28.1,72
2017-12-30,VIC,Geelong,087184,13.6,22.8,4.6,,,W,56,17.9,78,21.9,41
2017-12-30,NSW,Canberra,070351,18.6,28.3,16.4,,,WNW,50,22.8,70,27.8,33
2017-12-30,QLD,Gold Coast,040764,23.4,31.5,0,,,NW,41,27.2,61,28.0,74
2017-12-30,NSW,Albury,072160,20.3,27.7,13.8,,,W,44,23.0,65,26.2,36
2017-12-30,VIC,Ballarat,089002,8.2,18.6,1.4,,,WSW,50,14.7,81,16.6,70
2017-12-30,SA,Adelaide,023034,17.4,22.7,0.2,4.8,10.2,SW,41,19.1,72,22.0,51
2017-12-30,NT,Darwin,014015,24.2,34.8,1.2,4.4,11.2,NW,28,29.9,71,33.6,61
2017-12-30,NSW,Newcastle,061055,23.2,34.1,2.0,,,NW,52,24.6,81,31.2,50
2017-12-30,QLD,Toowoomba,041529,19.1,30.2,0,,,N,31,23.6,70,30.2,49
2017-12-31,QLD,Toowoomba,041529,21.1,30.2,1.4,,,E,54,24.7,75,23.6,66
2017-12-31,NSW,Canberra,070351,14.9,27.9,0,,,NNW,37,19.7,65,26.2,37
2017-12-31,VIC,Bendigo,081123,8.9,29.0,0,,,WNW,33,17.3,54,26.7,28
2017-12-31,NSW,Newcastle,061055,21.3,25.3,0.2,,,SSE,46,22.5,78,22.4,82
2017-12-31,NSW,Wollongong,068228,18.9,23.4,19.6,,,NNE,48,19.2,93,21.1,84
2017-12-31,QLD,Sunshine C,040861,24.1,32.5,0,,,SSW,65,30.3,62,27.1,78
2017-12-31,QLD,Gold Coast,040764,22.4,29.1,14.8,,,SE,56,27.1,84,25.6,97
2017-12-31,VIC,Geelong,087184,9.8,25.9,0,,,SSE,33,16.4,70,23.9,48
2017-12-31,QLD,Brisbane,040913,24.7,33.6,0,8.0,6.6,E,31,30.0,63,27.1,76
2017-12-31,VIC,Melbourne,086338,12.0,25.7,0.2,4.0,13.5,S,33,17.3,60,22.5,48
2017-12-31,WA,Perth,009021,19.7,33.6,0,12.4,13.2,WSW,41,26.0,45,30.6,36
2017-12-31,VIC,Ballarat,089002,5.7,25.2,2.0,,,W,39,12.8,77,23.5,35
2017-12-31,QLD,Townsville,032040,26.7,33.3,0,,,NNE,33,30.8,55,33.0,44
2017-12-31,NT,Darwin,014015,27.4,34.1,0,6.0,8.6,N,26,30.8,73,32.8,59
2017-12-31,QLD,Cairns,031011,21.6,33.1,0,,,NNE,28,29.9,61,31.2,54
2017-12-31,NSW,Albury,072160,12.7,29.5,0,,,WNW,33,19.9,67,27.7,30
2017-12-31,SA,Adelaide,023034,13.7,22.3,0,8.0,9.7,SW,35,17.7,59,21.4,53

/* 
Complete this javascript file according to the individual instructions
given in the comments. */

//1) Create an Object using an Object Literal (the easiest way)
// Name your object Breakfast
// Your object should have 3 key:value pairs
// The three keys should be: breakfast, lunch, dinner
// Put your food choice for each as the value




// 2) Display the keys of your Breakfast object in the 
// console. We have learned two ways to do this.. either 
// works here!




// 3) With the object you created above, use dot notation to change 
// the value of the lunch property to "grilled cheese".
// Add a method to your object named "digIn" that returns "Chomp!"
// Call the method on the Breakfast object and send the output 
// to the console.




// 4) Create an object constructor named Pizza.
// Pizza should require a parameter called size.
// size should be a property of Pizza.
//
// Create a new Pizza called LargePizza and 
// pass "large" as the parameter of the new Pizza.
// Next, add a slices property to your LargePizza object. 
// Set the slices equal to 12.
//
// Finally, create a child object of LargePizza named 
// Hawaiian. Add a property called toppings to Hawaiian. 
// Set the toppings equal to an array with these values: 
// green peppers, pineapple, canadian bacon
//
// Send the slices property of Hawaiian to the console
// Send Hawaiian's full array property of toppings to 
// the console also.




// 5) With the objects created in Problem #4,  
// utilize prototype to add a method to the Pizza constructor.
// Name the method bake and have it return "Ready in 10 minutes!" 
// 
// Create another child object of LargePizza named 
// TacoPizza. Call the bake method on TacoPizza and 
// log the result to the console.

In a language of your own choosing, write a computer program that takes as input a decimal (base 10) floating point number, and converts this number into a binary floating-point representation. The binary floating-point representation should consist of 1 bit for the sign of the significand; 8 bits for the biased exponent; and 23 bits for the significand. In addition to program source code, provide a screenshot showing the tasks identified below.

1. Provide an output that shows your input decimal floating-point values.

2. Demonstrate that your program works in the following input cases by showing the output in the form of 32 bits including sign bit, biased exponent, and significand:

1. 1. Small exponent value.
   2. Large exponent value.
   3. Negative exponent value.
2. 4. Negative significand.

In c++, write a program that reads a string consisting of a positive integer or a positive decimal number and converts the number to the numeric format. If the string consists of a decimal number, the program must use a stack to convert the decimal number to the numeric format.

Remarks: In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Do not write a program. Write pseudo codes or explain in words

Question 2: 1. Show how to implement a Queue by a Priority Queue. What is the run time per operation? 2. Show how to implement a Stack using Priority Queue. What is the run time per operation?

Remarks: In all algorithm, always explain how and why they work. If not by a proof, at least by a clear explanation. ALWAYS, analyze the running time complexity of your algorithms. In all algorithms, always try to get the fastest possible. A correct algorithm with slow running time may not get full credit. Do not write a program. Write pseudo codes or explain in words

Question 3: Give a data structure that implements a Min-Heap and the command M ax(S) that returns the maximum in the heap. Try and make the last operation as fast as possible.

Assume that aa = "11", bb = "22", m = 5 and n = 7. How do the following two statements differ?

System.out.println(aa + bb + m + n);

System.out.println(m + n + aa + bb);

Explain your answers in details. Only clear explanations will be given marks.

C++ OOP

•Write a program that evaluates a postfix expression (assume it’s valid) such as

6 2 + 5 * 8 4 / -

•The program should read a postfix expression consisting of digits and operators into a string.

•The algorithm is as follows:

1.While you have not reached the end of the string, read the expression from left to right.

–If the current character is a digit, Push its integer value onto the stack (the integer value of a digit character is its value in the computer’s character set minus the value of '0' in the computer’s character set).

–Otherwise, if the current character is an operator, Pop the two top elements of the stack into variables x and y.

–Calculate y operator x.

–Push the result of the calculation onto the stack.

2.When you reach the end of the string, pop the top value of the stack. This is the result of the postfix expression.

–[Example: In Step 2 above, if the operator is '/', the top of the stack is 2 and the next element in the stack is 8, then pop 2 into x, pop 8 into y, evaluate 8 / 2 and push the result, 4, back onto the stack. This note also applies to operator '–'.]

–The arithmetic operations allowed in an expression are

•+ addition

•– subtraction

•* multiplication

•/ division

•^ exponentiation

•% modulus

•[Note: We assume left-to-right associativity for all operators for the purpose of this exercise.] The stack should be maintained with stack nodes that contain an int data member and a pointer to the next stack node. You may want to provide the following functional capabilities:

a.function evaluatePostfixExpression that evaluates the postfix expression

b.function calculate that evaluates the expression (op1 operator op2)

c.function push that pushes a value onto the stack

d.function pop that pops a value off the stack

e.function isEmpty that determines if the stack is empty

f.function printStack that prints the stack

SAMPLE OUTPUT:

INPUT POSTFIX NOTATION: 23+2*

INFIX NOTATION: (2+3)*2

RESULT: 10