How Flutter and Dart work Together

Tags

, , ,

Beginning Flutter with Dart

Beginning Flutter with Dart

https://leanpub.com/beginningflutterwithdart

How Flutter and Dart work together? We know that Flutter works on the Dart platform, uses Dart programming language, but to understand Widget library, we should know the language basics of Dart.
If we have an introduction to class and object-oriented programming paradigms, in the light of new insights, we can define Flutter more precisely.
Flutter is a tool that builds native cross-platform (here cross-platform means for iOS and Android platforms, both) mobile applications with one programming language Dart and one code-base.
Flutter has its own SDK or Software Development Kit that converts our code to native machine code. SDK also helps us to develop our application more eloquently.
Due to the presence of the SDK Flutter works as a framework or Widget library that produces reusable User Interface or UI that builds different types of blocks, utility functions and packages.
Although Dart is an object-oriented programming language, for Flutter its role is more focused on front-end specific. It means with the help of Dart we will build different types of User Interfaces.
As we progress we will understand this core concepts more and more while building our first Flutter application. Understanding Dart language basic is important as it helps Flutter to build UI as code. Since Flutter is mainly different types of Widget trees, we have to write different types of code in Dart.
The advantage of Flutter is that it provides iOS specific code, as well as Android specific code from a single code-base. When we run a Flutter application on our smartphone, we actually see a bunch of Widgets. From the top to the bottom of the mobile screen Flutter divides its Widgets accordingly.
We may think these Widgets as controls that we create by writing code in Dart. In fact, we do not have to do the low level plumbing each time. Flutter framework and Widget libraries provide us the required assistance.
All we need to do is to memorize common rules of building basic Widgets, and moreover, we need to understand the core Dart language basic like function, class and object-oriented style of programming, different types of parameters and their roles in Flutter Widgets, etc.
As we have said, any Flutter application is a bunch of Widgets, we also mean that what we see on the mobile application is Widget trees. However complex application it appears to be, it is actually a bunch of Widget trees.
Since there is no Visual Editor code assistance, there is no drag-and-drop facility. We have to code the entire application. Although it sounds daunting at the beginning, in reality, it is not. Because Flutter SDK has come up with almost every kind of solutions, we just need to add those functionalities.
We will find different types of buttons, text boxes, text decorations available. The Flutter API comes up with two distinct facilities; one is Utility functions, and the other is Widget libraries. They are written in Dart, and Dart complies every code we write with the help of SDK, and finally we get the native code for iOS and Android.
The iOS platform has different types of buttons, so the Android. Flutter tackles this problem in its own way, it has a custom implementation. Every pixel is drawn on the mobile screen. For that reason, the platform specific limitations are tackled without any hitch.
If we think of a minimal Flutter app, it calls the runApp() function inside the main() function. We could have called the runApp() function with a Widget. Instead we passed a parameter MyFirstApp(), which is a class that extends ‘StatelessWidget’ class (code 1.22).
Now we are going to change the code 1.22 to get an idea of how Flutter can run minimally based only on runApp() function.

import 'package:flutter/material.dart';

void main() {
runApp(
Center(
child: Text(
‘My First Flutter App is running!’,
textDirection: TextDirection.ltr,
),
),
);
}

We have run the Flutter default Center() class constructor inside the runApp() function. It automatically changes the look of the virtual device.
Of course, this is not the way one should build a Flutter app. We will also do not take this way. However, getting an idea of how a Flutter app runs will not hurt the learning process.
The above image gives us another idea of writing our code, which is preferable especially for macOS and Linux users. We can run the virtual device from Android Studio, and after that we can open the same Flutter project using Visual Studio IDE. The virtual device will automatically synchronize with Visual Studio (VS); the advantage of using VS IDE is it gives you chance to ‘hot reload’ property. Each time we change the code, we will just click the ‘hot reload’ button that hangs loosely over the VS IDE. We can immediately see the change on the connected Virtual Device.
Now, we will get back to our old code snippet that gave us an ugly looking text output (Figure 1.9).
We will start building our code from the following code that we had seen in this code snippet:

import 'package:flutter/material.dart';

void main() {
runApp(MyFirstApp());
}

class MyFirstApp extends StatelessWidget {
Widget build(BuildContext context) {
return MaterialApp(home: Text(‘My First Flutter app from scratch…’),
);
}
}

Let us try to understand how our first Flutter Application ‘MyFirstApp’ gives the text output. First of all, it is a generic class that extends another Widget class StatelessWidget(). The ‘material.dart’ file has defined all these in-built classes.
Inside our ‘MyFirstApp’ class we have called a Widget class method build() that passes an object ‘context’ that is an instance of class ‘BuildContext’.
As we have said earlier, in Dart, everything is Widget. For that reason, inside the build() method of Widget class we have returned another Widget ‘MaterialApp()’, which draws everything from the ‘material.dart’ file.
We need to study this part of code more closely to know a few key concepts of Dart language. A function sometimes passes positional argument or parameter; and, sometimes a function passes named argument.
Look at this line of code:

Widget build(BuildContext context)

Here, the ‘context’ object is a positional argument. But the ‘MaterialApp()’ Widget passes named argument, like this:

