Recursive IDE

-

This is historical screenshot for our Cloud IDE

It shows our IDE running itself, then running itself again from itself, … and so on : D

-

-

Graph Coloring

Introduction and Definition

Hmmmm, do you love colors?! Seems interesting! Yes it is! Graph coloring is one of the most interesting topics in the graph theory, here’s a simplified problem definition for graph coloring:

Graph coloring is to give each node a color such that no two adjacent nodes have the same color.

It seems easy from the first look, “why not to give each node a unique color?!” … seems okay, but the real challenge appears when we say

Give each node a color such that no two adjacent nodes have the same color using the minimum number of colors. This is the real challenge!

-
Applications – Map Coloring

One of the most interesting applications on the graph coloring is to color a map; giving each region a color such that no to adjacent regions -having a common side- have the same color. We can translate the map into a graph by representing each region by a node, and making an edge between two nodes if the two regions having a common side.

Here’s an example:

Given this map of A, B, C, D, E and F regions:

We can translate it to be a graph as the following:

We can now apply a graph coloring algorithm:

So, we can color our map only using four colors, here it is:

It’s nice to know that, there is a theorem called Four Color Theorem states that:

Given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.

Here’s an example of a map-coloring to the states of United States.
It shows clearly that the minimum number of used colors is four.

-
Other Applications

There are many other applications on graph coloring like:

• Suduko generator, we can simply generate suduko boards by representing each cell as a node and link nodes in the same row and the same column and the same inner square, here’s an example of what cell (1,1) should be linked with
  
• Scheduling events
  Scheduling events that have common participants to find the minimum number of time slots to hold these events is a problem that can be solved graph coloring by representing each event by a node and link two nodes if they have common participant.

-
Algorithms

Greedy Algorithm:

Greedy graph coloring is very simple, it starts with any node, flooding from this node and giving each reached vertex the first available color, here the availability means that there’s no adjacent node has the color.

Here’s a trace for the greedy algorithm applied to the above example:

Starting with node (A) giving it blue color.
Go to node (B) and give it a new color –green- because it is adjacent to node (A) which has blue color.
Now, go to node (C) and also give it a new color – red-.
Coloring node (E) with the first available color in the used colors list, we’ll pick up the blue.
Now (D), picking the first available color –green-.
Coloring (F) with a new color –yellow- because its adjacent nodes has all the used colors.

Greedy algorithm is not the only one existed for solving the graph coloring problem; it’s good also to read about DOM algorithm

-
Do you know?!

Do you know that graph coloring is an NP complete problem; this means that no polynomial-time algorithm is found till now to solve this problem optimally. Do you know also that finding a solution for one of the NP Complete problems qualifies you to win the Nobel Prize! WOW! Why not to think about that : D
-
-

Facebook and Microsoft Phone Interviews

—

—

—-

_

_

Although I’m at the beginning of my life, and I don’t have a lot of business experience, I managed to post here my gained experience throughout my only two interviews I had till now. One of them was with Microsoft from about 4 months –for an internship-, and the other was with Facebook, only a week ago.

Before talking about the interview, you have to prepare an attractive CV that gives a very good first impression for the recruiter. Know that, the recruiter won’t give your CV more than 10 seconds if he/she took a bad first impression. I may prepare another post about “How to Write an Attractive CV” isA.

Here are some bullets that summarize my experience and some guides lines:

1. Be Full Of Confidence”, believe me, you are very good and you’ll pass the interview successfully isA, it’s just a few minutes to pass it, let those minutes pass.
   _
   Guide: You have nothing to lose, you are just going to gain a lot of experience through the interview. I always remember my elder brother -Zikas- quote; “The interviews are just a chain of failures that ends with a success”.
   _
2. English, English, English,…It’s very important to be very good in English, speaking, listening and writing, you have to be able to make discussions in English easily and without being nervous. You have to be ready at any time to have a call with an interviewer from USA. At my first interview I heard someone talking with me and he said “您好，這裡是微軟的招聘人員” , I hardly understood that this was a “yes or no” question, so I answered him “yes yes” , and he proceeded asking me, but the issue became easier later : ))
   _
   Guide: Know that you are Arabian, and the interviewer knows that very well, he doesn’t expect someone who talks like Americans, so feel free to ask the interviewer to say the question or the sentence again if you didn’t hear him/her well.
   _
   Guide: Make a rehearsal with your friends, ask a friend of yours –who’s excellent in English- to make a phone call with you, and let him talk with you for a 30 minutes. You may let him ask you the frequently asked questions.
   _
   
