Computer Lab Work on Theory
2010 (English)In: ITICSE 2010: PROCEEDINGS OF THE 2010 ACM SIGSE ANNUAL CONFERENCE ON INNOVATION AND TECHNOLOGY IN COMPUTER SCIENCE EDUCATION, NEW YORK: ASSOC COMPUTING MACHINERY , 2010, 93-97 p.Conference paper (Refereed)
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.
Place, publisher, year, edition, pages
NEW YORK: ASSOC COMPUTING MACHINERY , 2010. 93-97 p.
reductions, learning theoretical computer science, computer lab work
IdentifiersURN: urn:nbn:se:kth:diva-31020ISI: 000286906900021ScopusID: 2-s2.0-77955134619ISBN: 978-1-60558-820-9OAI: oai:DiVA.org:kth-31020DiVA: diva2:402257
15th Innovation and Technology in Computer Science Education Conference
QC 201103072011-03-072011-03-072014-09-29Bibliographically approved