C vs Java

Here are the major differences between C And JAVA.

1. JAVA is Object-Oriented while C is procedural. Different Paradigms, that is.

Most differences between the features of the two languages arise due to the use of different programming paradigms. C breaks down to functions while JAVA breaks down to Objects. C is more procedure-oriented while JAVA is data-oriented.

2. Java is an Interpreted language while C is a compiled language.

We all know what a compiler does. It takes your code & translates it into something the machine can understand-that is to say-0’s & 1’s-the machine-level code. That’s exactly what happens with our C code-it gets ‘compiled’. While with JAVA, the code is first transformed to what is called the bytecode. This bytecode is then executed by the JVM(Java Virtual Machine). For the same reason, JAVA code is more portable.

3. C is a low-level language while JAVA is a high-level language.

C is a low-level language(difficult interpretation for the user, closer significance to the machine-level code) while JAVA is a high-level lagunage(abstracted from the machine-level details, closer significance to the program itself).

4. C uses the top-down {sharp & smooth} approach while JAVA uses the bottom-up {on the rocks} approach.

In C, formulating the program begins by defining the whole and then splitting them into smaller elements. JAVA(and C++ and other OOP languages) follows the bottom-up approach where the smaller elements combine together to form the whole.

5. Pointer go backstage in JAVA while C requires explicit handling of pointers.

When it comes to JAVA, we don’t need the *’s & &’s to deal with pointers & their addressing. More formally, there is no pointer syntax required in JAVA. It does what it needs to do. While in JAVA, we do create references for objects.

6. The Behind-the-scenes Memory Management with JAVA & The User-Based Memory Management in C.

Remember ‘malloc’ & ‘free’? Those are the library calls used in C to allocate & free chunks of memory for specific data(specified using the keyword ‘sizeof’). Hence in C, the memory is managed by the user while JAVA uses a garbage collector that deletes the objects that no longer have any references to them.

7. JAVA supports Method Overloading while C does not support overloading at all.

JAVA supports function or method overloading-that is we can have two or more functions with the same name(with certain varying parameters like return types to allow the machine to differentiate between them). That it to say, we can overload methods with the same name having different method signatures. JAVA(unlike C++), does not support Operator Overloading while C does not allow overloading at all.

8. Unlike C, JAVA does not support Preprocessors, & does not really them.

The preprocessor directives like #include & #define, etc are considered one of the most essential elements of C programming. However, there are no preprocessors in JAVA. JAVA uses other alternatives for the preprocessors. For instance, public static final is used instead of the #define preprocessor. Java maps class names to a directory and file structure instead of the #include used to include files in C.

9. The standard Input & Output Functions.

Although this difference might not hold any conceptual(intuitive) significance, but it’s maybe just the tradition. C uses the printf & scanf functions as its standard input & output while JAVA uses the System.out.print & System Resources and Information..read functions.

10. Exception Handling in JAVA And the errors & crashes in C.

When an error occurs in a Java program it results in an exception being thrown. It can then be handled using various exception handling techniques. While in C, if there’s an error, there IS an error.

Features of Java

                                               

There is given many features of java. They are also known as java Power.The Java langguage
are very easy to understand.

1. Simple
2. Object-Oriented
3. Portable
4. Platform independent
5. Secured
6. Robust
7. Architecture neutral
8. Dynamic
9. Interpreted
10. High Performance
11. Multithreaded
12. Distributed

Simple:-

According to oracle java is very easy language to learn because:-

syntax is based on C++ (so easier for programmers to learn it after C++).

removed many confusing and/or rarely-used features e.g., explicit pointers, operator                     overloading etc.

No need to remove unreferenced objects because there is Automatic Garbage Collection in             java.

---

Object-oriented:-

Object-oriented means we organize our software as a combination of different types of objects that incorporates both data and behaviour.

Object-oriented programming(OOPs) is a methodology that simplify software development and maintenance by providing some rules.

Basic concepts of OOPs are:

Object Class Inheritance Polymorphism Abstraction Encapsulation

big history of java ?

History of Java

1.                        java history
2. 
   