return MaterialApp(home: Text('My First Flutter app from scratch...'),

We need to understand this key concept, first. After that we will again come back to our Flutter project and keeps on building our first platform independent mobile application using Flutter.

Relation between Flutter and Dart

Tags

, , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

We have found out that Flutter is a framework or tool that we need to create beautiful mobile applications. Flutter is written in Dart programming language. To understand how Flutter works, we need to understand Dart also.
Before digging deep to find out the relation between Flutter and Dart, let us try to understand one key concept of programming. There are two distinct parts of programming. One is abstraction and the other is concretion. We need to convert our abstract ideas into concretion, or a concrete shape or form.
Any mobile application is an abstract idea. We need a tool like Flutter to give it a concrete shape. Take a more real life example. Justice is an abstraction, but law is a tool. When we say that ‘justice is done’, the abstract idea of Justice gets a concrete shape. And it is ‘done’ by using the tool called ‘law’.
We hope that now we get a more clear picture why we need a tool like Flutter. Because we want to convert our abstract idea of making a mobile application we need a tool like Flutter.
While we use Flutter, we will encounter many terms like function, class, constructor, positional parameter, named parameter, object, Widget, etc, etc.
As an absolute beginner if you search the Internet, you will find that before Flutter developers used either Ionic or React Native to build mobile applications. Android developers used Java also. You can use Java to build Android application. Therefore, Flutter is not doing anything new. People used to do that before using other tools. Reading until this point, we may ask, then why we should learn Flutter. We could have learned something else, some other tools. Some other languages.
This question is pertinent to our discussion.
Flutter has some benefits. You enjoy some more privileges not enjoyed by other developers. To use the Flutter tool, you need to learn one programming language – Dart, and Flutter has a single code-base that can be used to build Android and native iOS mobile application.
It is a specialty, special advantage not enjoyed by all who use other tools.
Therefore, as an absolute beginner, you need to remember that Dart is a programming language. And Flutter uses Dart language building mobile applications on top of Dart platform. Flutter has some more components, such as Software Development Kit or SDK, flutter engine, foundation libraries and Widgets that are design specific.
As a programming language, Dart has other functionalities. We can build web or desktop applications with Dart. Feel free to differ, but Dart seems to be a mixture of C and Java. If you have already learned these two languages, Dart will appear to be less daunting. Flutter runs in the Dart virtual machine. Just like we have seen earlier in Java Virtual Machine or JVM.
We do not want to be more specific on Flutter internals, as this book is aimed for the absolute beginners.
To be more specific on how Flutter and Dart work together, we will create another Dart project in our IntelliJ IDEA Community Edition IDE. In that Dart project we will learn Dart simultaneously as we progress with Flutter in a different project. We hope that will make sense.
To create a separate Dart project, we will open our IntelliJ IDE and add the Dart and Flutter plugins first. After that, we will open up our IntelliJ IDE to create a console based Dart application.
As in the above image, we are going to create a Dart Console application. In this command line application sample, we will write different type of Dart code to learn the language basics.
The language basics is enough to give us a brief and primary idea about how Flutter works and builds a mobile application.
We are keeping these two projects separate. For Dart we have a console sample application named ‘beginning_flutter_with_dart’ and for the Flutter project we have ‘my_first_flutter_app’.
We have saved these two separate projects in two separate folders.
When we have created the Dart project, it comes up with two ‘.dart’ files. The ‘main.dart’ is in the ‘bin’ folder, and the ‘beginning_flutter_with_dart.dart’ file is in the ‘lib’ folder.
Like ‘C’, ‘C++’ or ‘Java’, Dart application runs through the ‘main()’ function. Therefore, the ‘main.dart’ file in the ‘bin’ folder is the main file through which our Dart console sample application will run.
What is the role of the ‘lib’ folder? We will place other dart files in the ‘lib’ folder, just like the ‘beginning_flutter_with_dart.dart’ file.
When we open up the ‘beginning_flutter_with_dart.dart’ file, we find a function inside.
// code 1.9
int calculate() {
return 6 * 7;
}

And the ‘main.dart’ file has this code inside:
// code 1.10
import 'package:beginning_flutter_with_dart/beginning_flutter_with_dart.dart'
as beginning_flutter_with_dart;

main(List arguments) {
print(‘Hello world: ${beginning_flutter_with_dart.calculate()}!’);
}

If we run this code we get this output:
//output of code 1.10
Hello world: 42!

If you are an absolute beginner, it really makes no sense. Let us tolerate this for a moment and try to understand what is actually happening.
As a beginner, try to understand programming language from the standpoint of natural language. In a natural language, we start with letters or alphabets. Then we form words by arranging those alphabets. After that we need to learn grammar, which is a set of rules that teaches us to make meaningful sentences. Only after learning to create sentences, we can think of writing a paragraph, an essay, a story, even a novel.
With the help of a programming language we also try to write an application, a software. A natural language works with words, and a programming language deals with data. This Dart console application gives us two types of data. One is ‘String’ data that gives the output: Hello World; and, it also gives us an ‘integer’ data, which gives us an output of 42.
Watch the code 1.9 carefully, it is a function of integer data type, and it has a name ‘calculate()’, and it returns an integer value of multiplication between two numbers 6 and 7. Quite predictably it has returned 42.
Therefore, we have learned one important concept, a function returns a value. If we mention what type of data type it will return, it will return that data type and in the main() function, we can call this function and get the desired output.
However, in the main() function, there are many more things that we should also discuss. If we take a look at the code 1.10, we see that in the ‘main.dart’ file we have imported the ‘beginning_flutter_with_dart.dart’ file from the ‘lib’ folder as a package. When we have created the Dart application, it automatically gives it a name, the same name that we used while creating the console sample application.
Now, inside the print() function, that usually prints an output, Dart uses that name (beginning_flutter_with_dart) and adds a ‘.’ symbol to call the ‘calculate()’ function.
Why this is happening? It is because Dart is an object-oriented programming language, and in Dart treats everything as an object. Through that object Dart calls any function as it has called here.
Now let us change the code 1.10 to this:
// code 1.11
import 'package:beginning_flutter_with_dart/beginning_flutter_with_dart.dart'
as an_object;

main(List arguments) {
print(‘Hello world: ${an_object.calculate()}!’);
}

Simultaneously, we have changed the code 1.9 to this, where we have changed the inside value of calculate() function.
// code 1.12
int calculate() {
return 6 * 12;
}

If we run this program, it works and gives us this output:
//output of code 1.11
Hello world: 72!

We have learned a few important concepts. Dart converts everything into an object. We can call that object by any name. At the time of creation, the object was named ‘beginning_flutter_with_dart’; later we have changed the name to a more generic name, such as ‘an_object’. After changing the name, we have called the same function that was written into the Dart file, inside the ‘lib’ folder.
Can we create another function in the ‘lib’ folder?
Let us try. Creating a new function is very simple process. We will click the second mouse on the ‘lib’ folder in our IntelliJ IDE, it will automatically ask for creating different types of file. We have chosen a Dart file and named it ‘a_new_function’. A new Dart file is generated inside the ‘lib’ folder.
We are trying to add two numbers through that function and returns its value. The code snippet looks like this:
// code 1.13
int addingTwoNumbers(var x, var y){
return x + y;
}

Now we will call this function inside the main() function just like before.
// code 1.14
import 'package:beginning_flutter_with_dart/beginning_flutter_with_dart.dart'
as an_object;
import 'package:beginning_flutter_with_dart/a_new_function.dart'
as a_new_function;

main(List arguments) {
print(‘Hello world: ${an_object.calculate()}!’);
print(‘Adding 10 and 20: ${a_new_function.addingTwoNumbers(10, 20)}’);
}

The output is quite predictable.
//output of code 1.14
Hello world: 72!
Adding 10 and 20: 30

We have passed two variables ‘x’ and ‘y’ as parameters through the function addingTwoNumbers(var x, var y); instead of using the word ‘var’ we could have written ‘int’. Dart is strongly typed programming language, so we can mention what data type we are passing. Otherwise, we can use only ‘var’, that stands for variable, and Dart will automatically infer it as integers; in this case we wanted to return an integer data type.
If you look at the meaning of the word in natural language, the word ‘function’ is used as noun as well as verb. When you use it as noun, one of the meanings tells us something like this: the actions and activities assigned to or required or expected of a person or group. And as a verb, its meaning is quite straight forward: perform as expected when applied.
In the programming paradigm, a function() does not always return something. It could be void. That means it does not return anything. Take a look at the main() function. Before the main() function, have seen any data type like ‘int’ or ‘String’? The main() function always calls other functions and gives us the output.
Can we create a void function and call it inside a main function?
Yes, we can do. Let us add a void function inside the ‘a_new_function.dart’ file and the code 1.13 looks like this:
// code 1.15
int addingTwoNumbers(var x, var y){
return x + y;
}

void doNothing(){
print(‘Do nothing’);
}

Now we can call this void function just like any other regular function, inside the man() function.
// code 1.16
import 'package:beginning_flutter_with_dart/beginning_flutter_with_dart.dart'
as an_object;
import 'package:beginning_flutter_with_dart/a_new_function.dart'
as a_new_function;

main(List arguments) {
print(‘Hello world: ${an_object.calculate()}!’);
print(‘Adding 10 and 20: ${a_new_function.addingTwoNumbers(10, 20)}’);
a_new_function.doNothing();
}

//output
Hello world: 72!
Adding 10 and 20: 30
Do nothing

Since inside the void function we have used a print() function and passed a String object – ‘Do nothing’. We get the same output.
We may ask, what is the function of this functions inside the Flutter project? Do this functions will have to do anything with our first mobile application?
To get that answer, we need to close our Dart project for a time being and move to the Flutter project ‘my_first_flutter_app’. Let us open the Android Studio.
When the Flutter project was created it came with a main() file, just like we have just seen in the Dart project.
The code snippet is quite long, but we want to see the whole code here, because we want to see if we can find something familiar as an absolute beginner. So far, we have learned to create functions, and we have heard that everything in Dart is object, but we still do not understand it very much.
Let us see the whole code snippets, without the comments, first.
// code 1.17
import 'package:flutter/material.dart';

void main() {
runApp(MyApp());
}

class MyApp extends StatelessWidget {
// This widget is the root of your application.
@override
Widget build(BuildContext context) {
return MaterialApp(
title: ‘Flutter Demo’,
theme: ThemeData(

primarySwatch: Colors.blue,

visualDensity: VisualDensity.adaptivePlatformDensity,
),
home: MyHomePage(title: ‘Flutter Demo Home Page’),
);
}
}

class MyHomePage extends StatefulWidget {
MyHomePage({Key key, this.title}) : super(key: key);

final String title;

@override
_MyHomePageState createState() => _MyHomePageState();
}

class _MyHomePageState extends State {
int _counter = 0;

void _incrementCounter() {
setState(() {

_counter++;
});
}

@override
Widget build(BuildContext context) {

return Scaffold(
appBar: AppBar(

title: Text(widget.title),
),
body: Center(

child: Column(

mainAxisAlignment: MainAxisAlignment.center,
children: [
Text(
‘You have pushed the button this many times:’,
),
Text(
‘$_counter’,
style: Theme.of(context).textTheme.headline4,
),
],
),
),
floatingActionButton: FloatingActionButton(
onPressed: _incrementCounter,
tooltip: ‘Increment’,
child: Icon(Icons.add),
),
);
}
}

Watching the above code, we can say that, yes, we have found one familiar thing, a main() function. And the main() function here directly calls a function runApp(); inside that runApp() function, Flutter has passed a parameter MyApp(), which also looks like a function. But it is not a regular function.

Dart and Flutter: how to solve the ‘/dev/kvm permission denied’ issue and launch virtual mobile device

Tags

, , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

Read Discrete Mathematical Algorithm and Data Structure

As a beginning Flutter developer, people often are stuck with one issue. They cannot launch the virtual mobile device while working with Android Studio.

Watch this image first, it will give you an idea.

android studio and virtual device

We want to do something like this. So that every code we write, will reflect on the virtual device. It can be done by going to the ‘AVD manager’ from tools. But sometimes an ugly error pops up its head and tells that ‘/dev/kvm permission denied’.

In Ubuntu 18 or Mac OS, you can give user the permission by issuing this command:

sudo chmod 777 -R /dev/kvm

But it has a drawback. If someone else uses your machine, then the other user also gets the permission.

The best remedy is – give permission to yourself only by the following commands:

sudo apt install qemu-kvm

sudo adduser your-username kvm

sudo chown your-username /dev/kvm

It will solve the issue for ever. Now you can launch any virtual device you want. You can launch the device with your Android Studio, and work with your Visual Studio, just like this:

Visula Studio and virtual mobile device

Visula Studio and virtual mobile device

 

Here is the sample of code that has been reflected on the above virtual mobile device:


import 'package:flutter/material.dart';

/**
 * void main(List args) {  
  runApp(MyApp());  
}
 */
void main(List args) => runApp(MyApp());

class MyApp extends StatelessWidget {

  //void answerQuestion(){
    //print('Question Answered!');
  //}
  
  @override
  Widget build(BuildContext context) {
    // TODO: implement build

    var questions = ['What\'s your favorite music?',
    'What\'s your favorite book?',
    'What\'s your favorite movie?',
    ];

    return MaterialApp(
      home: Scaffold(
        appBar: AppBar(
          title: Text('My First App'),
        ),
        body: Column(children: [
          Text('First Question?'),
          RaisedButton(
            child: Text('Answer 1'),
            onPressed: () => print('Answer 1 chosen!'),
          ),
          RaisedButton(
            child: Text('Answer 2'),
            onPressed: () => print('Answer 2 chosen!'),
          ),
          RaisedButton(
            child: Text('Answer 3'),
            onPressed: () {
              //...
              print('Answer 3 chosen!');
            }, 
          ),
        ]),
      ),
    );
  }
}

How to make permanent Flutter path to create Mobile App in Linux

Tags

, , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

Read Discrete Mathematical Algorithm and Data Structure

You want to build your first mobile application using dart and flutter. You have downloaded flutter latest stable version.

Now you are stuck with one problem, how to make the Flutter path permanent so that you can create flutter app anywhere in your machine and run it.

The best solution is to use your ‘vim’ or ‘nano’ text editor using terminal.

Issue this command to open .bashrc:

vim ~/.bashrc or nano ~/.bashrc

Add the following line at the end of the .bashrc:

# Add flutter to the path

export PATH="$PATH:`pwd`/flutter/bin"

Or, if the above code does not work, change it to:

export PATH=
$PATH:/your-full-path-name-where-you-have-unzipped-flutter/flutter/bin:$PATH

Save and close the file.

Write

echo $PATH

It will test the path.
Now you can run the ‘flutter doctor’ command.

 
ss@ss-H81M-S1:~/Documents/development$ cd flutter/
ss@ss-H81M-S1:~/Documents/development/flutter$ flutter doctor
Doctor summary (to see all details, run flutter doctor -v):
[✓] Flutter (Channel beta, v1.3.8, on Linux, locale en_US.UTF-8)
[✓] Android toolchain - develop for Android devices (Android SDK version 29.0.3)
[✓] Android Studio (version 3.5)
[✓] IntelliJ IDEA Community Edition (version 2019.1)
[✓] IntelliJ IDEA Community Edition (version 2019.3)
[✓] VS Code (version 1.45.1)
[!] Connected device
    ! No devices available

! Doctor found issues in 1 category.
ss@ss-H81M-S1:~/Documents/development/flutter$ 

Now I am going to create a new flutter app:

 
ss@ss-H81M-S1:~/Documents/development/flutter$ flutter create my_app
Creating project my_app...
  my_app/README.md (created)
  my_app/android/gradle/wrapper/gradle-wrapper.properties (created)
  my_app/android/settings.gradle (created)

....
In order to run your application, type:

  $ cd my_app
  $ flutter run

Your application code is in my_app/lib/main.dart.

ss@ss-H81M-S1:~/Documents/development/flutter$ cd my_app/
ss@ss-H81M-S1:~/Documents/development/flutter/my_app$ flutter run
No connected devices.
ss@ss-H81M-S1:~/Documents/development/flutter/my_app$ 

Since I had no connected device at that moment, it could not run. Get a connected device through Android Studio, your first mobile app will start running!

Permutation and combination in Data Structure and Algorithm

Tags

, , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

Let us see some common examples of Combinatorial algorithms. We can think of generating list of all structures of a given type. In this scenario, we can think of permutation with repetition, or without repetition. We can think of combinations with repetition, or without repetition.

Search algorithms are good examples where Optimization and Approximation algorithms are used to solve such problems. Optimization methods or algorithms also include dynamic programming. On the other hand, Approximation methods include greedy algorithms.

We cannot say that one algorithm is the best solution. There could be a better algorithm than the previously claimed ‘best’.

Let us solve a problem and see whether the solution is best or not.

There are five things. We have found out that if there are five things, there could be 120 possibilities. Let us pick any two of them and try to rearrange them in order. However, we cannot repeat the same thing twice. It is a permutation without repetition, still it is little bit different.

If we want to rearrange any two things from that five elements without repetition, what would be the order.



package chapterten;

/**
* permutation is a combination of collections where order matters
* permutation could be with repetition or without
* here we see an example of
* permutations without repetition
* if there are 16 things, and if we choose 14
* then we cannot choose 14 again
* in that case, 15 things remain
* no repetitions and order matters
*/

/**
* Here is our problem:
* what order could 5 balls be in
* for 5 balls the possibility is factorial(5)
* if we take any otwo out of it
* the possibility is factorial(5 - 3)
* but the order of 2 out of 5 balls
* is factorial(5) / factorial(5 - 3)
*/

public class SimplePermutation {

static int permutationWithoutRepetition(int n){
int i = 1;
int k = 1;
while (i <= n){
k *= i;
i++;
}
//we get the factorial of the number we have passed as parameter
return k;
}

public static void main(String[] args) {

/**
* the formula of permutation without repetition
* is factorial(listOfNumbers)/factorial(listOfNumbers - restOfNumbers)
*/
int listOfNumbers = 5;
int restOfNumbers = 3;
System.out.println("The list of numbers are (5, 4, 3, 2, 1)");
System.out.println("Our first choice has 5 possibilities.");
System.out.println("The number of orders 5 numbers could be in: ");
System.out.println(permutationWithoutRepetition(5));
System.out.println("Now we need any two numbers from this collection:");
System.out.println("The order of 2 numbers out of 5 numbers could be: ");
System.out.println(permutationWithoutRepetition(5)/permutationWithoutRepetition(3));

}
}

 

Here is the explanation. When we pick up 2 elements from 5 elements, 3 elements are left behind. The algorithm is quite simple.

First, find out the factorial of 5.
Second, find out the factorial of 3.
Third, divide factorial of 5 by factorial of 3.

We have done the same thing. And here is the output:



The list of numbers are (5, 4, 3, 2, 1)
Our first choice has 5 possibilities.
The number of orders 5 numbers could be in:
120
Now we need any two numbers from this collection:
The order of 2 numbers out of 5 numbers could be:
20

As we have said earlier, there are hundreds of Combinatorial algorithms. Besides more common ‘sorting’ and ‘searching’, we have different types of generating ‘permutations and combinations’, graphs, and many others.

Our next problem will deal with some kind of generating permutation and combination. How many ways we can rearrange a string? If repetition is allowed, it is obvious that number of rearrangement will be more.
How it happens?

A string is a sequence of characters. It is a representation of data structure, an array of characters.

Therefore, it has a length. If repetition is allowed, we can count the length of the string, and safely say that the factorial of that number is the possibility.

But the real trick is in the process of rearrangement.



package chapterten;

/**
* When repetition is allowed, we can rearrange the order
* of a string in various combination
* since we will keep the order with repetitions,
* we can call it a permutation of a string
*/

public class StringPermutation {
// we need a global recursive method
// that will print all the permutations of the string
static void arrangeTheStringWithRepetition(String anyString, String anotherString){

// we need to check if the given string is empty
if (anyString.length() == 0) {
System.out.print(anotherString + " ");
return;
}

for (int i = 0; i < anyString.length(); i++) {

// reaching to the last character
char ch = anyString.charAt(i);

// we can display the rest of the character after
// excluding the last character
String restOfTheString = anyString.substring(0, i) +
anyString.substring(i + 1);

// calling the method recursively
arrangeTheStringWithRepetition(restOfTheString, anotherString + ch);
}
}

public static void main(String[] args) {

String stringToArrange = "abcd";
// the given string 'abcd' is of length 4
// factors of 4 is 4,3,2,1
// factorial is 24
// the program will rearrange the string 24 times
arrangeTheStringWithRepetition(stringToArrange, " ");
System.out.println();

}

}

// output

abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba

In the above code snippet, the string is of length 4.

Therefore, factorial of 4, that is 24 is the number of possibility. The above program rearranges the string 24 ways. However, the condition was repetition was allowed.

 

Combinatorial Algorithm

Tags

, , , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

The area of mathematics in which counting is the primarily concern, it is known as Combinatorics. Besides other subjects like statistical physics, it has many applications in Computer Science.
The counting capabilities and other abstractions of Combinatorics is implemented in different ways (algorithm) to obtain results. In like manner, it also studies certain properties of finite structures, like data structures in Computer science.
Primarily, any data structure is related to the abstractions of any finite sets. We can apply different types of permutations on finite sets and that study also plays an important role in the fields of Combinatorics.
We can assume that when different types of permutations are required for data structures, different types of algorithms can also be emerged out from there.
For a single problem where enumeration or counting is required, there can be different types of algorithms. We can approach the problems whatever way. Regardless of how we solve the problems, different algorithms emerge from it.
Furthermore, to know how Combinatorics is associated with data structures and algorithm, we need to know the basic operations that are acted upon on the data structures with the help of different types of algorithms.
Be that as it may, but we cannot ignore these facts.
We have already found that enumeration of a specified data structure is a part of Combinatorics. Arrangements of a certain data structure is also a part of it. We can restructure or rearrange any ‘string’ value and place the characters in different combinations.
We can check whether a data structure fulfils a certain criteria. If there are several possibilities, we can also check, with the help of algorithms, what is the best structure or solution.
We have just learned that study of Combinatorics deals with different types of permutations on finite sets or data structures.
Therefore, to understand the key abstractions of Combinatorics we need to understand what permutations and combinations are.

Permutation and Combination

When we use the word ‘combination’, we forget whether ‘order’ is important or not. We also leave behind another key concept, ‘repetition’. When repetition is allowed, the number of combinations increase. When it is not allowed, the number of combination or, in other words, the number of rearrangement reduces.
Consider an example that will make it clear.
Take a word ‘forget’. If we go to any thesaurus and try to find what kind of word is it, we find several other words that are close to its meaning.
They are: overlook, drop, neglect, omit, leave out, etc. We can rearrange these group of words in many ways where order is not maintained. When we do not care what order the words are in, we say it a ‘combination’ of words.
However, when we apply the alphabetical order and rearrange the group of words again, then it comes out like this: drop, neglect, omit, overlook, leave out, etc. When order matters in a combination, it is called permutation.
Think about a combination lock. We can choose any three numbers from 0 to 10. If in our case, the combination works in this arrangement ‘562’, we can say that repetition is not allowed in this permutation. If it was like ‘223’, we could have said that repetition is allowed in this permutation.
Take a close look, we will find that any permutation where repetition is allowed, the number of possibilities is nothing but factorial of that number of things that are to be rearranged.
Consider any three things. How many ways we can rearrange them? Finding it is very easy.


3 * 2 * 1 = 6

There are 6 ways we can rearrange three elements. If there were 4 elements, the factorial of 4, that is, in 24 ways we could have rearranged those 4 things.
Enough theory; let us dive into our first code where we will find the best algorithm to solve the above problem.



package chapterten;

/**
 * permutation is a combination of collections where order matters
 * permutation could be with repetition or without
 * here we see an example of
 * permutations without repetition
 * if there are 16 things, and if we choose 14
 * then we cannot choose 14 again
 * in that case, 15 things remain
 * no repetitions and order matters
 */

/**
 * Here is our problem:
 * what order could 5 balls be in
 * for 5 balls the possibility is factorial(5)
 * if we take any otwo out of it
 * the possibility is factorial(5 - 3)
 * but the order of 2 out of 5 balls
 * is factorial(5) / factorial(5 - 3)
 */

public class SimplePermutation {

    static int permutationWithoutRepetition(int n){
        int i = 1;
        int k = 1;
        while (i <= n){
            k *= i;
            i++;
        }
        //we get the factorial of the number we have passed as parameter
        return k;
    }

    public static void main(String[] args) {

        /**
         * the formula of permutation without repetition
         * is factorial(listOfNumbers)/factorial(listOfNumbers - restOfNumbers)
          */
        int listOfNumbers = 5;
        int restOfNumbers = 3;
        System.out.println("The list of numbers are (5, 4, 3, 2, 1)");
        System.out.println("Our first choice has 5 possibilities.");
        System.out.println("The number of orders 5 numbers could be in: ");
        System.out.println(permutationWithoutRepetition(5));
    }
}

The output is quite expected. When 5 things are to be rearranged, there are 120 possibilities, which is actually the factorial of 5.



The list of numbers are (5, 4, 3, 2, 1)
Our first choice has 5 possibilities.
The number of orders 5 numbers could be in: 
120

What we have seen, is a tip of iceberg. In reality, there are hundreds of Combinatorial algorithms that deal with different types of data structures based on finite sets. We can include even structures that are built from graphs.

Time Complexity and Big O Notation

Tags

, , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

What is time complexity and Big O notation. In this article, we will have a very brief look at this concept.
We have already seen many examples of different kind of data structures and algorithms. We have also found out that to implement such algorithms, we do not have to go through low-level plumbing. Any stable good programming language provides many libraries to avoid such low-level plumbing and different types of algorithms, such as sorting, shuffling, or searching can be done through them.
We have also found out another important fact that tells us about the relationship between algorithms and discrete mathematics. Data structures are discrete structures and hence, the algorithms are all about discrete structures.
Let us consider a simple Java program, where we iterate over two loops at the same time. These outer and inner loops are connected with each other and they finally give us an output.

package fun.sanjibsinha;

public class Main {

static int i, j, totalOne, totalTwo;

public static void main(String[] args) {

for (i = 0; i <= 5; i++){
totalOne += i;
System.out.print("i = " + i);
System.out.println("--------");
for (j = 0; j <= 5; j++){
totalTwo += j;
System.out.println("j = " + j);
}
}
System.out.println("The total of outer loop: " + totalOne);
System.out.println("The total of inner loop: " + totalTwo);
}
}

And from this very simple program, we get an output like the following:

//output of 8.1
i = 0--------
j = 0
j = 1
j = 2
j = 3
j = 4
j = 5
i = 1--------
j = 0
j = 1
j = 2
j = 3
j = 4
j = 5
i = 2--------
j = 0
j = 1
j = 2
j = 3
j = 4
j = 5
i = 3--------
j = 0
j = 1
j = 2
j = 3
j = 4
j = 5
i = 4--------
j = 0
j = 1
j = 2
j = 3
j = 4
j = 5
i = 5--------
j = 0
j = 1
j = 2
j = 3
j = 4
j = 5
The total of outer loop: 15
The total of inner loop: 90

You have probably noticed that it is a simple algorithm of finding the total of inner loop and the outer loop. However, to do that, we need to jump sequentially; each iteration has taken place within a space of discrete data structure.
Any problem has one or more possible solutions. Suppose, we were asked to find the total of the one loop only; we should change the above code to the following code:


package fun.sanjibsinha;

public class Main {

static int i, j, totalOne, totalTwo;

public static void main(String[] args) {

for (i = 0; i <= 5; i++){
totalOne += i;
System.out.print("i = " + i);
System.out.println("--------");
/*
for (j = 0; j <= 5; j++){
totalTwo += j;
System.out.println("j = " + j + ", ");
}
*/
}
System.out.println("The total of loop: " + totalOne);
// System.out.println("The total of outer loop: " + totalTwo);
}
}

Now, in the changed circumstance, we will come up with this output:

//output of 8.2
i = 0--------
i = 1--------
i = 2--------
i = 3--------
i = 4--------
i = 5--------
The total of loop: 15

Now we can also solve this problem another way. By calling the function recursively, we can also solve the same problem. Our problem was, how we could get the total of a series of positive integers that starts from 0 and ends at 5.

It looks like this: total = 0 + 1 + 2 + 3 + 4 + 5; here the end point was chosen as 5. The value of total is 15.

We could have taken the user input and get the total of any big positive integer. Manually it is easy to get the total of a small series. But consider a case, where user gives us an input like 10 to the 6. Now, manually it is not possible to add all the numbers from 0 to that number. It becomes cumbersome.
Therefore our first algorithm was based on using looping. It easily adds all the numbers, whatever be the end number.
As we have said, any problem might have one or more solutions. Here we can solve the same problem, recursive way.

package fun.sanjibsinha;

public class Main {

static int total;

static int getTotal(int i){
if (i != 0){
total = i + getTotal(i - 1);
return total;
} else {
return 0;
}
}

public static void main(String[] args) {

System.out.println("Total : " + getTotal(5));

}
}

And we get the same output:


Total : 15

In the above case, the same jumping of iteration occurs through a discrete structure, but in a different way. It starts from a discrete positive integer 5, and the addition process goes on until we reach the base number by calling the function recursively.
Now we have found that this problem has two solutions. Question is which is desirable? Which algorithm is better than the other?
Here comes the question of time complexity. Time-Complexity has nothing to do with the execution time. But it has many things to do with the algorithm. Time-Complexity talks all about the better algorithm. A better algorithm always takes less time to reach the desirable discrete element (here output of a total).
Here we have to iterate over a series of positive integers, to reach our desirable goal. If we could have reached in one iteration, that would be the best algorithm, no doubt. But it is Utopian.
On the contrary, the worst case will take us to an iteration, that has to traverse each element for an indefinite period of time. In like manner, you may imagine a situation where user gives an input to find whether the integer is prime or not. There are several algorithms to test a number whether it is prime or not. Although there will be one algorithm that is better than other, and takes less time to give you the output. It depends entirely on the size of the input. For a real big integer, one algorithm might take several minutes to complete the operation and for another algorithm, it finishes the operation in a few seconds.
Before trying to understand Time-Complexity, we should remember that actual time requires to execute code is machine dependent; another key thing is network load. But the Time-Complexity has nothing to do with your machine configuration. It is all about better algorithm. That is why, whenever the terms data structures and algorithms appear, time-complexity comes with them.
In this chapter, we will try to understand how time-complexity works. What does the term Big O notation stand for? But before that, we need to understand what does ‘order of n’ mean?

Order of n, or O(n)

Let us implement an algorithm that will check whether the number or ‘n’ is prime or not. We know that a prime number is divided by only two numbers, 1 and the number itself and it has no remainder. Consider a prime number 11, it has only two factors 1, and 11. If we divide 11 by 1 and 11, we have no remainders. That is the most basic definition.
Therefore, using a normal looping construct, we can try to check whether that number is prime or not. We can write our algorithm in natural language, this way:

for each number where integer i starts from 2 to (n - 1)
if n % i == 0, then n is not prime
else n is prime

We can test this algorithm by using a small positive integer like 11. In that case, if we iterate from 2 to (11 – 1), we will see that between 2 to 10, there is no integer that can divide 11 with no remainder. Therefore, 11 is prime. When the value of n is small, our algorithm does not take much time. In fact, that time may appear negligible. Suppose for each iteration, it takes one millisecond or ms. This fraction of second stands for 10 to the power minus 3, that is, if you divide 1 second by 1000, then you get one millisecond.

By the way, as a student of computer science student we should know that one microsecond is 10 to the power minus 6, one nanosecond is 10 to the power of minus 9 and one picosecond is 10 to the power minus 12.
Now, let us assume that each iteration takes one microsecond. When the number of iteration is small, it does take mush time. However, with the increase of iteration, this time also increases. Instead of 11, we want to check a value like 1000003, it will iterate more than one million times. Now our algorithm appears to crumble. Because our algorithm will take huge time to finish the process of iteration.
We can transport this natural language algorithm to a Java code.

package fun.sanjibsinha.timecomplexity;

import java.util.Scanner;

public class TimeOne {

static long userInput;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a positive integer to test prime or not: ");
userInput = sc.nextInt();

for (long i = 2; i < (userInput - 1); i++){
if (userInput % i == 0){
System.out.println(userInput + " is not prime.");
} else {
System.out.println(userInput + " is prime.");
}
}
}
}

