Scientific Commons
Scientific Commons.org is a search engine for scientific publications made available via open access repositories. These repositories include institutional repositories such as the California Digital Library’s e-Scholarship, as well as discipline-based repositories. The major aim of the project is to develop the worlds largest communication medium for scientific knowledge products which is freely accessible to the public. A key challenge of the project is to support the rapidly growing number of movements and archives who admit the free distribution and access to scientific knowledge. These are the valuable sources for the ScientificCommons.org project. The ScientificCommons.org project makes it possible to access the largely distributed sources with their vast amount of scientific publications via just one common interface. ScientificCommons.org identifies authors from all archives and makes their social and professional relationships transparent and visible to anyone across disciplinary, institutional and technological boundaries. At the time of this posting, ScientificCommons.org included nearly 25 million documents from around 100 different repositories around the world.
Check it out: www.scientificcommons.org
Dynamic Programming – Integer Knapsack
The Integer Knapsack problem is a famous rubrick in Computer Science. The problem has a simple brute-force solution. However, solving large instances of this problem requires considerable work (run-time).
The problem is often given as a story:
- A thief breaks into a house. Around the thief are various objects: a diamond ring, a silver candelabra, a Bose Wave Radio ™, a large portrait of Elvis Presley painted on a black velvet background (a “velvet-elvis”), and a large tiffany crystal vase. The thief has a knapsack that can only hold a certain capacity. Each of the items has a value and a size, and cannot hold all of the items in the knapsack.
| Item | Size | Value |
| 1 – ring | 1 | 15 |
| 2 – candelabra | 5 | 10 |
| 3 – radio | 3 | 9 |
| 4 – elvis | 4 | 5 |
The problem is, which items should the thief take? If the knapsack were large enough, the thief could take all of the items and run. But, that is not the case (the problem states that the knapsack cannot hold all of the items). There are three types of “thieves” that we shall consider: a greedy thief, a foolish and slow thief, and a wise thief. Each of these thieves have a knapsack that can old a total size of 8.
The greedy thief breaks into the window, and sees the items. He makes a mental list of the items available, and grabs the most expensive item first. The ring goes in first, leaving a capacity of 7, and a value of 15. Next, he grabs the candelabra, leaving a knapsack of size 2 and a value of 25. No other items will fit in his knapsack, so he leaves.
The foolish and slow thief climbs in the window, and sees the items. This thief was a programmer, downsized as part of the “dot-bomb” blowout. Possessing a solid background in boolean logic, he figures that he can simply compute all combinations of the objects and choose the best. So, he starts going through the binary combinations of objects – all 2^5 of them. While he is still drawing the truth table, the police show up, and arrest him. Although his solution would certainly have given him the best answer, it just took long to compute.
The wise thief appears, and observes the items. He notes that an empty knapsack has a value of 0. Further, he notes that a knapsack can either contain each item, or not. Further, his decision to include an item will be based on a quick calculation – either the knapsack with some combination of the previous items will be worth more, or else the knapsack of a size that will fit the current item was worth more. So, he does this quick computation, and figures out that the best knapsack he can take is made up of items 1,3, and 4, for a total value of 29.
Greedy Algorithms
The mistake the first thief made was that he was too greedy. He took the items in non-decreasing order by their value. He ended up with a knapsack that was not completely filled. Not having a knapsack filled completely does not necessarily imply that the solution will be bad, but it is often the case.
One advantage to this technique is that it can be done very quickly. The amount of work for this solution is relative to how many objects the thief has to look at. In the worst case, how many items would this be? How much work is involved?
The greedy algorithm does not work for this version of the problem; but there is another closely related version. Suppose that instead of objects, there were piles of dust. The first pile was platinum dust, the second pile was gold, and the third pile were silver dust. In this version of the problem, the thief will fill his sack with as much as the sack will hold. If there were still capacity, the thief will next fill the sack with gold, and finally, silver. This version of the problem is often called the “Continuous Knapsack” problem.
Q: What key difference is there in the continuous problem that makes a greedy solution work?
Brute Force
The mistake the second thief in our rubric made was to try to enumerate all of the possible choices. There are 25 combinations in this example. Expressed more generally, there are 2n combinations of items that the thief can choose. This can be expressed as the power set of the items. Algorithms that require enumeration of this set will require exponential work: O(2n). Clearly, as the size of the set increases, the amount of work will increase exponentially.
Dynamic Programming
The wise thief used a technique that is known as “dynamic programming.” In this case, a table was made to track “the best knapsack so far.” The complete table that is show in subsequent examples is for demonstration purposes. In the following example, there is a column that indicates a range of values from 0 to the 9. This corresponds to the “target weight” of the knapsack. The table stops at the maximum capacity of the knapsack. There are then n+1 columns, one each for the items that can be selected.
The first column is initialized to zero. Logically, this corresponds to a knapsack with zero items having zero worth. The first row is also initialized to zero, corresponding to a knapsack of zero capacity.
Finally, the values of the table are filled in, from left to right, and from top to bottom. For each cell item, the total worth of a knapsack is determined as either the worth of a knapsack without the current item (expressed as the value directly to the left of the current value), or it is the value of the knapsack with the current item added into it.
| Items> Capacity |
i:1 15/1 |
i:2 10/5 |
i:3 9/3 |
i:4 5/4 |
|
| 0 | 0^ | 0^ | 0^ | 0^ | 0^ |
| 1 | 0^ | 15^ | 15^ | 15^ | 15^ |
| 2 | 0^ | 15^ | 15^ | 15^ | 15^ |
| 3 | 0^ | 15^ | 15^ | 15< | 15^ |
| 4 | 0^ | 15^ | 15^ | 24^ | 24< |
| 5 | 0^ | 15^ | 15< | 24^ | 24< |
| 6 | 0^ | 15^ | 25^ | 25< | 25< |
| 7 | 0^ | 15^ | 25^ | 25< | 25< |
| 8 | 0^ | 15^ | 25^ | 25< | 29^ |
Observe in the previous example, the knapsack starts at zero, and the computation continues down the first column. Since the first item has a size of one, a knapsack of value 15 can be made for all of the columns. The next column shows that knapsacks less than size 5 can only be made using an empty knapsack or else using only the first item. For knapsacks over size six, then a decision must be made: is it better to build a knapsack with both items, or only with one of them.
What makes this different than the greedy algorithm happens when processing the third item. First, notice that the best knapsack that can be made, up until size four, does not include the third item. Then, when the capacity of the knapsack increases enough to hold the third item, the value changes – the value of the knapsack now includes the second and third items, for a total value of 25. Finally, when the capacity is large enough to hold all three items, then the capacity is grown to hold all three items. However, following the same pattern for the fourth item, it is apparent that algorithm works by showing that including the fourth item in place of any other item is not required.
AES-CBC software execution optimization
Doomun, Razvi Doma, Jayramsingh Tengur, Sundeep
Computer Science and Engineering, University of Mauritius, Mauritius;
This paper appears in: Information Technology, 2008. ITSim 2008. International Symposium on
Publication Date: 26-28 Aug. 2008
Volume: 1, On page(s): 1-8
Location: Kuala Lumpur, Malaysia,
ISBN: 978-1-4244-2327-9
Digital Object Identifier: 10.1109/ITSIM.2008.4631586
Date Published in Issue: 2008-09-26 14:36:58.0
Abstract
With the proliferation of high-speed wireless networking, the necessity for efficient, robust and secure encryption modes is ever increasing. But, cryptography is primarily a computationally intensive process. This paper investigates the performance and efficiency of IEEE 802.11i approved Advanced Encryption Standard (AES)-Rijndael ciphering/deciphering software in Cipher Block Chaining (CBC) mode. Simulations are used to analyse the speed, resource consumption and robustness of AES-CBC to investigate its viability for image encryption usage on common low power devices. The detailed results presented in this paper provide a basis for performance estimation of AES cryptosystems implemented on wireless devices. The use of optimized AES-CBC software implementation gives a superior encryption speed performance by 12 − 30%, but at the cost of twice more memory for code size.
(PDF)
Cloud Computing (Part 2)
At the fringe are the end users making the requests that initiate computations and who receive the results. Although the future of cloud computing is less than clear, a few examples of present practice suggest likely directions:
Wordstar for the Web. The kinds of productivity applications that first attracted people to personal computers 30 years ago are now appearing as software services. The Google Docs programs are an example, including a word processor, a spreadsheet, and a tool for creating PowerPoint-like presentations. Another undertaking of this kind is Buzzword, a Web-based word processor acquired by Adobe Systems in 2007. Another recent Adobe product is Photoshop Express, which has turned the well-known image-manipulation program into an online service.
Enterprise computing in the cloud.
Software for major business applications (such as customer support, sales, and marketing) has generally been run on corporate servers, but several companies now provide it as an on-demand service. The first was Salesforce.com, founded in 1999, offering a suite of online programs for customer relationship management and other business oriented tasks; the company’s slogan is “No software!”
Cloudy infrastructure. It’s all very well to outsource the chore of building and maintaining a data center, but someone must still supply that infrastructure. Amazon.com has moved into this niche of the Internet ecosystem. Amazon Web Services offers data storage priced by the gigabyte-month and computing capacity by the CPUhour. Both kinds of resources expand and contract according to need. IBM has announced plans for the “Blue Cloud” infrastructure. And Google is testing the App Engine, which provides hosting on Google server farms and a software environment centered on the Python programming language and the Bigtable distributed storage system.
The cloud OS. For most cloud-computing applications, the entire user interface resides inside a single window in a Web browser. Several initiatives aim to provide a richer user experience for Internet applications. One approach is to exploit the cloud-computing paradigm to provide all the facilities of an operating system inside a browser. The eyeOS system, for example, reproduces the familiar desktop metaphor—with icons for files, folders, and applications—all living in a browser window.
YOUTUBE VIDEO LECTURES:
2. Computing in the Cloud – What Next?
Cloud Computing (Part one)
Something is happening today in the world of computing. Data and programs are being swept up from desktop PCs and corporate server rooms and installed in “the compute cloud.” Whether it’s called cloud computing or on-demand computing, software as a service, or the Internet as platform, the common element is a shift in the geography of computation. When you create a spreadsheet with the Google Docs service, major components of the software reside on unseen computers, whereabouts unknown, possibly scattered across continents. The shift from locally installed programs to cloud computing is just getting under way in earnest. Some substantial fraction of computing activity is migrating away from the desktop and the corporate server room. The change will affect all levels of the computational ecosystem, from casual user to software developer, IT manager, even hardware manufacturer.
The new regime is not quite a return to the hub-and-spoke topology of time-sharing systems, if only because there is no hub. A client computer on the Internet can communicate with many servers at the same time, some of which may also be exchanging information among themselves. However, even if we are not returning to the architecture of time-sharing systems, the sudden stylishness of the cloud paradigm marks the reversal of a long-standing trend. Where end users and corporate IT managers once squabbled over possession of computing resources, both sides are now willing to surrender a large measure of control to third-party service providers.
What brought about this change in attitude? For the individual, total control comes at a price. Software must be installed and configured, then updated with each new release. The computational infrastructure of operating systems and low-level utilities must be maintained. Every update to the operating system sets off a cascade of subsequent revisions to other programs. Outsourcing computation to an Internet service eliminates nearly all these concerns. Cloud computing also offers end users advantages in terms of mobility and collaboration.
For software vendors who have shifted their operations into the cloud, the incentives are similar to those motivating end users. Software sold or licensed as a product to be installed on the user’s hardware must be able to cope with a baffling variety of operating environments. In contrast, software offered as an Internet-based service can be developed, tested, and run on a computing platform of the vendor’s choosing. Updates and bug fixes are deployed in minutes. (But the challenges of diversity don’t entirely disappear; the serverside software must be able to interact with a variety of clients.) Although the new model of Internet computing has neither hub nor spokes, it still has a core and a fringe.
The aim is to concentrate computation and storage in the core, where high performance machines are linked by high-bandwidth connections, and all of these resources are carefully managed.
(Courtesy: ACM Communications July 2008)
YOUTUBE VIDEO LECTURES ON CLOUD COMPUTING
1. Cloud Computing – Introduction
3. The Future of Operating System – Cloud Computing?
Multimedia Forensics and Security
By Chang-Tsun Li, University of Warwick, UK
The advances and convergence of information and communication technology (ICT) and multimedia
techniques have brought about unprecedented possibilities and opportunities. To prevent abuses of the usage of ICT and multimedia techniques, the study of multimedia forensics and security has emerged in recent years as a new interdisciplinary area encompassing aspects of digital cryptography, digital watermarking, data hiding, steganography, and steganalysis. Moreover, multimedia forensic techniques have also opened up a new horizon for helping companies, government, and law enforcement agencies in combating crime and fraudulent activities. The past decade has seen an exciting development of techniques revolving around the issues of multimedia forensics and security.
Aiming at serving this purpose, this book contains a collection of informative and stimulating chapters written by knowledgeable experts and covers a wide spectrum of the state-of-the-art techniques for tackling the issues of multimedia forensics and security. Each chapter is a self-contained treatment on one aspect of the broad subject, allowing the readers to follow any order of their liking. The chapters are selected to suit readers of different levels with various interests, making this book an invaluable reference for beginners as well as experts alike.
Book Lovers: Ubiquitous Computing Technology for Real Time Enterprises
Handbook of Research on Ubiquitous Computing Technology for Real Time Enterprises
By Max Mühlhäuser, Iryna Gurevych
(2008)
As computing has become more and more an integral part of our daily business and personal lives, the
trend of ubiquitous computing will transform the way in which businesses will work and collaborate.
The well-known fact of a huge community of users on the Internet (1,100 million users as of March
2007) will be complemented by at least one order of magnitude higher (10,000 millions of artificial
users) instantiated by machines, sensors and things connected to the Internet. More precise data will be
generated and accumulated that enable completely new business scenarios for the future. The fact of
being connected to that universe of human users and artificial users will speed up decisions in business
(real-time enterprise) and enable those who can master the infrastructure and the application services
on top of the infrastructure to be more competitive than others. Application fields from logistics to
e-health, from supply-chain management and manufacturing to public security will benefit from the
fact that the “Internet of Things” and the “Internet of People” converge using an “Internet of Services”
architecture. (…..Want to read this great book?)
TEMPORAL KEY INTEGRITY PROTOCOL FOR EFFICIENT WIRELESS NETWORK SECURITY
Temporal Key Integrity Protocol (TKIP) is the IEEE TaskGroupi’s solution for the security loop holes present in the already widely deployed 802.11 hardware. It is a set of algorithms that wrap WEP to give the best possible solution given design constraints such as paucity of the CPU cycles, hardwiring of the WEP encryption algorithm and software upgrade dependent. Thus, TKIP is significantly more difficult and challenging to implement and optimise than WEP. The objective of this research is to examine the cost/benefit of TKIP security mechanisms and optimise its implementation to reduce security overhead for better performance. We propose a modified TKIP (MoTKIP) with improved packet encapsulation and decapsulation procedure that reduces computation and packet overhead in classic TKIP substantially and optimises total wireless network throughput rates.
www.researchgate.net
A group of scientists from Harvard and some other universities from different countries started a project, in which they try to establish a web 2.0 application for scientists. This platform would facilitate the communication between researchers and would increase the efficacy of the research work. This niche social network site called ResearchGATE was launched with the aim of connecting scientists from all disciplines around the world. It aims to change the world of science by providing a global and powerful scientific web-based environment, in which scientists can interact, exchange knowledge and collaborate with researchers of different fields. ResearchGATE enables the following: present yourself and your research projects, enroll, expand, and broaden your science network globally, exchange know-how and expertise, initiate collaboration, discuss your research limitations and get positive feedback, and use innovative tools and work environments for online collaboration. Social networks sites appear to be a dime a dozen, however the ones that will survive will provide a value that users within their target market can’t see a world without it again. ResearchGATE provides that networking technology.
Each researcher can sign up for the network free of charge are then able to post their research work and publications within their profiles, exchange messages, build groups and other various network components. The main advantage for these niche solution networks, especially within this field, is that actual interaction between likeminded individuals can occur that will not only form new relationships, but will also further their actual work. Users can add to an existing scientific database and find and discuss current conferences.
Founding members reign from various backgrounds within the research community.
-
Flickr Photos
More Photos
-
Archives
- June 2009 (1)
- February 2009 (1)
- December 2008 (2)
- October 2008 (14)
- September 2008 (21)
- August 2008 (8)
- July 2008 (7)
- June 2008 (6)
- May 2008 (7)
- April 2008 (10)
- February 2008 (12)
- January 2008 (18)
-
Categories
-
RSS
Entries RSS
Comments RSS
