Technology Corner

Home » Tutorials

Category Archives: Tutorials

Follow Technology Corner on WordPress.com

Programming languages and contribution of Mathematics : An overview

Application of Discrete Mathematics in Computer Science

Discrete Mathematics play a vital role in software Development in Computer science . Almost ever program is based on some Mathematical Model . To explore the application of Discrete mathematics in computer science let us begin from the evolution of computer languages and how mathematics played important role in the evolution of computer languages .

Programming languages and contribution of Mathematics : An overview

Here, we will not explore the history of programming languages in detail but we will only focus on those parts which are concerned and connected to our topic. Computers are electronic devices which are made of registers ,logics & gates etc. All the electronic devices can only understand the ON and OFF logic. Mathematics fertilized logic with the mathematical logic operations and number system. Despite the complex hardware the computer systems operates on a very rudimentary level .10 symbol number system(0,1,2,…9) is too complicated for the computer system to process. At the logic level a computer can understand only two states i.e. ON logic and OFF logic. The ON state is represented by Binary 1 and OFF state is represented by Binary 0.In modern computers the most basic unit of information is a BIT (0 or 1).A processor reads some sequence of Bits and then Performs some binary operation on them. The information which is processed by processor generates some output. There are lot of abstractions involved the whole process.(abstractions like conversion of user input to binary information, than processing the information in the processor and then again converting the processor’s binary output to human readable format).

All the programming languages which are developed till now are Greatly influenced by Mathematics. we can say that the evolution of computer and programming is made possible only due to Mathematics and Mathematical Logic involved in it . Mathematical logic is a subfield of mathematics with close connections to the foundations of mathematics and theoretical computer Science .each and every assignment statements, subroutines, conditional statements, iteration, etc everything follows some mathematical Logic which is rooted from low level binary logic to high level computational logic.

The history of  Binary number system also known as BASE-2-NUMBER is very interesting and worth reading. evidence proves that binary numbers were used in India prior to around 5th–2nd centuries, more than 1500 years before their discovery in the west. The source of this discovery is a text of music by Pingala named “Chhandahshastra” meaning science of meters. Pingala developed mathematical concepts for describing prosody(poem), and in doing so he presented the first known description of a binary number system. The modern Binary numbers were discovered in the west by German mathematician Gottfried Leibniz in 1695 (Suggested Reading Leibniz G., Explication de l’Arithmétique Binaire, Die Mathematische Schriften, ed. C. Gerhardt, Berlin 1879, vol.7, p.223;). Let’s not Deviate focus from our topic .

In 1940’s with the invention of first electronic computer ,the first recognizable programming languages came into existence which is basically a low level assemble language. The Limited speed and limited memory capacity forced Programmers to write hand tuned assemble language programs. These assembly languages includes are very complex instructions. Even the programming of simple task is difficult and complex in assemble languages. These languages generally have binary information which needs to be converted into hex decimal codes to make it more Human Readable.

Between 1943-1945 Konrad Zuse proposed a programming language Plankalkül which is described for engineering purposes. It was the first high-level non-von Neumann programming language to be designed for a computer, Plankalkül was not published at that time due to the circumstances(2nd world war). In 1948 Zuse published a paper about the Plankalkül in the “Archiv der Mathematik” but still did not attract much feedback (Paper : for a long time to come programming a computer would only be thought of as programming with machine code). Plankalkül has drawn comparisons to APL(name after the book : A Programming Language) and relational algebra. It includes assignment statements, subroutines, conditional statements, iteration, floating point arithmetic, arrays, hierarchical record structures, assertions, exception handling, and other advanced features such as goal-directed execution. Plankalkül used Logical notation which was proposed in Begriffsschrift ( “concept-script”) a book on logic by Gottlob Frege, published in 1879. The Begriffsschrift was arguably the most important publication in logic since Aristotle founded the subject. The work of Plankalkül was influenced by Heinz Rutishauser. Heinz Rutishauser (30 January 1918 in Weinfelden, Switzerland – 10 November 1970 in Zürich) was a Swiss mathematician and a pioneer of modern numerical mathematics and computer science.