We are not going to run this code; it is just for an example of time-complexity. In the above code you can guess that to reach our goal we need to iterate ‘n’ number of times. Here ‘n’ is user’s input. It is called ‘order of n’ or O(n). As the value of ‘n’ starts increasing, our algorithm starts crumbling. For a value like 10 to power 6 plus 3, it takes huge to time and it simply goes out of our hands.
Therefore, we have to search for a better algorithm to solve the same problem.
Let us take the user’s input and instead of iterating over the whole range of that number, we can calculate the square root of that user’s input. After that we can iterate up to that value.
It serves our purpose, and at the same time, shortens the length of iteration in a great way. Let us write the code in Java.

package fun.sanjibsinha.timecomplexity;

import java.util.Scanner;

public class TimeTwo {
static double userInput;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter a positive integer to test prime or not: ");
userInput = sc.nextInt();

// 10 to the power 6 + 3 = 1000003
for (long i = 2; i < (Math.sqrt(userInput)); i++){
if (userInput % i == 0){
System.out.println(userInput + " is not prime.");
} else {
System.out.println(userInput + " is prime.");
}
}
}

}

If we have a user’s input like 1000003, our algorithm allows us not to iterate more than 1 million times. On the contrary, it allows us to iterate in and around 1000 times.
We write another short Java code to find the square root of any number.


