Search

We aim to access entropy sources available within smartphones in order to construct and evaluate a random number generator which is competitive in comparison with existing and proven random number generators. A prototype utilizing the herein proposed algorithm shall generate data that can be tested against the Statistical Test Suit provided by NIST. Although our initial intention of using cosmic radiation failed, we were able to extract randomness from incoming video and audio sources. We found that it is possible to access these sources of entropy utilizing sensors from smartphones resulting in 15 out of 15 successful passed tests within the Statistical Test Suit. We also found that wrong methods of sensor data collection using our prototype eventually generates weak random numbers and fails NIST's Statistical Test Suit. Finally, we suggest that in order to reach the initial goal of providing a smartphone-based true nondeterministic random number generator the detection of muons shall be researched., Comment: Submitted to (IEEE) International Conference on Electrical, Computer, Communications and Mechatronics Engineering - ICECCME'22; 16-18 November 2022, Maldives

Educational games are commonly used to motivate students and provide enhanced learning opportunities. Apps and mobile games play an increasingly important role in education and smartphones are part of the daily lives of most female teenagers: Half of mobile gamers are women and 64% of women prefer smartphones to other platforms. However, gender differences in playing behaviour and preferences raises concerns about potential gender inequalities when games are developed for education. In order to develop a tutorial game that suits the female target group and provides challenging tasks to solve, girls were involved at a very early stage of the development cycle and the idea was developed on the basis of surveys and focus group discussions. A first prototype of the game has been tested in a mixed-gender group to get feedback about the learning content, the worked examples, and the whole structure of the game. Finally, a tutorial game with six worked examples has been released in our Luna&Cat app, a programming tool that has been designed for our female target group in particular., Comment: Constructionism 2020, Dublin/Ireland May, 24-25, 2020, 12 figures, 9 pages

Knowledge in Computer Science (CS) is essential, and companies have increased their demands for CS professionals. Despite this, many jobs remain unfilled. Furthermore, employees with computational thinking (CT) skills are required, even if they are not actual technicians. Moreover, the gender disparity in technology related fields is a serious problem. Even if companies want to hire women in technology, the number of women who enter these fields is remarkably low. In high schools, most teenagers acquire only low-level skills in CS. Thus, they may never understand the fundamental concepts of CS, have unrealistic expectations or preconceptions, and are influenced by stereotype-based expectations. Consequently, many teenagers exclude computing as a career path. In this research study, we present two promising concepts to overcome these challenges. First, we consider alternative paths to enter the field of CS. In 2018, a voluntary lecture "Design your own app" at the University of Graz for students of all degree programs was introduced. In total, 202 students participated. We applied a Game Development-Based Learning (GDBL) approach with the visual coding tool Pocket Code, a mobile app developed at Graz University of Technology. The students were supposed to create simple games directly on smartphones. The course received positive evaluations and led to our second concept; In January 2019, we started to design a MOOC (Massive Open Online Course) with the title "Get FIT in Computer Science". First, this course can be used to encourage young women who have little to no previous knowledge in CS. Second, it should help all teenagers to get a more realistic picture of CS to its basic concepts. Third, teachers can use the course materials to lead high school classes (Open Educational Resources). Finally, the MOOC can be accessed by everyone interested in this topic., Comment: 9 pages, 4 figures, ECGBL 2019, Odense, Denmark

Recent studies from all over the world show that more boys than girls play video games. The numbers are different for mobile gaming apps, where 65% of women are identified as gamers. Adapting game design activities for academic purposes is a widely applied approach at schools or off-school initiatives is seen as a promising opportunity for all teenagers to learn to code in an entertaining way. This raise the questions do special girls' game-design patterns exist, and what can we learn from them? This paper describes a girl-only intervention where girls were asked to create their own games. This "Girls' Coding Week" was designed as an off-school event and took place during summer 2018 with 13 girls between 11 to 14 years old. To explain the basic steps of programming and to create personalized games, the visual coding app Pocket Code, an app developed at Graz University of Technology, was used. The girls created their own games with the help of a storyboard after receiving all important information about coding. Qualitative and quantitative data was collected through open interviews, as well as created artefacts and surveys which refer to motivational aspects. The findings show that gaming elements female teenagers tend to like, create, and play, mostly follow stereotypical expectations. In contrast to our experiences in heterogeneous course settings, this was not seen as something negative by girls. Furthermore, the findings provided evidence for game-making environments for girls. Subsequently, the results contributed to the development of new featured games to be used in our app to inspire female users around the world to code their own games. The authors argue that by understanding these differences in game design, we can support girls so that they become game designers and thereby more interested in coding., Comment: 10 pages, 11 Figures, 13th European Conference on Game Based Learning

