Good (Morning | Afternoon | Evening)!
Here, I share my journey / explorations in computer science. I will document various “Ooo!” and “Ahh!” moments as I discover new tidbits of information. I look forward to this being interactive on both ends so that we can learn more together!
I hope you enjoyed figuring out the finite automaton (FA) from last time!
I’m sure you have figured out that this FA accepts strings of a’s with an odd number of a’s. Let us walk through the steps this FA takes when processing the string aaa.
Start at state q0
See ‘a’, go to state q1
See ‘a’, go back to state q0
See ‘a’, go to state q1
We stopped on state q1, which is an “accept state”, therefore, we will accept the string aaa.
Today, we will look at the formal definition of a FA. And, drumroll, …
(Q, Σ, δ, q0, F)
This is quite an impressive statement! This one line defines a FA … almost! We just have to fill in the spaces. In defining our FA, we will use set notation using curly braces. For example, the set comprised of an a, b, and c is {a, b, c}. Now, for our FA definition:
Q – Set of all states in this FA, for our example, it is {q0, q1}.
Σ – The alphabet – a set of all symbols this FA will process, which is just {a}.
δ – The transition function, which describes where to go, given current state and input symbol. We can define ours with two equations:
δ(q0,a) = q1
δ(q1,a) = q0
q0 – Start state, q0
F – Set of accept states or “final” states, {q1}
Let us name our FA “M”, and putting all the parts together, we have:
M = ({q0, q1}, {a}, δ, q0, {q1})
Where δ can be described with:
δ(q0,a) = q1
δ(q1,a) = q0
Or you can say,
δ(qi, a) = qj, where j = 1 if i = 0 and j = 0 if i = 1.
Now that we know what a FA is and how to define one, we can start making some interesting ones. More FA to come next time!
One of the building blocks mentioned last time was math. Actually, computation is, by nature, mathematical. A smart way of creating your programs is to first look into mathematical issues involved. For example will your program deal with graphs, trees, combinations, permutations, sorts, etc.? Looking into these domains will reveal incredible algorithms and solutions.
Today, I will introduce finite automata (FA). In further posts, we will build on the idea of FA but for now I will suffice in communicating the basic gist. FA is a very simple model of computation, but even so, many problems can be solved by writing programs based on FA. Also, if you have written a program based on your FA, chances that the program will work as expected are much higher because its correctness can be mathematically proven!
We can think of a FA as a machine that takes a string of characters as input, but it will only accept strings of a specific form. Such a program would be useful, for example, on a webpage form which asks for your email. In other words, the webpage should reject strings that do not follow some name@domain.com format. Most of you should be thinking “regular expressions” by now. We will get to this!
The FA works by processing each character in the string, one by one. When it is finished, it will tell you if the string is accepted. In order to accomplish this task, it needs to track some sort of state, and it needs a way to get to different states. Finally, it will need to know when it finishes in some “acceptable” state.
The “pseudo”-FA pictured at the beginning of this post models a light switch. The arrow that points to the “OFF” state indicates that we start in the “OFF” state. The other arrows show what state to go to based on what action is taken. When we hit the light “SWITCH”, the light goes into the “ON” state. If the light is “ON” and we hit the “SWITCH” again, it will go into the “OFF” state. We show that we want to be in the “ON” state by marking the “ON” state with double-lines (“ON” is the “accept” state).
Now, below we have a real FA. It has states q0 and q1, takes a series of a’s as input (e.g. “aaaaa”), and has accept state, q1. What types of strings does this FA accept? Check your answer the next time we meet!
In the posts that I will be writing, I will be covering topics revolving around the building blocks of algorithms, data structures, and math. And the reason I said “building blocks” is because you will find they are enjoyable to develop, build, stack on top of each other, and play with.
Today, I will be covering an efficient sorting algorithm: quicksort. I will not guide you through the implementation, but I will update this post later on with a link to my code on github. In pseudocode, quicksort is carried out in the following fashion:
quicksort on array
1. pick an element of the array to be the partition
2. arrange the array - move everything less than the partition
to the left portion of the array, make sure the partition element
comes after this left portion
3. quicksort on left portion
4. quicksort on right portion
Lets navigate through the algorithm.
pick an element of the array to be the partition
1. You start off with an unsorted array. Pick an element to be the partition (you may pick an element in a random fashion – this is an ok choice). Now lets set our pivot off to the side by swapping it with the last element of the array.
Array: 9 3 6 2 5 8
^
Chose: 5
Swap: 9 3 6 2 8 5
^
arrange the array
2. Now, scan the array, moving everything less than this partition to the left of the array so that everything on the right will be greater than the partition. We can accomplish this task by swapping lower values with the first index, the next one in the second index, etc. I will use the bar symbol “|” to separate the “left” and “right” portions.
9 3 6 2 8 5
^ no, 9 is greater than 5
9 3 6 2 8 5
^ yes, 3 is less than 5, swap 3 with index 0 (9)
3|9 6 2 8 5
^ no, 6 is greater than 5
3|9 6 2 8 5
^ yes, 2 is less than 5, swap 2 with index 1 (9)
3 2|6 9 8 5
^ no, 8 is greater than 5
3 2|6 9 8 5
^ stop. 5 is our partition.
Notice that everything left of the bar “|”, is less than the partition and everything to the right is greater than the partition. Now, move the partition into place.
3 2|6 9 8 5 the last index we swapped with was 1, so we will swap
our partition with index 2 (6)
3 2 5 9 8 6
^
quicksort on left and right portion
3 & 4. Finally, recursively call the quicksort algorithm on both right and left portions of the array (until the array is only one element). Why does this sort the array?
recursive calls 1 | < than pivot | > than pivot | recursive calls 2 | < than pivot | > than pivot | < than pivot | > than pivot | recursive calls 3 | < | > | < | > | < | > | < | > | recursive calls 4 | < | > | < | > | < | > | < | > | < | > | < | > | < | > | < | > | ...
Basically, if you organize an array into lower and higher parts, then organize those parts into lower and higher parts, you successively get an array that is closer and closer to being sorted; from the rough sorting of high and low portions of the whole array, to finer sorting of an array whose portions that were roughly sorted themselves, to the finest sorting of a perfectly sorted array.
This reminds me of when you view a large image file from the internet. Sometimes it appears really pixelated and over time the image quality improves until it appears the way it is supposed to.
Now that you understand quicksort, try to code one! Even better, post a comment with your implementation!
I don’t know where I am half the time, it makes life twice as hard when I don’t know where I am in my computer! This is quick tip for new terminal users trying to feel comfortable in their shell!
user@host:~$
Fear not, the bash shell has got your back covered (Ok, I will stop the shell jokes)!
0. pwd
Print where you are. Really useful command, but to tell you the truth, I don’t find myself using it very often. I have included it just in case you feel that you might!
user@host:~$ pwd /home/user
1. ls
Prints the contents of your current working directory. A couple of options that are useful are -a to view all files (including hidden files) and -l to view permissions.
user@host:~$ ls Desktop Documents Downloads Public Templates user@host:~$ ls -a .bashrc Documents Public .cache Downloads Templates .config .gitconfig user@host:~$ ls -l drwxr-xr-x 2 user user 4096 Mar 12 16:09 Desktop drwxr-xr-x 3 user user 4096 Mar 15 20:47 Documents drwxr-xr-x 2 user user 4096 Mar 24 19:56 Downloads drwxr-xr-x 2 user user 4096 Mar 12 16:09 Public drwxr-xr-x 2 user user 4096 Mar 12 16:09 Templates
2. cd
Now, let’s get moving! Lets use cd to change our location.
user@host:~$ cd Documents # Moves you into the Documents folder user@host:~/Documents$ cd .. # Moves you to the parent directory user@host:~$ cd / # Moves you to root directory user@host:/$ cd ~ # Brings you to your home directory user@host:~$
3. tree
This is an awesome tool that will graphically (almost – in a terminal sort of way) display the file tree of whichever directory you pass to it. If you do not tell it a specific directory, it will print the tree of your current working directory.
user@host:~$ tree /home
/home
└── user
├── Desktop
├── Documents
│ ├── Pictures
│ │ ├── img1.jpg
│ │ ├── img2.jpg
...
With these tools, you should no longer be lost in your computer. Now, if only we could find out the real-life equivalents.
In Part 1/2, we created a timer in a file named “d_prog.c”. The timer made entries into /var/log/syslog.
user@host-$ sudo vim /var/log/syslog ... Mar 15 19:23:18 HOST-PC d_prog[5533]: d_prog begin. Mar 15 19:23:20 HOST-PC d_prog[5533]: dprog timer finished. Mar 15 19:23:22 HOST-PC d_prog[5533]: message repeated 2 times: [ dprog timer finished.] Mar 15 19:23:22 HOST-PC d_prog[5533]: d_prog end.
In this part, we will turn this program into a daemon – a program that runs in the background. The following is our main () from the timer.
int main ()
{
g_running = 1;
openlog("d_prog", LOG_PID, LOG_DAEMON);
syslog(LOG_INFO, "d_prog begin.");
setTimerAlarm ();
while(g_running);
syslog(LOG_INFO, "d_prog end.\n");
closelog ();
exit(EXIT_SUCCESS);
}
Modifications
Now we will add some code at the beginning of our main(). We will step through the process of daemon creation.
0. More includes: Add the following includes:
#include <sys/types.h> // unmask() #include <sys/stat.h> // unmask() #include <unistd.h> // POSIX definition STDIN_FILENO, STDOUT_FILENO, STDERR_FILENO
1. Fork: The parent process will fork a child process. If the fork succeeds, we will close the parent. Our process is now the child.
void main ()
{
pid_t pid, sid;
pid = fork(); // Fork off parent process
if (pid < 0) exit(EXIT_FAILURE); //
if (pid > 0) exit(EXIT_SUCCESS); // and close the parent
g_running = 1;
openlog("d_prog", LOG_PID, LOG_DAEMON);
...
2. Umask: Set the file mode using umask(), otherwise we may end up with some unexpected file mode.
void main ()
{
pid_t pid, sid;
pid = fork(); // Fork off parent process
if (pid < 0) exit(EXIT_FAILURE); //
if (pid > 0) exit(EXIT_SUCCESS); // and close the parent
umask(0);
...
3. Session: Create a new session ID so the child will not be seen as an orphan:
void main ()
{
...
umask(0);
sid = setsid(); // create session ID for child process
if (sid < 0) exit(EXIT_FAILURE);
...
4. Working Directory: Change the working directory for the daemon. There will always be a root directory, so we are setting the working directory to that.
void main ()
{
...
sid = setsid(); // create session ID for child process
if (sid < 0) exit(EXIT_FAILURE);
// Attempt to change working
// directory to root because
// all systems have a root
// directory
if ((chdir("/")) < 0) exit(EXIT_FAILURE);
...
5. Close File Descriptors: Close these as they may become a security risk, and are not needed by daemons anyways.
void main ()
{
...
if ((chdir("/")) < 0) exit(EXIT_FAILURE);
close(STDIN_FILENO); // Close out file descriptors
close(STDOUT_FILENO); // They may introduce a
close(STDERR_FILENO); // security risk.
...
Adding the above sections to the beginning of your main () turns the timer into a daemon timer. Now, when you execute your program from the bash prompt, your daemon is spawned and control immediately returns to the prompt as the daemon runs in the background.
user@host-$ ./d_prog user@host-$ # d_prog is already running in the background user@host-$ ps -A | grep d_prog # lets check if it is reeeeaally running! 4033 ? 00:04:42 d_prog user@host-$ killall d_prog # kill it
Of all the features of the Gnome desktop that I enjoy, quick search has to be the top. Nothing beats four keystrokes to open an application: Super, f, i, r, Enter –> Firefox opens. Of course this feature is present in other desktop environments and OSes as well (Mac OS X: Spotlight and Windows start menu search). Why is it so good you ask, well … try it!
Recently, I installed Eclipse (extract eclipse*.tar.gz file and moved to /opt). However, “installing” software in this manner will not make the software available in the Gnome search. To do that, we need *.desktop files!
These files are normally located in the /etc/share/applications folder. That is where I created the following file “eclipse.desktop”:
[Desktop Entry] Version=1.0 Name=Eclipse Luna Comment= Exec=/opt/eclipse/eclipse Path=/opt/eclipse Icon=/opt/eclipse/icon.xpm Terminal=false Type=Application Categories=Application;Development;
I will only mention the required fields, so you can get your search up and running:
name – the name of your application
exec – the path to the executable file
type – Application | Link | Directory
Kabam! You can now launch your application through search!
Ok, lets make stuff! Today, we will begin the construction of a basic, but working, example of a Linux daemon. Daemons are programs that work in the background, invisible, helping or hurting your machine … explaining the reason why they are called daemon’s (“nature spirits”). During this first part, we will make a program that runs on a timer. On the second part, we will make it run in the background as a daemon. Once we have constructed the final program, you can make him do background tasks as you please.
We will be building a timer in C today. I named my program “d_prog.c”. The goal will be to make a program that will make posts on your system log. We will make it so that messages are posted on startup, on regular timed intervals, and on exit. The system log is commonly located at /var/log/syslog. You can check if your program is working correctly by looking for your program’s output within that log. I will look for output of the program “d_prog”. Below is the basic setup.
#include <signal> // for dealing with SIGALRM
#include <stdio> // for use of printf()
#include <stdlib> // for EXIT_SUCCESS / EXIT_FAILURE
#include <sys/time.h> // for itimerval struct
#include <syslog.h> // for using the system log
int g_running = 0;
void setTimerAlarm ()
{
}
int main ()
{
g_running = 1;
setTimerAlarm ();
while(g_running); // run the program while g_running == 1
// for now, the program will run in an infinite loop
exit(EXIT_SUCCESS);
}
We will flesh out the details of the program using the above layout. main () will set up the environment and setTimerAlarm () will set up a timer that posts messages. I have written comments next to the header files that we must include so you will know why they are included.
In order for our timer to work, we definitely need more things.
itimerval struct (from sys/time.h)- This is a struct that can hold parameters needed to set up a timer. We will use this to set up our timer the way we want.
setitimer() (from sys/time.h) – We will use this function call to set up the timer. We will pass in the itimerval struct we made to make the timer work the way we want. Note: the timer made by this function works by sending us a signal called “SIGALRM”. Imagine your alarm clock yelling “SIGALRM!” It works just like that!
handleTimerAlarm() (we will make this function) – This function will handle the “SIGALRM” signal. Imagine your hand turning off the yelling alarm clock – it will work like that. We call the function signal(SIGALRM, handleTimerAlarm), from sys/time.h, to let the system know that handleTimerAlarm() will handle SIGALRM signals.
handleClose() (we will make this too)- This function will catch signals that are meant to close the program, like SIGTERM.
void handleTimerAlarm (int sig)
{
syslog (LOG_INFO, "dprog timer finished.\n");
}
void handleClose (int sig)
{
g_running = 0; // handling signals to close this program
// by setting g_running to 0 (stops the
// while () loop in main ())
}
void setTimerAlarm ()
{
struct itimerval timer;
timer.it_value.tv_sec = 2; // period til 1st interrupt
timer.it_value.tv_usec = 0;
timer.it_interval.tv_sec = 1; // period between following interrupts
timer.it_interval.tv_usec = 0;
signal (SIGALRM, handleTimerAlarm); // set handleTimerAlarm to handle SIGALRM - see setitimer
signal(SIGHUP, handleClose); // handleClose () will handle signals
signal(SIGTERM, handleClose); // that close this program.
signal(SIGINT, handleClose); //
signal(SIGQUIT, handleClose); //
setitimer (ITIMER_REAL, &timer, 0); // timer will send "SIGALRM" signal
}
Before we compile and run this program, lets add a few more lines to main() which will write an entry to the system log when the program begins and when it ends.
int main ()
{
g_running = 1;
openlog("d_prog", LOG_PID, LOG_DAEMON);
syslog(LOG_INFO, "d_prog begin.");
setTimerAlarm ();
while(g_running);
syslog(LOG_INFO, "d_prog end.\n");
closelog ();
exit(EXIT_SUCCESS);
}
Before you compile and run it, remember, that this program will run in an infinite loop, so be ready to hit Ctrl+C to end it. Ok! Now, lets compile and run it!
user@host-$ gcc d_prog.c -o d_prog user@host-$ ./d_prog
Viewing the system log, you should see something like this near the end:
Mar 15 19:23:18 HOST-PC d_prog[5533]: d_prog begin. Mar 15 19:23:20 HOST-PC d_prog[5533]: dprog timer finished. Mar 15 19:23:22 HOST-PC d_prog[5533]: message repeated 2 times: [ dprog timer finished.] Mar 15 19:23:22 HOST-PC d_prog[5533]: d_prog end.
As we can see, the program works as intended! Next time, we will work on turning this program into a daemon, however, in the meantime, have fun putting your timer to use in other projects!