package fun.sanjibsinha.timecomplexity;

public class TestClass {

public static void main(String[] args) {

System.out.println(Math.sqrt(1000003));
//1000.001499998875
}
}

//output of 8.6

Square root of 10 to the power of 6 plus 3 is: 1000.001499998875

In the above code we can clearly see that the square root of 1000003
Let us go back to the code 8.5, where we have successfully shortened the length of iteration by calculating the square root of user’s input. Reducing the length of iteration means the algorithm takes much less time. Now the running time of our code is not ‘order of m’, but ‘order of square root of n’; it means O(square root of n).
It is quite evident that code 8.5 represents much better algorithm than code 8.4 to solve the same problem. Why so? Because, it solves the large test cases in acceptable time. Better algorithm is necessary for better performance.
Here the running time of the program depends on the user’s input; and, user’s input represents the growth of time which exerts influence on the running time.
As a conclusion to this section, we can say that time-complexity only cares about the ‘input’. It also cares about the algorithm that tackles the ‘input’ in a better way.
Moreover, time-complexity does not care about the machine’s hardware configuration. Whether the machine is single processor or multi processor does not matter. What is the network load, is unimportant. The time-complexity really does not care about 32 bit or 64 bit.
Input is the key word for time-complexity. Nothing else.
In the above examples, we have inputs like single integer. It could have been an array, a data structure; is not it? Now, again, we come to the point of the data structures, and algorithms. And, of course, now we also understand how time-complexity is related to them.