3. You have to search for articles on the web that summarize what you can prepare before the interview for the company you are going to applying for.
   _
   Guide: The interview requirements differ from a company to another, study the type of questions you are going to be asked depending on the company you are going to apply for. You can ask a friend, search on the web, do anything, …
   _
4. Regardless your level in English, prepare a paper(s) with some points that you might need during the interview.
   _
   Guide: Only prepare bullets, not full sentences, Never let the interviewer feels that you are reading from a paper.
   _
   Guide: Train, train, train to reply to the frequently asked questions very well. It’s not enough to know that you’ll be asked X, it’s more important to know how to answer this X question in a professional way.
   _
   
5. Don’t talk like a robot. (Be flexible)
   _
   Guide: Don’t make it a one-way-call, don’t talk talk talk, make it something like a discussion, ask the interviewer for his opinion, you may even joke with him/her sometimes.
   _
   
6. Which team/department do you want to join inside Koko Company?
   _
   Guide: Study the company very well, know the teams working there, know the departments, or even tell him I’m interested in joining the team work in XYZ such that XYZ is your area of interest.
   _
7. When will you be available to join us? Will it be fine with you to join us on mm/yy? (Availability)
   For graduates who’ll apply for full-time, when will you be able to know your military status?
   _
   Guide: Check your coming events in the summer or after graduation.
   _
   Guide: Know when will your military status be defined depending on your birth date (1st/2nd half).
   _
   
8. It’s much better to receive the call on Land line, the voice will be much better and clearer. If you can’t receive it on land line, try to talk using headphone to be able to hear from two ears instead of one. Also to free your hands and to be able to write anything -notes, code, …- during the call.
   _
   Guide: For me, the best thing to make the call on Skype, I think most of interviewers have no mind for that. You can ask for that in the confirmation mail before the interview itself.
   

-

There are some frequently asked questions in MS and FB interviews.
(Note: I’m only talking about the first interview, which is the HR interview)

1. Introduce youself!
   Let me know more about yourself!
   _
   I consider this question as one of the hardest to improvise, you have to know yourself very well, know how to talk about yourself, about your achievements, about your interests. Prepare them in a paper and be ready to talk about yourself in a way that attracts the interviewer and gives him the impression that he is talking with someone unique, someone differs from others. know that, It’s all about how to market yourself!
   _
2. Why are you interested in joining Koko company?
   Why are you interested in getting an internship in Koko company?
   (Must be asked, and always is the first to be asked)
   _
   You have to know the company in which you are applying to very well; you have to know why you are interested in joining Koko Company. Prepare a list of reasons that made you interested.
   _
3. What can you add to Koko company?
   Why do you think we have to employ you in Koko company?
   _
   Guide: Here you have to divide and categorize your answer into two sections:
   • Some points that show what are your points of strengthen -both technical and soft skills-.
   • Some points that show your deep knowledge about the needs of Koko company, and how you are suitable to satisfy these needs.

   _
   

4. What’s your technical background?
   What’s your background?
   _
   Guide: From my point of view, you can list your background as follows:
• _____ Courses you studied in the faculty. (Algorithms, Data Structures, SW Engineering, … etc. ) List about 10-15 course!
  