Java history is interesting to know. The history of java starts from Green Team. Java team members (also known as Green Team), initiated a revolutionary task to develop a language for digital devices such as set-top boxes, televisions etc.

For the green team members, it was an advance concept at that time. But, it was suited for internet programming. Later, Java technology as incorporated by Netscape.

James Gosling

Currently, Java is used in internet programming, mobile devices, games, e-business solutions etc. There are given the major points that describes the history of java.

1) James Gosling, Mike Sheridan, and Patrick Naughton initiated the Java language project in June 1991. The small team of sun engineers called Green Team.

2) Originally designed for small, embedded systems in electronic appliances like set-top boxes.

3) Firstly, it was called "Greentalk" by James Gosling and file extension was .gt.

4) After that, it was called Oak and was developed as a part of the Green project.

Why "Oak" name

5) Why Oak? Oak is a symbol of strength and choosen as a national tree of many countries like U.S.A., France, Germany, Romania etc.

6) In 1995, Oak was renamed as "Java" because it was already a trademark by Oak Technologies.

Why "Java" name

7) Why had they choosen java name for java language? The team gathered to choose a new name. The suggested words were "dynamic", "revolutionary", "Silk", "jolt", "DNA" etc. They wanted something that reflected the essence of the technology: revolutionary, dynamic, lively, cool, unique, and easy to spell and fun to say.

According to James Gosling "Java was one of the top choices along with Silk". Since java was so unique, most of the team members preferred java.

8) Java is an island of Indonesia where first coffee was produced (called java coffee).

9) Notice that Java is just a name not an acronym.

10) Originally developed by James Gosling at Sun Microsystems (which is now a subsidiary of Oracle Corporation) and released in 1995.

11) In 1995, Time magazine called Java one of the Ten Best Products of 1995.

12) JDK 1.0 released in(January 23, 1996).

---

Java Version History

There are many java versions that has been released. Current stable release of Java is Java SE 8.

1. JDK Alpha and Beta (1995)
2. JDK 1.0 (23rd Jan, 1996)
3. JDK 1.1 (19th Feb, 1997)
4. J2SE 1.2 (8th Dec, 1998)
5. J2SE 1.3 (8th May, 2000)
6. J2SE 1.4 (6th Feb, 2002)
7. J2SE 5.0 (30th Sep, 2004)
8. Java SE 6 (11th Dec, 2006)
9. Java SE 7 (28th July, 2011)
10. Java SE 8 (18th March, 2014)

What happens when we turn on computer?

A computer without a program running is just an inert hunk of electronics. The first thing a computer has to do when it is turned on is start up a special program called an operating system. The operating system’s job is to help other computer programs to work by handling the messy details of controlling the computer’s hardware.

An overview of the boot process
Image courtsey : IBM

The boot process is something that happens every time you turn your computer on. You don’t really see it, because it happens so fast. You press the power button come back a few minutes later and Windows XP, or Windows Vista, or whatever Operating System you use is all loaded.

The BIOS chip tells it to look in a fixed place, usually on the lowest-numbered hard disk (the boot disk) for a special program called a boot loader (under Linux the boot loader is called Grub or LILO). The boot loader is pulled into memory and started. The boot loader’s job is to start the real operating system.

Functions of BIOS

POST (Power On Self Test) The Power On Self Test happens each time you turn your computer on. It sounds complicated and thats because it kind of is. Your computer does so much when its turned on and this is just part of that.

It initializes the various hardware devices. It is an important process so as to ensure that all the devices operate smoothly without any conflicts. BIOSes following ACPI create tables describing the devices in the computer.

The POST first checks the bios and then tests the CMOS RAM. If there is no problems with this then POST continues to check the CPU, hardware devices such as the Video Card, the secondary storage devices such as the Hard Drive, Floppy Drives, Zip Drive or CD/DVD Drives.If some errors found then an error message is displayed on screen or a number of beeps are heard. These beeps are known as POST beep codes.

Master Boot Record

The Master Boot Record (MBR) is a small program that starts when the computer is booting, in order to find the operating system (eg. Windows XP). This complicated process (called the Boot Process) starts with the POST (Power On Self Test) and ends when the Bios searches for the MBR on the Hard Drive, which is generally located in the first sector, first head, first cylinder (cylinder 0, head 0, sector 1).

