| 1. |
- Crescenzi, P., et al.
(författare)
-
From theory to practice : NP-completeness for every CS student
- 2013
-
Ingår i: ITiCSE '13 Proceedings of the 18th ACM conference on Innovation and technology in computer science education. - New York, NY, USA : Association for Computing Machinery (ACM). - 9781450320788 ; , s. 16-21
-
Konferensbidrag (refereegranskat)abstract
- NP-completeness is one of the most central concepts in computer science, and has been extensively applied in many diverse application areas. Despite this, students have problems grasping the concept and, more specifically, applying it to new problems. Independently, we have identified these problems at our universities in different countries and cultures. In an action research approach we have modified our courses and studied the effects. We here present some promising results. Our approach is mainly based on the idea of making more evident the fact that proving a new NP-completeness result is not at all different from designing a new algorithm. Based on this idea, we used tools typically used to teach algorithms (such as automatic program assessment and algorithm visualization systems), accompanied by other activities mainly devoted to augmenting the motivation to study computational complexity and forcing students to think and adopt a standpoint.
|
|
| 2. |
- Enström, Emma, et al.
(författare)
-
Computer Lab Work on Theory
- 2010
-
Ingår i: ITICSE 2010. - NEW YORK : ASSOC COMPUTING MACHINERY. - 9781605588209 ; , s. 93-97
-
Konferensbidrag (refereegranskat)abstract
- This paper describes an attempt to introduce computer lab exercises on NP-completeness proofs in a class already containing computer lab exercises on algorithms and data structures. In the article we are interested in the answer of the following question: Can the students feel that their understanding of theoretical computer science is improved by performing a computer lab exercise on the subject? The class is mandatory for students in a computer science program, and is taken by about 130 students each year. Theory of NP-completeness proofs with reductions has previous years been examined on an individual assignment with written solutions handed in and later explained orally by the student to a teacher. The new assignment is performed as a computer lab exercise where students are working in small groups of two. This exercise is placed before the individual assignment, and is examined first by running automated test cases and later by an oral presentation in lab to a teacher. An improvement can be observed of the students' average results since the new assignment was introduced. This is not enough to prove the benefit of using the new assignment. However, the responses to questionnaires at course evaluations show that almost all students think that the assignment redly gave them better understanding of polynomial reductions in NP completeness proofs. The students' result on the new assignment corresponds closely to their results on the following individual assignment. Seemingly, the new assignment predicts accurately who is going to pass the following assignment.
|
|
| 3. |
- Enström, Emma, et al.
(författare)
-
Five Years with Kattis – Using an Automated Assessment System in Teaching
- 2011
-
Ingår i: 2011 Frontiers in Education Conference (FIE). - New York : IEEE. - 9781612844695
-
Konferensbidrag (refereegranskat)abstract
- Automated assessment systems have been employed in computer science (CS) courses at a number of different universities. Such systems are especially applicable in teaching algorithmic problem solving since they can automatically test if an algorithm has been correctly implemented, i.e., that it performs its specified function on a set of inputs. Being able to implement algorithms that work correctly is a crucial skill for CS students in their professional role, but it can be difficult to convey the importance of this in a classroom situation. Programming and problem solving education supported by automated grading has been used since 2002 at our department. We study, using action research methodology, different strategies for deploying automated assessment systems in CS courses. Towards this end, we have developed an automated assessment system and both introduced it into existing courses and constructed new courses structured around it. Our primary data sources for evaluation consists of course evaluations, statistics on students' submitted solutions, and experience teaching the courses. Authors of this paper have been participating in teaching all of the courses mentioned here.
|
|
| 4. |
|
|
| 5. |
- Frenckner, Kerstin, et al.
(författare)
-
Att utvärderas och utvecklas : om datalogi och medieteknik i ljuset av EAE på KTH
- 2011
-
Ingår i: 3:e Utvecklingskonferensen för Sveriges ingenjörsutbildningar. - : Linköping University Electronic Press. ; , s. 82-86
-
Konferensbidrag (refereegranskat)abstract
- Under 2011 genomförs en stor utvärdering av samtliga utbildningsprogram på KTH. Projektet går under namnet Education Assessment Exercise (EAE) och är den största enskilda aktiviteten inom KTH:s systematiska kvalitetsarbete under året [2]. Projektet går genom tre huvudstadier: självvärdering, extern bedömning och uppföljning. Den första delen skedde under våren 2011, del två i augusti, medan större delen av uppföljning och utveckling var tänkt att ligga efter bedömarnas slutrapport i oktober. Det stadiet påbörjades dock redan i augusti. Syftet med EAE är i första hand att bidra till kvalitetsutveckling, men EAE fungerar också som en förberedelse inför den utvärdering som Högskoleverket planerar att genomföra under 2012.Skolan för datavetenskap och kommunikation (CSC) vid KTH ansvarar för civilingenjörs-, master- och kandidatprogram inom datalogi och datateknik, medieteknik, beräkningsteknik och människa-datorinteraktion. Skolan ansvarar också för ett stort utbud av kurser inom skolans ämnen, datalogi, medieteknik, människa-datorinteraktion, numerisk analys och tal- och musikkommunikation, liksom omfattande forskning i dessa ämnen.Skolan ger kurser inte bara för studenter på skolans egna program utan även för studenter på andra skolors program. Studenterna på CSC-skolans program läser inte bara CSC-skolans kurser utan även kurser som ges av andra skolor, till exempel matematikkurser från Skolan för teknikvetenskap.CSC har länge haft ett systematiskt kvalitetsarbete inom grundutbildningen, som bland annat ledde till att skolan tilldelades Högskoleverkets utmärkelse Framstående utbildningsmiljö 2009. I denna artikel beskriver vi skolans kvalitetsarbete och arbete med EAE, i alla faser av utvärderingsprojektet.
|
|
| 6. |
- Kann, Viggo, 1964-
(författare)
-
En programsammanhållande kurs med många funktioner
- 2011
-
Konferensbidrag (refereegranskat)abstract
- På civilingenjörsprogrammet i Datateknik på KTH startades 2010 kursen Programsammanhållande kurs i datateknik, som går över hela de tre första åren av programmet. Kursen fyller minst tio olika funktioner, vilka beskrivs i artikeln. Den är inspirerad av en liknande kurs som getts för Medieteknikprogrammet vid KTH [3]. Kursformatet är att teknologerna träffas i årskursöverskridande grupper om ungefär tio elever och en lärarmentor vid tre eller fyra så kallade reflektionsseminarier per år. Tretton av programmets datalogilärare är mentorer och varje mentor har tre grupper var. Inför varje träff ska varje teknolog skriva en sidas reflektion över sina studier och över det speciella temat för träffen. Var och en ska också läsa övriga deltagares skriftliga reflektioner inför eflektionsseminariet. De tio temana för reflektionsseminarierna är för närvarande:1) Studiemotivation och studieteknik2) Kursmål, programmål, betygskriterier och examination3) Plagiering och eget ansvar4) Hur ser jag min framtida roll som D-civilingenjör och hur når jag dit?5) Kvalitet i utbildningen – vad är det?6) Plugga och jobba utomlands7) Generiska kompetenser och bildning8) Studentinflytande9) Entreprenörskap och innovationsutveckling10) Egenutveckling under en yrkeskarriär – livslångt lärandeFörsta temat ges bara för årskurs 1 och inleder alltid kursen. Övriga teman ges tre om året och kommer därför i olika ordning för olika årskullar. Utöver detta ryms i kursen två andra moment: etik, som ges av filosofienheten, och datorhistoria, som ges av teknikhistoriaenheten. Dessa moment innehåller både föreläsningar, seminarier och rapportskrivande. Förutom genomgången av kursens tio funktioner i utbildningen beskriver artikeln resultatet av utvärderingar av första årets kursomgång och diskuterar svårigheter som måste bemästras då en sådan här kurs ska genomföras. vslutningsvis ges argument för konceptets generaliserbarhet.
|
|
| 7. |
- Kann, Viggo, 1964-, et al.
(författare)
-
Hur kan en språkpolicy bli verklighet?
- 2014
-
Konferensbidrag (refereegranskat)abstract
- KTH antog år 2010 en språkpolicy som beskriver universitetets ambitioner vad gäller språklig kvalitet och språkliga förmågor. För att ett policydokument verkligen ska påverka verksamheten krävs att några arbetar med att göra policyn känd och implementera den [2]. Därför inrättades KTH:s språkkommitté, som sedan 2011 har arbetat med att bevaka språkfrågor i vid mening på KTH. Kommittén ska implementera KTH:s språkpolicy i verksamheten och ge råd och tips i språkliga frågor av generell art. Detta bidrag beskriver några aktiviteter som språkkommittén har genomfört i detta syfte och diskuterar hur dessa har påverkat verksamheten. År 2011 och 2012 genomförde språkkommittén två enkäter för att få en aktuell bild av språkanvändningen på KTH och vilka problem som kan finnas. Första enkäten vände sig till alla lärare på KTH och gav över 500 svar. Andra enkäten gick till alla studenter och doktorander vid KTH och gav över 3 000 svar. Båda enkäterna visade att språkintresset är mycket stort och att både lärare och studenter gärna vill gå språkkurser. Många öppna svar bekräftar resultaten från en liknande enkät vid SU [1], till exempel de komplexa problem som uppstår då masterprogram börjar undervisas på engelska. Lärarenkäten visade att bara 40 % av kurserna följer språkpolicyns rekommendationer att presentera fackterminologin både på svenska och engelska. Både lärare och studenter anser att det är ett problem att studenterna inte har parallell fackspråkskompetens på svenska och engelska. Många studenter på masterprogrammen exponeras inte heller för det svenska fackspråket vilket kan ge problem i examensarbetet och vid första anställningen. För att komma tillrätta med fackspråksproblematiken har språkkommittén gett ett seminarium om fackspråk i samarbete med TNC och anordnat en workshop för lärare där idéer till hur parallellspråkig terminologi i undervisningen ska tillhandahållas och övas. Idéerna har sedan sammanställts, strukturerats och publicerats på språkkommitténs webbplats, där såväl KTH:s lärare som övriga intresserade kan hitta dem och inspireras av dem. På webbplatsen finns också länkar till språkresurser och språkverktyg, bland annat en svensk-engelsk KTH-ordbok med ettusen administrativa termer, som språkkommittén utvecklat för att den engelska terminologin ska bli mindre yvig. En webbsida med vanliga språkliga frågor svarar till exempel på frågor om användning av svenska och engelska vid examination, i examensarbetsrapporter och avhandlingar. Lärare och administratörer vid KTH kan prenumerera på språkkommitténs gruppwebb och får därigenom meddelande om när nyheter läggs upp på webben. Språkkommitténs aktiva arbete med att medvetandegöra språkfrågor har gjort språkpolicyns genomslag större på KTH.
|
|
| 8. |
- Kann, Viggo
(författare)
-
Kan kvalitet på ett elitcollege föras över till svenska förhållanden?
- 2010
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Några högskolor i världen är erkända för sin mycket högautbildningskvalitet. Stints program Excellence in Teaching är avsettatt ge lärare möjlighet att uppleva detta, med förhoppningen att detska gagna svensk utbildning. Är det möjligt att överföra kvalitet frånen utbildningsanstalt som har enorma resurser och knivskarp konkurrensvid rekryteringen till den knappa svenska utbildningsverkligheten?Självfallet har vi inte råd att flytta över utbildningsmodellendirekt, men det går att lära mycket av ett elitcolleges excellens ochimplementera det hemmavid.Själv var jag Stintstipendiat 2006 och tillbringade höstterminen vidAmherst College, rankat nummer två i USA. Det var en fantastiskperiod och jag fick massor av idéer. Här är en lista med tio punkter som jag sedan dess arbetat med attgenomföra på KTH.1. Upptäck den som kommer efter så tidigt som möjligt i kursen/studiernaDetta är nyckeln till hög genomströmning men svårt och dyrt att genomföra.Vi provar olika sätt, till exempel diagnostiska datorprov och enprogramsammanhållande kurs med små mentorsgrupper som träffas varje period.2. Lärare hjälper studenterna med kursvalLärarmentorer erbjöd D-studenter vägledning inför kurs- och mastervalet2009. Detta kommer att bli en del av programsammanhållande kursen.3. EntimmesföreläsningarKortare föreläsningar så att lärare och elever kan vara koncentrerade hela tiden. Jag och min fru har med framgång infört det i två kurser.4. Väl fungerande lärosalarVi har bildat en grupp som synar alla lärosalar ur pedagogisk synvinkel, anmäler fel och ger förslag på förbättringar.5. Lärarna suddar tavlan efter lektionenDetta hänsynsfulla beteende är en kulturfråga, men med hjälp av tydligaskyltar i två salar har det kunnat frammanas.6. Fina campusbilder på datorernas bakgrundsbilderInfört på våra Macdatorer. KTHs campus är vackert på skärmarna!7. Valfrihet och breddJag har diskuterat detta i olika grupper och fått medhåll från många, mendet är svårt att få förändringar. Vårt nya datalogimasterprogram haråtminstone tagit intryck.8. FamiljedagSedan 2008 har vi en vårdag visat upp skolan och undervisningen för familjer, utomstående och personal.9. Visningar av campusBorde genomföras centralt på KTH, men vi har hittills bara lyckats genomföradet under familjedagarna.10. SpråkverkstadPraktisk hjälp för den som ska göra en muntlig eller skriftlig presentationsaknas. Jag har arbetat fram KTHs nya språkpolicy som säger att enspråkverkstad ska införas.Det går alltså att genomföra många ändringar om man ligger i, och det har gettresultat. Skolan fick HSV-utmärkelsen Framstående utbildningsmiljö 2009!
|
|
| 9. |
- Kann, Viggo
(författare)
-
KTHs morfologiska och lexikografiska verktyg och resurser (Morphological and lexicographical tools and resources from KTH)
- 2010
-
Ingår i: LexicoNordica. - 0805-2735 .- 1891-2206. ; 17, s. 99-117
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- During the last 15 years the human language technology group at KTH has developed tools and resources that may have interest to the lexicographical community. Several tools were developed as part of the group's research on Swedish authoring tools: spelling error detection and correction, grammar checking, part-of-speech tagging, lemmatization, compound splitting, and an interactive learning environment called Grim. Most of the tools are made open source and may be downloaded from www.csc.kth.se/theory/humanlang We have also made several dictionaries available on the web: the Lexin series of dictionaries for 15 languages, the Scandinavian Dictionary, the Tvärslå dictionary collection, the Swedish Hyphenation Dictionary and the two crowd sourced resources The People's Dictionary of Synonyms and The People's English-Swedish Dictionary.
|
|
| 10. |
- Kann, Viggo, 1964-
(författare)
-
Lärosalsgruppen fixar salarna åt lärarna!
- 2012
-
Konferensbidrag (refereegranskat)abstract
- En lärosalsgrupp bestående av lärare och studenter som varje år synar alla lärosalar, mötesrum och grupprum kan vara den lilla åtgärd som behövs för att få ett slitet salsbestånd att fortsätta fungera och till och med bli mer användbart i undervisningen än tidigare.Lärosalarnas skick och funktion är något som påverkar studenternas lärande. Fleming och Storr (1999) fann i en undersökning att nästan 80 procent av respondenterna menade att lärosalens kvalitet påverkade inlärningen. Framstående utbildningsmiljöer har funktionella läromiljöer som kännetecken (Kann 2010).På KTH finns det många lärosalar av skiftande storlek, utrustning och ålder. KTHs huvudbyggnad byggdes 1917 och totalrenoverades 1993. Det betyder att lärosalarna i byggnaden i allmänhet är nästan 20 år gamla. När salarna skulle renoveras las ett stort arbete ner på att ge dem den funktionalitet som lärarna och teknologerna då efterfrågade. Många av behoven är tidlösa, men nya pedagogiska metoder och ny teknik har gjort att vissa krav på salarna har ändrats. Dessutom har lokalerna och inventarierna åldrats. Hur kan man utan en ny renovering få bukt med detta problem?Skolan för datavetenskap och kommunikations lösning var att inrätta en grupp kallad lärosalsgruppen, bestående av lärare och studenter, med uppdrag att göra en årlig syn av alla husets lärosalar, mötesrum och grupprum. Vid syningen upprättas ett protokoll för varje sal, där det framgår vad som fungerar och vad som brister i salen, med avseende på ett antal pedagogiska krav. Fleming och Storr (1999) har också undersökt vilka funktioner som är viktigast i en lärosal. Deras studie visar att de tio högst rankade designvariablerna (i fallande skala) är kvaliteten på AV-utrustning, bordsutrymme, tavlors och projektionsdukars synlighet, akustik, sittkomfort, naturligt ljus, ventilation, användningsgrad, belysning, störande ljud. Vårt lärosalsprotokoll tar upp dessa variabler och ytterligare några.Efter syningen åtgärdar gruppen själv vissa brister och felanmäler övriga brister till lokalvården, KTHs hantverkargrupp, eller hyresvärden Akademiska Hus, beroende på var bristen finns.I skolans seminarierum och labbsalar har lärosalsgruppen installerat projektorer och ljudanläggningar och låtit förbättra belysningen och installera fler eluttag. I övriga salar som undervisningen hyr per timme av KTH har vi felanmält klimatproblem och trasig utrustning. Vi har också lämnat förslag till KTHs arkitekt på funktionella förbättringar av salar, till exempel titthål i dörrarna, nya eluttag och flyttning av tavelupphängningsskenor.För att lärarna enkelt ska kunna se vilken utrustning och möjligheter varje sal har har gruppen fotograferat varje sal från tavlan (lärarvy) och från andra sidan av salen (elevvy) och lagt upp på en webbsida.Lärosalsgruppens arbete har varit uppskattat bland lärarna och gjort att salarna fungerar bättre i undervisningen. Det har gett upphov till en påtaglig kvalitetsförbättring till en minimal kostnad.
|
|
| 11. |
- Kann, Viggo, 1964-, et al.
(författare)
-
Reflektionsseminarier som håller ihop och utvecklar programmet
- 2013
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- En programsammanhållande kurs går över flera år, visar den röda tråden i programmet och har som syfte att kursdeltagarna ska bli professionella studenter, samtidigt som kursen har positiva effekter på mentorerna, övriga kurser och själva programmet. Detta uppnås genom regelbundna reflektionsseminarier där studenterna träffas i små årskursöverskridande grupper tillsammans med en lärare som mentor.Den programsammanhållande kursen på civilingenjörsprogrammet i datateknik på KTH är nu inne på sitt femte år och har utvecklats och utvärderats för varje år. I denna artikel motiveras kursens förmåga att ge akademisk integration och ökad genomströmning, visas hur reflektionerna utvecklats med högre nivåer och hur kurskonceptet spritts till flera program både inom och utanför KTH.
|
|
| 12. |
- Kann, Viggo, 1964-
(författare)
-
Using Reflections in a Program Integrating Course
- 2014
-
Ingår i: ITiCSE '14 Proceedings of the 2014 conference on Innovation & technology in computer science education. - New York, New York, USA : Association for Computing Machinery (ACM). - 9781450328333 ; , s. 350-350
-
Konferensbidrag (refereegranskat)abstract
- A program integrating course runs over several years, shows the mainthread of the program, and its purpose is to enable students to becomemore professional in handling their studies, at the same time as thecourse has a positive effect on thementors, other courses and the program itself. This is achieved throughregular reflection seminars where students meet in small cross-gradegroups with a professor as a mentor.
|
|
| 13. |
|
|
| 14. |
- Rosell, Magnus, et al.
(författare)
-
Global Evaluation of Random Indexing through Swedish Word Clustering Compared to the People’s Dictionary of Synonyms
- 2010
-
Konferensbidrag (refereegranskat)abstract
- Evaluation of word space models is usually local in the sense that it only considers words that are deemed very similar by the model. We propose a global evaluation scheme based on clustering of the words. A clustering of high quality in an external evaluation against a semantic resource, such as a dictionary of synonyms, indicates a word space model of high quality. We use Random Indexing to create several different models and compare them by clustering evaluation against the People’s Dictionary of Synonyms, a list of Swedish synonyms that are graded by the public. Most notably we get better results for models based on syntagmatic information (words that appear together) than for models based on paradigmatic information (words that appear in similar contexts). This is quite contrary to previous results that have been presented for local evaluation. Clusterings to ten clusters result in a recall of 83 % for a syntagmatic model, compared to 34% for a comparable paradigmatic model, and 10% for a random partition.
|
|
| 15. |
- Viggo, Kann
(författare)
-
Visst gör ett s skillnad
- 2011
-
Ingår i: Språktidningen. - : Språktidningen i Sverige. - 1654-5028. ; :9, s. 46-49
-
Tidskriftsartikel (populärvet., debatt m.m.)
|
|
| 16. |
- Wenner, Cenny, 1984-
(författare)
-
Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction
- 2014
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). Most CSPs are NP-hard to solve optimally and we turn to approximations - a solution is said to be a factor-c approximation if its satisfies at least c times the optimal number of constraints. This thesis presents new results on the approximation limits of CSPs in various settings.In ordering CSPs, one is given constraints which specify the relative order of items, and the objective is order the items so as to satisfy as many constraints as possible. We give improved approximation hardness results for two classical problems: it is NP-hard to approximate Maximum Acyclic Subgraph with a factor better than 14/15 and Maximum Betweenness with a factor better than 1/2. We present ordering problems which are NP-hard to approximate better than random assignments, and that there are ordering problems arbitrarily hard to approximate.Next, Gaussian elimination can efficiently find exact solutions for satisfiable collections of so-called parity constraints. We show that whenever constraints accept at least one assignment in addition to a parity, then the problem is NP-hard to approximate better than random assignments. Finally, we study the uselessness property which basically states that if one is given a collection where almost all constraints are simultaneously satisfiable and one is permitted to relax the constraints to accept or reject additional assignments, then it is still NP-hard to find solutions noticeably better than random assignments. We consider the setting where all variables appear unnegated and provide the first examples of non-trivially useless predicates assuming only P != NP.
|
|