• _____ Languages you know. (C++, C#, Java, HTML, PHP, … etc.)
  
• _____ Technologies and Concepts (Agile development, Game programming, … etc.)
  _
  
5. What was the best project for you to work in?
   _
   To professionally answer this question(What?), prepare a good, clear and brief description for this project that sounds well without going into deep details.
   _
   Guide: Take care! You’ll be asked “What was your role in this project?”, try to specify briefly and clearly your role in this project in case of team working.
   _
6. Why do you think this was the best project for you to work in?
   _
   Guide: Prepare a list of reasons that made this project the best for you. Improvising -for me- is not good in this questions, It increases the chance for forgetting important and attractive details that is of course very important.
   _
7. Did you face any problems working in this project?
   He is expecting “yes”, that’s why he’ll ask you.
   _
8. How did you overcome those problems?
   _
9. What was the maximum number of lines you wrote in a project?
   Guide: He is expecting something like X thousands (Don’t say, “hmmmmm, I don’t remember, but may be 200″ )
   _
10. After finishing the questions, you will be asked, “Do you have any questions?”, This is a very important question, Never say “No, Thanks”, Ask him any question that gives him the impression that you are very interested and that you care about the opportunity, for example:
• _____ How can I prepare myself for the next interview?
• _____ What topics shall I revise and cover before the next interview?
• _____ Guide: Don’t be solid, don’t you all ask him/her the same question (balash 7efz )

You may be asked some easy technical questions like:
(Guide: Generally, try to make your answers simple and direct, don’t act like Egyptians please )

1. What’s “deadlock” ?
2. What’s the difference between “classes” and “structs”?
3. What’s the difference between “thread” and “process”?
4. What’s “good code” from your point of view? (always asked in MS interviews)
   Take care, there is no ideal answer, but he only wants to know more about your mind, although there are main factors that defines good code, for example:
• _____ Bug free
• _____ Readable and commented
• _____ Runs on multiple platforms
• _____ and more … (don’t tell him “and more” : P)
5. So, how can you measure your code efficiency?
   Guide: Try to match most of the previous answer points!

For Microsoft internship interviews, you may be asked a testing question, It won’t be a code testing, it’ll be as follows:

• You are given a product X (Elevator, Pepsi Machine, Microwave, … etc.), how will you test this product?
• You may be asked, “How to test if a stack is working fine?”

The golden rule here, is to

• Take your time in thinking!
• Be creative!
• Imagine yourself in the real life and you are testing this product!
• You have to know that, to test any product:
  • Start with normal and happy scenarios and test cases. (Don’t start with “we’ll test how it’ll act under fires and strong hits” )
  • Then proceed with unhappy scenarios (You may also categorize the unhappy cases, try to be systematic during the testing as much as you can) 
    • Fires
    • Wrong presses on buttons (Invalid inputs)
    • Electric cutoff
    • Push in full stack and pop from empty one.
    • ….

_

- Here’s another helpful post written by Zikas.
_

The last thing to say and the most important one to care of, is to know that, this is “rezq” and ALLAH will give you your “rezq” whatever, wherever and whenever it is! Don’t be sad if you didn’t do well, you’ll not pay a “sa7tot”, and you’ll just learn and gain a lot.

Feel free to add and post your experience in the replies : )
-
-
-

C++ Big Integer

-

As I looked more than once for BigInteger class in C++ like this one in Java and didn’t find a well prepared one, I decided to implement mine.

The main idea of BigInteger class is to perform all arithmetic operations with no upper limit of values.  Data are stored as strings, Operations performed on these strings. It is good to know that 32 bit unsigned integer can store numbers from 0 to 4294967295, While signed int stores values from -2147483648 to +2147483647. Using BigInteger enables us to store and perform operations on very big values like 10^10000.

Some functions are increasing very fast like Fibonacci and Factorial functions, You can see how your scientific CASIO calculator prints “Sorry” for 70!   : D.

Main operations supported (+, -, *, / and %) and 15 additional  operator (=, ==, !=, >, >=, <, <=, ++, –, +=, -=, *=, /=, %= and unary minus). Four constructors existed for usability and data conversions.

One of (+ and -) operations costs O( max( len(operand1) , len(operand2) ) ), O( len(operand1) * len(operand2) )  for (*) operation and O( len(numerator) ) for (/ and %) operations. I have to say that we pay both time and memory when BigIntegers must be used.

Here’s simple clarification of the main idea:

As I found implementation file too big to be posted, I posted only the header file and linked the Cpp one.

Here’s “BigInteger.h”:

//-------------------------------------------------------------
// Class: BigInteger
// Author: Amr Mohammed
// Last update: 17-02-2011
//-------------------------------------------------------------
#include <string>
#define MAX 10000 // for strings

using namespace std;
//-------------------------------------------------------------
class BigInteger
{
private:
	string number;
	bool sign;
public:
	BigInteger(); // empty constructor initializes zero
	BigInteger(string s); // "string" constructor
	BigInteger(string s, bool sin); // "string" constructor
	BigInteger(int n); // "int" constructor
	void setNumber(string s);
	const string& getNumber(); // retrieves the number
	void setSign(bool s);
	const bool& getSign();
	BigInteger absolute(); // returns the absolute value
	void operator = (BigInteger b);
	bool operator == (BigInteger b);
	bool operator != (BigInteger b);
	bool operator > (BigInteger b);
	bool operator < (BigInteger b);
	bool operator >= (BigInteger b);
	bool operator <= (BigInteger b);
	BigInteger& operator ++(); // prefix
	BigInteger  operator ++(int); // postfix
	BigInteger& operator --(); // prefix
	BigInteger  operator --(int); // postfix
	BigInteger operator + (BigInteger b);
	BigInteger operator - (BigInteger b);
	BigInteger operator * (BigInteger b);
	BigInteger operator / (BigInteger b);
	BigInteger operator % (BigInteger b);
	BigInteger& operator += (BigInteger b);
	BigInteger& operator -= (BigInteger b);
	BigInteger& operator *= (BigInteger b);
	BigInteger& operator /= (BigInteger b);
	BigInteger& operator %= (BigInteger b);
	BigInteger& operator [] (int n);
	BigInteger operator -(); // unary minus sign
	operator string(); // for conversion from BigInteger to string
private:
	bool equals(BigInteger n1, BigInteger n2);
	bool less(BigInteger n1, BigInteger n2);
	bool greater(BigInteger n1, BigInteger n2);
	string add(string number1, string number2);
	string subtract(string number1, string number2);
	string multiply(string n1, string n2);
	pair<string, long long> divide(string n, long long den);
	string toString(long long n);
	long long toInt(string s);
};

