liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Färnqvist, Tommy
Publications (10 of 12) Show all publications
Färnqvist, T., Heintz, F., Lambrix, P., Mannila, L. & Wang, C. (2016). Supporting Active Learning by Introducing an Interactive Teaching Tool in a Data Structures and Algorithms Course. In: Proceedings of the 47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016): . Paper presented at 47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016), Memphis, Tennessee, USA, March 2-5, 2016 (pp. 663-668). ACM Publications
Open this publication in new window or tab >>Supporting Active Learning by Introducing an Interactive Teaching Tool in a Data Structures and Algorithms Course
Show others...
2016 (English)In: Proceedings of the 47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016), ACM Publications, 2016, p. 663-668Conference paper, Published paper (Refereed)
Abstract [en]

Traditionally, theoretical foundations in data structures and algorithms (DSA) courses have been covered through lectures followed by tutorials, where students practise their understanding on pen-and-paper tasks. In this paper, we present findings from a pilot study on using the interactive e-book OpenDSA as the main material in a DSA course. The goal was to redesign an already existing course by building on active learning and continuous examination through the use of OpenDSA. In addition to presenting the study setting, we describe findings from four data sources: final exam, OpenDSA log data, pre and post questionnaires as well as an observation study. The results indicate that students performed better on the exam than during previous years. Students preferred OpenDSA over traditional textbooks and worked actively with the material, although a large proportion of them put off the work until the due date approaches.

Place, publisher, year, edition, pages
ACM Publications, 2016
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-122401 (URN)10.1145/2839509.2844653 (DOI)978-1-4503-3685-7 (ISBN)
Conference
47th ACM Technical Symposium on Computer Science Education (SIGCSE 2016), Memphis, Tennessee, USA, March 2-5, 2016
Available from: 2015-11-01 Created: 2015-11-01 Last updated: 2018-12-06Bibliographically approved
Engstrom, R., Färnqvist, T., Jonsson, P. & Thapper, J. (2015). An Approximability-related Parameter on Graphs - Properties and Applications. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 17(1), 33-66
Open this publication in new window or tab >>An Approximability-related Parameter on Graphs - Properties and Applications
2015 (English)In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, ISSN 1462-7264, Vol. 17, no 1, p. 33-66Article in journal (Refereed) Published
Abstract [en]

We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (MAX H-COL), which is a restriction of the general maximum constraint satisfaction problem (MAX CSP) to a single, binary, and symmetric relation. Using known approximation ratios for MAX k-CUT, we obtain general asymptotic approximability results for MAX H-COL for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Samal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as MAX H-COL.

Place, publisher, year, edition, pages
DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 2015
Keywords
graph H-colouring; approximation; graph homomorphism; circular colouring; combinatorial optimisation; graph theory
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-117670 (URN)000352198400003 ()
Note

Funding Agencies|National Graduate School in Computer Science (CUGS), Sweden; Center for Industrial Information Technology (CENIIT) [04.01]; Swedish Research Council (VR) [2006-4532, 621-2009-4431]; European Communitys Seventh Framework Programme (FP7) [257039]; LIX-Qualcomm Postdoctoral Fellowship

Available from: 2015-05-11 Created: 2015-05-06 Last updated: 2018-01-11
Heintz, F., Färnqvist, T. & Thorén, J. (2015). Programutvecklingsstrategier för att öka kopplingen mellan programmering och matematik. In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng): . Paper presented at 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng) Uppsala universitet, 18 - 19 november 2015.
Open this publication in new window or tab >>Programutvecklingsstrategier för att öka kopplingen mellan programmering och matematik
2015 (Swedish)In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 2015Conference paper, Published paper (Refereed)
Abstract [sv]