Between 1950 to 1957 lot of different programming languages like ARITH-MATIC, MATH-MATIC, MATRIX_MATH, FLOW-MATIC, etc are proposed .( Check the programming language timeline at http://en.wikipedia.org/wiki/Timeline_of_programming_languages)

In 1957 Fortran-I was introduced which is developed by IBM at their campus in south San Jose, California for scientific and engineering applications. In 1954-1955 FORTRAN concept was introduced. The Name FORTRAN is derived from The IBM Mathematical Formula Translating System. It is one of the most popular languages in the area of high-performance computing  and is the language used for programs that benchmark and rank the world’s fastest supercomputers. A significant improvement in programming languages and new programming languages which came overtime put more abstractions on internal design of programming and the mathematics involved in it.

Later in  1957 Noam Chomsky published a book Syntactic Structures  in which he developed the idea that each sentence in a language has two levels of representation — a deep structure and a surface structure. In 1959 Noam Chomsky introduced the mathematical Structure of a Grammar. This mathematical structure seeded all the modern programming languages.

In the summary written by ROBERT W. FLOYD in his paper The Syntax of Programming Languages-A Survey says

The syntactic rules for many programming languages have been expressed by formal grammars, generally variants of phrase-structure grammars. The syntactic analysis essential to translation of programming languages can be done entirely mechanically for such languages. Major problems remain in rendering analyzers efficient in use of space and time and in finding fully satisfactory formal grammars for present and future programming languages. “

References and Suggested Readings :

  1. http://home.ica.net/~roymanju/Binary.htm
  2. http://www.leibniz-translations.com/binary.htm
  3. http://en.wikipedia.org/wiki/Begriffsschrift
  4. http://en.wikipedia.org/wiki/Plankalk%C3%BCl
  5. http://www.zib.de/zuse/Inhalt/Programme/Plankalkuel/Plankalkuel-Report/Plankalkuel-Report.htm
  6. http://en.wikipedia.org/wiki/Heinz_Rutishauser
  7. http://www.jsoftware.com/papers/APL.htm
  8. http://www.win.tue.nl/~mvdbrand/courses/seminar/0809/papers/Floyd.pdf
  9. http://en.wikipedia.org/wiki/Fortran
  10. http://en.wikipedia.org/wiki/Timeline_of_programming_languages
  11. http://www.tutorialsdownload.com/application-of-discrete-mathematics-in-computer-science/
Advertisements

General Tips: How to validate from and to date of jquery datepicker control

I am using Jquery Date picker control and my page has from date and to date. This control already have some generic validations.

Here I am going to one scenarion where it is failing:

Validation statement: From date cannot be greater than to date.

If you select dates from calendar which is popup on focus or click of image, then it is not allowing invalid date. But if you typed in from date to make it greater than todate, it doesn’t validate.

You can validate dates like below:
Declaration of Date picker control


//Date picker
var dates = $("#from, #to").datepicker({
changeMonth: true,
changeYear: true,
numberOfMonths: 1,
dateFormat: "dd-M-yy",
onSelect: function (selectedDate) {
var option = this.id == "from" ? "minDate" : "maxDate",
instance = $(this).data("datepicker"),
date = $.datepicker.parseDate(
instance.settings.dateFormat, //||
// $.datepicker._defaults.dateFormat,
selectedDate, instance.settings);
dates.not(this).datepicker("option", option, date);
}
});

Validation Code (Comparison of dates)


if($('#from').datepicker("getDate")>$('#to').datepicker("getDate")) {
alert("From Date cannot be more than to date.");
return;
}

Process Synchronization (Part 1)

We can divide processes in two Categories

1) Co-operative Processes

2) Independent Processes

Co-operative processes are those where the execution of one process affects or affected by other process and if they are not dependent than they are independent processes.

In this tutorial we will study :-

1) problems

2) Conditions to achieve synchronization

3) Solutions to achieve synchronization (which will cover both wrong & right solutions)

Lets Start with Problems which we faced during implementing  Co-operative processes

Producer- Consumer Problem :

The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer’s job is to generate a piece of data, put it into the buffer and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer) one piece at a time. The problem is to make sure that the producer won’t try to add data into the buffer if it’s full and that the consumer won’t try to remove data from an empty buffer.

Consider the Following Program

Producer Code

Int Count =0;

Void producer(void){

int temp;

While(true){

Produe_item(itemp);

while(count==n);

buffer[in]=temp;

in=(in + 1)mod n ;

count=count+1;

}

}

Consumer Code

void consumer(void){

int itemc;

while(true)

{

while(count==0);

itemc=buffer[out];

out=(out+1)mod n;

count=count-1;

process.item(item c);

}

}

can you find any error in the above programs?

when we see these programs individually than these programs works fine but if both of these programs have to work on same data , same resources than they fail to achieve synchronization  which results in inconsistency , loss of data and sometimes can cause DEADLOCK.

Now before continuing to  the next Topic lets know some important terms

Critical Section :-  The portion of program where shared resource or the shared variables is placed

Non Critical Section :- The portion of program which is independent to respective processes

Race Condition :- The condition in which the output of the process depends on execution sequence of statements

Conditions which are important to achieve Synchronization :

1) Mutual Exclusion :- No two processes may be simultaneously present inside the Critical Section at any point of time.

2) Progress :- No process running outside the critical section should block the other interested processes from entring into critical section when critical section is free.

3) Bounded waiting :- No process should have to wait forever to enter into critical section .i.e. their should  be a bound on getting chance to enter into critical section .

(note : – if any solution which is not following bounded waiting than their is a possibility of starvation.)

4) No assumption related to hardware of the process or speed should be taken .

Continued …