The bootstrap loader is stored in the master boot record (MBR) on the computer’s hard drive. When the computer is turned on or restarted, it first performs the power-on self-test, also known as POST. If the POST is successful and no issues are found, the bootstrap loader will load the operating system for the computer into memory. The computer will then be able to quickly access, load, and run the operating system.

init

init is the last step of the kernel boot sequence. It looks for the file /etc/inittab to see if there is an entry for initdefault. It is used to determine initial run-level of the system. A run-level is used to decide the initial state of the operating system.
Some of the run levels are:

Level

0 –> System Halt

1 –> Single user mode

3 –> Full multiuser mode with network

5 –> Full multiuser mode with network and X display manager

6 –> Reboot

The above design of init is called SysV- pronounced as System Five Several other implementations of init have been written now. Some of the popular implementatios are systemd and upstart. Upstart is being used by ubuntu since 2006. More details of the upstart can be found here.

The next step of init is to start up various daemons that support networking and other services. X server daemon is one of the most important daemon. It manages display, keyboard, and mouse. When X server daemon is started you see a Graphical Interface and a login screen is displayed.

binary heaps

Binary Heaps :-

Introduction :-

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types: • 

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root. • the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.    

In a heap the highest (or lowest) priority element is always stored at the root, hence the name "heap". A heap is not a sorted structure and can be regarded as partially ordered. As you see from the picture, there is no particular relationship among nodes on any given level, even among the siblings. 

Since a heap is a complete binary tree, it has a smallest possible height - a heap with N nodes always has O(log N) height. 

A heap is useful data structure when you need to remove the object with the highest (or lowest) priority. A common use of a heap is to implement a priority queue. 

Array Implementation A complete binary tree can be uniquely represented by storing its level order traversal in an array. 

 

The root is the second item in the array. We skip the index zero cell of the array for the convenience of implementation. Consider k-th element of the array, the 

its left child is located at 2*k index  its right child is located at 2*k+1. index  its parent is located at k/2 index  

Insert The new element is initially appended to the end of the heap (as the last element of the array). The heap property is repaired by comparing the added element with its parent and moving the added element up a level (swapping positions with the parent). This process is called "percolation up". The comparison is repeated until the parent is larger than or equal to the percolating element. 

  

The following code example demonstrates the algorithm 

public void insert(Comparable x) {  if(size == heap.length - 1) doubleSize();  

 //Insert a new item to the end of the array  int pos = ++size;  

 //Percolate up  for(; pos > 1 && x.compareTo(heap[pos/2]) < 0; pos = pos/2 )   heap[pos] = heap[pos/2];  

 heap[pos] = x; }  

The worst-case runtime of the algorithm is O(log n), since we need at most one swap on each level of a heap on the path from the inserted node to the root. 

DeleteMin The minimum element can be found at the root, which is the first element of the array. We remove the root and replace it with the last element of the heap and then restore the heap property by percolating down. Similar to insertion, the worst-case runtime is O{log n).  

HeapSort The algorithm runs in two steps. Given an array of data, first, we build a heap and then turn it into a sorted list by calling deleteMin. The running time of the algorithm is O(n log n). 

Priority Queue 

Priority queues are useful for any application that involves processing elements based on some priority. 

A priority queue is different from a "normal" queue, because instead of being a "first-in-firstout" data structure, values come out in order by priority. A priority queue might be used, for example, to handle the jobs sent to the Computer Science Department's printer: Jobs sent by the department chair should be printed first, then jobs sent by professors, then those sent by graduate students, and finally those sent by undergraduates. The values put into the priority queue would be the priority of the sender (e.g., using 4 for the chair, 3 for professors, 2 for grad students, and 1 for undergrads), and the associated information would be the document to print. Each time the printer is free, the job with the highest priority would be removed from the 

print queue, and printed. (Note that it is OK to have multiple jobs with the same priority; if there is more than one job with the same highest priority when the printer is free, then any one of them can be selected.) 

The operations that need to be provided for a priority queue are shown in the following table, assuming that just priorities (no associated information) are to be stored in a priority queue. 

