Global ETD Search

31	Average case analysis of algorithms for the maximum subarray problem Bashar, Mohammad Ehsanul January 2007 (has links) Maximum Subarray Problem (MSP) is to find the consecutive array portion that maximizes the sum of array elements in it. The goal is to locate the most useful and informative array segment that associates two parameters involved in data in a 2D array. It's an efficient data mining method which gives us an accurate pattern or trend of data with respect to some associated parameters. Distance Matrix Multiplication (DMM) is at the core of MSP. Also DMM and MSP have the worst-case complexity of the same order. So if we improve the algorithm for DMM that would also trigger the improvement of MSP. The complexity of Conventional DMM is O(n³). In the average case, All Pairs Shortest Path (APSP) Problem can be modified as a fast engine for DMM and can be solved in O(n² log n) expected time. Using this result, MSP can be solved in O(n² log² n) expected time. MSP can be extended to K-MSP. To incorporate DMM into K-MSP, DMM needs to be extended to K-DMM as well. In this research we show how DMM can be extended to K-DMM using K-Tuple Approach to solve K-MSP in O(Kn² log² n log K) time complexity when K ≤ n/log n. We also present Tournament Approach which solves K-MSP in O(n² log² n + Kn²) time complexity and outperforms the K-Tuple Maximum Subarray Problem Distance Matrix Multiplication All Pairs Shortest Path Problem Shortest Path Expected Time Average Time Average Case Analysis Binary Heap Prefix Sum Directed Acyclic Graph X + Y Problem Binary Tournament Tree Solution Set MSP K-MSP DMM K-DMM APSP K-Tuple
32	AspectKE: Security aspects with program analysis for distributed systems Fan, Yang, Masuhara, Hidehiko, Aotani, Tomoyuki, Nielson, Flemming, Nielson, Hanne Riis* January 2010 (has links) Enforcing security policies to distributed systems is difficult, in particular, when a system contains untrusted components. We designed AspectKE, a distributed AOP language based on a tuple space, to tackle this issue. In AspectKE, aspects can enforce access control policies that depend on future behavior of running processes. One of the key language features is the predicates and functions that extract results of static program analysis, which are useful for defining security aspects that have to know about future behavior of a program. AspectKE* also provides a novel variable binding mechanism for pointcuts, so that pointcuts can uniformly specify join points based on both static and dynamic information about the program. Our implementation strategy performs fundamental static analysis at load-time, so as to retain runtime overheads minimal. We implemented a compiler for AspectKE, and demonstrate usefulness of AspectKE through a security aspect for a distributed chat system. aspect oriented programming program analysis security policies distributed systems tuple spaces Data processing Computer science Language Constructs and Features (E.2) Abstract data types Classes and objects (NEW) Concurrent programming structures Constraints (NEW) Control structures Coroutines Data types and structures Dynamic storage management Frameworks (NEW) Inheritance (NEW) Input/output Modules, packages Patterns (NEW) Polymorphism (NEW) Procedures, functions, and subroutines Recursion Security and Protection (K.6.5) Access controls Authentication Cryptographic controls Information flow controls Security kernels Verification Algebraic approaches to semantics Denotational semantics Operational semantics Partial evaluation (NEW) Process models (NEW) Program analysis (NEW)

Search results

Average case analysis of algorithms for the maximum subarray problem

AspectKE*: Security aspects with program analysis for distributed systems