RHCE Preparation, How to Prepare for Red Hat Certification.

Some rights reserved by Clifford

1^st Part Welcome

1.       Concentration mainly on commandline tool only

2.       GUI is not always available

3.       Command line is quicker

4.       Exam is completely hands on based

5.       RHEL6 system only to be used

6.       Rebuilds like CentOS or scientific linux may be used as well. These use the RPM’s provided by Red Hat to public downloads

7.       Open Source code is available and Rebuilds use the same code.

8.       www.scientificlinux.org / www.centos.org

2^nd Part Practice Requirements

1.       Compatible H/W list is available on www.redhat.com/rhel/compare

2.       For installation any 32 bit or 64 bit machine can be used with minimum 512 MB or 1 GB RAM

3.       Using Virtual Machine is fine

a.       VirtualBox

b.      VMWare Player

c.       Parallels Desktop for MAC

d.      Virt Manager built in kernel

3^rd Part Basic Installation

1.       Kickstart Installation is the only method that is covered in RHCSA

2.       Basic Installation needs to be known

3.       Insert the disc after starting the computer

4.       Select Install or Upgrade an existing system

5.       Skip the check for installation media as per requirements

6.       Click next

7.       Choose Language and choose next

8.       Choose keyboard type and next

9.       Select Basic/Specialized Storage device and Next

10.   Yes Discard any data and next

11.   Hostname choose

a.       Enter host name

b.      Click configure network

c.       Choose system eth0 device

d.      Click edit

e.      Check mark connect automatically

f.        Check IP4 setting automatic DHCP

g.       Apply and close

12.   Click next

13.   Time zone select

14.   Root Password and confirm and next

15.   Installation method select use all space

16.   Check review and modify partition lay out and observe

17.   Write changes to disk select

18.   Install Bootloader to a particular location

19.   Choose Bootloader password if needed and next

20.   What type of installation needed and next

21.   System installation starts and after it ends Reboot

22.   Restart First boot screen

23.   Final configuration steps ‘Forward’

24.   Agree license Forward , Register Later

25.   No thanks I’ll connect to RHEL later

26.   Username and other details Forward

27.   System Time set

28.   Finish

4^th Part KickStart Files

1.       Automated installation using kickstart

2.       Kickstart installations are performed based on files that contain instructions of how the system needs to be setup

3.       A kickstart configuration file is automatically created by the anaconda installer at the end of the RHEL installation

4.       This file is saved in the root user’s home directory called Anaconda-ks.cfg

5.       You can manually create a kickstart file manually by the system config kickstart utility

6.       Application > system tools > kickstart

7.       This application is not installed by default however its easy to get it post installation

8.       Open kick start file to view its content

# kickstart file automatically generated by anaconda

# version = DEVEL

Install cdrom  //this means installation media was cdrom

Network enable //network was enabled

Root password encrypted

Firewall started ssh port opened

Shadow password for authentication

Selinux—set to enforcing mode

Timezone -> set

Bootloader

Below this is hard drive and LVM layout

All are commented by ‘#’ reason being a new system requiring the file may not have same hard drive layout

Installation repository name RHEL

Packages section have all software info ‘@’ indicates package group

‘@’ absent indicated individual package

‘-‘ indicates package excluded from install

9.       Uncomment the drive details since we need it for the automated install later

10.   The system configuration kickstart file can be used to modify existing kickstart config file as well

11.   File > open > select anaconda-ks.cfg and fields will be automatically filled along with partition info

12.   Display configuration : if we do not include directives for installing Graphical Desktop Environment than the 1^st boot service will not run after the installation has finished. In this event u will have to manually add a user to the system. By default kickstart only defines a root user, we can add a new user to kickstart file with ‘user’ directive

13.   Simplest place to specify a user is right below the root user in the kickstart file

User –name=Kenny –password=pass1234

More info at www.fedoraproject.org/wiki/anaconda/kickstart