OPERATION DESCRIPTION 

PriorityQ() (constructor) create an empty priority queue 

boolean empty() return true iff the priority queue is empty 

void insert ( p ) add priority p to the priority queue 

removeMax() 

remove and return the highest priority from the priority queue (error if the priority queue is empty) 

A priority queue can be implemented using many of the data structures that we've studied (an array, a linked list, or a binary search tree). However, those data structures do not provide the most efficient operations. To make all of the operations very efficient, we'll use a new data structure called a heap. 

Implementing priority queues using heaps 

Now let's consider how to implement priority queues using a heap. The standard approach is to use an array (or an ArrayList), starting at position 1 (instead of 0), where each item in the array corresponds to one node in the heap: • 

The root of the heap is always in array[1]. • Its left child is in array[2]. • Its right child is in array[3]. • In general, if a node is in array[k], then its left child is in array[k*2], and its right child is in array[k*2 + 1]. • If a node is in array[k], then its parent is in array[k/2] (using integer division, so that if k is odd, then the result is truncated; e.g., 3/2 = 1). 

Here's an example, showing both the conceptual heap (the binary tree), and its array representation:  

Implementing insert 

When a new value is inserted into a priority queue, we need to: • 

Add the value so that the heap still has the order and shape properties, and • Do it efficiently! 

The way to achieve these goals is as follows: 

1. Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or, if the tree was a complete binary tree, i.e., all leaves were at the same depth d, then that corresponds to adding a new leaf at depth d+1). 

2. Step 1 above ensures that the heap still has the shape property; however, it may not have the order property. We can check that by comparing the new value to the value in its parent. If the parent is smaller, we swap the values, and we continue this check-andswap procedure up the tree until we find that the order property holds, or we get to the root. 

Here's a series of pictures to illustrate inserting the value 34 into a heap: 

 

Because heaps have the order property, the largest value is always at the root. Therefore, the removeMax operation will always remove and return the root value; the question then is how to replace the root node so that the heap still has the order and shape properties. 

The answer is to use the following algorithm: 

