Abstract this paper describes an algorithms and data structures course that uses acm programming competition problems as the basis for the lectures, homework and exams

Computer Science Department

Montana State University – Bozeman

Bozeman, MT 59717

406-994-5979

paxton@cs.montana.edu
ABSTRACT

This paper describes an algorithms and data structures course that uses ACM programming competition problems as the basis for the lectures, homework and exams. The course, designed and developed as part of a Fulbright Award, was delivered to students at The University of Leipzig in Leipzig, Germany during Winter Semester 2006/2007. The course is described, assessed and evaluated for future usage.

In May of 2004, the author began a dialogue with the department head of the Computer Science Department at The University of Leipzig in Germany to develop a custom, upper-division elective course as part of a Fulbright Application. The four credit course, entitled “Practical Applications of Data Structures and Algorithms”, would use programming competition problems [4] as the basis for the lectures, homework and exams. The rationale behind using the programming competition problems was to make the course more appealing to a broader range of students. The Fulbright Award [3] was granted and the course was delivered in Germany during Winter Semester 2006/2007.

The paper is organized in the following manner. First, the logistics of the course are described in the course overview section. Second, the course is assessed by both the students and the instructor in the assessment section. Third, possibilities to partially or fully adapt the course into another institution’s curriculum are explored in the curriculum ideas section. Finally, a few concluding remarks are made.
COURSE OVERVIEW
Description

The goals of the course were threefold: to refine students’ problem solving skills; to further their practical programming knowledge; and to increase their familiarity with technical English. The course was taken by a total of 75 students as an upper-division elective. It covered the following topics: performing input and output in Java 5, base conversions, handling very large numbers, solving miscellaneous math problems, sorting, strings, grids, trees, graphs and artificial intelligence search techniques. No textbook was required as all relevant supporting materials were either available from the course website [7] or available on the internet.

The class met once a week for a 90 minute lecture and once a week for a 90 minute help session. During the lecture, a topic (such as handling very large numbers) was introduced. A problem from a past programming competition was then selected that illustrated this topic. Once the problem statement was understood, the rest of the lecture period was spent designing, coding (in Java on a laptop attached to a projector) and testing a solution. Student input was solicited throughout the process. During the optional help session, students could ask for clarifications on any course related topic.

Grading

There were three graded components to the course. First, students could earn 10% of the course grade by participating in an ACM-style programming competition. The competition was held three weeks into the semester, giving students a better appreciation of the environment from where the lecture and homework problems were being drawn. 25 groups of students, working in teams of three, attempted to solve as many of the five problems as quickly as possible during a five hour period - using just one laptop computer. Participation, regardless of performance, guaranteed the 10% credit. However, the top two teams were chosen to compete at an ACM Southwest Europe Regional Competition in Lisbon, Portugal [1] – with full financial support from the Computer Science Department. This provided a good incentive for students to do their best during the competition.

Second, students could earn 30% of the course grade by solving the weekly homework problem. After a topic was introduced and a problem illustrating that topic was solved during the lecture, students were given a second problem drawn from a past programming competition that illustrated that same topic. A student could either solve the problem on his or her own, or work with a partner. Problems were required to be submitted electronically, approximately five days after they were assigned. Originally, it was planned that everyone would solve two problems per week; one during the help session and one as outside homework. However, due to the large number of students and the lack of a teaching assistant, the help session problem was offered as a non-graded, practice problem.

The grading of the homework problems was simple. Each homework problem was worth three points. In general, if the problem was solved correctly, three points were awarded. If at least one non-trivial test case was solved, two points were awarded. If an attempt was made, one point was awarded. Finally, if the input/output instructions were not followed exactly, additional points (or half points) would be deducted.

Although there was an average of 50 submissions a week to grade, the author found that the grading could be done in approximately four hours - not overly onerous. First, a test input file had to be carefully designed. Second, each submitted program was compiled and run, comparing the produced output to the desired output. Third, the test input file and a sample correct solution was posted to the website. Finally, each student was sent an e-mail with his or her results. Based on the homework scores, the three most challenging topics were dynamic programming, graph algorithms, and utilizing search techniques such as depth-first or breadth-first search.

For the third and final grading component, students could earn 60% of the course grade through performance on the three hour final. During the final, students were given three problems to solve on a laptop. All of the problems utilized techniques that had been studied and practiced during the course. If two students had worked together during the semester on the weekly homework, they were given the opportunity to work together on the final. All other students were required to work alone. Surprisingly, the students who worked alone outscored those students who worked in pairs by 12.5%!

Because the course had many unusual aspects, an optional survey was developed to gather student feedback. 21 of the 75 students responded. A portion of these survey results appear in this subsection.

Each student was asked what he or she particularly liked about this course. Some of the aspects that were mentioned more than once included: the practical orientation of the course (14 students), the problem-based lecture style [6] (6 students), having the course taught in English by a native English speaker (4 students), the enjoyable problems (2 students) and the final exam format (2 students).