The number of women in IT-related disciplines is far below the number of men, especially in developed countries. Middle-school girls appear to be engaged in coding courses, but when they choose academic majors relevant to their future careers, only few pursue computer science as a major. In order to show students a new way of learning and to engage them with coding activities, we used the learning app Pocket Code. In the "No One Left Behind" H2020 European project, the app was evaluated in several school subjects. An evaluation of the attractiveness of the app shows that students were motivated by Pocket Code's ease of use and its appealing design; however, girls rated the app less enthusiastically. To appeal to female teenagers in particular, a tailored version of the app "Luna&Cat" has been developed. This customised version stands in contrast to the "one size fits all" solution Pocket Code, which may discourage certain user groups. For apps to have a higher chance to appeal to a specific target group, it is, among many other points, necessary to optimise their store listing on app stores, especially as we found that app stores are the most effective way to reach teenagers. Thus, this paper covers the following research question. What customizations are necessary in Pocket Code to reinforce female teenagers in their coding activities? To answer this question, a focus group discussion was performed. This discussion first brought insights about our target group and suggested names and designs for the new app; and second, allowed each student to make proposals for their desired games. Later, these game ideas were analysed, graphically designed, and further developed together with university design students. By showing female teenagers games designed by other young women in their age group, we help them to get ideas and inspiration to code their own programs., Comment: 10 pages, 6 figures, Proceedings of the 2nd International Conference on Gender Research ICGR 2019 Rom, Italy, 11-12 April 2019 isbn: 978-1-912764-16-7,issn: 2516-2810, Academic Conferences and Publishing International Limited

Although female students engage in coding courses, only a small percentage of them plan to pursue computer science (CS) as a major when choosing a career path. Gender differences in interests, sense-of belonging, self-efficacy, and engagement in CS are already present at an early age. This article presents an overview of gender stereotypes in CS and summarizes negative impressions female students between 12 and 15 experience during CS classes, as well as influences that may be preventing girls from taking an interest in CS. The study herein draws on a systematic review of 28 peer-reviewed articles published since 2006. The findings of the review point to the existence of the stereotypical image of a helpless, uninterested, and unhappy "Girl in Computer Science". It may be even more troubling a construct than that of the geeky, nerdy male counterpart, as it is rooted in the notion that women are technologically inept and ill-suited for CS careers. Thus, girls think they must be naturally hyper-intelligent in order to pursue studies in CS, as opposed to motivated, interested, and focused to succeed in those fields. Second, based on the review, suggestions for inclusive CS education were summarized. The authors argue that in order to make CS more inclusive for girls, cultural implications, as well as stereotypization in CS classrooms and CS education, need to be recognized as harmful. These stereotypes and cultural ideas should be eliminated by empowering female students through direct encouragement, mentoring programs, or girls-only initiatives., Comment: 22 pages