Matematik och programmering är två viktiga inslag i civilingenjörsprogram inom data- och mjukvaruteknik. De studenter som klarar dessa kurser klarar sannolikt resten av utbildningen. Idag har fler studenter programmering än matematik som huvudsakligt intresse. Därför har Linköpings universitet aktivt jobbat med olika strategier för att öka kopplingen mellan programmering och matematik, främst i de inledande kurserna. För att undersöka studenternas attityder till matematik och programmering har vi genomfört flera enkätstudier som bl.a. visar att intresset för matematik är stort men intresset för programmering ännu större och att studenterna tror de kommer ha betydligt mer nytta av programmering än matematik under sin karriär. Texten är tänkt som grund för en diskussion kring hur kopplingarna mellan matematik och programmering kan göras tydligare och starkare.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2016-002
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-122397 (URN)
Conference
5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng) Uppsala universitet, 18 - 19 november 2015
Available from: 2015-11-01 Created: 2015-11-01 Last updated: 2018-01-10
Färnqvist, T., Heintz, F., Lambrix, P., Mannila, L. & Wang, C. (2015). Supporting Active Learning Using an Interactive Teaching Tool in a Data Structures and Algorithms Course. In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng): . Paper presented at 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), Uppsala, Sverige, 18-19 november 2015 (pp. 76-79).
Open this publication in new window or tab >>Supporting Active Learning Using an Interactive Teaching Tool in a Data Structures and Algorithms Course
Show others...
2015 (English)In: Proceedings of 5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 2015, p. 76-79Conference paper, Published paper (Other academic)
Abstract [en]

Traditionally, theoretical foundations in data structuresand algorithms (DSA) courses have been covered throughlectures followed by tutorials, where students practise theirunderstanding on pen-and-paper tasks. In this paper, we presentfindings from a pilot study on using the interactive e-bookOpenDSA as the main material in a DSA course. The goal was toredesign an already existing course by building on active learningand continuous examination through the use of OpenDSA. Inaddition to presenting the study setting, we describe findings fromfour data sources: final exam, OpenDSA log data, pre- and postcourse questionnaires as well as an observation study. The resultsindicate that students performed better on the exam than duringprevious years. Students preferred OpenDSA over traditionaltextbooks and worked actively with the material, although alarge proportion of them put off the work until the due dateapproaches.

Series
Technical report / Department of Information Technology, Uppsala University, ISSN 1404-3203 ; 2016-002
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-122400 (URN)
Conference
5:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), Uppsala, Sverige, 18-19 november 2015
Available from: 2015-11-01 Created: 2015-11-01 Last updated: 2018-01-10
Färnqvist, T. (2013). Exploiting Structure in CSP-related Problems. (Doctoral dissertation). Linköping: Linköping University Electronic Press
Open this publication in new window or tab >>Exploiting Structure in CSP-related Problems
2013 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we investigate the computational complexity and approximability of computational problems from the constraint satisfaction framework. An instance of a constraint satisfaction problem (CSP) has three components; a set V of variables, a set D of domain values, and a set of constraints C. The constraints specify a set of variables and associated local conditions on the domain values allowed for each variable, and the objective of a CSP is to assign domain values to the variables, subject to these constraints.

The first main part of the thesis is concerned with studying restrictions on the structure induced by the constraints on the variables for different computational problems related to the CSP. In particular, we examine how to exploit various graph, and hypergraph, acyclicity measures from the literature to find classes of relational structures for which our computational problems become efficiently solvable. Among the problems studied are, such where, in addition to the constraints of a CSP, lists of allowed domain values for each variable are specified (LHom). We also study variants of the CSP where the objective is changed to: counting the number of possible assignments of domain values to the variables given the constraints of a CSP (#CSP), minimising or maximising the cost of an assignment satisfying all constraints given various different ways of assigning costs to assignments (MinHom, Max Sol, and CSP), or maximising the number of satisfied constraints (Max CSP). In several cases, our investigations uncover the largest known (or possible) classes of relational structures for which our problems are efficiently solvable. Moreover, we take a different view on our optimisation problems MinHom and VCSP; instead of considering fixed arbitrary values for some (hyper)graph acyclicity measure associated with the underlying CSP, we consider the problems parameterised by such measures in combination with other basic parameters such as domain size and maximum arity of constraints. In this way, we identify numerous combinations of the considered parameters which make these optimisation problems admit fixed-parameter algorithms.

In the second part of the thesis, we explore the approximability properties of the (weighted) Max CSP problem for graphs. This is a problem which is known to be approximable within some constant ratio, but not believed to be approximable within an arbitrarily small constant ratio. Thus it is of interest to determine the best ratio within which the problem can be approximated, or at least give some bound on this constant. We introduce a novel method for studying approximation ratios which, in the context of Max CSP for graphs, takes the form of a new binary parameter on the space of all graphs. This parameter may, informally, be thought of as a sort of distance between two graphs; knowing the distance between two graphs, we can bound the approximation ratio of one of them, given a bound for the other.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2013. p. 165
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1496
National Category
Computer Sciences
Identifiers
urn:nbn:se:liu:diva-85668 (URN)978-91-7519-711-1 (ISBN)
Public defence
2013-02-08, Visionen,Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2012-12-17 Created: 2012-11-27 Last updated: 2018-01-12Bibliographically approved
Heintz, F. & Färnqvist, T. (2013). Återkoppling genom automaträttning. In: Proceedings of 4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng): . Paper presented at 4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 27-28 november, Umeå.
Open this publication in new window or tab >>Återkoppling genom automaträttning
2013 (Swedish)In: Proceedings of 4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 2013Conference paper, Published paper (Refereed)
Abstract [sv]

