# Month: December 2017

### Algorithm*You Always Wanted to ask, But did not know Where to Find Answer

**What is divide and conquer ?**

**How this technique improves performance of an algorithm? **

**Example of this technique when applied to search an element ?**

**What is Master Theorem?**

**Example of the theorem.**

These are some of the questions students of information technology and computer science ask. Most of the time they are not able to answer. On ‘Googling’ they find the example but can’t explain.

**We at Vissicomp invite you to answer these questions and get rewarded for correct answer. **

To help you, we give steps of ‘Divide and conqure’.

## **CONCEPT OF DIVIDE AND CONQUER **

In order to accomplish a task using the above technique, the following steps need to be

**Carried out:**

- Divide the problem domain into SMALL unit(atomic level), where SMALL is the basic unit whose solution is known.
- Solve individual sub-problems using the solution of basic unit.
- Combine the sub-solutions to get the final answer.

Your time starts now!

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

**Installation Of Raspberrypi Operating System( NOOBS & Wheezy-pi)**

** **

The SD card contains the Raspberry Pi’s operating system (the OS is the software that makes it work, like Windows on a PC or OSX on a Mac). This is very different from most computers and it is what many people find the most daunting part of setting up their Raspberry Pi.

The following instructions are for Windows users. Linux and Mac users can find instructions at www.raspberrypi.org/downloads

- Download the Raspberry Pi operating system The recommended OS is called Raspbian.Downloadit here: http://downloads.raspberrypi.org/images/raspbian/2012-12-16-wheezy-raspbian/2012-12-16-wheezy-raspbian.zip
- Unzip the file that you just downloaded
- a) Right click on the file and choose “Extract all”.

- b) Follow the instructions—you will end up with a file ending in .img This .img file can only be written to your SD card by special disk imaging software, so…
- Download the Win32DiskImager software
- a) Download win32diskimager-binary.zip (currently version 0.6) from: https://launchpad.net/win32-image-writer/+download
- b) Unzip it in the same way you did the Raspbian .zip file c) You now have a new folder called win32diskimager-binary You are now ready to write the Raspbian image to your SD card.
- Writing Raspbian to the SD card
- a) Plug your SD card into your PC
- b) In the folder you made in step 3(b), run the file named Win32DiskImager.exe (in Windows Vista, 7 and 8 we recommend that you right-click this file and choose “Run as administrator”). You will see something like this:

- c) If the SD card (Device) you are using isn’t found automatically then click on the drop down box and select it Preparing your SD card for the Raspberry Pi 3
- d) In the Image File box, choose the Raspbian .img file that you downloaded

- e) Click Write
- f) After a few minutes you will have an SD card that you can use in your Raspberry Pi
- Booting your Raspberry Pi for the first time
- a) Follow the Quick start guide
- b) On first boot you will come to the Raspi-config window
- c) Change settings such as timezone and locale if you want
- d) Finally, select the second choice: expand_rootfs and say ‘yes’ to a reboot
- e) The Raspberry Pi will reboot and you will see raspberrypi login:
- f) Type:
**pi** - g) You will be asked for your Password
- h) Type:
**raspberry** - i) You will then see the prompt:
**pi@raspberry ~ $** - j) Start the desktop by typing:
**startx** - k) You will find yourself in a familiar-but-different desktop environment.
- l) Experiment, explore and have fun!

### 2.Install NOOBS on the Raspberry Pi

This project is pretty simple. Besides your Raspberry Pi and essential peripherals, here’s all you’ll need:

- A computer with an SD card slot
- An SD or microSD card of at least 8 GB

### Step 1: Download NOOBS and extract it

You’re going to use your computer to put NOOBS on an SD card – so step one is to get NOOBS onto your computer!

The NOOBS download page will let you choose between NOOBS and “NOOBS Lite.” NOOBS includes a full version of Raspbian, so you can install that particular operating system without using the internet at all. With NOOBS Lite, on the other hand, you’ll need a network connection to install any of the operating systems NOOBS makes available – even Raspbian.