Big O Notation

We have already seen how through order of ‘n’, or ‘input’, we can represent any algorithm. Consider the code 8.4, where we have to iterate over one million times if ‘n’ is 1000003. Therefore, the O(n) is the worst case scenario. Any algorithm could not be worse than that O(n).
Big O notation is the most convenient way to express the worst-case scenario for an algorithm. Compare code 8.5 with the previous code 8.4. In code 8.5, the Big O notation is like this: O(square root of n). This algorithm could not be worse than anything. Now, comparing these two worst case scenarios, we can safely tell that the algorithm of code 8.5 is better than code 8.4.
If you are still confused with the definition, do not worry. Everything takes time. The concept of time-complexity is related to algorithm. More you practice, you will be able to get your head around this topic.
Let us try call back the second code snippet of this chapter. The code 8.2 looks like this:

package fun.sanjibsinha;

public class Main {
public static void main(String[] args) {
int totalOne = 0;
for (i = 0; i <= 5; i++){
totalOne += i;
}
System.out.println("The total of loop: " + totalOne);
}
}

For brevity we have trimmed the code omitting the commented parts. When we have declared the variable ‘totalOne’ to 0, the constant is 1 and the time is also 1.
In the next step, the first line of the ‘for loop’ tells us about two things. First, the constant is more than one, and the same rule applies for the time.
In the next line the algorithm keeps adding the value of iteration for ‘n’ number of times. Therefore, we have two constants, but the time equals ‘n’.
The last line gives us the output. The constant is 1, and the time is also 1.
When we add them up, we get O(n). It happens so, because while summing it up, we remove all the constants.
However, for the code 5.1, where we have used nested loop to get the total of inner loop, this order of ‘n’ changes to (n * n), that is n squared. Therefore, the Big O notation or the worst case scenario of that algorithm is O(n^2). Although in that code, we have total of the outer loop also. That means, we have O(n) at the same breath. Since there are consecutive statements, we count the statement with maximum complexity, that is O(n^2).
We have got an initial idea of how Big O notation works, and what principles govern it. Many common algorithms we use very often, use the above Big O notation O(n^2). Common algorithms, such as bubble sort, selection sort and insertion sort takes the above Big O notation.
There are many other Big O notations that are related to different types of algorithms. The idea of time-complexity rests on finding the better algorithm to solve a problem. We should analyse the Big O notations, or worst-case scenarios for the test cases and we will try to find the best solution.

