Programming & Computer Science Answers

Rahul lives in City A and would like to travel to City B for work. There is a shuttle service for people in these cities which has a fixed schedule. The schedule for City A is a list of boarding times(at City A) and departure times(from City A) for each bus.

Note: No one is allowed to board a shuttle after the boarding time.

He arrives at time t and sometimes has to wait at the station. You are given a list of arrival times for n days.

1. Devise an algorithm to find him the shuttle with the least waiting time. (waiting time  = boardingj - t ,  where j is the next shuttle. And boardingj  >= t ) for each ti
2. If he also has access to the travel time of each shuttle. Can you help him find the shuttle which will help him reach his destination at the earliest ?

Return an array of shuttle indexes that Rahul took for n days

If there is no such shuttle return -1.

Write your algorithms as pseudo-code and make sure to explain how your algorithm works and the time and space complexity of your algorithm.

In a hypothetical server, we have a list of tasks arranged in form of a doubly linked list. In this list in addition to next and previous pointer each node also has a tertiary pointer, which represents some cleanup tasks required before moving on to next tasks of the list. The current scheduler however does not recognize this list structure. Your task is to implement an algorithm that takes input the head of the doubly linked list with nodes having a tertiary pointer and gives the head of a rearranged doubly linked list with all tasks arranged linearly (with nodes having just the next and previous pointers only, no tertiary pointer). The modifications should be in-place, that means you cannot change the contents (other than next and previous pointer)  or the address of any of the nodes. Analyse the running time of the algorithm for the given ‘n’ being the number of tasks. 

(For algorithm, write the pseudo code and explain the logic, write base cases and sub problems too)

Consider a pile of coins. You have given ‘n’ coins of different sizes and you want to sort the pile so that smaller coins are on the top of larger ones. The only “operation” you are allowed to perform is- take top ‘k’ coins together, and place them back to the pile upside down.

1. Describe an algorithm to sort an arbitrary pile of n coins using O(n) operations. Exactly how many operations does your algorithm perform in the worst case.
2. For every positive integer ‘n’, describe the pile structure that requires (Omega) Ω(n) operations to sort. In other words, generate an example of a pile that will require at least cn operations for some c > 0. (n > 3)
3. Now suppose in the sorted array we want all coins to have heads face up. Describe an algorithm to sort an arbitrary pile of ‘n’ coins, such that all coins have tails face down, using O(n) operations. Exactly how many operations does your algorithm perform in the worst case.

Explain how you would use JavaFX classes to make your own graphical user interface (GUI) to produce the same GUI that you find in an existing device or software program you already use 

Which classes would you use ?

(1) (a)Define a class Pairs with two integer data members, f and s, where f represents

the first value in the ordered pair and s represents the second value in an ordered

pair. Write a program to test all the overloaded operators in your class definition.

(b) Overload the stream extraction operator >> and the stream insertion operator << as

friend functions so that objects of class Pairs are to be input and output in the

form (5,6) (5,-4) (-5,4) or (-5,-6).

(c) Overload binary operator + as a friend function to add pairs according to the rule

(a,b) + (c,d) = (a + c, b + d)

(d)Overload operator – as a friend function in the same way, i.e. according to the rule

(a,b) - (c,d) = (a - c, b - d)

(e) Overload operator * as a friend function on Pairs and int according to the rule

(a,b) * c = (a * c, b * c)

Consider the following structure used to keep record of a module:

struct Module

{

string moduleName;

string moduleCode;

string lecturer;

int nrStudents;

}

Turn the Module struct into a class. The class should have member variables for all

the values in the corresponding struct. Make all the member variables private.

Include public member functions for each of the following:

 a default constructor that sets the string member variables to blank strings,

and the int member variable to 0;

 an overloaded constructor that sets the member variables to specified values;

 member functions to set each of the member variables to a value given as an

argument to the function (i.e. mutators);

 member functions to retrieve the data from each of the member variables (i.e.

accessors);

Test the class in a program that instantiates an object of class Module. The program should then input values for the object

(obtained from the keyboard), and use the mutators to assign values to the member

variables.

In a hypothetical server, we have a list of tasks arranged in the form of a doubly linked list. In this list in addition to the next and previous pointer each node also has a tertiary pointer, which represents some cleanup tasks required before moving on to the next tasks of the list. The current scheduler however does not recognize this list structure. Your task is to implement an algorithm that takes input the head of the doubly linked list with nodes having a tertiary pointer and gives the head of a rearranged doubly linked list with all tasks arranged linearly (with nodes having just the next and previous pointers only, no tertiary pointer). The modifications should be in-place, that means you cannot change the contents (other than next and previous pointer)  or the address of any of the nodes. Also Analyse the running time of the algorithm for the given ‘n’ being the number of tasks