Go ahead and choose whichever version you would like. NOOBS will download as a .zip file, so before you do anything else, go ahead and extract it.

### Step 2: Format an SD card

Now you’re going to want to go ahead and stick your SD card into the corresponding slot on your computer. You’re going to want to format it as FAT. There are a few ways to do this:

On Mac or Windows, use the SD Association’s Formatting Tool (Mac users can also just use the disk utility). Make sure the “Format size adjustment” option is set to “on.” Then erase it in FAT (or MS-DOS) format.

### Step 3: Put the NOOBS files on the SD card

Now, just drag and drop the NOOBS files into your newly formatted SD card. You want the files only, so if your .zip extracted to a folder, open that folder up and select only the stuff inside of it.

### Step 4: Put your SD card into your Raspberry Pi and boot it up

- Once you have NOOBS on your SD card, using it is incredibly easy. Just put the SD card into your Raspberry Pi
- This is the step in which that happens. After booting to NOOBS, you’ll be greeted with a menu that will let you choose which operating system you’d like to install on your Pi.
- Your menu may look a little bit different than the one in the screenshot above, because NOOBS ingeniously adapts to your generation and model of Raspberry Pi.
- just click on “Install” and sit back. From now on, your Pi will boot directly to that operating system.

Posted By-: Vissicomp Technology Pvt. Ltd.

Website -: http://www.vissicomp.com

### Best Suggestion

Every Month Win a Prize For Best Suggestion On Blog Article.. (y)

vissicompcodder.wordpress.com

Comment Fast & Get Prize

### Test Your Knowledge

Test Your Knowledge.. HURRY UP!

Can You Find Multiple Inheritance in Shown Here ? if yes find how

Comment Fast & Get Prize

### Big-Oh Notation…

**Big-Oh Notation**

This idea of an upper bound can be stated more formally. The formal statement of an upper bound is called Big-Oh notation. The Big-Oh refers to the Greek letter Omicron which is used for expressing upper bounds of overheads of an algorithm.. As computer programmers, our number one concern is how our programs will perform when we have large amounts of data, in this particular case very very large value of n.

As computer programmers, our number one concern is how our programs will perform when we have large amounts of data. In terms of the memory and CPU time usage of a computer, we wanted to know how our program would perform if we have a very large number of assignments statements to be executed. We found that for second algorithm, all calculations are done in the same amount of time irrespective of value of n (n is number of first integers to be added). Let’s represent the size of the data set by a variable called n. Let the average performance time for computing sum of size n be given by f (n). Now one can state the following.

O(g(n)) ={ f |∃d > 0, n_{0} ∈ Z, +∋ 0 ≤ f (n) ≤ d *g(n), ∀n ≥ n_{0} }

In simple English above mathematical statement translates in to: The class of functions defined by O( g(n)) consists of all functions f, where there exists a d greater than 0 and an n_{0 } (a positive integer) such that 0 is less than or equal to f(n) is less than or equal to d times g(n) for all n greater than or equal to n_{0. }This behavior is shown as graph in Figure ……

If f is an element of O( g(n)), then f(n) is O( g(n)). The function g is called an **asymptotic upper bound** for f in this case. Stated in English **the set named O( g(n)) consists of the set of all functions, f(n), that have an upper bound of d* g(n), as n approaches infinity.** This is the meaning of the word asymptotic. The idea of an asymptotic bound means that for some small values of n the value of f(n) might be bigger than the value of d* g(n), but once n gets big enough (i.e. bigger than n_{0 }), then for all bigger n it will always be true that f(n) is less than d* g(n).

Mathematically, if f(n) is O(g(n)), then

However, other way it is not true:

if f(n) is not O(g(n)),

Consider following example if f(n) = log n, and g(n) =n , we say log n is O(n) , but n is not O(log n). one can easily prove

The scaling factor d and the threshold n_{0 } are interdependent and differ for different particular functions f(n) in O(g (n)).

- Notations f(n) = O(g (n)) or f(n) is O( g(n)) mean actually f(n) ∈ O(g (n)).
- The notation f(n) ∈ O(g (n)) indicates thatf(n) is a member of the set O( g (n)) of functions.
- All the functions in the set O( g (n)) are increasing with the same or the lesser rate as