5^th Part Rhel installation from kickstart file

Network location install

1.       You can use kick start file from a:

a.       Network location

b.      Cd

c.       hard drive

d.      web location

e.      ftp server

f.        nfs server

g.       usb device

2.       basic syntax is the same

3.       modify location every time

4.       steps to install

a.        boot install media

b.      press escape key

c.       boot prompt appears

d.      boot: linux ks=nfs:192.168.75.132:/srv/nfs/ks.cfg (enter)

5.       (nfs folder needs to be shared out)

6.       installation will finish automatically press reboot at the end

6^th Part Accessing terminal

1.       application > system tool > terminal

2.       steven born > bourn shell

3.       bash shell default

4.       change color edit preferences

5.       virtual/tty(teletype) console ctrl + alt + f1 to f6 while in gui

6.       enter username password n access is it

7.       while in tty console u can switch to any other console by alt+f1 to f6

8.       shift and page up and page down key to scroll up and down in the tty console

9.       to return to desktop ctrl+alt+f7

10.   all the Linux config files are in human readable format

11.   login shell for example

12.   when a login shell is started it is run from /etc/profile

13.   this scripts has users environment variables such as users path, hostname, history size, iot will also run the scripts in /etc/profile.d

14.   next the .bash_profile script in the users home directory is run this script modifies some of the environment variables stored in /etc/profile scripts

15.   next the .bash_prifile script cause the .bashrc script in the users home directory

16.   this script sets some of the local variables such as ps 1 variables which dictates how the command prompt appears

17.   a non login shell utilize the same scripts just in a different orders

18.   the 1st script that runs in the non login shell is the .bashrc script in the home directory

19.   this script in turn calls the  etc/bashrc scripts and this script calls the etc/profiel.d

7^th Part Basic Commands

1.       ls- list directories

2.       ls-l long listing permission, user ownership n file size

3.       ls –lh file size in human readable

4.       ls –a hidden file and all other files with ‘.’

5.       Cd change directory cd /dir_name

6.       Cd .. to parent directory

7.       Cd -~ home directory

8.       Pwd print working directory

9.       Clear to clear screen

10.   Mkdir to make a directory

11.   Mkdir –p  subdirectory beneath a directory /name/name1/name12

12.   Rmdir to remove a directory only works on empty directory

13.   Rmdir –p whole tree provided empty

14.   Cp copy files n folder from one to another

15.   Rm to remove files n dir that has content

16.   Rm -f to not have warning before delete

17.   Rm –r to remove directory with content

18.   Mv to moves files n directory also used to rename

19.   Less to read content of file scroll using up and down using arrow key and skip page using page up and page down keys or use j and k to scroll and press q  to quit

20.   Man to print manual page associated for each command ‘/’ we can search whatever we want to search in the manual page quit by q

21.   Apropos term_name to get details of any particular term existing it will give a list of the details present about that term in any of the commands and display it. By default there will be a number associated with every page e.g number 8 is for system administration tasks number 1 shows commands available for regular users 5 for specific file formats and configuration files

22.   –help can be used with any command to see what options to be used with that command

23.   Info much like man pages but may have more info not all commands have info pages

9^th Part Cat and Nano

1.       Cat is short for concatenate we can join many files into one or we can concatenate output of the terminal into a new file.

2.       Also used to show content of a file in terminal

3.       To create anew file into terminal using cat use the following syntax cat << EOF > test.txt (enter) input_your_text EOF(end of file)

4.       Cat filename.txt to read its content

5.       To combine files into new file cat file1.txt file2.txt > file3.txt

6.       NANO text editor

7.       Type nano (enter)

8.       Similar to edit text editor

9.       Type text

10.   Ctrl o to save file filename to file exit by ctrl x

11.   Nano space filename

12.   Ctrl x to exit

13.   Ctrl w for searching ctrl r to replace

14.   Ctrl g to help on nano

10^TH Part Vim

1.       Improved Vi