Vi har undersökt olika former av återkoppling genom automaträttning i en kurs i datastrukturer och algoritmer. 2011 undersökte vi effekterna av tävlingsliknande moment som också använder automaträttning. 2012 införde vi automaträttning av laborationerna. Vi undersökte då hur återkoppling genom automaträttning påverkar studenternasarbetssätt, prestationsgrad och relation till den examinerande personalen. Genom automaträttning får studenterna omedelbar återkoppling om deras program är tillräckligt snabbt och ger rätt svar på testdata. När programmet är korrekt och resurseffektivt kontrollerar kursassistenterna att programmet även uppfyller andra krav som att vara välskrivet och välstrukturerat. Efter kursen undersökte vi studenternas inställning till och upplevelse av automaträttning genom en enkät. Resultaten är att studenterna är positiva till automaträttning (80% av alla som svarade) och att den påverkade studenternas sätt att arbeta huvudsakligen positivt. Till exempel svarade 50% att de ansträngde sig hårdare tack vare automaträttningen. Dessutom blir rättningen mer objektiv då den görs på exakt samma sätt för alla. Vår slutsats är att återkoppling genom automaträttning ger positiva effekter och upplevs som positiv av studenterna.

National Category
Other Computer and Information Science
Identifiers
urn:nbn:se:liu:diva-100988 (URN)
Conference
4:de Utvecklingskonferensen för Sveriges ingenjörsutbildningar (UtvSvIng), 27-28 november, Umeå
Projects
PUG
Available from: 2013-11-15 Created: 2013-11-15 Last updated: 2018-01-11Bibliographically approved
Färnqvist, T. (2012). Constraint Optimization Problems and Bounded Tree-width Revisited. In: : . Paper presented at CPAIOR-2012:9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems, May 28 - June 1, 2012, Nantes, France (pp. 163-179). Springer Berlin/Heidelberg
Open this publication in new window or tab >>Constraint Optimization Problems and Bounded Tree-width Revisited
2012 (English)Conference paper, Oral presentation only (Other academic)
Abstract [en]

The valued constraint satisfaction problem (VCSP) is an optimization framework originating from artificial intelligence which generalizes the classical constraint satisfaction problem (CSP). In this paper, we are interested in structural properties that can make problems from the VCSP framework, as well as other CSP variants, solvable to optimality in polynomial time. So far, the largest structural class that is known to be polynomial-time solvable to optimality is the class of bounded hypertree width instances introduced by Gottlob et al. Here, larger classes of tractable instances are singled out by using dynamic programming and structural decompositions based on a hypergraph invariant proposed by Grohe and Marx. In the second part of the paper, we take a different view on our optimization problems; instead of considering fixed arbitrary values for some structural invariant of the (hyper)graph structure of the constraints, we consider the problems parameterized by the tree-width of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. Such parameterizations of plain CSPs have been studied by Samer and Szeider. Here, we extend their framework to encompass our optimization problems, by coupling it with further non-trivial machinery and new reductions. By doing so, we are able to determine numerous combinations of the considered parameters that make our optimization problems admit fixed-parameter algorithms.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 7298
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-79501 (URN)10.1007/978-3-642-29828-8_11 (DOI)978-3-642-29827-1 (ISBN)978-3-642-29828-8 (ISBN)
Conference
CPAIOR-2012:9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems, May 28 - June 1, 2012, Nantes, France
Available from: 2012-08-06 Created: 2012-08-06 Last updated: 2018-01-25
Färnqvist, T. (2012). Counting Homomorphisms via Hypergraph-based Structural Restrictions. In: : . Paper presented at 2nd International Symposium on Combinatorial Optimization (ISCO-2012), April 17-18, Athens (pp. 380-391). Springer Berlin Heidelberg
Open this publication in new window or tab >>Counting Homomorphisms via Hypergraph-based Structural Restrictions
2012 (Swedish)Conference paper, Oral presentation only (Refereed)
Abstract [en]

