| Updated: Andrzej Wąsowski Feb 07, 2010 22:18 |
|---|
| Andrzej Wąsowski's Home |
|---|
Most of the following projects can be specialized into 7.5, 15, and 30 ECTS (thesis) projects. I am also welcoming project proposals brought by students.
If you would like to write your thesis under my supervision and you still have some control over your courses then try to follow Models and Programs as your specialization and complement it with courses in Scalable Computing, Modern AI, or Mobile and Distributed Systems. The choice depends a bit on the kind of project you want to write. Feel free to ask.
A research publication is a nice thing to have on your CV regardless whether you want to aim for an academic career or not. If you would like a thesis that results in a research publication, then I recommend that we slowly start to work on it a year before the final deadline. Come to meet me as soon as you think this is a path for you.
Typically a frequent traveler has to schedule a number of flights (say up to 30) between few (say 2-6) airports. Design an extensible architecture with optimization algorithms and implement a prototype system, for an advanced flight reservation planner. The system finds the cheapest coverage of required routes given constraints on travel dates, times and endpoints, and price data available in online ticketing systems. The system should have a modular architecture, so that new ticket vendors/airlines can be added by providing plugins or similar extensions.
Size: 15-30 ECTS, well suited to group work. you preferably have experience with web technologies, and have followed Efficient AI and Programming. Since the work is fairly modular, it is sufficient, if there is at least one person in the group for has each (not all) of the required competences. For 30ECTS more advanced constraints and input data should be supported (for example alternative routings). For larger groups an advanced web-interface, or plugins for more airlines, are a good extension.
Published: 2 Jan 2010
Study the open source audio server Pulseaudio (www.pulseaudio.org). You need to understand how a local srever and clients are configured (what modules can be loaded, what options can be tweaked), and how multiple clients and servers can be combined in a topology over a local area network. Design a domain specific language for modeling pulse audio installations. Prototype an editor for the language using MetaEdit+, Eclipse's Graphical Modeling Framework, or Microsoft Visual Studio DSL tools (or any other infrastructure you consider useful for the purpose).
The extent of the implementation expected depends on the size of the group.
Published: 27 September 2009
Study th architecture of a large open source project, from a product family engineering perspective (for example Mozilla Firefox). Built a feature model for it. I provide basic algorithms and infrustructure, but you need to study the project, feature modeling and interface the infrastructure to the project. Size: 30 ECTS. Having passed the following courses may be an advantage, when doing this project: Efficient AI and Programming, Model Driven Development, Advanced Models and Programs.
Published: 25 August 2009
Implement an efficient and competitive linear programming engine in pure Java (so that it can be used on any platform running JVM). The project includes studying research papers about efficient LP solvers, implementing the tool, and benchmarking it against popular open source LP libraries for C/C++. Size: 15 to 30 ECTS points. You need background in operations research, or you have taken a course on Efficient AI and Programming.
Published: 25 August 2009
Design a grammar for C# that parses not only the main C# language, but also its preprocessor language, so that both the syntax and the preprocessor directives can be maintained in a single abstract syntax tree (warning: this may be challenging). Implement a parser for this grammar. The parser should be tested on mono test suite, and on available open source projects using preprocessor (for example the C5 library). Size: 30 ECTS. You need background in compiler theory, for example by following Advanced Models and Programs.
Published: 25 August 2009
Design and implement an eclipse plugin for governing composition of ATL transformations. Size: 15 to 30 ECTSs. Requires interest in model driven development, specialization in advanced models and programs. Familiarity with reasoning techniques for propositional logics is an advantage. Results of the project following below, can be incorporated into this one.
Published: 14 June 2009
Design and implement program analyses synthesizing interfaces (or precise types) for model transformations expressed in ATL. The types of transformations can, for example, be expressed using the interface framework of Hessellund and Wasowski (MODELS'08). You need background in program analysis (Advanced Models and Programs) and genuine interest in model driven development. Size: 15 to 30 ECTSs. Ideally for two students.
Published: 14 June 2009
Design and implement an efficient toolkit for manipulating boolean formulae, and translating them to standard CNF representation. Experiment with various instances, to see how various translations interact with SAT-solvers. For this task you should have decent background in propositional logics (ideally you have followed Efficient AI and Programming, or know logics from you prior studies). It is preferable that you can program in C, and are interested in releasing your work as an open source project. A substantial amount of code can be provided to help your task. Scalable from 7.5 to 30 ECTs.
Published: 31 May 2009
Extend the SPLC'07 paper by Czarnecki and Wasowski, to select a single feature diagram from the feature graph. This has to be done using spanning tree algorithms on hypergraphs.
Prerequisites: an ideal combination is Advanced Algorithms and Efficient AI and programming, but it can also be done with just Efficient AI and Programming and Performance and Test. You need to know basic graph algorithms, and you have to be comfortable with formulating problems as integer linear programming programs. Scalable from 7.5 ECTS to 30 ECTS.
Published: 10 May 2009
AM3 Atlantic Zoo provides a metamodel for eclipse plugins (OSGi bundles). Implement a tool that synthesizes these models from actual plugins and then provides debugging information for eclipse users (this could mean composing models, to find errors, visualizing dependencies, etc). A part of the project is to brainstorm on desirable functionality.
Implement algorithms (and perhaps an interactive GUI) for CVS like merge operations for feature models. Prerequisites: VOP, AMP + IAIP (or equivalent). Size: up to 30 ECTS.
Eclipse and eclipse based technologies are heavily componentized. Each application/framework is decomposed into a typically large number of dynamically loadable plug-ins. The project uses OSGi bundles as the technology underlying its plug-in mechanism. Bundles are like Java packages, but they have more fine grained interfaces.
The problem with the OSGi model is that there is no explicit description of how bundles are composed, or use each other. This information is embedded in each bundle, so the overview is lost. The composition is done in a very similar way to Java classes. Basically bundles are placed in the scope of the build environment, which allows name resolution. So to try another implementation of the component you need to replace it physically with something else (or tweak Eclipse options).
In this project you implement a tool that extracts and visualized a model of composition for OSGi bundles (Eclipse plug-ins). Time permitting you can think about other functionality for the tool (like generating build/execution environments for a given composition configuration expressed in your language).
This project gives you a good insight in modern component technologies (like OSGi) and the Eclipse ecosystem. Note that Eclipse is popular with several Danish software houses as a platform for developing end-user applications. You get to work with large complicated set ups, using sophisticated industrial quality technologies (learning curve can be steep, but you get skills sought for!).
Prerequisites: ideally you have background in software engineering and/or in Advanced Models and Programs (or you excelled in Advanced Object-oriented programming). Fluency in software development is expected.
Preferred size: 30 ECTS. Smaller versions possible, including a run up of 7.5 ECTS. Available at both BSc and MSc level.
Published: 2009-2-18
Use the Axivion tool suite (academic license available) to detect overlaps of code in two branches that originate in the same project - ideally an open source project that has been forked. Use the results of the analysis to propose changes in the architecture that introduce common and variable assets. Model the variability using a feature model, or some other description formalism. Implement a code generator (or a code composer) that is able to regenerate the original variants, or even their hybrids!
The project includes learning the Axivion technology (or some other clone detection tool), and selected reading on product lines (aka software factories).
This project gives you a good insight in software architecture, especially product lines architecture. As a bonus you get to work with code that you have not written yourself.
Prerequisites: ideally you have background in software engineering and/or in Advanced Models and Programs. Fluency in software development is expected. You have to read and analyze a lot of code written by others. This is harder than writing your own programs, usually, but it is a very useful skill.
Size: 30 ECTS, both at BSc and MSc level. The content of the project can be tailored slightly depending on size and level. However the best fit is 30 ECTS. For smaller versions you may take a reading course on clone detection tools and product line architectures which could also server as a good run up for the thesis.
Published: 2009-1-20
Collect feature models (and other variability models like decision models) available in the literature and collect them on a website. Write a report reflecting on the quality and diversity of the models available, characterizing the weaknesses of the sample, pointing to what kind of models are needed to support the software engineering research.
The project requires research by searching and reading literature, contacting researchers and research groups, developing a website, finding/designing a flexible meta-model (file format) for feature diagrams, converting obtained models to that format, and finally analyzing and reflecting on the obtained model.
Prerequisites: interest in software engineering, object-oriented modeling and design.
Size: 7.5 ECTS - 30 ECTS. Ideal size is 15 ECTS. The extent of the work depends on the size of the project, and the depth of reflection. The largest projects should include a small study of experimental software engineering.
Published: 2009-01-20
Study models for variability modeling, primarily feature models (literature will be provided). Build models of one or more example domains: a family of embedded systems based on manuals available on the web (for example digital camera, or media players), webhosting services across several providers, versions of Java platform (or .NET platform), services of mobile operators, or bank accounts for private customers.
Some of the domains lean themselves easily to a simple code generation project. For example one can easily implement an infrastructure to generate a manual for a particular variant of a digital camera (as opposed to a shared manual for several variants).
You are probably ready for this project if you have interest in object-oriented modeling and design, software architecture, domain specific languages, or model-driven development. The project will extend your modeling skills and expand the way of thinking about services and products from closed entities to families of configurable variants.
Size: 7.5 ECTS. A good warm up for other projects related to variability modeling.
Published: 2009-01-20
Use the Axivion tool suite (academic license available) to analyze evolution of an open source project, for example the Open for Business ERP system. The project includes learning the Axivion technology, some reading on software metrics, and very selected reading on some of the analysis algorithms. The knowledge is applied to the source code of an available system, emulating evolution, by analyzing consecutive snapshots in the SCM repository of the project.
You are expected to asses quality of evolution of the open source project in question, you are also expected to communicate with the community developing it, to verify your conclusions and recommendations. Reflection of usefulness of tools like Axivion, vs standard QA practices of open source, is welcome. Another possibility would be to explain weaknesses of Axivion, by analyzing the particular case, and algorithms used for analysis. Publications about the technology behind this tool suite are available on the web.
This project gives you a good insight in quality assurance technology for developers, and into architectural solutions used in large scale industrial strength software systems. You also get used to work with code that you have not written yourself.
Prerequisites: ideally you have background in software engineering and/or in Advanced Models and Programs. Certain fluency in software development is expected. There is no, or not much, programming expected, but you have to read and analyze a lot of code written by others. This is harder than writing your own programs, usually.
Size: anywhere from 7.5 ECTS to 30 ECTS, both at BSc and MSc level. The content of the project can be tailored depending on size and level. However the best fit is 30 ECTS. For smaller versions you may want to use a smaller project to analyze, and a more easily available static analysis tool. Alternatively you may use a smaller project to run a reading course on software metrics. In any case a small project would be a good run up for the thesis.
Published: 2008-12-11
Implement a product family of graph editors (or if you have time and resources a family of simple Class Diagram Editors, or Feature Diagram Editors). More precisely implement plugins for several IDEs (at least two) in a single code base, that provide roughly the same graph editing (modeling) functionality.
Use aspect oriented programming (AspectJ) or feature oriented programming (AHEAD) to manage variability within the family of plugins. If you are particularly interested in trying some other variability maintenance mechanism, then this is also a possibility.
A variation of this project, which can well be trimmed to a smaller project than 30 ECTS, is to design and implement one plugin, for example for Eclipse, using AspectJ or Ahead. Instead of maintaining variability caused by several embedding IDEs, introduce variability in features of the editor, that can be added or removed.
This project will give you solid experience in GUI development, background in modern programming paradigms (aspect oriented, feature oriented), and acquittance with modern component technologies (like OSGI).
Prerequisites: ideally you have background in advanced object oriented programming. Certain fluency in software development is expected.
Size: anywhere from 7.5 ECTS to 30 ECTS, both at BSc and MSc level. The content of the project can be tailored depending on size and level. However the best fit is 15 ECTS, or 30 ECTS. The smallest 7.5 ECTS, would only allow for a preliminary study (for example studying AOP or FOP).
Published: 2008-11-5
Implement a library for checking referential integrity of large collections of XML files. The theoretical basis has been laid out in Interfaces and Meta-interfaces for models and meta-models, a paper by Hessellund and myself, published at MODELS'08 conference. Expected work is to use BDDs to compute compositions of interfaces, and then script this operation so that it encompasses an entire collection. The case study should use the OfBIZ ERP system, leading to uncovering some errors.
Prerequisites: ideally you have background in Efficient AI Programming, and know about XML.
Size: anywhere from 7.5 ECTS to 30 ECTS, both at BSc and MSc level. The content of the project can be tailored depending on size and level. For example in a small version no evaluation is performed, while in a large version one needs to use the tool to track evolution of OfBIZ code base and reflect on the usefulness of the feedback. It is also possible to split this project in parts, for example 7.5 ECTS warm-up + a thesis.
Published: 2008-10-14
Collect OCL constraints available on the Internet. In your collection identify syntactic patterns that encode specific generic constraints, known in the constraints programming (CSP) community. Produce a tool compiling such a constraints into a CSP language (for example gecode or Mozart), or produce a design document for an OCL revision with specific constraints. Such a language extension could have a compiler to a regular OCL (to exploit existing tools) and to a CSP language (to exploit constraint programming tools).
Prerequisites: ideally a combination of competences from specialisations on Models & Programs, and Scalable Computing (some courses from each).
Size: between 7.5 and 30 ECTS.
Published: 2008-07-20
Study UML sequence diagrams and related modeling languages (message sequence charts, live sequence charts) and existing work on establishing consistency between several such models. Try to see if Common Implementation (CI) of Modal Transition Systems can be reduced to this consistency problem, effectively establishing EXPTIME-completeness of the consistency problem. Argue for hardness of consistency for different modifications of the language separately. Ask me for related reading if interested.
This work comprises software engineering issues (design of modeling languages), theoretical complexity work, and a drop of concurrency theory. A similar project can be defined for the problem of refinement/generalization between two diagrams.
Prerequisites: Ideally you know the language of sequence diagrams and have followed Advanced Algorithms. In general: combinations of courses from Models and Programs, Distributed Systems and Scalable Computing are fine. You should be mathematically inclined (but not a "hard-core" mathematician).
Size: between 7.5 and 30 ECTS.
Published: 2008-07-20
Design a domain sepcific language (DSL) for abstract and
concise specification of JUnit test-cases. For example, specify tests
like that: test method F with parameter objects A, B such that A.amount
<100 && B.category == VIP.
You should implement a generator of JUnit tests from your constraints, most
likely using an existing constraint solver (like gecode, alloy, or an ILP
solver). Consider adding quantifiers, like "generate-all", "select-one", or
"select-k", to your language. Provide feedback for the modeler how tight the
constraints are (the number of possible test cases satisfying a
constraint). Ask me for related reading, if interested.
If you really insist, this project can be realized for .NET (not necessarily for Java), or even for your other favorite programming language with a unit test framework. This project is particularly well suited for splitting into several parts (for example into a 7.5 ECTS preliminary study and a thesis).
Size: between 7.5 and 30 ECTS. For whom: ideally you have taken some courses from Models and Programs specialization and have followed Efficient AI Programming (IAIP).
Published: 2008-07-20
Study graphical library JHotDraw – as an example of a programing framework. Define a domain specific language modeling usage of several JHotDraw API concepts. The domain specific language can be seen as a formal version of a collection of cookbooks. Use grammars, or class-diagrams/feature models (metamodels) with some constraints to define the DSL.
Implement several analyses (AST based, control flow based) detecting some instances of the concepts in existing JHotDraw applications. Alternatively: implement generation of code skeletons from models in your DSL. Yet alternatively: do both.
It is possible to work with other frameworks than JHotDraw. Some examples are listed in Kirk. Roper. Wood. Identifying and addressing problems in object-oriented framework reuse. Another excellent object to study is JUnit or its derived testing frameworks.
Size: between 7.5 and 30 ECTS. For whom: ideally you follow or have followed SASP (Advanced Models and Programs).
Updated: 2008-10-25
Build an interactive configurator for constraint systems, which on top of usual combinatorial constraints allow expressing soft dependencies (for example if a car is sold in USA then it will have an automatic gear with probability 0.9). The configurator should use Bayesian Networks as an underlying representation (or some compiled form of BN) and it should be able to compute valid domains, given choices already made by a user. For each value in the valid domain, a probability of this value being selected by the user should be calculated.
We provide configuration algorithms and supervision. So this work is primarily about creating an efficient implementation of abstract ideas.
For whom: Ideally you are interested in constraint programming, know about interactive configuration and are not scared of simple discrete probability theory. Acquaintance with bayesian inference would be an advantage but it is not required.
Size: between 7.5 - 30 ECTS (we will scale it to your needs). ideally for 2 persons, but lone rangers also welcome.
Published: 2008-02-26
Each mixed transition system describes a set of implementation. So does each modal transition system. However modal transition systems are a strict subset of mixed transition systems. The claim is that mixed transition systems are polynomially more succinct in the sense that the set of all implementations of a mixed modal transition systems, can be described as an intersection of sets of all implementations of a polynomial number of modal transition systems. Prove this by proposing suitable reductions and arguing for their correctness. Talk to AW about details.
Prerequisites: This is a topic in theoretical computer science. You should know some basics of concurrency theory (transition systems, bisimulation, simulation) and some basics of complexity theory (for example by following Advanced Algorithms at ITU).
Published: 2007-10-29
The problem is to translate a logical formula represented as a binary decision diagram to a possibly concise and readable textual representation. Investigate known methods, design your own, and implement.
Prerequisites: Efficient AI and Programming (IAIP) or knowledge of BDDs and propositional logics.
Added: 2007-10-17
Read Modal I/O Automata for Interface and Product Line Theories by Larsen, Nyman and Wąsowski. Design a compatibility checking tool based on section 6 of that work (this includes designing syntax for modeling language of modal I/O automata). Or, if you prefer, work on designing, analyzing and implementing the algorithm for deriving a decomposition of a complex system of requirements. Existance of such an algorithm is hinted by Theorem 14.
Prerequisites: the course on Mobile and Distributed Systems at ITU, or some other semantics course. Algorithms and Data Structures. If you want to implement stuff then some compiler implementation experience could be useful.
Added: 2007-09-17
Linux kernel is an amazingly configurable system. It has an enormous number of parameter, and it is always perplexing for unexperienced hackers to configure and compile it. Still the kernel configurations available on the web are fairly limited. It seems that not more than several hundreds configurations are published instead of gazillions of the possible choices. It would be interesting to try to analyze whether this variability could not be abstracted (simplified) for most typical users.
The task is to mine the Internet for available kernel configurations. Then this set of configurations should be analyzed to see what is the variability exhibited by the actually used configurations, as apposed to the variability specification in the kernel source files themselves. One possible method for doing that was published by Felix Loesch (Optimization of Variability in Software Product Lines, SPLC 2007). You can propose other complex projects in place of the Linux kernel for such a project.
Added: 2007-09-13
Extract variability information from autotools files and source files of some open source project. Create a constraint model of the information parsed and visualize it (for example as a feature model using the technique presented in Feature Models and Logics: There and Back Again by Czarnecki and Wąsowski in SPLC 2007).
Prerequisites: prior programming language and compiler experience, which can be obtained by following the specialization on Models & Programs at ITU. It is helpful to have some prior experience with compiling open-source software (for example linux kernel, gcc, mozilla, etc), though this is not strictly necessary.
Added: 2007-09-13
Assume a configurable product, or a software product line, having k options (features) that control the configuration or product selection (let the options be binary for simplicity). On top of that there is a number of combinatorial constraints controlling what are legal combinations of options. Typically the number of all legal configurations is lower than 2k, because of the constraints, but it is still too large to consider testing the application in all variants (configurations). Instead one can use n-way interaction testing, for some positive natural number n.
N-way interaction testing makes an assumption that most realistic errors can be exhibited by finding combinations of options (features) that interact in a bad way, hoping that it is small sets of selections combined that already exhibit errors. In particular 2-way testing assumes that it is enough to test all pairs of feature selections to uncover more errors (3-way testing requires testing triples of combinations, etc).
The essential observation here is that testing one instance of a product (one configuration) establishes the test outcome for many n-tuples of feature combinations. In particular for k features and 2-way case testing, one instance can be used to test up to k(k-1)/2 (roughly quadratic) number of feature interactions. So instead od running an exponential number of tests, one can hope to succeed with much smaller number of instances.
The problem is to generate a minimal set of instances (feature configurations) that is enough to do n-way testing (of all n-feature combinations). Minimality (or almost minimality) is essential here, as running tests on each instance is presumable time consuming. Prerequisites: for ITU students it is best to take "Scalable Computing" as specialization, or at least the first of its two courses.
Added: 2007-09-13
| Updated: Andrzej Wąsowski Feb 07, 2010 22:18 |
|---|