2.       Installed and available by default

3.       Buy borrow editor lets u view contents but not modify  it. Editor mode to modify

4.       Enter vim and press enter u will get a welcome screen

5.       :help to see help to use VIM j n k to navigate

6.       :q to quit file

7.       I for insert mode

8.       Esc to normal mode

9.       Save the file esc :wq

10.   :q! close without saving

11.   Vim filename

12.   Shift+a to end of line append

13.   0 to move cursor to beginning of the line

14.   O to go beneath the beginning of the present line

15.   K to move up

16.   Yy to yank the line i.e copy

17.   P to paste

18.   U to undo

19.   Delete the 1^st character by x key

20.   Vimtutor to instructions

ACM ICPC (3)

Some rights reserved by Kiewic

1st day

Our 1st day stay was an unofficial one. We reached there one day prior to the actual reporting day. There was actually nothing to do and a few teams like ours who had arrived a day before. Even though lunch and dinner arrangements were not done for the 1st day, we were directed to the college canteen, we dint go for lunch just had a light snack.
We had rest at noon, and evening we went to a seashore(cant call it a beach) nearby which is very much near to Amrita amma's ashram, as locals directed us there. Spent the evening near the sea shore, clicked a few pics and had fun. While returning to the hostels clicked a few pics near the huge college building which almost looked like a palace.
For dinner, we were told to go to the hostel mess, the dinner was decent enough and free although it was an official stay. The 1st day itself we got to know the rule for the college hostel students and i guess although few may not like it, but with a discipline point of view it was very much needed and good although. You are supposed to wash your own plates after the meal. This rule was only for the college students not for the guests.
After dinner had a nice walk and finally returned to the hostel, studied a bit and went to sleep
2nd Day (THE 1ST OFFICIAL DAY)
By the time we woke up, Many more students have had already arrived. We woke up late lazily since there was nothing to do as such, had bath and went to hotel Amma for breakfast. Had something new there called Omlette dosa..... :P Now we went for checking the college campus and building. The college building is a huge palace like structure pure white in color and looks highly royal. Looks sure like a ICPC centre. The classrooms and the campus was much like any other campus. thereafter went for registrations met few other students there, made a few friends there among the volunteers. Got to know few other colleges and school came from Maharashtra. There were certain documents to be presented, the college I-Card and other stuff. It all got wind up pretty soon. Just wanted to go in the rooms and have rest. Lunch was in the college canteen. The canteen was really big and was clean as well. The food was awesome. Volunteers to serve us the same. The coordination was splendid among the volunteers.

Josephus Problem Ruby Code

Ruby code for solving josephus problem. Although the presentation isn't good enough. This was my first Ruby exercise so ignore the mistakes in it... :P

#! /usr/bin/ruby -w
class List
  attr_accessor :element,:next_element,:last_element
  def initialize(element)
      @element = element
      @next_element = nil
      @last_element = nil
  end
end
number = ARGV[0]
number=number.to_i
first = List.new(1)
temp = first
for i in 2..number
  temp=temp.next_element = List.new(i)
end
temp.next_element = temp.last_element
temp.next_element = first
temp = first
count=0
while temp.next_element.next_element != temp
  count = count + 2
  if count % 100 == 0
    puts "100 killed total count #{number+1}"
    temp.last_element= List.new(number = number + 1 )
  end
  temp = temp.next_element = temp.next_element.next_element = temp.next_element.next_element.next_element
end
STDOUT.puts "last one is #{temp.element.to_s}"

Ruby and Sinatra Example of Automatic Mutt Configuration

# these will include sinatra and erb gem(gem is a package in ruby it will have additional info like files required to be installed) in the code here we are including sinatra because sinatra is a DSL domain specific language(DSL is a language which is concerned with a specific domain problem, it helps us solve a particular problem and then advance accordingly there are other DSL's as well like HTML)sinatra is a DSL for quick development of webpages. ERB is embedded ruby erb gives a powerful way to embed ruby code to plain text document or an html file etc this helps in generation of documents etc. since we will b using WEBrick server which sinatra activates we will be requiring sinatra and since we will be creating a template with ruby embedded in it we will be requiring erb as well.
require 'sinatra'
require 'erb'