Most of the 700 million teenagers everywhere in the world already have their own smartphones, but comparatively few of them have access to PCs, laptops, OLPCs, Chromebooks, or tablets. The free open source non-profit project Catrobat allows users to create and publish their own apps using only their smartphones. Initiated in 2010, with first public versions of our free apps since 2014 and 47 releases of the main coding app as of July 2018, Catrobat currently has more than 700,000 users from 180 countries, is available in 50+ languages, and has been developed so far by almost 1,000 volunteers from around the world ("the world"). Catrobat is strongly inspired by Scratch and indeed allows to import most Scratch projects, thus giving access to more than 30 million projects on our users' phones as of July 2018. Our apps are very intuitive ("rock bottom"), have many accessibility settings, e.g., for kids with visual or cognitive impairments, and there are tons of constructionist tutorials and courses in many languages. We also have created a plethora of extensions, e.g., for various educational robots, including Lego Mindstorms and flying Parrot quadcopters ("the sky"), as well as for controlling arbitrary external devices through Arduino or Raspberry Pi boards, going up to the stratosphere and even beyond to interplanetary space ("the sky"). A TurtleStitch extension allowing to code one's own embroidery patterns for clothes is currently being developed. Catrobat among others intensely focuses on including female teenagers. While a dedicated version for schools is being developed, our apps are meant to be primarily used outside of class rooms, anywhere and in particular outdoors ("rock bottom", "the world"). Catrobat is discovered by our users through various app stores such as Google Play and via social media channels such as YouTube as well as via our presence on Code.org., Comment: Constructionism 2018

Game jams are a way to create games under fast-paced conditions and certain constraints. The increase in game jam events all over the world, their engaging and creative nature, with the aim of sharing results among players can be seen in the high participation rate of such events (2013: 16,705 participants from 319 jam sites in 63 countries produced 3248 games) . This promising concept can be easily transferred to a classroom setting., Comment: 4 pages, 3 figures, ICGBL 2016

This paper will present a cross-European experience of game jams as part of a Horizon 2020 funded project: No-one Left Behind (NOLB). The NOLB project was created to unlock inclusive gaming creation and experiences in formal learning situations from primary to secondary level, particularly for children at risk of social exclusion. The project has engendered the concept of game jams, events organised with the aim of designing and creating small games in a short time-frame around a central theme. Game jams can support engagement with informal learning beyond schools across a range of disciplines, resulting in an exciting experience associated with strong, positive emotions which can significantly support learning goals. This paper will disseminate experience of two cross-European game jams; the first a pilot and the second having over 95 submissions from countries across Europe, America, Canada, Egypt, the Philippians and India. Data collected through these games jams supports that coding, designing, reflection, analysing, creating, debugging, persevering and application, as well as developing computational thinking concepts such as decomposition, using patterns, abstraction and evaluation. The notion of game jams provides a paradigm for creating both formal and informal learning experiences such as directed learning experience, problem-solving, hands-on projects, working collaboratively, and creative invention, within a learner-centred learning environment where children are creators of their own knowledge and learning material., Comment: 10 pages, 4 figures, 2 tables, EduLearn 2016

Learning theories emphasize the importance of intrinsic and extrinsic motivators in curricula, and games are a promising way to provide both while constructing the game and presenting or sharing it in public or with a community. New technologies and the emerging mobile gaming sector further the case that learning should be promoted everywhere and anytime. What seems to be a promising opportunity for all pupils to learn coding in an entertaining way raises the question of whether such game based concepts also help to fix the gender gap of women in IT related fields. Gender differences are already present in secondary schools. These are the years where first career choices but also low levels of participation in technical subjects occur. To address this gender bias, a goal of the European project No One Left Behind (NOLB) was to integrate Pocket Code, an app developed by Catrobat, a free open source non-profit project at the University of Technology in Graz/Austria, into different school subjects, thus making coding more accessible and attractive to female pupils. During the period of this project (2015-2017), teachers were supported to guide their pupils in the learning processes by constructing ideas and realizing them through game design. For this paper an analysis of submitted programs according to their game design has been performed. In detail, the evaluation considered formal game elements, gaming structures, and used graphics, as well as Pocket Code specific aspects. The programs analysis showed commonly used design patterns by genders and suggests preferred game design characteristics of female teenagers. This analysis helps to build a more creative and inclusive Game Development-Based Learning (GDBL) environment that provides room for self-expression and inspires by building on intrinsic and extrinsic motivators by constructing personal experiences., Comment: 10 pages, 8 figures, ECGBL 2018

