Archive
The project ‘parkman’ (Parking Manager).
Within the framework of the course “Software Engineering I – Laboratory” (Department of Informatics and Communications, T.E.I of Serres) we developed as a semester assignment a parking management application.
Both the graphical user interface (GUI) and the application are implemented with Qt in C++. Specifically, with this application, the end user can manage a variety of customers, customer cards, vehicles, transactions, parking, vehicle fees, etc.
The project ‘PGASystem’ (Parallel Genetic Algorithms System).
The project “PGASystem” (Parallel Genetic Algorithms System) is an under development system based on the client / server architecture and can be used to implement and study of parallel genetic algorithms.
Implementation of breadth-first search algorithm in graphs.
The following function is applied onto a graph and it specifically implements the method of breadth-first search. To visit all nodes connected to node k of a graph, we put the k in a FIFO queue and then go into a loop, during which we get the next node from the queue and, if we have not already visited it, we visit it and push into the queue all nodes belonging to the adjacency list of this node, continuing this process until we empty the queue.
Implementation of an algorithm for creating a syntax tree.
The following program creates the syntax tree of a mathematical expression in prefix notation. For simplicity, we assume that the terms of the expression are individual characters (digits). Each time the recursive function parse() is called, a new node is created, whose value is the next character of the expression. If the value is a term (digit), we return the new node. However, if it is an operator, we set the left and right pointers to point the tree made (recursively) for the two operands.
Implementation of algorithms (without recursion) for preorder & level-order traversal of binary trees.
The iterative (non-recursive) function preorderTreeTraverse() can perform preorder traversing of a binary tree with the help of a stack that can hold pointers to nodes of the tree.
Also, the iterative (non-recursive) function layerTreeTraverse() can perform level-order traversing of a binary tree with the help of a queue that can hold pointers to nodes of the tree.
Implementation of algorithm for the calculating of prefix expressions.
To calculate a prefix expression, we either convert a number from ASCII to decimal (in the loop ‘while’ at the end of the program) or implement the operation indicated by the first character of the expressions to the two terms, with a recursive calculation. This function is recursive, but it uses a global array containing the expression and an index number for the current character of the expression. The index number goes beyond each sub-expression calculated.
Collection of useful recursive functions.
The elegant recursive solution to a problem is most of the times invaluable. Although the iterative solution of that problem is likely to have a better space and time complexity, it is often preferred to use the recursive version for clarity and simplicity. It is remarkable how easily a problem can be solved by use of a recursive manner. In this article we will try to record a collection of useful recursive functions:
Implementation of algorithm for converting an expression from infix to postfix notation.
The following program converts an expression from infix to postfix notation. The conversion is carried out with the help of a stack. For example, to turn the expression (A + B) into the postfix form A B +, we ignore the left parenthesis, convert the A to postfix form, we store the + operator on the stack, we convert B to postfix form and then, when find the right parenthesis, we pop the + operator from the top of the stack. In particular, the following implementation works only for the addition and multiplication of integers.
Implementation of algorithm for calculating a postfix expression.
The following program reads any postfix expression that includes integer multiplication and addition, evaluates the expression and displays the final result on the screen. The program stores the intermediate results in a stack of integers.
The terms (operands) are pushed onto the stack. The operators are applied to the two entries at the top of the stack (the two entries are popped from the stack); the result is pushed back into the stack. Because the order in which the two pop() functions are performed in the expression of this code is not specified in C++, the code for some non-commutative operators, such as the ones for subtraction and division, would be somewhat more complicated.
Implementation of an application for the sorting of an array of strings.
The following program demonstrates a significant processing operation on arrays of strings. More precisely, we present the re-sorting of a set of strings in order to classify them. So, we read the strings and place them in a temporary storage area (buffer) large enough to be able to store all, keeping in an array a pointer to each string. Then we re-sort the pointers (only pointers and not strings to increase the performance) to place the pointer to the “smallest” string at the first position of the array, the pointer to the next “largest” string at the second position of the array, and so on.
Implementation of graph representation with an adjacency list.
The following program reads a set of edges that define a graph and creates a representation of this graph with an adjacency list. The adjacency list of a graph is an array of lists, one for each vertex, where the j-th list contains a linked list of the nodes which are connected with the j-th vertex.
Implementation of graph representation with an adjacency matrix.
The following program reads a set of edges that define an undirected graph and creates a representation of this graph with an adjacency matrix, giving a[i][j] and a[j][i] the value of 1 if there is an edge from i to j or from j to i in the graph, or the value of 0 if it does not exist. Also, we assume that the number of vertices V is a constant known at compilation time. Otherwise, there should be dynamic memory allocation for the array that represents the adjacency matrix.
Implementation of string search algorithm.
The following program finds all the occurrences of a word in a text string. We set the text string as an array of characters of fixed size (although we could, instead, use the operator ‘new’) and read it from the standard input using the function cin.get(). The memory allocation for the word entered in the command line and passed on as argument is done by the system before this program is called and we find the pointer to the string in argv[1]. For every starting position i in the array a, tries to associate the substring starting from this position with the p, checking character by character for equality. Each time we reach the end of p successfully, we display the starting position (i) of the word in the text on the screen.
Black Box Unit Testing with the QT Framework.
Black Box testing and general testing is a key step in the iterative development methodologies (e.g. UP, XP, Agile) as it performs both the validation and verification of units in a system.
Differential Evolution – Example 5.
I quote below a personal portable implementation (in C++) of a classic Differential Evolution algorithm used to maximize the function f(x) = sin(x) in the domain 0 <= x <= 2pi. You can compile the program with the g++ compiler.
Genetic Algorithm – Example 4.
I quote below a personal portable implementation (in C++) of a classic genetic algorithm (evolutionary algorithm) used to maximize the function f(x, y) = sin(x) * sin(y) in the domain 0 <= x, y <= 2pi. You can compile the program with the g++ compiler.
Genetic Algorithm – Example 3.
I quote below a personal portable implementation (in C++) of a classic genetic algorithm (evolutionary algorithm) used to maximize the function f(x) = sin(x) in the domain 0 <= x <= 2pi. You can compile the program with the g++ compiler.
Genetic Algorithm – Example 2.
I quote below a personal portable implementation (in C++) of a classic genetic algorithm (evolutionary algorithm) used to maximize the function f(x) = sin(x) in the domain 0 <= x <= 2pi. You can compile the program with the g++ compiler.
Genetic Algorithm – Example 1.
I quote below a personal portable implementation (in C++) of a classic genetic algorithm (evolutionary algorithm) used to maximize the function f(x) = sin(x) in the domain 0 <= x <= 2pi. You can compile the program with the g++ compiler.
The project ‘Reception’ (Hotel Reception Manager).
Within the framework of the course “Software Engineering II – Laboratory” (Department of Informatics and Communications, T.E.I of Serres) we developed as a semester assignment an application for the management of hotel businesses.
Both the graphical user interface (GUI) and the application were implemented with Qt while the database in SQLite. More specifically, the end user can perform through this application functions such as: processing of customers / rooms, booking rooms, search rooms / customers, inventory of hotel services offered to customers, central management for the correct operation of the hotel, central management of the cost of services provided, as well as adding new users and system administrators to the system.
Implementation of insertion sort algorithm for single linked lists.
The following program generates N random integers between 0 and 999, creates a linked list inserting a number in each node and then rearranges the nodes of the list so that the numbers appear sorted when we go through the list. For the sorting, it maintains two lists: one input list (not sorted) and one output list (sorted). In each iteration of the loop, it removes a node from the input list and enters it in the appropriate position in the output list. The code is simplified by using head nodes for each list, which contains links to the first node lists. Also, both lists (input and output) are printed.
Implementation of closest point calculation.
This program demonstrates the use of an array and is representative of the usual situation in which we store data in one array to process them later. It counts the number of pairs of N randomly generated points of the unit square, which can be connected to a line segment of length less than ‘d’, using the point data type. Because the execution time of this program is O(n2), it can’t be used for large N.
Implementation of a circular list for solving the problem of Josephus.
For the representation of individuals arranged in a circle, we create a circular linked list with a combination of each person to the person on his left in the circle. The integer i represents the i-th person in the circle. After you create a circular list of one node for 1, we insert its unique node to nodes 2 to N. We end up with a cycle from 1 to N, with x indicating the node N. Then, starting from 1 we omit M-1 nodes, we define the pointer of the (M-1)-th node to omit the M-th, and continue that way until only one node remains in the list.
Implementation of algorithm for finding primes with the sieve of Eratosthenes.
The aim of this program is to assign to a[i] the value 1 if i is a prime number and the value 0 if not. Initially, all elements of the array take the value 1 to indicate that there are no numbers which are known not to be prime. Then all elements of the array corresponding to indexes that are known not to be primes (multiples of known primes) take the value 0. If a[i] has the value 1 even after all multiples of smaller primes have taken the value 0, we know that i is a prime number.
Implementation of algorithm for the simulation of the ‘twisting’ of a coin.
The program generally simulates a Bernoulli trials sequence, a familiar and abstract notion of probability theory. So, if you flip a coin N times, we expect “head” to occur N/2 times – but it could occur anything between 0 and N times. The program performs the experiment M times, reading the N and M from the command line. It uses an array ‘f’ to count the frequency with which the result “i heads” appears for 0 <= i <= N, and then displays a histogram of the results of experiments with an asterisk for every 10 appearances. Also, the operation behind the program – of indexing an array with a calculated value – is critical to the effectiveness of many computational procedures.
Implementation of sequential and binary search (iterative version).
Sequential Search.
This algorithm checks whether the number ‘v’ is contained in a set of numbers already stored in the data a[0], a[1], …, a[r-1] of the array ‘a’ (where ‘r’ the number of elements in it), comparing it sequentially with all numbers, starting from the beginning. If the check reaches the end without finding the number, the value -1 is returned. Otherwise, we are returned the index of the position of the one-dimensional array containing the number.
Arduino: A library for implementing a generic, dynamic queue (array version).
This project refers to an Arduino library implementing a generic, dynamic queue (array version).
The data structure is implemented as a class in C++.
For more information, you can get the project itself ‘QueueArray‘.
Solving the problem of connectivity with the weighted quick-union algorithm with path compression by halving.
If we replace the loops ‘for’ of the simple version of weighted quick-union (you’ll find it in a previous article) with the following code, we reduce the length of each route passing to the half. The end result of this change is that after a long sequence of operations the trees end up almost level.
Solving the problem of connectivity with the quick-find algorithm.
This program reads from the standard input a sequence of pairs of non-negative integers which are less than N (interpreting the pair [p q] as a “link of the object p to object q”) and displays the pairs that represent those objects which are not yet connected. The program complies with the array ‘id’ to include an entry for each object and applies that id[q] and id[p] are equal if and only if p and q are connected.
Solving the problem of connectivity with the quick-union algorithm.
If we replace the body of the while loop of the quick-find algorithm (you can find it in a previous article) with the following code we have a program that meets the same specifications as the quick-find algorithm but performs fewer calculations for the act of union, to the expense of more calculations for act of finding. The ‘for’ loop and the ‘if’ operation that follows in this code determine the necessary and sufficient conditions in the array ‘id’ that p and q be linked. The act of union is implemented by the assignment id[i] = j.
Solving the problem of connectivity with the weighted quick-union algorithm.
This program is a modification of the simple quick-union algorithm (you’ll find it in a previous article). It uses an extra array ‘sz’ to store the number of nodes for each object with id[i] == i in the corresponding “tree”, so the act of union to be able to connect the smaller of the two specified “trees” with the largest, and thus avoid the formation of large paths in “trees”.
Arduino: A library for implementing a generic, dynamic stack (array version).
This project refers to an Arduino library implementing a generic, dynamic stack (array version).
The data structure is implemented as a class in C++.
For more information, you can get the project itself ‘StackArray‘.
Portable and Abstract version for storing settings in QT applications.
The QT provides an adorable way to store the settings of a program with a GUI (and not only) by means of the QSettings library. Below, we quote a personal version of the project ‘parkman‘ (Parking Manager).
C++ function library for the comparison of floating point numbers.
Below I quote a simple but useful library (implemented in C++) which contains functions for comparing double precision floating point numbers.
The project ‘clinicadmin’ (Clinic Administrator).
Within the framework of the course “Visual Programming – Theory” (Department of Informatics and Communications, T.E.I of Serres) we developed a clinic management application as a semester project.
The database of the application was implemented in Microsoft SQL Server and the graphical user interface in Borland C++ Builder.
More specifically, this application enables the end user to manage different patients, visits, appointments, diagnoses, treatments, prescriptions, tests, links.
|
|
|
|
|
|
|
FSF News
- Free Software Foundation statement on PRISM revelations
- World Wide Web Consortium takes next step with controversial DRM proposal, Defective by Design condemns decision
- "Oscar" awarded to W3C for Best Supporting Role in "The Hollyweb"
- FSF-certified to Respect Your Freedom: ThinkPenguin USB Wifi adapter with Atheros chip
- The FSF is hiring: Seeking a full-time outreach and communication coordinator
- International coalition of Internet freedom organizations urges W3C to reject Encrypted Media Extensions, a proposal to build Digital Restrictions Management into the Web