Download the cpp file from HERE.

To test the class and train yourself to use it, I collected some UVa problems that requires BigInt, Here’s a list of some problems:

• Fibonacci Freeze
• 500!

Any technical feedback, bug more optimizations are completely welcomed : )

-

Content aware image resizing V.1.0 Beta

Content Aware image resizing V 1.0

Content aware resizing is how to re-size images without losing important details in it. Compared to traditional scaling, content aware resizing keeps the important focused objects as it is when shrinking or enlarging. That’s done by determining which part of the image is not very important or does not have a lot of details using energy function that shows the color gradients which mean less important pixels or sudden differences which mean the most important details.

Main software features:

• Drag & Drop images.
• Show energy map at any time of process
• Choose resizing mode between traditional scaling, DP content aware and greedy content aware.
• Highlight objects to freeze/erase with re-sizable brush.
• Choose whether to use unique seams when enlarging images or not.
• Statistics about energy loss after re-targeting.
• Export the image to a file or print it directly.

Screen shots of the program:

Main program panel screen shot

Initial input image (400 x 530)

We can press “Show Energy” button to view energy map of the image,

We can select any object to remove;

After erasing the object:

Reducing the initial width from 400 to  330 will cause fault image – The faces affected after resizing because it have little energy -

So, We can use Freezing brush to select our important objects;

Here’s the output after using Freeze brush;

About

20-day trial, 12.75 LE for Full version!

Press HERE to download!

Remainder of devision “Trial”

Salamo 3alykom

As part of preparation to make Innovative, Interesting educational videos, we made this video to illustrate the concept of “Remainder”.

But after valuable feedback from one of our friends. we remade it to be as following.

We are still waiting for your valuable feedback.

Thanx in advance

ACM Contest Tips

السلام عليكم ورحمة الله وبركاته

دي شوية Tips for ACM contest قعدت جمعتها وقسمتها لتلات محاور

1- قبل المسابقة

2- خلال المسابقة

3- بعد المسابقة

قبل المسابقة

1- تظبيط النية. والنية هي الحاجة اللي بتفرق بين المسلم وغيره. فالمفروض تبقى ناوي كده شوية نوايا لله وطبعا أهمها

a. بر الوالدين: إنك تحاول تجيب مركز كويس وتفرحهم بيك وتدخل الفرحه عليهم

2- إدعي ربنا كتيير إنه يوفقك في المسابقة

3- نام على الأقل ست أو سبع ساعات عشان فعلا الراحة بتفرق جدا خلال الكونتست خصوصا في آخر ساعتين.

4- المفروض التيم يتدرب كويس جدا على الـ Team work عشان فعلا التجانس بين أفراد التيم حاجة مؤثرة جدا.

5- تجهيز Library/Reference فيها كل الأكواد اللي ممكن تحتاجها في الكونتست ومش محتاج تقعد تفكر فيها جوا الكونتست. ويا ريت تبقى الـ Library دي فيها Table of contents في الأول عشان لما بتكبر بيبقى صعب توصل للكود اللي انت عايزه بسهولة.

6- دخول Individual contests كتير هدفها

a. تحديد المستوى وإن كل واحد يعرف هو إيه ال category اللي مقصر فيها ومحتاج يتدرب عليها أكتر.

b. إن الواحد يشوف نفس المسأله أصحابه حلوها إزاي ويعملو analysis عشان يشوفو أني حل أحسن.

7- دخول Teams contests هدفها:

a. التدريب على Team work وإن التيم يبقو فاهمين بعض كويس

b. وضع Strategy للتيم: يعني مثلا هنعمل إيه لو

i. فاضل ساعتين ومعانا خمسه WA

ii. فات ساعة ولسه محلناش ولا مسألة

iii. الجهاز اللي قاعدين عليه باظ في نص الكونتست