The number of women in technical fields is far below the average number of males, especially in developed countries. Gender differences in STEM are already present in secondary schools in students aged between 12 to 15 years. Adolescence is a critical time for identity formation, and self-attributes are a source for internal conflicts, especially for female teenagers. It is during this intermediate female adolescence that girls begin to make critical career choices, which therefore makes this a key age to reinforce them and reduce the gender disparities in ICT. Computational thinking skills are important from a philosophical point of view, since they allow us to understand the foundations of rational thought in a clear, easily understandable, but also inspiring and challenging way. To address the gender bias in schools, one of the goals of the European H2020 project No One Left Behind (NOLB) included integrating Pocket Code, a free open source app developed by the non-profit project Catrobat, into different school lessons. Through game design, Pocket Code allows teenage girls to incorporate diversity and inclusiveness, as well as the ability to reflect their cultural identity, their emotions, their likes, and their ways of interacting and thinking. To evaluate the impact of the use of the app in these courses, we captured the results on engaging girls in design and coding activities. For this paper, the authors present the data of surveys during the second cycle of the project. With a focus on female teenagers, the results allow us to conclude that a suitable classroom setting is significantly more important for them than the coding tool itself., Comment: 12 pages, 8 figures, Constructioism 2018

Game creation challenges in schools potentially provide engaging, goal-oriented, and interactive experiences in classes; thereby supporting the transfer of knowledge for learning in a fun and pedagogic manner. A key element of the ongoing European project No One Left Behind (NOLB) is to integrate a game-making teaching framework (GMTF) into the educational app Pocket Code. Pocket Code allows learners to create programs in a visual Lego-style way to facilitate learning how to code at secondary high schools. The concept of the NOLB GMTF is based on principles of the Universal Design for Learning (UDL) model. This framework provides a coherent approach to learning and teaching by integrating leisure oriented gaming methods into multi-discipline curricula. One output of this framework is the integration of game-based methods via game templates that refer to didactical scenarios that include a refined set of genres, assets, rules, challenges, and strategies. These templates allows: 1) teachers to start with a well-structured program, and 2) pupils to add content and adjust the code to integrate their own ideas. During the project game genres such as adventure, action, and quiz, as well as rewards or victory point mechanisms, have been embedded into different subjects, e.g., science, mathematics, and arts. The insights gained during the class hours were used to generate 13 game templates, which are integrated in Create@School (a new version of the Pocket Code app which targets schools). To test the efficiency of these templates, user experience (UX) tests were conducted during classes to compare games created by pupils who used templates and those who started to create a game from scratch. Preliminary results showed that these templates allow learners to focus on subject-relevant problem solving activities rather than on understanding the functionality of the app., Comment: 10 pages, 5 figures, 4 tables European Conference of game based learning (ECGBL)

The constructionist approach is more interested in constructing personal experience than about acquiring information. It states that learning is most effective when building knowledge through active engagement. Experiential and discovery learning by challenges inspire creativity, and projects allow independent thinking and new ways of learning information. This paper describes how the "No One Left Behind" (NOLB) project plans to integrate this approach into school curricula using two concepts. The first one is to enable students to create their own games with Pocket Code by using its easy-to-learn visual programming language. The second concept is to foster collaboration and teamwork through hands-on sessions by conducting Game Jams using Pocket Code, so called Pocket Game Jams. We present insights into such a Pocket Game Jam and give an outlook on how we will use this concept., Comment: 5 pages, MobiHCI 2015

The next generation of jobs will be characterized by an increased demand for people with computational and problem solving skills. In Austria, computer science topics are underrepresented in school curricula hence teaching time for these topics is limited. From primary through secondary school, only a few opportunities exist for young students to explore programming. Furthermore, today's teachers are rarely trained in computer science, which impairs their potential to motivate students in these courses. Within the "No One Left Behind" (NOLB) project, teachers were supported to guide and assist their students in their learning processes by constructing ideas through game making. Thus, students created games that referred to different subject areas by using the programming tool Pocket Code, an app developed at Graz University of Technology (TU-Graz). This tool helps students to take control of their own education, becoming more engaged, interested, and empowered as a result. To ensure an optimal integration of the app in diverse subjects the different backgrounds (technical and non-technical) of teachers must be considered as well. First, teachers were supported to use Pocket Code in the different subjects in school within the feasibility study of the project. Observed challenges and difficulties using the app have been gathered. Second, we conducted interviews with teachers and students to underpin our onsite observations. As a result, it was possible to validate Pocket Codes' potential to be used in a diverse range of subjects. Third, we focused especially on those teachers who were not technically trained to provide them with a framework for Pocket Code units, e.g., with the help of structured lesson plans and predefined templates., Comment: 10 pages, 5 tables EduLearn 2017