# get is a route which will map the get method of http to the controller action here /tryerb is a controller action.(A controller action is supplied with more info many a times for specific data e.g. GET /movies/3 will mean the route GET should map HTTP method to movies with id 3 and show the information of that movie with id 3)  information will be rendered from tryerb. get route will show the page. POST would create one. DELETE will remove and PUT will update.
get '/tryerb' do
    erb :tryerb
end

#muttconf_template will store the template info whenever a template encounters a <% %> it will consider it a ruby code and whenever it encounters a <%= %> it will consider that a statement there are few more tags as well.
muttconf_template = "set imap_user =\"<%= @usrname %>\"
set imap_pass =\"<%= @paswd %>\"
set spool_file =\"<%= @spool_file %>\"
set folder =\"<%= @folder %>\"
set postponed =\"<%= @postponed %>\"
set header_cache =\"<%= @header_cache %>\"
set message_cachedir =\"<%= @message_cache_dir %>\"
set certificate_file =\"<%= @certificate_file %>\""

#An object 'configure' of class ERB is created to which the above template is supplied
configure = ERB.new(muttconf_template)

# post route will create a new tryerb with the data that is attached to it.
post '/tryerb' do
  @usrname = params[:usrname]
  @paswd = params[:paswd]
  @spool_file = params[:spool_file]
  @folder = params[:folder]
  @postponed = params[:postponed]
  @header_cache = params[:header_cache]
  @message_cache_dir = params[:message_cache_dir]
  @certificate_file = params[:certificate_file]

#configure.result will give the data that was supplied to it. binding methods binds the global variables, i.e. retains the values of the variables that have been used earlier. FInally the mutrc file is opened and the output is written into it. aftr creation of the mutrc the msg of mutt being successfully configured is displayed.
  output = configure.result(binding)
  File.open('mutrc','w') do |f|
    f.write output
    f.close
  end
"MUTT CONFIGURED SUCCESSFULLY!!!"
end

The code was further Modified as below....

newfile.rb
# encoding: utf-8
#roshan again
require 'rubygems'
require 'sinatra'
require 'erb'

get '/newfile' do
    erb :newfile
end

file = File.open("template", "r")
muttconf_template = file.read
configure = ERB.new(muttconf_template)
post '/newfile' do
  @usrname = params[:usrname]
  @paswd = params[:paswd]
  output = configure.result(binding)
  user = @usrname
  passwd = @paswd
  pass = passwd
  system("(perl -e 'print crypt($ARGV[0], \"#{pass}\")' $#{pass})");
  system("sudo useradd #{user} -p '#{passwd.crypt("$1$password")}'")
  Dir.mkdir("/home/#{user}");
  File.open("/home/#{user}/.muttrc","w") do |f|
    f.write output
    f.close
    end
  erb :postfile
end

template file
set imap_user ="<%=@usrname%>@gmail.com"
set imap_pass ="<%=@paswd%>"
set folder ="imaps://imap.gmail.com:993"
set spoolfile ="+INBOX"
set header_cache ="~/.mutt/cache/headers"
set message_cachedir ="~/.mutt/cache/bodies"
set certificate_file ="~/.mutt/certificates"
set smtp_url ="smtp.googlemail.com:587"

views/newfile.erb
<form name="text_form" action="/newfile" method="post"
<H1>MUTT CONFIGURATION PAGE</H1>
Username: <input type="text" name="usrname" /><br/>
Password: <input type="password" name="paswd" /><br/>
<input type="submit">
</form>