iv. ـBlablablaـ

v. كل ديه حالات لازم يبقى التيم عارف لما يتحط فيها هيبقى إيه رد الفعل وإيه أحسن حاجه يعملها في الحاله دي:

c. التدريب على الحل على جهاز واحد وسرعة الحل.

d. التدريب على كتابة الكود على الورق. وكتابة الكود مش معناها PsuduCode لأ, معناها Real Code بحيث لما تكتبه يشتغل.

8- يبقى أهم نقطة قبل المسابقة وهي: إنك تبقى واثق من نفسك ومن التيم كله وإن احنا مش رايحين نجرب حظنا, لأ احنا رايحين نكسب إن شاء الله. فعلا دي نقطة مهمة جدا جدا جدا إنك تبقى داخل الكونتست منتصر نفسيا.

خلال المسابقة

1- أول ما الكونتست تبدأ قسموا المسائل بسرعة وكل واحد يبدأ يقرا المسائل اللي معاه وكل هدفه وهو بيقرا إنه يعرف ال Category بتاعت المسألة ويكتب بقلم رصاص عليها ويسيبها ويقرا اللي بعدها إلا لو هي ACE وسهلة جدا يروح يحلها ويبقى يكمل قراية بعد أما يحلها. وبعد كده كل واحد يرتب المسائل اللي معاه على حسب الصعوبة. ويكتب الكود بتاعها على ورق الأول ومش PsuduCode زي ما قلنا. لأ, كود بجد. ولو كتبه وعمله Trace ومتأكد إنه صح, يروح يكتبه على الجهاز ويبقى قدامه من 20 لـ 25 دقيقه يكون جايب الـ Sample لو معرفش في 25 دقيقة. يبعت للـ Judges ويطبع الكود ويقعد يعمله Debug على الورق. ولو معرفش خلال كمان 20 دقيقة يسيب المسأله فورا للـ Freeze hour

2- حاولو تنفذو خطة 1-3-1 ودي معناها إنك تقسم الكونتست:

a. أول ساعه Hunting for aces: تحاولو تحلو أي مسألة سهلة بسرعة جدا ولازم يبقى فيه على الأقل مسألة سهلة جدا تتحل على طول.

b. تلات ساعات؛ محاولة حل بقيت المسائل من الأسهل للأصعب زي ما قلنا.

c. آخر ساعه Freeze hour: دي مفيهاش أي أي مسائل جديدة, مهمة الساعة دي إنك تعمل Debug لأي مسأله حلتوها ولسه مش AC.

3- نظموا الورق اللي في إيديكو كويس جدا: الورق الأبيض في ناحية والمسائل في ناحية تانية. المسائل الـ AC في ناحية واللي لسه في ناحية تانية. فعلا تنظيم الورق ده مهم جدا إحنا في ال WarmUp اللي فاتت في مسأله ضاعت مننا وخدناها من اللي جمبنا :D

4- ركزو أوي على الـ Scoreboard شوفوا إيه المسائل اللي اتحلت وانتو لسه محلتوهاش. شوفو مثلا المسائل اللي الناس بتجيب فيها WA كتير وحاولو تفكرو في Critical test cases ليها قبل ما تبعتوها.

5- لو حد جاب WA إوعو حد يزعل ولا يبين إنه زعلان هو مش أول وآخر واحد يجيب WA في الكونتست

6- محدش يلوم حد جوه الكونتست خاااااااالص. مش وقته خالص كله بعد الكونتست.

7- إكتبو Clean Code عشان لما حد من إصحابك ييجي يعمل معاك Debug في الكود ما يقلكش يعني إيه:

a. ـTempـ

b. ـZZـ

c. ويا سالام بقى على الناس اللي بتستخدم حرف واحد , k l y p h d

8- في مسائل كتير بتبقى سهله جدا جدا بس ال Description بتاعها طويييييييييييل وممكن تلاقي كلمات صعبة ورخمة في النص. وهدف الـ Problem setter إنها تكون خادعة. فياريت محدش يخاف لو لقى مسألة طويلة قوي وفيها رسومات وحاجات

9- حلّو لحد آخر ثانية ومحدش يقول “كفاية” لو حليتو كتير. وبردو محدش يقول “مش هنلحق” لو حليتو عدد قليل. في سنة من السنين في الـ Regional تيم جامعة القاهرة كانو حالين مسألتين بس لحد الـ Freeze hour وفي الـ Freeze hour حلو أربع مسائل وتقريا كانو الرابع ساعتها بس هما مقالوش “كفاية” وحلو المسألة السابعة وبعتوها في آخر دقيقه وجابت AC وبقو الأول على الكونتست. مش محتاج أعلق كتير الصراحة