The widespread use of mobile phones is changing how learning takes place in many disciplines and contexts. As a scenario in a constructionist learning environment, students are given powerful tools to create games using their own ideas. In the "No One Left Behind" (NOLB) project we will study through experimental cycles whether the use of mobile game design has an impact on learning, understanding, and retention of knowledge for students at risk of social exclusion. We will use the mobile learning app Pocket Code with partner schools in three countries: Austria, Spain, and the UK. This paper focuses on the Austrian pilot, which is exploring gender inclusion in game creation within an educational environment. We first study differences in game creation between girls and boys. This study that started in September 2015, will help teachers to integrate Pocket Code effectively into their courses. For future studies an enhanced school version of Pocket Code will be designed using the results and insights gathered at schools with pupils and teachers., Comment: 8 pages, 3 figures, 1 table, Constructionism 2016

Pocket Code is a free and open source mobile visual programming system for the Catrobat language. It allows users, starting from the age of eight, to develop games and animations with their smartphones. Children can create programs with their Android phone, iPhone, Windows Phone, or other smartphone with an HTML5 browser. No notebook or desktop computer is needed. Pocket Code is inspired by, but distinct from, the Scratch programming system developed by the Lifelong Kindergarten Group at the MIT Media Lab. This tool demo describes an in-practice experience with Pocket Code, the Windows Phone IDE for the Catrobat language., Comment: 2 pages, 5 figures, Published in PRoMoTo'13 [arXiv:1309.5500]

The emergence of cloud computing presents a strategic direction for critical infrastructures and promises to have far-reaching effects on their systems and networks to deliver better outcomes to the nations at a lower cost. However, when considering cloud computing, government entities must address a host of security issues (such as malicious insiders) beyond those of service cost and flexibility. The scope and objective of this paper is to analyze, evaluate and investigate the insider threat in cloud security in sensitive infrastructures as well as to propose two proactive socio-technical solutions for securing commercial and governmental cloud infrastructures. Firstly, it proposes actionable framework, techniques and practices in order to ensure that such disruptions through human threats are infrequent, of minimal duration, manageable, and cause the least damage possible. Secondly, it aims for extreme security measures to analyze and evaluate human threats related assessment methods for employee screening in certain high-risk situations using cognitive analysis technology, in particular functional magnetic Resonance Imaging (fMRI). The significance of this research is also to counter human rights and ethical dilemmas by presenting a set of ethical and professional guidelines. The main objective of this work is to analyze related risks, identify countermeasures and present recommendations to develop a security awareness culture that will allow cloud providers to utilize effectively the benefits of this advanced techniques without sacrificing system security.

We developed a website for kids where they can share new as well as remixed animations and games, e.g., interactive music videos, which they created on their smartphones or tablets using a visual "LEGO-style" programming environment called Catroid. Online communities for children like our website have unique requirements, and keeping the commitment of kids on a high level is a continuous challenge. For instance, one key motivator for kids is the ability to entertain their friends. Another success factor is the ability to learn from and cooperate with other children. In this short position paper we attempt at identifying the requirements for the success of such an online community, both from the point of view of the kids as well as of their parents, and at finding ways to make it attractive for both., Comment: 4 pages; short paper at the 11th International Conference on Interaction Design and Children (IDC2012)

Catroid is a free and open source visual programming language, programming environment, image manipulation program, and website. Catroid allows casual and first-time users starting from age eight to develop their own animations and games solely using their Android phones or tablets. Catroid also allows to wirelessly control external hardware such as Lego Mindstorms robots via Bluetooth, Bluetooth Arduino boards, as well as Parrot's popular and inexpensive AR.Drone quadcopters via WiFi., Comment: 4 pages. Demo paper at the 11th International Conference on Interaction Design and Children (IDC 2012)