views/postfile.erb
<html>
  <title>
  Success!!!
  </title>
    <head>
      <body>
        <h1>Successfully Configured Mutt!!!</h1>
         Open Terminal<br/>
         Type ssh [username]@[ip_address](ENTER)<br/>
         Type 'mutt' press enter and check you inbox
      </body>
    </head>
</html>

May be modified further as well....

Let’s talk CLOUD COMPUTING

Cloud Computing, what’s the big deal? I heard someone saying that data is actually stored on cloud and could get wet due to rain water… lol Well yes could be… :P

Storing you data in a location outside your organization, where servers are actually present somewhere you don’t really know is cloud. Someone could make the definition even better for me. To actually understand the concept of what is new in cloud, one needs to understand, how things were before cloud came into existence (cloud was always their in existence, its just that the term was coined later).

Traditionally, companies had their own data servers or data centers to maintain or keep their data safe. Incase they had multiple centers they had distributed systems to maintain and use data, but the concept remains the same that each company took care of its own data through its own data centers. Incase they wanted to access this data at the same location or at different location they could do it through network. Basically, they kept their own data with themselves handled it or maintained it all by themselves.

So what’s the problem with it? Well in a way no problem. But if we understand cloud computing we will get what it helps in. Sometimes you get so used to a problem, that you don’t really think if it’s a problem. Now suppose for an X company the data servers were present in such a location with an illusion of being stored in a centralized manner, so that the company and all its centers can connect and access data from it whenever and wherever they want without worrying about the existence and maintenance of data how better it would be. Well sounds much like distributed databases except for the data is distributed throughout, what’s the difference? What if your organization is not supposed to worry about all of this hassle and handled it all to some third organization for maintaining? Sounds cool, but how does it help? X company works in a domain that has nothing to do with software. E.g X is a telecom company, all they worry about is if communication is perfect between their customers. But if X also has to maintain and keep up the database of all the communications like files sent and received from one customer to another, and this happening for a millions of customers. X will have to have a separate department that handle database, employ more workers, pay administrators, buy database servers maintain them. Distribute it to various locations. Rather if the job is being handled by a third organization which works itself in database maintenance and storage and is ready to provide the data whenever and wherever in an efficient manner with a little cost which should be surely less then employing more people and buying servers for yourself, why not go for it?

So, is that all? No, but there's more to it and more keeps growing too. This was just an example of what it really could do. Lets elaborate a bit.

Cloud services as mentioned in the earlier example are essentially divided into 3 major services. While these 3 are not the only services, but these services conquer the major part of the cloud. So what are these services:

SAAS : Software as a Service
PAAS : Platform as a Service
IAAS : Infrastructure as a Service

By now with the example stated above you probably might have had a hint of what these services really are all about.

SAAS: Software as a Service is using a Software as a service from the service provider on demand when the software is actually hosted on some cloud servers out there.
But whats the benefit? I would rather install the software on my own PC and use it when i want. Why cloud.
Suppose your work in some industry and you don't necessarily need Microsoft Office all the time. You probably may need it may be once every month or so may be to just view a document and edit it a bit. If you buy MS-Office for this reason and get it installed on your system lets see what all you did for this one year.

1. You bought MS-Office professional for Rs. 24000 as per the latest price stated on Flipkart for 2013 edition.
2. You called someone and paid him to have it installed on you machine since you were not good at installations and stuff.
3. On your machine the installation took around 1 GB or more of your Hard disk drive
4. Whenever you start it it consumes around 60 MB of RAM disk.
5. Whenever in this year you had a problem accessing Office you called up Microsoft service center too get help from customer care and waited for long queues.
6.  Every time Microsoft comes up with an update, you download the new update and install it which consumes more of your internet.
7. If Microsoft decides to stop docx, pptx extensions again as they did with the Old office in their new release. Gosh!!! you buy another office.
8. If system crashes, data done!!

Instead if you were using Office 365 which is Microsoft's cloud based Software as a Service lets see how the above mentioned steps changed.