10- حاولو تركزو أوي على الـ First submission وعشان تعملو كده ركزو فى الآتي:

a. إتأكدو إنكو فهمتو المسألة كويس أوي وإن مفيش سطر مش مفهوم.

b. ركزو جدا في الـ Input Limit وده بيفرق طبعا في الطريقة اللي المفروض تحل بيها.

c. استخدموا الـ Data types المناسبة int, long long, double, long double….

d. قبل ما تبعتو إتأكدو من ال Boundry cases مثلا قالك 0 < N <= 1000 جربو ال 1 والـ 1000

e. إوعو تنسو سطر ال freopen()

f. لو جالكو CE والكود شغال صح على ال Visual Studio تجربوه على ال Eclipse وتشوفو المشكله عشان ال Visual Studio فيه حاجات مش Standard. أو اشتغلو من الأول على Eclipse وخلاص.

11- آخر حاجة وأهم حاجة: لو انت نيتك لله متخليش الكونتست تأخرك عن الصلاة.

بعد الكونتست

1. إفرح وقول مبروك للتيم بتاعك والتيمز التانية واضحك مع الناس وافتكر دايما إن كل ده بيتنسي وتبقى الزكريات الجميلة . Have Fun !!!

2. قول الحمد لله على كل حال. وفي حالة إنكو عملتو مركز عالي إوعى تقول “أنا” وفي حالة إنكو لخبطو في الكونتست إوعى تقول “هما”. “عييييب” انتو Team واحد.

3. إعملو Analysis بعد الكونتست الهدف منه تَجَنُّب الأخطاء اللي وقعتو فيها في نص الكونتست.

طولت عليكو معلش

شكرا لـ:

- حسين هشام

- عبد الرحمن زكريا

- مجدي مدحت

- خالد أحمد

- محمود عبد الرحمن

Complexity Analysis and Introduction to Algorithms

Contents:

· Coplexity Analysis

o Introduction

o Analysis of algorithms

o Orders of growth

o Big O notation

· Introduction to Algorithms

o Sorting Algorithms

§ Bubble sort

· Introduction

· Implementation

· Complexity analysis

§ Insertion sort

· Introduction

· Implementation

· Complexity analysis

o Searching Algorithms

§ Linear sort

· Introduction

· Implementation

· Complexity analysis

§ Binary sort

· Introduction

· Implementation

· Complexity analysis

· References

Complexity Analysis:

Introduction

Complexity theory is the study of the resources (especially computation time and memory) required by algorithms.

Analysis of algorithms

To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or complexity of an algorithm is stated as a function -f()- relating the input length (n) to the number of steps (time complexity) or storage locations (space complexity).

Orders of growth

Informally, an algorithm can be said to exhibit a growth rate on the order of a mathematical function if beyond a certain input size n, the function f(n) times a positive constant provides an upper bound or limit for the run-time of that algorithm. In other words, for a given input size n greater than some n_o and a constant c, an algorithm can run no slower than c × f(n). This concept is frequently expressed using Big O notation

f(n)	n=20	n=40	n=60
n n2 n3 2n	2/(105) sec 4/(104) sec 8/(103) sec 1 sec	4/(105) sec 16/(104) sec 64/(103) sec 12.7 days	6/(105) sec 36/(104) sec 216/(103) sec 366 years

Big O notation

In mathematics, computer science, and related fields, big O notation (also known as Big Oh notation, Landau notation, Bachmann–Landau notation, and asymptotic notation) describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. Big O notation allows its users to simplify functions in order to concentrate on their growth rates: different functions with the same growth rate may be represented using the same O notation.

Although developed as a part of pure mathematics, this notation is now frequently also used in computational complexity theory to describe an algorithm‘s usage of computational resources: the worst case or average case running time or memory usage of an algorithm is often expressed as a function of the length of its input using big O notation. This allows algorithm designers to predict the behavior of their algorithms and to determine which of multiple algorithms to use, in a way that is independent of computer architecture or clock rate. Big O notation is also used in many other fields to provide similar estimates.

A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

Algorithms:

In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem using a finite sequence of instructions. Algorithms are used for calculation, data processing, and many other fields.

There are many algorithms like;

1. Sorting Algorithms

a. Bubble Sort

b. Insertion Sort

c. And many other algorithms (Quick Sort, Selection Sort, …. )

2. Searching Algorithms

a. Linear search (sequential search)

b. Binary search