Recent reports reveal that violent extremists are trying to obtain insider positions that may increase the impact of any attack on critical infrastructure and could potentially endanger state services, people's lives and even democracy. It is of utmost importance to be able to adopt extreme security measures in certain high-risk situations in order to secure critical infrastructure and thus lower the level of terrorist threats while preserving the rights of citizens. To counter these threats, our research is aiming for extreme measures to analyse and evaluate human threats related assessment methods for employee screening and evaluations using cognitive analysis technology, in particular functional Magnetic Resonance Imaging (fMRI). The development of fMRI has led some researchers to conclude that this technology has forensic potential and may be useful in investing personality traits, mental illness, psychopathology, racial prejudice and religious extremism. However, critics claim that this technology may present many new human rights and ethical dilemmas and could result in potentially disastrous outcomes. The main thrust of the research is to counter above concerns and harmful consequences by presenting a set of ethical and professional guidelines that will substantially reduce the risk of unethical use of this technology. The significance of this research is to ensure the limits of the state/organisation's right to peer into an individual's thought process with and without consent, to define the parameters of a person's right to ensure that fMRI scans do not pose more than an appropriate threat to cognitive liberty, and the proper use of such information in civil, forensic and security settings.

We submitted two kinds of strategies to the iterated prisoner's dilemma (IPD) competitions organized by Graham Kendall, Paul Darwen and Xin Yao in 2004 and 2005. Our strategies performed exceedingly well in both years. One type is an intelligent and optimistic enhanced version of the well known TitForTat strategy which we named OmegaTitForTat. It recognizes common behaviour patterns and detects and recovers from repairable mutual defect deadlock situations, otherwise behaving much like TitForTat. The second type consists of a set of strategies working together as a team. These group strategies have one distinguished individual Godfather strategy that plays OmegaTitForTat against non-members while heavily profiting from the behaviour of the other members of his group, the Hitman. The Hitman willingly let themselves being abused by their Godfather while themselves lowering the scores of all other players as much as possible, thus further maximizing the performance of their Godfather in relation to other participants. The study of collusion in the simplified framework of the iterated prisoner's dilemma allows us to draw parallels to many common aspects of reality both in Nature as well as Human Society, and therefore further extends the scope of the iterated prisoner's dilemma as a metaphor for the study of cooperative behaviour in a new and natural direction. We further provide evidence that it will be unavoidable that such group strategies will dominate all future iterated prisoner's dilemma competitions as they can be stealthy camouflaged as non-group strategies with arbitrary subtlety. Moreover, we show that the general problem of recognizing stealth colluding strategies is undecidable in the theoretical sense.

We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is $s$-chromatic if it is colorable in $s$ colors and any coloring of it uses at least $s$ colors. The forcing chromatic number $F(G)$ of an $s$-chromatic graph $G$ is the smallest number of vertices which must be colored so that, with the restriction that $s$ colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of $F(G)$ relating it to the complexity class US introduced by Blass and Gurevich. We prove that recognizing if $F(G)\le 2$ is US-hard with respect to polynomial-time many-one reductions. Moreover, this problem is coNP-hard even under the promises that $F(G)\le 3$ and $G$ is 3-chromatic. On the other hand, recognizing if $F(G)\le k$, for each constant $k$, is reducible to a problem in US via disjunctive truth-table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph., Comment: 24 pages; This is the final version

Given a graph $G$, we consider a game where two players, $A$ and $B$, alternatingly color edges of $G$ in red and in blue respectively. Let $l(G)$ be the maximum number of moves in which $B$ is able to keep the red and the blue subgraphs isomorphic, if $A$ plays optimally to destroy the isomorphism. This value is a lower bound for the duration of any avoidance game on $G$ under the assumption that $B$ plays optimally. We prove that if $G$ is a path or a cycle of odd length $n$, then $\Omega(\log n)\le l(G)\le O(\log^2 n)$. The lower bound is based on relations with Ehrenfeucht games from model theory. We also consider complete graphs and prove that $l(K_n)=O(1)$., Comment: 20 pages