The way in which the graph structure of the constraints influences the computational complexity of counting constraint satisfaction problems (#CSPs) is well understood for constraints of bounded arity. The situation is less clear if there is no bound on the arities. Here we initiate the systematic study of these problems and identify new classes of polynomial time solvable instances based on dynamic programming over tree decompositions, in a way generalizing well-known approaches to combinatorial optimization problems on bounded treewidth graphs, but basing the decompositions on various hypergraph width measures from the literature on plain CSPs.

Place, publisher, year, edition, pages
Springer Berlin Heidelberg, 2012
Series
Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 7422
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:liu:diva-79502 (URN)10.1007/978-3-642-32147-4_34 (DOI)978-3-642-32146-7 (ISBN)978-3-642-32147-4 (ISBN)
Conference
2nd International Symposium on Combinatorial Optimization (ISCO-2012), April 17-18, Athens
Available from: 2012-08-06 Created: 2012-08-06 Last updated: 2018-02-19
Heintz, F. & Färnqvist, T. (2012). Pedagogical Experiences of Competitive Elements in an Algorithms Course. In: Proceedings of LTHs 7:e Pedagogiska Inspirationskonferens (PIK). Paper presented at LTHs 7:e Pedagogiska Inspirationskonferens, 30 augusti, Lund.
Open this publication in new window or tab >>Pedagogical Experiences of Competitive Elements in an Algorithms Course
2012 (English)In: Proceedings of LTHs 7:e Pedagogiska Inspirationskonferens (PIK), 2012Conference paper, Oral presentation only (Refereed)
Abstract [en]

We claim that competitive elements can improve thequality of programming and algorithms courses. To test this, weused our experience from organising national and internationalprogramming competitions to design and evaluate two differentcontests in an introductory algorithms course. The first contestturned lab assignments into a competition, where two groups rancompetitions and two were control groups and did not compete.The second, voluntary, contest, consisting of 15 internationalprogramming competition style problems, was designed tosupport student skill acquisition by providing them withopportunities for deliberate practise. We found that competitiveelements do influence student behaviour and our mainconclusions from the experiment are that students really likecompetitions, that the competition design is very important forthe resulting behaviour of the students, and that active studentsperform better on exams.

We also report on an extra-curricular activity in the form of asemester long programming competition as a way of supportingstudent's deliberate practise in computer programming.

National Category
Pedagogy
Identifiers
urn:nbn:se:liu:diva-80397 (URN)
Conference
LTHs 7:e Pedagogiska Inspirationskonferens, 30 augusti, Lund
Projects
PUG
Available from: 2012-08-28 Created: 2012-08-24 Last updated: 2013-01-16Bibliographically approved
Färnqvist, T., Jonsson, P. & Thapper, J. (2009). Approximability Distance in the Space of H-Colourability Problems. COMPUTER SCIENCE - THEORY AND APPLICATIONS, 5675, 92-104
Open this publication in new window or tab >>Approximability Distance in the Space of H-Colourability Problems
2009 (English)In: COMPUTER SCIENCE - THEORY AND APPLICATIONS, ISSN 0302-9743, Vol. 5675, p. 92-104Article in journal (Refereed) Published
Abstract [en]

A graph homomorphism is a vertex map which carries edges from a source graph to edges in a target graph. We Study the approximability properties of the Weigh feel Maximum H-Colourable Subgraph problem (MAX H-COL). The instances of this problem are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to H note that for H = K-k this problem is equivalent to MAX k-CUT. To this end, we introduce a metric structure on the space of graphs which allows us to extend previously known approximability results to larger classes of graphs. Specifically, the approximation algorithms for MAX CUT by Goemans and Williamson and MAX k-CUT by Frieze and Jerrum can he used to yield non-trivial approximation results for MAX H-COL For a variety of graphs, we show near-optimality results under the Unique Games Conjecture. We also use our method for comparing the performance of Frieze andamp; Jerrums algorithm with Hastads approximation algorithm for general MAX 2-CSP. This comparison is, in most cases, favourable to Frieze andamp; Jerrum.

Keywords
optimisation, approximability, graph homomorphism, graph H-colouring, computational complexity
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-21521 (URN)10.1007/978-3-642-03351-3_11 (DOI)
Available from: 2009-10-02 Created: 2009-10-02 Last updated: 2017-02-23
Organisations

Search in DiVA

Show all publications