g (n) when n → ∞.

Because the time consumed by second algorithm does not depend on n, the size of the instance, one can say g(n) = 1.So, the average time to complete the summation for second algorithm of size n is O(1). If it never takes longer than 1 µs in second case in Python, then a good choice for d would be 1. According to the definition above then it must be the case that f(n) is less than or equal to 1 µs once n gets big enough.

**Rate of Growth**

The choice of g(n) = 1 is arbitrary in computing the complexity of an algorithm. One could have taken g(n) = 2. If g(n) = 2 were chosen, d might be taken as 5 instead of 1. But, since we are only concerned with the overall growth in the function g, the choice of 1 or 2 is irrelevant and the simplest function is chosen, in this case O(1). In English, **when an operation or program is O(1), it is said to be constant time operation or program.** This means the operation does not depend on the size of n. This behavior is shown in figure……

The behavior of an algorithm is represented as the rate of growth of its execution time ( CPU time) as a function of the size of the input problem instance (n). Characterizing an algorithm’s performance in this way is a common practice (an abstraction) that ignores numerous details. To use this measure properly requires an awareness of the details hidden by the abstraction. Every program is run on a computing platform, which is a general term meant to contain:

- The computer on which the program is run, its CPU, data cache, floating-point unit (FPU), and other on-chip features
- The programming language in which the program is written, along with the compiler/interpreter and optimization settings for generated code
- The operating system
- Other processes being run in the background

Thus changing the platform will change the execution time of the program(an algorithm) by a constant factor. Therefore ignoring platform differences in comparing algorithms with the asymptotically equivalent principle is feasible.

**Analysis in the Best, Average, and Worst Cases**

One question to ask is whether the results of the previous section will be true for all input problem instances. Most studied algorithms are **search** and **sorting** in computer engineering. How will the behavior of different sorting algorithms change with different input problem instances of the same size?

- The data could contain large runs on elements already in sorted order
- The input could contain duplicate values
- Regardless of the size n of the input set, the elements could be drawn from a much smaller set and contain a significant number of duplicate values

The conclusion to draw is that for many problems, no single optimal algorithm exists. Choosing an algorithm depends on understanding the problem being solved and the underlying probability distribution of the instances likely to be treated, as well as the behavior of the algorithms being considered.

To provide some guidance, algorithms are typically presented with three common cases in mind:

**Worst case**

Defines a class of problem instances for which an algorithm exhibits its worst runtime behavior. Instead of trying to identify the specific input, algorithm designers typically describe properties of the input that prevent an algorithm from running efficiently. **For a given program and a given value n, the worst-case execution time is the maximum execution time, where the maximum is taken over all instances of size n.**

**Best case**

Defines a class of problem instances for which an algorithm exhibits its best runtime behavior. For these instances, the algorithm does the least work. In reality, the best case rarely occurs.

**Average case**

Defines the expected behavior when executing the algorithm on random problem instances. While some instances will require greater time to complete because of some special cases, the vast majority will not. This measure describes the expectation value of CPU time, an average user of the algorithm should have.

Therefore describing the rate of growth of work or time, we consistently ignore constants. So when we say that **Linear Search **of n elements takes on average:

n +

Comparisions (subject to our earlier assumptions), then by convention subject to these assumptions, we expect **Linear Search** algorithm average time complexity to be of O(n).

One can look at **‘Linear Search’** algorithm of a huge list in Python. If the search item is the last in the list, instance size n very large, will have to make n comparisons before computer can find the item. This will be **‘Worst Case’** scenario. { O(n), understand why?}.

If the item to be searched is first in the list, CPU will make only one comparison irrespective of value of n. This will be the ‘Best Case’ scenario. The average case will be the arithmetic average of the worst case and best case. In this case time complexity will be O(n) . Behaviour of O(n) against n is straight line as shown in figure ……

For further details contact Vissicomp 26708190 / 9320957718 /17

Written and Edited by

Dr. Ashwin I Mehta