In the graph avoidance game two players alternatingly color edges of a graph G in red and in blue respectively. The player who first creates a monochromatic subgraph isomorphic to a forbidden graph F loses. A symmetric strategy of the second player ensures that, independently of the first player's strategy, the blue and the red subgraph are isomorphic after every round of the game. We address the class of those graphs G that admit a symmetric strategy for all F and discuss relevant graph-theoretic and complexity issues. We also show examples when, though a symmetric strategy on G generally does not exist, it is still available for a particular F., Comment: 14 pages, 6 figures; for a video of a talk based on a preliminary version see http://www.msri.org/publications/ln/msri/2000/gametheory/slany/1/index.html For related material see http://www.dbai.tuwien.ac.at/proj/ramsey/

Generating high-quality schedules for a rotating workforce is a critical task in all settings where a certain staffing level must be guaranteed beyond the capacity of single employees, such as for instance in industrial plants, hospitals, or airline companies. Results from ergonomics \cite{BEST91} indicate that rotating workforce schedules have a profound impact on the health and social life of employees as well as on their performance at work. Moreover, rotating workforce schedules must satisfy legal requirements and should also meet the objectives of the employing organization. We describe our solution to this problem. A basic design decision was to aim at quickly obtaining high-quality schedules for realistically sized problems while maintaining human control. The interaction between the decision maker and the algorithm therefore consists in four steps: (1) choosing a set of lengths of work blocks (a work block is a sequence of consecutive days of work shifts), (2) choosing a particular sequence of work and days-off blocks among those that have optimal weekend characteristics, (3) enumerating possible shift sequences for the chosen work blocks subject to shift change constraints and bounds on sequences of shifts, and (4) assignment of shift sequences to work blocks while fulfilling the staffing requirements. The combination of constraint satisfaction and problem-oriented intelligent backtracking algorithms in each of the four steps allows to find good solutions for real-world problems in acceptable time. Computational results from real-world problems and from benchmark examples found in the literature confirm the viability of our approach. The algorithms are now part of a commercial shift scheduling software package., Comment: 24 pages, uses dbairep.sty

We consider combinatorial avoidance and achievement games based on graph Ramsey theory: The players take turns in coloring still uncolored edges of a graph G, each player being assigned a distinct color, choosing one edge per move. In avoidance games, completing a monochromatic subgraph isomorphic to another graph A leads to immediate defeat or is forbidden and the first player that cannot move loses. In the avoidance+ variants, both players are free to choose more than one edge per move. In achievement games, the first player that completes a monochromatic subgraph isomorphic to A wins. Erdos & Selfridge (1973) were the first to identify some tractable subcases of these games, followed by a large number of further studies. We complete these investigations by settling the complexity of all unrestricted cases: We prove that general graph Ramsey avoidance, avoidance+, and achievement games and several variants thereof are PSPACE-complete. We ultra-strongly solve some nontrivial instances of graph Ramsey avoidance games that are based on symmetric binary Ramsey numbers and provide strong evidence that all other cases based on symmetric binary Ramsey numbers are effectively intractable. Keywords: combinatorial games, graph Ramsey theory, Ramsey game, PSPACE-completeness, complexity, edge coloring, winning strategy, achievement game, avoidance game, the game of Sim, Polya's enumeration formula, probabilistic counting, machine learning, heuristics, Java applet, Comment: 47 pages; To actually play small but nontrivial game instances, go to http://www.dbai.tuwien.ac.at/proj/ramsey/

Real world combinatorial optimization problems such as scheduling are typically too complex to solve with exact methods. Additionally, the problems often have to observe vaguely specified constraints of different importance, the available data may be uncertain, and compromises between antagonistic criteria may be necessary. We present a combination of approximate reasoning based constraints and iterative optimization based heuristics that help to model and solve such problems in a framework of C++ software libraries called StarFLIP++. While initially developed to schedule continuous caster units in steel plants, we present in this paper results from reusing the library components in a shift scheduling system for the workforce of an industrial production plant., Comment: 33 pages, 9 figures; for a project overview see http://www.dbai.tuwien.ac.at/proj/StarFLIP/