c. And many other algorithms (BFS, DFS, … )

3. And There are many and many algorithms : ) used in this fields and other fields.

Sorting Algorithms

Bubble sort algorithm

The bsort() function sorts the array using a variation of the bubble sort. This is a simple (although notoriously slow) approach to sorting. Here’s how it works, assuming we want to arrange the numbers in the array in ascending order. First the first element of the array (arr[0]) is compared in turn with each of the other elements (starting with the second). If it’s greater than any of them, the two are swapped. When this is done we know that at least the first element is in order; it’s now the smallest element. Next the second element is compared in turn with all the other elements, starting with the third, and again swapped if it’s bigger. When we’re done we know that the second element has the second-smallest value. This process is continued for all the elements until the next-to thelast, at which time the array is assumed to be ordered. Figure 10.8

Code of bubble sort

void buble_sort(int arr[])

{

For(int i=0; i<strlen(arr); i++)

For(int j=0; j<strlen(arr); j++)

If(arr[i] > arr[j])

swap(arr[i], arr[j]);

}

Complexity analysis of Bubble sort

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as Insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

Code of Insertion sort:

void insert(int arr[], int arrLen ,int value)

{

int insertionPosition = 0;

for(int i=0; i<arrLen; i++)

{

if(value < arr[i])

break;

insertionPosition++;

}

for(int i=arrLen; i>insertionPosition; i–)

arr[i] = arr[i-1];

arr[insertionPosition] = value;

}

Complexity analysis of Insertion sort

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time (i.e., O(n²)).

Searching Algorithms

Linear Search (sequential search)

In computer science, linear search or sequential search is a method for finding a particular value in a list, that consists in checking every one of its elements, one at a time and in sequence, until the desired one is found.

Code of Linear search:

/* This function return the index if the value if found and (-1) if not */

int linear_search(int arr[], int value_to_be_searched)

{

for(int i=0; i<strlen(arr); i++)

if(arr[i] == value_to_be_searched)

return i;

return -1;

}

Complexity analysis of Linear search

The worst-case cost and the expected cost of linear search are both O(n).

Binary Search Algorithm

In computer science, a binary search is an algorithm for locating the position of an element in a sorted list. It inspects the middle element of the sorted list: if equal to the sought value, then the position has been found; otherwise, the upper half or lower half is chosen for further searching based on whether the sought value is greater than or less than the middle element. The method reduces the number of elements needed to be checked by a factor of two each time, and finds the sought value if it exists in the list or if not determines “not present, in logarithmic time.

Code of binary searcing

/* Return the index of the value_to_be_searched if found and (-1) if not */

int BinarySearch(const int container[], int arraySize, const int & value_to_be_searched)

{

int middle;

int start = 0;

int end = arraySize – 1;

while(start <= end)

{

middle = (start + end) / 2;

if (value_to_be_searched < container[middle])

end = middle – 1;

else if (value_to_be_searched > container[middle])

start = middle + 1;

else

return middle;

}

return -1;

}

Complexity analysis of Binary search

The worst-case cost of binary search are both O(log(n) ), Where n is the number of elements in the list.

References:

http://en.wikiversity.org/

http://en.wikipedia.org/

Slides of Dr.El Sayed el Horbati

Object Oriented Book – Rebort Lafore –

Introduction to CPlusPlus Programming

C++ and C :

C++ evolved from C, which evolved from two previous programming languages, BCPL and B.

BCPL was developed in 1967 by Martin Richards as a language for writing operating-systems software and compilers for operating systems.

The C language was evolved from B by Dennis Ritchie at Bell Laboratories. C uses many important concepts of BCPL and B.

C initially became widely known as the development language of the UNIX

operating system. Today, most operating systems are written in C and/or C++.

American National Standards Institute (ANSI) cooperated with the International Standardization Organization (ISO) to standardize C worldwide; the joint standard document was published in 1990.

C++, an extension of C, was developed by Bjarne Stroustrup in the early 1980s at Bell Laboratories. C++ provides a number of features that “spruce up” the C language, but more importantly, it provides capabilities for object-oriented programming.

Basic Program Construction :

Let’s look at a very simple C++ program. This program is called FIRST, so its source file is FIRST.CPP.

It simply prints a sentence on the screen. Here it is:

#include <iostream>

using namespace std;

int main()

{

cout << “We are TENNIN programmers\n”;

return 0;

}

Despite its small size, this program demonstrates a great deal about the construction of C++

programs. Let’s examine it in detail.