Each student was asked what he or she did NOT particularly like about this course. Some of the aspects that were mentioned included: there was not enough theoretical analysis of the problems (2 students), there was too much homework (2 students), the grading was too strict (1 student) and the problems should be harder (1 student). Students suggested improving the course by making the first few weeks of the semester more difficult, choosing harder problems to solve during the lecture, explaining each technique’s relevance to real-world problems and examining the underlying code of the solutions with the intent of making suggestions for improvement.
Instructor Assessment

Having developed and taught the course for the first time, this author would make the following changes to the course on a second offering:

• 
  The importance of testing one’s solution should be emphasized during the first few weeks of the course. A common approach to the homework was to work on it until the program passed the test cases in the problem description. However, the sample test cases often did not include boundary cases that would expose errors or inefficiencies in the proposed solution.
  
• 
  To help a student to better track the solution to the lecture problem, diagrams that summarize the design of the lecture solution should be placed on the whiteboard. It is important to foster good process in a course that utilizes programming contest problems [8] to avoid the course turning into a hack fest.
  
• 
  Oftentimes, a problem has multiple solutions. Alternative solutions to the lecture problem should be solicited, perhaps rewarded with extra credit, and made available. This author believes that an effective way to become a better problem solver is to see and compare multiple solutions to the same problem.
  
• 
  To speed up the grading process, all solutions should be named in a standard way and a simple script should be developed that compiles, runs and compares the output of the submitted program against the correct output.
  
• 
  Each student should be required to take the final individually. Students who took the final individually outscored those who did not by 12.5%, indicating that some of the students who worked with a teammate were not as motivated to prepare for the final.
  
• 
  Although students were verbally engaged in solving the lecture problem, the instructor did the coding. In the future, this author would like to give students the opportunity to do some of the in-class coding.
  
• 
  The course website should contain more links to theory and explanation that underlies the week’s lecture topic.
  
• 
  The next time the course is offered, problems from the first offering could be reused as either lecture problems or as non-graded, practice problems. However, the graded problems should be new ones, to avoid the problem of students finding solutions online. Fortunately, the web contains thousands of suitable past programming competition problems. One such site is [10].
  
• 
  Develop a more rigorous assessment process to better evaluate the course.
  

• 
  The course could be adapted into a standalone problem solving and/or algorithms and data structure course. The level of the course could be beginning, intermediate or advanced [5].
  
• 
  Programming competition problems could be integrated into an existing course and used as the basis for lectures, labs or programming assignments. The problems are relevant to a wide range of courses including artificial intelligence, networks, compilers, learning a programming language [2], and algorithms and data structures.
  
• 
  The course could be used as a standalone course that prepares students to compete in programming competitions. In this case, [9] is an excellent textbook to consider.
  
• 
  The course could be used as the basis for an institutionally sponsored study abroad course. Because the course is easy to modify, relatively self-contained and contains no large projects, it is logistically easy to take on the road.
  

The course described in this paper was a delight to develop and teach. Although several improvements can be made to the course on its second offering, the students who took the course found it to be worthwhile and fun. The author hopes that some of the ideas presented here might be of use at the reader’s home institution.

[1] ACM International Collegiate Programming Contest, 2007, http://icpc.baylor.edu/icpc/, retrieved February 26, 2007.

[2] Bierre, K., Ventura, P., Phelps, A., Egert, C., Motivating OOP by blowing things up: an exercise in cooperation and competition in an introductory java programming course, Proceedings of the 37^th SIGCSE Technical Symposium on Computer Science Education, 38, (1), 354-358, 2006.

[3] Fulbright Scholar Program, 2007, http://www.cies.org/, retrieved February 26, 2007.

[4] Ladd, B., Harcourt, E., Student competitions and bots in an introductory programming course, Journal of Computing Sciences in Colleges, 20, (5), 274-284, 2005.

[5] Paxton, J., Mumey, B., Teaching advanced problem solving: implications for the CS curriculum, Proceedings of the Fourteenth Annual Consortium on Small Colleges Southeastern Conference, 16, (2), 50-55, 2000.

[6] O’Kelly, J., Gibson, J., Robocode & problem-based learning: a non-prescriptive approach to teaching programming, Proceedings of the 11^th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, 38, (3), 217-221, 2006.

[7] Practical Applications of Data Structures and Algorithms Course Website, 2007, http://www.informatik.uni-leipzig.de/~paxton/algorithmics/, retrieved February 26. 2007.

[8] Sherrell, L., McCauley, L., A programming competition for high school students emphasizing process, Proceedings of the Second Annual Conference on Mid-South College Computing, 61, (1), 173-182, 2005.

[9] Skiena, S., Revilla, M., Programming Challenges: The Programming Contest Training Manual, New York, NY: Springer-Verlag, 2003.