1. You opened any browser and accessed the URL http://office.microsoft.com/en-in/business/compare-office-365-for-business-plans-FX102918419.aspx paid some amount on per month basis or per year basis as per your need which was 3 times less then what you paid for in a local installation
2. You accessed URL : https://office.live.com/start/Word.aspx?ui=en-US
3. You started working opened closed edited your docs saved it. Done!!!

Thats it?
No installation charges. No space consumed on local drive. No RAM consumed other than the browser RAM. No customer care calls needed as per SLA. No upgrades needed since they will handle it all by them self. If they plan to change the file extension in the next release, it get automatically reflected. Plus Advantages also include, you can access you documents online from anywhere. Your documents are protected with you username passwords. No worries of system crash.

This was just one example of a Saas based service there are surely many more such services existing that you could look for. Now that Saas is clear Paas and Iaas will be easy to understand.

PAAS: Just like in Saas you used office to create docs, In Platform as a service a service provider, provides you with a platform to build apps. Its basically used by the developers to create web applications without worrying about the infrastructure beneath for development purpose. The benefit remains almost the same however the added ones could be that it promotes collaborative development, and comes up with so many tools for development making it easy for developers.

IAAS: Many a times you might have felt the need to have a greater storage space for some reason but did not consider buying a disk for it. Also you might have felt a need to greater CPU or RAM for some performance reason but again, why buy something for a task that wont take more than an hour. Infrastructure as a service is a way to provide you with Hardware Infrastructure over the cloud. Its been heavily used by most of the companies and users. Storage, CPU and Memory are not the only things that Iaas is limited to. There's more to it for sure. Nowadays different options are provided by different service providers only to make the world a better place to live in.

Most of these services are free to use or at least free to try. Before making a mind, if or not to purchase it. We could surely try them out.
Some well known cloud services/providers

SAAS : Facebook, Gmail
PAAS : Googel App Engine, Heroku
IAAS : Amazon, Rackspace

Corruption

A king once announced in his kingdom, "Anyone who gets him  something that is really unique, which no one in this world has will be rewarded, but if its not unique, he will be hanged" A tailor came forward and gifted him an air jacket. He said that the jacket was invisible and was made up of air. The king proudly got up wore nothing but the jacket and proudly went on a ride in the kingdom. No one else, but a 12 year old kid came forward laughing out of his innocence and honesty saying "O king!! You are wearing absolutely nothing and are roaming naked giving your kingdom a full view of yourself." This is the end of the story. Don’t really know what happened with the kid, but pretty sure he dint live thereafter!!! Hope everyone got the right message….

ACM ICPC 2011 (2)

Some rights reserved by Kiewic

Onsite Competition Registration

Once you are selected for the regionals, the college is supposed to pay a registration fees of Rs. 3500/- which is for 5 people 3 contestants one reserve and a coach. This fees includes the accommodation and food for 5 days. The fees is to be sent by DD. After having a terrible experience with the Online registration I dint take a risk of being late for the Onsite one. I sent the amount as soon as possible. The money was paid by College. Registration was accepted. We were supposed to fill online registration forms for travel and accommodation. ICPC this time also took care about those students travel expenses, for those whose colleges could not sponsor it (Our college did it for us... ;)). You can even get guests to the venue subject to availability of accommodation and at their own expenses. As i mentioned earlier, we could not register a reserve due to technical problems. We registered him as a guest. So 4 of us. Me, Shreyas Damle, Rahul Dange and Gaurav Deochakke. were all set for the Onsite Contest. Our coach couldn't come for she had work in college.

Railway Reservation

Had a tough time with this one. I already knew it since i did Google a few blogs which did mention how previous year students had problems with it. Well, so did we. We booked Kanyakumari express, waiting ticket  and 2 nights and 3 day travel. We obviously didn't wanted this. We checked again for other trains from Mumbai and found Kerala Kranti Express from Panvel to Kollam 18 rs travel and seats available. Cancelled the previous tickets booked Kerala Kranti ticket for 8th December and mailed ICPC that we will be coming a day earlier cos of unavailability of proper reservations. Not to risk the return journey booked a return ticket as well. Netravati Express for 15th December Kollam to Panvel. 

