1. Assessment of BSCS.OC9

1. Assessment of BSCS.OC9

1.1. Raw Data

Each rubric specifies a list of tasks. For each task instructors describe an exam question or homework problem representative of the task. I will refer to these as task questions. For each task question the instructor records the percentage of passing students (i.e., students who received a C- or higher in the course) who received full or near-full credit.

1.1.1. Beginning Level

Students who pass CS46B should be able to perform the following tasks:

Task 1

Implement a search algorithm for a given abstract data type. For example, write a search algorithm for a binary search tree or for a hash table. (An exam question)

Task 2

Implement a data structure such as a linked list, stack, queue, or binary search tree. Use the data structure in the context of a simple application. (A programming assignment)

Task 3

Write in Java a recursive solution to a simple programming problem. (An exam question)

The report indicates that 61%, 83%, and 39% of passing students were able to execute the task questions for tasks 1, 2, and 3, respectively.

1.1.2. Intermediate Level

Outcome 9 is assessed in two courses at the intermediate level: CS149 and CS151.

1.1.2.1. CS 149

Students who pass CS149 should be able to perform the following tasks:

Task 1

Select an appropriate CPU scheduling algorithm or mechanism that is suited to a particular Operating System. Justify the answer in detail, possibly using metrics (e.g., average turnaround time, average response time). (Assessed with an exam question.)

Task 2

Describe the main characteristics of a page replacement algorithm. Write the algorithm in detail using pseudocode. (Assessed with an exam question.)

Task 3

Describe a page table of a certain kind that can be used to keep track of where pages are located in memory and to maintain page usage information. Describe how the table is used by means of pseudocode. (Assessed with an exam question.)

The report indicates that on the average 81%, 73%, and 55% of passing students could execute tasks 1, 2, and 3, respectively.

1.2.2.2. CS 151

Students who pass CS151 should be able to perform the following tasks:

Task 1

Given a UML class diagram including a class, C, that has a UML association endpoint with unbounded multiplicity, implement C in Java. (Assessed with an exam question.)

Task 2

Given a Java class that overrides the equals method, define an appropriate hashCode method that would be suitable for use with a hash table. (Assessed with an exam question.)

The report indicates that on the average 86% and 71% of passing students could execute tasks 1 and 2, respectively.

1.3. Advanced Level

Students who pass CS146 should be able to perform the following tasks:

Task 1

Apply DFS to a given graph, giving the sequence of nodes visited and the edge type of each edge in the graph. (Assessed with an exam question.)

Alternative Task 1: Given the discovery and finish times for nodes in a graph covered by DFS, give the edge types of a specified set of edges. (Assessed with an exam question.)

Task 2

For a particular sorting algorithm (such as radix sort, heapsort, mergesort or quicksort) indicate what the array being sorted will hold at a specified point during the execution of the algorithm. (Assessed with an exam question.)

Task 3

Write a program that implements a specified data structure (such as list, stack, queue, search tree, heap, union-find ADT, 234 tree, or graph). (Assessed with a programming exercise.)

The instructor reported data averaged over two sections. In the raw data matrix this averaged data is used for each section.

The report indicates that on the average, 50%, 70%, and 63% of passing students were able to perform the tasks.

The author of the CS146 report makes the following noteworthy comment:

I generally give exams where I expect the average to be about 50%. Getting 70% on a problem generally means that the student understands it, but made some error in their work.

1.4. Summary

The following BSCS.OC9 sheet is taken from data.xls. The entries indicate the percentages of passing students who received full or near-full credit on the task question representing the corresponding task:

Tasks

Sec1

Sec2

Sec3

 

Beginning

% success

% success

% success

mean

CS46B.Task1

61%

 

 

61%

CS46B.Task2

83%

 

 

83%

CS46B.Task3

39%

 

 

39%

Intermediate

 

 

 

 

CS149.Task1

97%

67%

79%

81%

CS149.Task2

74%

73%

72%

73%

CS149.Task3

56%

56%

54%

55%

CS151.Task1

85%

86%

 

86%

CS151.Task2

78%

64%

 

71%

Advanced

 

 

 

 

CS146.Task1

50%

50%

 

50%

CS146.Task2

70%

70%

 

70%

CS146.Task3

63%

63%

 

63%

 

1.5. Analysis

Perhaps the statistic that stands out in this data is the meager 39% of students able to successfully implement a recursive method. The specific task question asks students to implement a recursive method that counts the number of occurrences of some data value in a binary tree.

It might be argued that this problem is too difficult for CS46B students, but the success of such an argument would depend on the amount of coverage given to recursion, binary trees, and similar problems.

More importantly, the department needs to decide how much recursion students need to know. Is it a dying art, an anachronism from a more elegant age? Many practicing software engineers freely admit to not being comfortable with recursion. Many problems can be solved using recursion or (often more efficiently) iteration. Should the department accept that only 39% of CS46B students can implement a recursive method?

On the other hand, recursive solutions are often easier to find than equivalent iterative solutions (assuming the programmer is comfortable with recursion). In some cases-- e.g. implementing compilers and parsers-- iterative solutions are hard to find. If found they tend to be complex and messy.

In functional languages like LISP, Haskell, and XSLT iteration either doesn't exist (because of its dependence on the state of some loop control variable) or is grafted onto the language Frankenstein-style, the way goto statements are grafted onto structured languages. Instead, programmers are encouraged to eschew traditional control structures in favor of higher order recursive functions (such as map and filter). In effect, functional languages exploit the trade-off between complexity and abstraction.

 

1.6. Recommendations

Students should see recursion again in CS152, where they are required to learn a functional language. Perhaps the department should consider adding a task that addresses recursion to BSCS.OC11:

The ability to write programs of moderate sophistication in a functional programming language

Note: this outcome is scheduled to be assessed this fall.

Recursion tends to be second nature to students who learn Scheme as their first language. For this reason many top universities (MIT, Berkeley, Carnegie-Mellon) teach Scheme in their introductory programming course. Recursion is taught to children using the Logo programming language. (Years ago the SJSU CS department taught Logo and Scheme.)

Last semester CS40 students learned to solve difficult problems by building models using NetLogo, the agent-based successor of Logo. At the end of the semester students were able to build useful engaging models that used recursion.

The department might kill several birds with a single stone by strongly suggesting to incoming students with weak backgrounds that they take NetLogo-based CS40 class before taking CS46A.