Comparator, Comparable, and Iterator, how three interfaces in Java Collection Framework work

Tags

, , , , , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

Java Collection framework provides three major interfaces, which have all the qualities of being important and worthy of note. Comparison plays a great role in sorting or shuffling algorithm. In the like manner, iteration is also very important.
We are going to see a few code snippets where these three interfaces ( Comparator, Comparable and Iterator ) are implemented.
To get elements in sorted order, we can use TreeSet and TreeMap from Java Collection Framework; but, it is the Comparator or the Comparable interface that precisely defines what sorted order means.
Implementing the Comparator and Comparable interfaces, we can have objects that encapsulate ordering. Watch the next code snippet:

package fun.sanjibsinha.chapter7.collection;

/**
* How Comparator and Comparable interfaces are implemented by a class
* to sort String and Integer data types provided by List and
* ArrayList data structures
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Account implements Comparator<Account>, Comparable<Account> {

private String accountHoldersName;
private int accountNumber;

Account() {
}

Account(String name, int number) {
accountHoldersName = name;
accountNumber = number;
}

public void setAccountHoldersName(String accountHoldersName) {
this.accountHoldersName = accountHoldersName;
}

public String getAccountHoldersName() {
return accountHoldersName;
}

public void setAccountNumber(int accountNumber) {
this.accountNumber = accountNumber;
}

public int getAccountNumber() {
return accountNumber;
}

/**
* overriding the compareTo() method to sort the name
* @param account
* @return
*/
public int compareTo(Account account) {
return (this.accountHoldersName).compareTo(account.accountHoldersName);
}