Train Journey

The best journey i ever had. Thankfully all the passengers in our berth were cooperative and talkative too (or i guess we were too social... :P ) Made friends with almost all of them. One was a teacher in Kollam and one of them was sitting with his Mom was working in Punjab, and one was a student just like us. Clicked pics with all of them throughout the journey. Got down from the train at every signal at every station, bought everything at every station. Pretty sure people admired our appetites...:P

When train reached Kerela, we were not sure if were supposed to be picked up cause we were a day earlier than expected. Called up the Technical Director of ICPC (which we were not knowing earlier, else would have never dared to do so, for such a cheap reason). A very polite sounding gentleman recieved the call and ensured that a team will be recieving us on Kayankullam Junction. Kayankullam was one station before Kollam. Thereafter got numerous calls from ICPC volunteers to check as to where the train had reached. The volunteers were standing outside the station main gate in orange ICPC T-Shirts as they had already informed us over the phone. They welcomed us. Happy lot of crowd I must say. Although I feel sorry cause I forgot their names. They took us to their Hostel.

Introduction to algorithms by MIT

Lecture 1

This blog is an extract from MIT's Introduction to Algorithm course.

First part of the course ids focused on Analysis. Second part is focused on design i.e. before u design algorithms; you have to master and analyze a bunch of algorithms. Analysis is a theoretical study of a computer program performance and resource usage.

How to make fast and memory reliable programs?

What is more important than performance?

1.        correctness

2.        simplicity

3.        maintainability

4.        cost(programmer’s time)

5.        stability(robustness)

6.        features(functionality)

7.        modularity(changes implementation easy)

8.        security

9.        scalability

10.     user friendliness

Then, why study algorithm and performance?

Some times performance is correlated to user friendliness. Some times there are real time constraints. i.e. the software wont work untilit performs a function for a particular time. Performance measures the line between feasible and infeasible. In real time , if it is not fast enough, its as good as not functional. If it simply uses more memory, its not going to work for you.

Algorithms are at the cutting edge of entrepreneurship. If you are thinking of doing something that already exists, performance isn’t that necessary. But, if you are planning to do something’s that’s never done before, than its most important.

The reason why performance is at the bottom of the heap is because performance is just like money. What good is a $100 bill for you? Instead you would want to have food worth $100, that should be of some use to you. Performance is something you pay for. E.g you pay for user friendliness, you pay for security, etc.

So for this reason, a user may gor for JAVA instead of C for it may be slow, but it gives more functionality like exceptions, Object Orientations,etc.

PROBLEM: INSERTION SORT

Input: sequence <a1,a2,a3,….,an>of numbers

Output: permutations<a’1,a’2,a’3,…..,a’n>

Such that a’1 <= a’2 <= a’3 <= ….. <= a’n

Pseudo code:

Insertion_Sort(A,n) //Sorts A[1….n]

for j = 2 to n

                do key = A[j]

                                i = j-1

                while i>0 and A[i]>key

                                do A[i+1] = A[i]

                                                i=i-1

                A[i+1]=key

Figure 1

                   

                It basically takes array A[] and at any point we are running the outer loop of j from 2 to n and the inner loop that starts with i = j-1 and goes until i = 0 .  so we are looking at some element j in the algorithm, and then we pull out here a value called a key and the important thing to note is that there is an invariant that is being maintained by the loop each time through. The invariant is that the LEFT part of the array in the above figure 1 is sorted. And the goal each time through the loop is to add one to the length of the strings that are sorted. And the way we do that is we pull out the key, and we just copy the value up like the arrows shown until we find a place for the key shown and then INSERT it in that place, hence the name INSERTION SORT. Once we have arrays till j sorted we go for j+1. now let us see an example for the same.