1. Replace the value in the root with the value at the end of the array (which corresponds to the heap's rightmost leaf at depth d). Remove that leaf from the tree. 

2. Now work your way down the tree, swapping values to restore the order property: each time, if the value in the current node is less than one of its children, then swap its value with the larger child (that ensures that the new root value is larger than both of its children). 

Here's a series of pictures to illustrate the removeMax operation applied to the heap shown above. 

 

Dynamic Programming

Tabulation vs Memoizatation

There are following two different ways to store the values so that the values of a problem can be reused. Here, will discuss two patterns of solving DP problem:

1. Tabulation: Bottom Up
2. Memoization: Top Down

Bottom up vs. Top Down:

• Bottom Up - I'm going to learn programming. Then, I will start practicing. Then, I will start taking part in contests. Then, I'll practice even more and try to improve. After working hard like crazy, I'll be an amazing coder.
• Top Down - I will be an amazing coder. How? I will work hard like crazy. How? I'll practice more and try to improve. How? I'll start taking part in contests. Then? I'll practicing. How? I'm going to learn programming.

Not a great example, but I hope I got my point across. In Top Down, you start building the big solution right away by explaining how you build it from smaller solutions. In Bottom Up, you start with the small solutions and then build up.

Another good example:-

• Version 1: I will study the theory of Dynamic Programming from GeeksforGeeks, then I will practice some problems on classic DP and hence I will master Dynamic Programming.
• Version 2: To Master Dynamic Programming, I would have to practice Dynamic problems and to practice

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

• example: If doing fibonacci, you choose to calculate the numbers in this order: fib(2),fib(3),fib(4)... caching every value so you can compute the next ones more easily. You can also think of it as filling up a table (another form of caching).

Now, it is quite obvious that dp[x+1] = dp[x] * (x+1)

// Tabulated version to find factorial x.
int dp[MAXN];

// base case
int dp[0] = 1;
for (int i = 1; i< =n; i++)
{
    dp[i] = dp[i-1] * i;
}

The above code clearly follows the bottom up approach as it starts its transition from the bottom most base case dp[0] and reaches it destination state dp[n]. Here, we may notice that the dp table is being populated sequentially and we are directly accessing the calculated states from the table itself and hence, we call it tabulation method.
Memoization Method – Top Down Dynamic Programming 

You typically perform a recursive call (or some iterative equivalent) from the root, and either hope you will get close to the optimal evaluation order, or you have a proof that you will get the optimal evaluation order. You ensure that the recursive call never recomputes a subproblem because you cache the results, and thus duplicate sub-trees are not recomputed.

• example: If you are calculating the Fibonacci sequence fib(100), you would just call this, and it would call fib(100)=fib(99)+fib(98), which would call fib(99)=fib(98)+fib(97), ...etc..., which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn't need to recalculate fib(2), because we cached it.
• This starts at the top of the tree, and evaluates the subproblems from the leaves/subtrees back up towards the root.

// Memoized version to find factorial x.
// To speed up we store the values
// of calculated states

// initialized to -1
int dp[MAXN]

// return fact x!
int solve(int x)
{
    if (x==0)
        return 1;
    if (dp[x]!=-1)
        return dp[x];
    return (dp[x] = x * solve(x-1));
}

competitive practice

Trains, Boats and Streams

Trains

• If two trains are moving in same direction with speeds a km / hr and b km / hr, then their relative speed would be |a – b| km / hr.
• If two trains are moving in different directions, i.e., coming towards each other or going away from each other, with speeds a km / hr and b km / hr, then their relative speed would be (a + b) km / hr.
• Time taken by a train, ‘t’ meters long, to pass a stationary object of length ‘l’ meters would be the time taken by the train to travel ‘t + l’ meters. For example, to cover a platform of 800 m, a train of length 200 m moving at the speed of 10 m / s would be the time taken by the train to cover 800 + 200 = 1000 m at the speed of 10 m / s, i.e., 1000 / 10 = 100 s.
• To pass a pole or a man or a post (or any stationary object with negligible length as compared to the length of the train, like if the train is 500 m long and a pole is 1 m in length), the time taken by the train would be the time it takes to travel the length of the train. For example, if a train of length 100 m is moving at the speed of 10 m / s, it would take 100 / 10 = 10 s to pass a pole / man / post.
• If two trains of lengths L1 and L2 are moving in the same direction with speeds S1 and S2, then the time required by faster train to overtake the slower train would be the time taken to cover an equivalent distance of L1 + L2, with relative speed |S1 – S2|, i.e., Time = (L1 + L2) / |S1 – S2|.
• If two trains of lengths L1 and L2 are moving in opposite directions with speeds S1 and S2, then the time required by the trains to cross each other completely would be the time taken to cover an equivalent distance of L1 + L2, with relative speed (S1 + S2), i.e., Time = (L1 + L2) / (S1 + S2).
• If two trains started moving towards each other at the same time with speeds S1 and S2 respectively and after meeting, they take ‘T1’ and ‘T2’ seconds respectively, then S1 : S2 = T21/2 : T11/2

Boats and Streams

• If the boat is moving in the direction of the stream, it is said to be going downstream. And if the boat is moving opposite to the direction of stream, it is said to be going upstream.
• If the speed of boat in still water is B km / hr and speed of the stream is S km / hr,
  1. Speed Upstream = B – S km / hr
  2. Speed Downstream = B + S km / hr
• If the speed upstream is U km / hr and speed downstream is D km / hr,
  1. Speed of boat in still water = 0.5 x (D + U) km / hr
  2. Speed of stream = 0.5 x (D – U) km / hr

Sample Problems

Question 1 : A 100 m long train moving at a speed of 60 km / hr passes a man standing on a pavement near a railway track. Find the time taken by the train to pass the man.
Solution : Length of the train = 100 m = 0.1 km
Speed of the train = 60 km / hr
So, time taken by the train to pass the man = time taken to cover 0.1 km at the speed of 60 km / hr
Therefore, time taken by the train to pass the man = 0.1 / 60 hour = (0.1 / 60) x 3600 sec = 6 sec

Question 2 : How long does a train 1000 m long moving at a speed of 90 km / hr would take to pass through a 500 m long bridge?
Solution : Here, time taken by the train to pass the bridge completely would be the time it takes to cover 1000 + 500 = 1500 m at the speed of 90 km / hr = 90 x (5/18) = 25 m / sec.
Therefore, time required = 1500 / 25 = 60 sec = 1 minute

Question 3 : A man standing near a railway track observes that a train passes him in 80 seconds but to pass by a 180 m long bridge, the same train takes 200 seconds. Find the speed of the train.
Solution : Let the length of the train be L meters.
=> The train covers L meters in 80 seconds and L + 180 meters in 200 seconds, with the same speed.
We know that Speed = Distance / Time.
=> Speed = L / 80 = (L + 180) / 200
=> L / 80 = (L + 180) / 200
=> 2.5 L = L + 180
=> 1.5 L = 180
=> L = 120
Thus, speed of the train = 120 / 80 = 1.5 m / sec

Question 4 : Two trains 140 m and 160 m long are moving towards each other on parallel tracks with speeds 40 km / hr and 50 km / hr respectively. How much time would they take to pass each other completely ?
Solution : Total distance to be covered = 140 + 160 m = 300 m
Relative speed = 40 + 50 = 90 km / hr = 90 x (5 / 18) m / sec = 25 m / sec
Therefore, time taken to pass each other = 300 / 25 = 12 sec

Question 5 : Two trains 140 m and 160 m long are moving in the same direction on parallel tracks with speeds 40 km / hr and 50 km / hr respectively. How much time would the faster train require to overtake the slower train ?
Solution : Total distance to be covered = 140 + 160 m = 300 m
Relative speed = 50 – 40 = 10 km / hr = 10 x (5 / 18) m / sec = 50 / 18 m / sec
Therefore, time taken by faster train to overtake the slower train = 300 / (50/18) = 108 sec

Question 6 : A 500 m long train takes 36 seconds to cross a man walking in the opposite direction at the speed of 10 km / hr. Find the speed of the train.
Solution : Let the speed of the train be T km / hr.
=> Relative speed = T + 10 km / hr
=> Length of the train = 500 m = 0.5 km
We know that Distance = Speed x Time
=> 0.5 = (T + 10) x (36 / 3600)
=> 50 = T + 10
=> T = 40 km / hr
Therefore, speed of the train is 40 km / hr.

Question 7 : A non – stop train started from Delhi towards Mumbai and at the same time, another non – stop train started from Mumbai towards Delhi. If after meeting in Bhopal they took 9 and 16 hours respectively to reach their destinations, find the speed of the train that started from Delhi, given that the speed of the train that started from Mumbai was moving at a speed of 90 km / hr.
Solution : We know that for two trains starting at the same time, S1 : S2 = T21/2 : T11/2
Here, S2 = 90 km / hr
T1 = 9  hrs
T2 = 16  hrs
=> S1 : 90 = 4 : 3
=> S1 = 120 km / hr
Therefore, speed of train that started from Delhi = 120 km / hr

Question 8 : A boatman can row a boat upstream at 14 km / hr and downstream at 20 km / hr. Find the speed of the boat in still water and speed of the stream.
Solution : We are given that speed downstream, D = 20 km / hr and speed upstream, U = 14 km / hr
Therefore, Speed of boat in still water = 0.5 x (D + U) km / hr = 0.5 x (14 + 20) = 17 km / hr
Also, speed of the stream = 0.5 x (D – U) km / hr = 0.5 x (20 – 14) = 3 km / hr

Another method : 
Speed of the stream = 0.5 x (D – U) = 0.5 x 6 = 3 km / hr
Speed of the boat in still water = Speed of the stream + Speed Upstream = 3 + 14 = 17 km / hr
Question 9 : A boatman can row a boat at the speed of 5 km upstream and 15 km downstream. To cover upstream he needs 2.5 hours and to cover downstream, he needs 1.5 hours. Find the speed of the stream and speed of the boat in still water.
Solution : We are given that the boatman covers 5 km upstream in 2.5 hours and 15 km downstream in 10 hours.
=> Speed upstream, U = 5 / 2.5 = 2 km / hr
=> Speed downstream, D = 15 / 1.5 = 10 km / hr
Therefore, Speed of boat in still water = 0.5 x (D + U) km / hr = 0.5 x (10 + 2) = 6 km / hr
Also, speed of the stream = 0.5 x (D – U) km / hr = 0.5 x (10 – 2) = 4 km / hr

Question 10 : A man has to go from a port to an island and return. He can row a boat with the speed 7 km / hr in still water. The speed of the stream is 2 km / hr. If he takes 56 minutes to complete the round trip, find the distance between the port and the island.
Solution : Speed upstream = 7 – 2 = 5 km / hr
Speed downstream = 7 + 2 = 9 km / hr
Let the distance between the port and the island be D km. Also, we know that Time = Distance / Speed
=> (D/5) + (D/9) = 56/60
=> (14 D) / 45 = 56 / 60
=> D = 3 km
Therefore, distance between the port and the island = 3 km

Question 11 : In a boat race, a person rows a boat 6 km upstream and return to the starting point in 4 hours. If the speed of the stream is 2 km / hr, find the speed of the boat in still water.
Solution : Let the speed of the boat in still water be B km / hr.
=> Speed upstream = (B – 2) km / hr
=> Speed downstream = (B + 2) km / hr
We know that Time = Distance / Speed
=> 6/(B-2) + 6/(B+2) = 4
=> 6 B + 12 + 6 B – 12 = 4 (B – 2) (B + 2)
=> 12 B = 4 (B – 2) (B + 2)
=> 3 B = B2 – 4
=> B2 – 3 B – 4 = 0
=> (B + 1) (B – 4) = 0
=> B = 4 km / hr (Speed cannot be negative)

Question 12 : A racer can row a boat 30 km upstream and 44 km downstream in 10 hours. Also, he can row 40 km upstream and 55 km downstream in 13 hours. Find the speed of the boat in still water and speed of the stream.
Solution : Let the speed upstream be U km / hr and speed downstream be D km / hr.
We know that Distance / Speed = Time
=> (30 / U) + (44 / D) = 10 and (40 / U) + (55 / D) = 13
Solving the above pair of linear equations, we get
D = 11 km / hr
U = 5 km / hr
Therefore, Speed of boat in still water = 0.5 x (D + U) km / hr = 0.5 x (11 + 5) = 8 km / hr
Also, speed of the stream = 0.5 x (D – U) km / hr = 0.5 x (11 – 5) = 3 km / hr

Write a program to calculate pow(x,n):-

Given two integers x and n, write a function to compute xn. We may assume that x and n are small and overflow doesn’t happen.

Input : x = 2, n = 3
Output : 8

Input : x = 7, n = 2
Output : 49

Below solution divides the problem into subproblems of size y/2 and call the subproblems recursively.

1. #include<stdio.h>
2.  
3. /* Function to calculate x raised to the power y */
4. int power(int x, unsigned int y)
5. {
6. if (y == 0)
7. return 1;
8. else if (y%2 == 0)
9. return power(x, y/2)*power(x, y/2);
10. else
11. return x*power(x, y/2)*power(x, y/2);
12. }

Time Complexity: O(n)
Space Complexity: O(1)
Algorithmic Paradigm: Divide and conquer.


Above function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

1. int power(int x, unsigned int y)
2. {
3. int temp;
4. if( y == 0)
5. return 1;
6. temp = power(x, y/2);
7. if (y%2 == 0)
8. return temp*temp;
9. else
10. return x*temp*temp;
11. }

Time Complexity of optimized solution: O(logn)

Let us extend the pow function to work for negative y and float x.

1. /* Extended version of power function that can work
2. for float x and negative y*/
3. #include<stdio.h>
4.  
5. float power(float x, int y)
6. {
7. float temp;
8. if( y == 0)
9. return 1;
10. temp = power(x, y/2);
11. if (y%2 == 0)
12. return temp*temp;
13. else
14. {
15. if(y > 0)
16. return x*temp*temp;
17. else
18. return (temp*temp)/x;
19. }
20. }
21.  
22. /* Program to test function power */
23. int main()
24. {
25. float x = 2;
26. int y = -3;
27. printf("%f", power(x, y));
28. return 0;
29. }