/**
* overriding the compare() method to sort the account number
* @param account
* @param anotherAccount
* @return
*/
public int compare(Account account, Account anotherAccount) {
return account.accountNumber - anotherAccount.accountNumber;
}
}

public class ComparatorInterfaceExample {

public static void main(String[] args) {

// list of account object
List<Account> listOfAccounts = new ArrayList<Account>();

listOfAccounts.add(new Account("Sanjib", 203));
listOfAccounts.add(new Account("Json", 205));
listOfAccounts.add(new Account("John", 201));
listOfAccounts.add(new Account("Hicky", 204));
listOfAccounts.add(new Account("Amubrata", 202));

// sorting the ArrayList
Collections.sort(listOfAccounts);

/**
* printing the sorted names
*/
System.out.println("Printing the sorted names of account holders: ");
for(Account account: listOfAccounts){
System.out.print(account.getAccountHoldersName() + ", ");
}

/**
* sorting the ArrayList with the help of comparator
*/
Collections.sort(listOfAccounts, new Account());
System.out.println(" ");

/**
* sorting based on account numbers
*/
System.out.println("Printing the names of account holders based on sorted account" +
" numbers in ascending numbers: ");
for(Account account: listOfAccounts)
System.out.print(account.getAccountHoldersName() + " : "
+ account.getAccountNumber() + ", ");
}
}

First of all, we have sorted the names of the account holders; in similar fashion, we have printed the names of account holders based on sorted account numbers in ascending numbers.

Printing the sorted names of account holders:
Amubrata, Hicky, John, Json, Sanjib,
Printing the names of account holders based on sorted account numbers in ascending numbers:
John : 201, Amubrata : 202, Sanjib : 203, Hicky : 204, Json : 205,
Process finished with exit code 0

What will happen if inadvertently someone adds a negative account number? Therefore, for the second part of the code where we have implemented Comparator interface method compare(), we should write the logic in this way.

public int compare(Account account, Account anotherAccount) {
/**
* Don't do it unless you're absolutely
* sure no one will ever have a negative account number!
*/
//return account.accountNumber - anotherAccount.accountNumber;
/**
* this is more logical approach
*/
return (account.accountNumber < anotherAccount.accountNumber ? -1 :
(account.accountNumber == anotherAccount.accountNumber ? 0 : 1));
}

Printing the sorted names of account holders:
Amubrata, Hicky, John, Json, Sanjib,
Printing the names of account holders based on sorted account numbers in ascending numbers:
John : 201, Amubrata : 202, Sanjib : 203, Hicky : 204, Json : 205,
Process finished with exit code 0

Now, our code is more protected. Why we need to take such protections? It is little bit theoretical and this book is not about only Java Collection Framework. Yet, it is good to know that if an integer is a large positive integer and another integer is a large negative integer, then their subtraction will return a negative integer. To represent the difference of two arbitrary signed integers, a signed integer type is not big enough.
When we implement Comparable or Comparator interfaces, we need to maintain the technical restrictions.
If we want to compare two elements, especially for that type of algorithm, implementing the Comparable interface is always the better choice.

package fun.sanjibsinha.chapter7.collection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class City implements Comparable<City>{

private String name;

City(String name){
if (name == null){
throw new NullPointerException();
}
this.name = name;
}

public String displayName(){
return name;
}

public String toString(){
return name;
}

@Override
public int compareTo(City city) {
int lastCompare = name.compareTo(city.name);
return (lastCompare != 0 ? lastCompare : name.compareTo(city.name));
}
}

public class ComparableInterfaceExample {

public static void main(String[] args) {

City cityNames[] = {
new City("Berlin"),
new City("Kolkata"),
new City("Munich"),
new City("Paris"),
new City("Mew York"),
};

List<City> names = Arrays.asList(cityNames);

Collections.sort(names);

System.out.println("The city names in ascending order: ");

System.out.println(names.toString());

}
}

We can get the city names in ascending order. For the algorithm that is related to sorting and comparing, it is a good choice in Java Collection framework.

The city names in ascending order:
[Berlin, Kolkata, Mew York, Munich, Paris]

Process finished with exit code 0

Finally we will curtain the Java Collection framework with iteration. It is also a very important part of algorithm and data structure. Java Collection framework handles it quite well by implementing the Iterator interface.

package fun.sanjibsinha.chapter7.collection;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;

/**
* An Iterator is an object that enables you to traverse through a collection
* public interface Iterator<E> {
* boolean hasNext();
* E next();
* void remove(); //optional
* }
* An Iterator object implements either Iterator, or ListIterator interface
*/