Example

8 2 4 9 3

2 8 4 9 3

2 4 8 9 3

2 4 8 9 3

2 3 4 8 9 sorted

Analysis of this algorithm

Running time:

1. Depends on input. (e.g if already sorted, insertion sort has very little to do, cos every time we try to sort it would be like the step number 3 above where 9 is already sorted and was at its correct position so you don’t need to move it. Worst case is if its reverse sorted then there will be a lot of work to do, lot of shuffling to do as well.
2. Depends on the input size. (6 elements less time 10 elements more time) so large number of elements means long time for sorting. So we handle it by:

-          parameterize things in the input size.

3. generally we want upper bound on running time i.e we want to know that the time is no more than  a certain amount reason being that represents a guarantee to the user. E.g if I tell you that there’s  aprogram that wont run more than 3 seconds, that gives you real information about how you could use it for example in a real time setting. And if I say there’s a program that goes for at least 3 seconds, it could go for years. That doesn’t give you a guarantee if you are a user.

- guarantee to the user.

Different kinds of analysis :

Worst case analysis: this is done usually

Where T(n) = maximum time on any input of size n

So as we saw running time depends on input that some times the inputs are better like in sort if already sorted less time and if reverse sorted maximum time. So we are looking at the worst case. If T(n) is not for maximum time then T(n) is a relation and not a function, because the time on input size n will depend on which input of size n, I can have many different times. But by putting a maximum at it, turns that relation into a function, cos there’s only one maximum time.

Average case analysis: this is done sometimes.

Where T(n) = expected time over all inputs of size n

What is expected time? Time of every input and average them? Time of every input times of probability that it will be there that it would occur. How do we know the probability time of every input occurs is?

Well we don’t know it.

So we need an assumption of statistical distribution of inputs. Common assumption is that all inputs are equally likely that’s called uniform distribution.

Best case analysis: bogus

Because its already done. You can cheat, it doesn’t tell u of the vast majority cases.

What is insertion sort’s worst case time?

Depends on computer you are running on.

-          Compare two algorithm for Relative speed (on same machine)

-          Absolute speed (if onde algorithm is betr than the other no matter what machine it runs on.

Asymptotic analysis: ignore machine dependent constants and look at growth of running time T(n) as n -> ∞

Asymptotic notations

(Theta notation) q - notation:

Drop low order terms and ignore leading constants

e.g if there is a formula 3n^3+90n^2-5n+6046= q(n^3)

here n^3 is a bigger term than n^2 , n and all the leading terms thus it becomes q(n^3)

as n -> ∞ , q(n^2) algorithm always beats a q(n^3) algorithm.

n^2 will be faster than n^3

There will always be a point n0 where q(n^2) algorithm will be cheaper than q(n^3) algorithm

Insertion sort analysis

Worst case: input reverse sorted biggest element comes 1^st and smallest comes last.

T(n)= S ^j=2 to _n q(j) = q(n^2) (arithmetic series)

Is insertion sort fast? Moderately fast for small n but not for large n. Merge sort is faster instead.

MERGE SORT

Merge sort A[1….N}

1.        If n =1 done

2.         Recursively sort
A[1….[n/2]] and
A[[n/2]+1….n]

3.        Merge 2 sorted lists

Key subroutine here is merge and it works like this one of them is

20 13 7 2

12 11 9 1

We look at the two sorted arrays and see where is the smallest element and now we find 1 and two are smallest so we now look for the smallest of them and place the smallest in the new list so 1 is placed in new list. Now we compare the 1^st element of first list and 2^nd element from second list, similarly

Time = q(n) on n total elements

Recurrence for the program

q(1)

2T(n/2)

q(n)

Performance of merge sort T(n) = q(1) if n=1 (omit usually),2T(n/2)+ q(n) if n>1

Recursion tree T(n)=2T(n/2)+cn const c>0

T(n) = cn - > T(n/2) 2 times