• Functions: Functions are one of the fundamental building blocks of C++. The “FIRST “program consists of a single function called main(). The only parts of this program that are not part of the function are the first two lines. the ones that start with #include and using. (We’ll see what these lines do in a moment.)

• Function Name: The parentheses following the word main are the distinguishing feature of a function. Without the parentheses the compiler would think that main refers to a variable or to some other program element. When we discuss functions in the text, we’ll follow the same convention that C++ uses: We’ll put parentheses following the function name. The word int preceding the function name indicates that this particular function has a return value of type int.

• Braces and the Function Body: The body of a function is surrounded by braces (sometimes called curly brackets). These braces play the same role as the BEGIN and END keywords in some other languages: They surround or delimit a block of program statements. Every function must use this pair of braces around the function body. In this example there are only two statements in the function body: the line starting with cout, and the line starting with return. However, a function body can consist of many.

• Always Start with main()

When you run a C++ program, the first statement executed will be at the beginning of a function called main(). The program may consist of many functions, classes, and other program elements, but on startup, control always goes to main(). If there is no function called main() in your program, an error will be signaled. In most C++ programs, as we’ll see later, main() calls member functions in various objects to carry out the program’s real work. The main() function may also contain calls to other standalone functions

• Program Statements

• cout << “We are TENNIN programmers”;
• return 0;

The first statement tells the computer to display the quoted phrase. Most statements tell the computer to do something. In this respect, statements in C++ are similar to statements in other languages. In fact, as we’ve noted, the majority of statements in C++ are identical to statements in C.

A semicolon signals the end of the statement. This is a crucial part of the syntax but easy to forget. In some languages (like BASIC), the end of a statement is signaled by the end of the line, but that’s not true in C++. If you leave out the semicolon, the compiler will often (although not always) signal an error. The last statement in the function body is return 0;. This tells main() to return the value 0 to whoever called it, in this case the operating system or compiler. We’ll learn more about return later.

• Whitespace

We mentioned that the end of a line isn’t important to a C++ compiler. Actually, the compiler ignores whitespace almost completely. Whitespace is defined as spaces, carriage returns, linefeeds, tabs, vertical tabs, and formfeeds. These characters are invisible to the compiler. You can put several statements on one line, separated by any number of spaces or tabs, or you can run a statement over two or more lines. It’s all the same to the compiler. Thus the FIRST program could be written this way:

#include <iostream>

using

namespace std;

int main () { cout

<<

“We are TENNIN programmers\n”

; return

0;}

We don’t recommend this syntax, it’s nonstandard and hard to read—but it does compile

correctly.

There are several exceptions to the rule that whitespace is invisible to the compiler. The first line of the program, starting with #include, is a preprocessor directive, which must be written on one line.

• Output Using cout

As you have seen, the statement

cout << “We are TENNIN programmers\n”;

causes the phrase in quotation marks to be displayed on the screen. How does this work?

A complete description of this statement requires an understanding of objects, operator overloading, and other topics we won’t discuss until later in the book, but here’s a brief preview. The identifier cout (pronounced “C out”) is actually an object. It is predefined in C++ to correspond to the standard output stream. A stream is an abstraction that refers to a flow of data. The standard output stream normally flows to the screen display—although it can be redirected to other output devices. We’ll discuss streams (and redirection) in Chapter 12, “Streams and Files”.

The operator << is called the insertion or put to operator. It directs the contents of the variable on its right to the object on its left. In FIRST it directs the string constant “Every age has a language of its own\n” to cout, which sends it to the display.

Although the concepts behind the use of cout and << may be obscure at this point, using them is easy.They’ll appear in almost every example program.

• Directives

The two lines that begin the FIRST program are directives. The first is a preprocessor directive, and the second is a using directive.

They occupy a sort of gray area: They’re not part of the basic C++ language, but they’re necessary anyway.

• Preprocessor Directives

The first line of the FIRST program,

#include <iostream>

The preprocessor directive #include tells the compiler to insert another file into your source file. In effect, the #include directive is replaced by the contents of the file indicated. Using an #include directive to insert another file into your source file is similar to pasting a block of text into a document with your word processor.

• Header Files

In the FIRST example, the preprocessor directive #include tells the compiler to add the source file IOSTREAM to the FIRST.CPP source file before compiling. Why do this? IOSTREAM is an example of a header file (sometimes called an include file). It’s concerned with basic input/output operations, and contains declarations that are needed by the cout identifier and the << operator. Without these declarations, the compiler won’t recognize cout and will think << is being used incorrectly. There are many such include files. The newer Standard C++ header files don’t have a file extension, but some older header files, left over from the days of the C language, have the extension .H.