public class IteratorInterfaceExample {

public static void main(String[] args) {

/**
* creating an ArrayList that will use iterator object
*/

ArrayList arrayList = new ArrayList();

/**
* adding some city names to the array list
*/
arrayList.add("Calcutta");
arrayList.add("Allahabad");
arrayList.add("Edinburgh");
arrayList.add("Berlin");
arrayList.add("Detroit");
arrayList.add("Fujiyama");

/**
* we can use iterator to display all the city names now
*/

System.out.print("The city names as entered in the list : ");
Iterator itratorObject = arrayList.iterator();

while(itratorObject.hasNext()) {
Object element = itratorObject.next();
System.out.print(element + ", ");
}
System.out.println();

/**
* ListIterator object can implement the ListIterator interface
*/
ListIterator listIterator = arrayList.listIterator();

System.out.print("Now we can cycle through the city names forward through listIterator : ");
System.out.println();
while(listIterator.hasNext()) {
Object element = listIterator.next();
listIterator.set(element);
System.out.println(element);
}

System.out.print("Now we can cycle through the city names forward through iterator : ");
itratorObject = arrayList.iterator();

while(itratorObject.hasNext()) {
Object element = itratorObject.next();
System.out.print(element + ", ");
}
System.out.println();

System.out.print("Now we can cycle through the city names forward through listIterator : ");

while(listIterator.hasPrevious()) {
Object element = listIterator.previous();
System.out.print(element + ", ");
}
System.out.println();
}
}

To traverse through a collection of elements, we need iteration; and, to do that we need an iterator object that implements the Iterator interface.


The city names as entered in the list : Calcutta, Allahabad, Edinburgh, Berlin, Detroit, Fujiyama,

Now we can cycle through the city names forward through listIterator :
Calcutta
Allahabad
Edinburgh
Berlin
Detroit
Fujiyama

Now we can cycle through the city names forward through iterator : Calcutta, Allahabad, Edinburgh, Berlin, Detroit, Fujiyama,
Now we can cycle through the city names forward through listIterator : Fujiyama, Detroit, Berlin, Edinburgh, Allahabad, Calcutta,

Process finished with exit code 0

When we want to iterate through the elements in a collection, and display each element, the easiest way is shown above. Employing an iterator object is the best solution to such algorithmic problems. The iterator object either implements the Iterator interface, or implements ListIterator interface.

Recursive or iterative, which algorithm is better

Tags

, , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

The advantage of using recursion is its shortness, cleanliness, and moreover, it is closer to our discrete mathematical definitions. If you think and model your code keeping the mathematical conceptions in your mind, then recursion is close to your definition.
It is more evident when we use recursion in finding the Fibonacci series. Mathematically, the Fibonacci is defined as the following:

Fibonacci of 1 or 2 is 1
Fibonacci of F (for F > 2) is Fibonacci of (F - 1) + Fibonacci of (F – 2)

If we want to find the Fibonacci series using recursion, it is not only the simplest version, but also mathematically similar.
Watch the next line of code snippet.

package fun.sanjibsinha.recursive;

public class AlgoFibTwo {

static int getFibonacci(int f) {
if ((f == 1) || (f == 2)){
return 1;
} else {
return (getFibonacci(f - 1) + getFibonacci(f - 2));
}
}

public static void main(String[] args) {

int newNumber = 6, result;
result = getFibonacci(newNumber);
System.out.printf("Fibonacci series of " + newNumber + " = " + result);
System.out.printf("");
System.out.printf("");
}

}

//output of the above code

Fibonacci series of 6 = 8

We can do the same thing using iterative way, but it does not reflect the mathematical conception as the recursion does. The next code snippet shows us the same thing.

package fun.sanjibsinha.recursive;

public class AlgoFibOne {

static int getFibinacci(int f) {
int k1, k2, k3;
k1 = k2 = k3 = 1;
for (int j = 3; j <= f; j++) {
k3 = k1 + k2;
k1 = k2;
k2 = k3;
}
return k3;
}

public static void main(String[] args) {

int newNumber = 6, result;
result = getFibinacci(newNumber);
System.out.printf("Fibonacci series of " + newNumber + " = " + result);
System.out.printf("");
System.out.printf("");
}
}

//output of the above code
Fibonacci series of 6 = 8

Ability to simulate the mathematical models cannot always give the moral support to the recursions. Because there are many other factors while we program, we need to keep them in our mind.
Maintaining that the recursive versions are slower than the iterative versions, we may still want to adopt it for some reasons. When the code is heavy in iterative versions, it is much simpler to adopt the recursions, it also easier to debug and maintain. Whatever our reasons to adopt the recursions, slowing down the program may cost at the end.
We cannot save the memory space, we cannot speed up the execution; yet, in some cases, recursions are essential.

As we progress, we will find that later.

What is Algorithm?

Tags

, , , , , ,

discrete-mathematical-algorithm-data-structures

discrete-mathematical-algorithm-data-structures

https://leanpub.com/discretemathematicalalgorithmanddatastructures

Algorithm is expressed as a set of steps. By describing the actions at each step we instruct the computer do something. Usually we can use any natural language to describe the actions to perform at each step.

Consider this simple description.

  • 1. Enter one integer
    2. Enter another integer
    3. Compare both integers and return the maximum value
    4. Compare both integers and return the minimum value

In C++ programming language, on one hand, we can create generic functions to find the maximum or minimum value; and, on the other, we can take help from the ‘algorithm’ template library to find the same values.

Every high level language comes with its own algorithm library. They do so for one reason. Any system of counting or calculation by means of a device like computer involves following a steps or directions. Computer scientists use the word ‘algorithm’ to describe such as ‘set of directions’.

In some cases, these directions could be simple as described above. In most cases, it is much more complex. For complex cases, we need the help of ‘algorithm’ library. Otherwise, we have to do the low-level plumbing, which is much more time consuming and that takes us away from building other important parts of any application.

Historically, the derivation of this word has some interesting facts. At the beginning of ninth century an Arabian mathematician wrote a book called ‘Kitab al jabr w’al muqabala’ (Rules of Restoration and Reduction). The word ‘algebra’ comes from the title of the book. This textbook introduced the use of Hindu numerals and included a systematic discussion of fundamental operations on integers.

The word ‘algorithm’ comes from the name of the mathematician, Abu Ja’far Mohammed ibn Musa al-Khowarizmi.

One of the most famous and well known algorithms is of course Euclid’s Algorithm. It is a process for calculating the greatest common divisor (GCD) of two integers.
We can illustrate this algorithm in the following way.

  • 1. Take two integers x and y
    2. Divide y by x and get the remainder as r
    3. Now replace the value of x with the value of r and replace the value of y with the value of x
    4. Again divide y by x
    5. This process will continue until we get r = 0
    6. Once we get r = 0, stop the calculation, x is the GCD

Notice that the algorithm is expressed as a set of steps. Each step describes some action to take. The important thing is to describe the actions to be performed clearly and unambiguously.

Let us summarize this introductory part on algorithm in one sentence.
Data go inside the computer as inputs, algorithm takes charge, processing the data and after that the data as outputs come out.

By the way, people often mistake the word ‘data’ as singular; but, it is actually a plural form of the Latin word ‘datum’. Since we have used this word too often in our discourse, and will use in future, therefore, for the curious readers I opened up the Oxford dictionary and searched for the word: datum.

Oxford dictionary defines datum as “A thing given or granted; a thing known or assumed as a fact, and made the basis of reasoning or calculation; a fixed starting-point for a series of measurements etc.” It has also made it clear that the plural form of ‘datum’ is ‘data’.

For instance, in Java we have Collection class and in C++ we have containers that manage this data structure part. We are going to find out how they are related in the next post.