CS1101S: Programming Methodology

A Freshmen Module in the Department of Computer Science

School of Computing

National University of Singapore

by Martin Henz and Low Kok Lim

CS1101S is a module taught in the Department of Computer Science at the NUS School of Computing. It serves as a rigorous and thorough introduction to programming methodology. The module follows the didactic strategy of the classic textbook Structure and Interpretation of Computer programs (SICP), which Harold Abelson and Gerald Jay Sussman developed for MIT introductory programming class 6.001. Since the module's introduction at NUS as IC1101S in 1997, it underwent substantial revisions and additions. As of 2016, CS1101S is characterized by a constructivist didactic approach, an immersive gamified learning environment and a considerable wealth of application domains covered in examples to stimulate student interest in computing.

The teaching team shares a set of values that guides it in its effort to achieve the module outcomes.

Curiosity
Natural human curiosity is the best starting point for learning.
Technical depth
Excellence in programming comes from a mastery of the concepts, tools and processes involved.
Engagement
The impact of computing in society is vast, and it is the responsibility of computing professionals to help humankind to use computing for its benefit.
Playfulness
Play is a central component of learning and of human life in general.

The module carries five modular credits (typical NUS modules have four), and additional programming exercises called side quests carry the option of one further modular credit, which means that the module has a maximum of six attainable modular credits.

CS1101S is offered as a more challenging alternative to CS1010. Eligible are the students in the 4-year undergraduate degrees offered by the Department of Computer Science. Out of 321 eligible students, 102 students have chosen CS1101S in Semester 1 AY2016/17.

Approach

The module broadly follows constructivist teaching methods, with a particular emphasis on problem-based learning. The following list contains the main instructional components:
Lectures
The module content is introduced in one two-hour and one one-hour lecture per week that bring the whole cohort (around 100 students as of 2016) together in a classroom. [example webcast, example slides]
Paths
The digestion of the material is then facilitated with paths, which are small sets of compulsory simple online quizzes and exercises, to be completed within two days of the lecture. (The picture on the right shows an example path, while in progress.)
Recitations
The main examples given in the lectures are re-visited in 1-hour practical sessions led by a lecturer, and conducted in smaller classes of around 20 students each. [example recitation sheet]
Discussion groups
The main vehicle for the constructivist teaching approach are discussion groups that comprise 8 students and a facilitator called "Avenger". These groups meet physically in a 2-hour session every week to discuss the current material based on discussion group sheets that are handed out a few days prior to the meetings. [example discussion group exercises]
Discussion forum
The module uses the NUS Integrated Virtual Learning Environment (IVLE) to host a semester-long forum for students to discuss their progress, questions and difficulties.
Missions
A central vehicle for learning in CS1101S are "missions", which are homework programming assignments that are completed by the students under close online supervision by the students' Avenger. The Avenger points out mistakes, answers questions and provides guidance, and—upon online submission of the mission—grades it and provides written feedback. The module comprises 22 missions, grouped into seven themes, and the mission schedule is given below. [example mission description]

The mission work is facilitated by the Source Academy, an online programming environment built for CS1101S. The missions are embedded into a coherent story line in the Academy; the picture on the right shows a scene set on an alien planet.

Side quests
Side quests are additional optional homework programming assignments. By completing most of the these, the student earns one additional modular credit for CS1101S. The module comprises 13 side quests, typically aligned with the missions, and the side quest schedule is given below. [example side quest description]
Contests
The module comprises seven programming contests, covering runes and curves, robotics and sound processing. [example contest description (Contest 15.3)]
In the terminology of constructivist learning theory, the Avengers are the primary More Knowledgeable Others in this module, and the Discussion Groups let students enter their personal Zones of Proximal Development, both during the discussion group sessions and while engaging with the material in the Source Academy and interacting with their Avenger online.

Highlights

The Source Academy
The module is fully gamified. Students are immersed in a sci-fi-themed spaceship environment called "The Source Academy" and experience the online material as "cadets" in the Academy. The images on the right depict the student "dorm" room in the Academy and the control room of the spaceship, respectively. The Source Academy was designed by a team of graphic artists under the direction of Ng Tse Pei.
Online Integrated Development Environment
Programming in CS1101S is facilitated by a custom-built web-based integrated development environment (IDE), which supports multiple interactive sessions, syntax highlighting, error reporting, customization of the student workspace, Avenger/lecturer/student comments and custom support for runes, curves and lists.
The Source
The programming language used in CS1101S is playfully named "The Source". It is a small subset of the widely used programming language JavaScript. More precisely, the module uses a succession of eight versions of The Source, starting with a very small language called The Source Week 3 and ending in a fairly comprehensive object-oriented subset of JavaScript called The Source Week 12. For each student task, the IDE is configured to accept only programs written in the respective version of The Source. This provides the teaching team with rigorous control over the programming language constructs to be used by the students. [example description of The Source (The Source Week 4)] The choice of features of JavaScript to be included in The Source is inspired by Douglas Crockford's JavaScript: The Good Parts.
Textbook
The interactive textbook of CS1101S is a JavaScript version of the original Scheme-based SICP, translated by Martin Henz.
Sumobot
The module comprises an annual robot programming contest called "Sumobot". This contest also serves as the main social gathering where current students, Avengers, lecturers and alumni gather to celebrate the spirit of computing. [footage of the winning contest, 2016 Computing News]
Runes, curves, sounds
Graphics and sound provide excellent domains to practice basic problem solving skills and experientially demonstrate computational processes. CS1101S harnesses this potential. Below are examples of artwork produced by students Ang Yee Chin and Ang Zhan Yu in 2016, entirely through programming as submissions to programming contests, and Liu Hang's entry to the sound contest of the same year can be heard by clicking here.
Community
CS1101S has over the years cultivated a community of learners. The best and most dedicated students typically join the team of Avengers in their second, third or fourth year of study, and even many alumni keep up to date on the activities in CS1101S through the module's Facebook group.

Lecture and Mission Topics

Lectures

The following list contains the lecture schedule. The number designates the semester week and the letter designates the duration of the lecture; "A" lectures are 2-hour lectures and "B" lectures are 1-hour lectures.
Lecture 1A: Introduction; Procedural Abstraction
Lecture 1B: Elements of Programming
Lecture 2A: Abstraction, Scope, Recursion (webcast)
Lecture 2B: Orders of Growth (glimpes into algorithm analysis)
Lecture 3A: More Recursion; Higher-order Functions
Lecture 3B: Functional Composition - Curve Drawing (glimpses into computer graphics)
Lecture 4A: Introduction to Data Abstraction (slides)
Lecture 4B: The Game of Nim (glimpses into software engineering)
Lecture 5A: List and Tree Processing
Lecture 5B: Symbolic Data (glimpes into Artificial Intelligence)
Lecture 6A: Representation of data structures
Lecture 6B: Sound Processing (glimpses into sound processing)
Recess
Midterm Test (in lieu of 7A)
Lecture 7B: Language Processing (glimpses into programming languages)
Lecture 8A: Environment Model and Mutable Data (recitation sheet)
Lecture 8B: Memoization (glimpses into data structures and algorithms)
Lecture 9A: Object-oriented Programming I (discussion group exercises)
Lecture 9B: Object-oriented Programming II
Lecture 10A: Streams I
Lecture 10B: Streams II
Lecture 11A: Meta-circular Evaluator I (glimpses into programming language implementation)
Lecture 11B: Meta-circular Evaluator II
Lecture 12A: HTML5 I
Lecture 12B: HTML5 II
Lecture 13A: Special Topics in Web Programming (glimpses into programming the web)
Lecture 13B: Module Summary

Missions

The homework consists of 22 missions and 13 optional side quests, grouped into seven themes.
Runes (graphics based on tiling 2D and 3D space)
Mission 1: Understanding the Force
Mission 2: Rune Reading
Side Quest 2.1: Runic Carpets
Mission 3: Beyond the Second Dimension
Side Quest 3.1: Force Efficiency
Curves (graphics based on drawing lines on a 2D canvas)
Mission 4: Curve Introduction (mission description)
Side Quest 4.1: Defend Yourself (side quest description)
Mission 5: Curve Manipulation
Side Quest 5.1: Wizard
Mission 6: Gosperize
Side Quest 6.1: Kochize
Mission 7: Diagnostics and Dragonize
Encryption (cyphers, codes, public/private key encryption)
Mission 8: Tome Theory
Mission 9: Breaking the Code
Side Quest 9.1: Drill on Cryptography
Mission 10: Turing into the Force
Mission 11: Reflections
Sound Processing
Mission 12: Premorseal Communications
Mission 13: POTS and Pans
Mission 14: Musical Diversions
Mission 15: The Magical Tone Matrix
Side Quest 15.1: Ship Arming - The Grand Laser
Side Quest 15.2: Ship Arming - EMP Missile
Robotics
Mission 16: RoboWarriors
Game Programming
Mission 17: Rookie Training
Mission 18: Advanced Training
Mission 19: The Final Showdown
Side Quest: Back to Basics
Side Quest: Back to Basics! - Part 2
Streams
Mission 20: Stream Manipulation
Side Quest: Multiple Headaches
Mission 21: Force Calculus
Mission 22: Extreme Streams
Side Quest: Force Regeneration
Side Quest: Scanning Streams

Outcomes

The outcomes of the module are fourfold:
Subject-specific learning outcomes
The module aims to meet the learning outcomes specified by the NUS Department of Computer Science as delineated below. The module covers an additional list of learning outcomes, which are not required by the department but which are deemed of fundamental importance by the lecturers.
Overview of computing
The module provides glimpses into various fields in computing, with lectures and hands-on exercises in software engineering, computer graphics, algorithms and their analysis, robotics, game development, sound processing, programming languages and their implementation, Artificial Intelligence and web programming. These topics are typically covered in the weekly 1-hour lecture (lectures XB).
Computing culture
The module exposes the students to the culture specific to the field of computing: its obsession with formal structures, its extensive use of standards and APIs, its relentless drive for abstraction, e.g. separation of concerns (syntax vs semantics), as well as good doses of hacker/geek/nerd pride. (The picture on the right shows adult students immersed in building Lego robots for fighting sumo-wrestling matches. Nuff said!)
Love of computing
The module provides an environment in which students can fall in love with computing, even if they have chosen computing for practical or opportunistic reasons. (The heart is a student submission to the runes contest 2016.)

The following list of learning outcomes has been established on 11/8/2014 in a committee of lecturers of CS101 modules in the School of Computing. Each item is followed by the techniques how the learning outcomes are achieved in CS1101S.

"be able to write simple programs in the corresponding programming language to solve a task, given the constraints on the inputs"
After successful completion of the module, the students will be able to solve simple computational tasks by employing adequate abstraction techniques, by designing a computational process that solves the problem and by implementing a corresponding program in JavaScript.
"be able to manually trace through a program to identify logical errors"
The manual execution of programs is supported by two mental models. The substitution model serves as the basis for understanding simple state-less programs, whereas the environment model allows for manual tracing of difficult examples and can be applied to most modern programming languages.
"be able to differentiate between logical errors, syntax errors, and run-time errors"
Students learn this difference throughout the module through interacting with the module's Integrated Development Environment (IDE).
"be exposed informally to the concept of code specification in the form of comments in the code, explaining what are the expected inputs and outputs and what are the assumptions."
CS1101S emphasizes the importance of rigorously specifying the given problem. An outline of the solution always precedes its actual implementation in a computer program.
"know about what are some insecure functions to avoid (where applicable. e.g, CS1010)."
not applicable
"be able to generate test cases on their own, with focus on boundary/special cases."
The students are strongly encouraged to test their programs thoroughly before submitting them for grading.
"be able to debug with printf or equivalent functions."
"be aware of common strategies and good practices of debugging with printf or equivalent functions."
The students learn various practical techniques for identifying program errors, including such "print" statements.
"be able to identify opportunities to, and write, modularized code."
"be exposed to the concept of exception handling (where applicable, e.g., in CS1010S/FC, CS1010J)"
not applicable
"be exposed to a debugger (where suitable tools are available, e.g., for CS1010, CS1010J)"
not applicable
"introduction to good programming styles (e.g., naming convension, indentation, comments to explain complex logic)."
The classes emphasize the role of programs as devices for communicating computational processes, primarily between humans. Te students get gradually introduced to techniques for making programs readable. Over time, they learn to adhere to a fairly strict style guide for programming in The Source.
The following complementary list of desired learning outcomes has been established on 17/5/2016 in a committee of lecturers of CS101 modules in the School of Computing. Each item is followed by the techniques how the learning outcomes are achieved in CS1101S.
"Understand the concept of reusability and how a software application can be built on top of software libraries/packages (standard or third parties)."
CS1101S students are exposed to libraries and packages for most of their exercises. These libraries typically consist of data types that are built into their programming environment. For example, there is a Rune data type which allows for 2D graphics, and on operation stack(rune1, rune2) which puts one rune on top of another one.
"Be able to understand at a high level the compilation process (from pre-processing to compiling to linking), where applicable."
Students generally work in an interpretation-style environment, and the custom-built virtual machine for The Source is introduced to the students in a one-hour lecture (6B) that explains interpretation and compilation in detail, using T-diagrams.
"Develop a simple mental model of how a program is executed (CPU runs the code on data that is store in memory, function call leads to creation of call frames, which can explain recursion and variable scoping, etc) as a precursor to cs2100. For interpreted language, understand the role of virtual machine/interpreter."
The main goal of CS1101S is to instill a mental model for program execution. It is called the “environment model” and is adapted from the textbook Structure and Interpretation of Computer programs (SICP) by Abelson and Sussman. This mental model includes call frames and explains recursion.
"Understand the different data types and that there exists a representation of each in the memory, as well as the limitation of the representations due to limited number of bits. (Details can be left for CS2100.)"
Data abstraction plays a major role in CS1101S. We emphasize the contractual model (specification vs implementation) and discuss different representations of data structures (e.g. cartesian and polar coordinates for complex numbers). The students also get some appreciation for the double-precision floating point representation of numbers in JediScript (The only number type in the underlying JavaScript language), and its limitations for cryptography (where we use a BigNum library).
"[The module] should expose students to interesting exercises from different areas of CS (e.g., sound processing for 1D array, image procession for 2D array, drawing shapes, etc.) with the help of third party libraries or libraries provided by SOC."
Exercises in CS1101S include: 2D graphics (using rectangular patches called "runes" and using lines), sound processing, robotics, game programming and cryptography.
"[The module should introduce] object-oriented programming."
Students get exposed to object-oriented programming in dedicated lectures (Lectures Week 9A and 9B), which cover classes/instances, inheritance and late binding. The data structure of a “pair” is covered in Week 4 and serves as the main data abstraction, until object-oriented programming is introduced in Week 9.
The following desired outcome is covered from 2017 onwards.
After taking the module (CS1010 or its variants), students should:
These outcomes will be addressed in Week 12 of the 2017 edition of the module.

The following subject-specific learning outcomes are achieved as a result of the chosen didactic approach and are not required by the department. The lecturers consider these topic of sufficient importance for inclusion in the learning outcomes of CS1101S:

Recursive/inductive problem solving
Induction and recursion is the modules's central problem solving technique, and the "divide and conquer" method is described in terms of recursion. The photo on the right depicts CS1101S students working on the midterm test in 2016, which revolved around a classic example of recursive problem solving: Chinese Rings.
Higher-order programming
The students get exposed to higher-order programming early in the module as a natural consequence of functions as values.
Lists as fundamental data structure
Singly-linked, stateless list are introduced in Week 4 and serve as the primary data structure throughout the module. In Week 7, stateful ("destructive") operations on such lists are introduced.
Dynamic programming and memoization
The module introduces the students to the general ideas of dynamic programming and memoization through lectures and many programming exercises.
Streams
The representation of "activity" as functions that can be generated at will, stored and activated when needed is fundamental in modern programming. The students are exposed to this idea throughout the module, but specifically in the segment on stream processing, which highlights its potential for problem solving.
Web programming
The module covers HTML5 with two dedicated lectures and emphasizes the importance of web programming with an additional lecture on special topics in web programming.

Assessment

The student assessment is currently distributed as follows:
35%: Missions
The completion of programming assignments ("missions") is assessed by Avengers via visual inspection of the programs submitted by the students. Timely submission and tidy programming style is incentivized via deduction of marks.
5%: Discussion group participation
Active participation in discussion groups is essential for achieving the learning objectives and therefore incentivized in the assessment.
15%: Midterm test
The midterm test is a 95-minute written test, comprising a mix of comprehension, analytical and programming tasks.
15%: Practical Test
The practical test assesses student's programming skills with time constraints. It is conducted in a laboratory without internet access and the student attempts are automatically graded.
30%: Final Assessment
The final assessment is a 2-hour written test, comprising a mix of comprehension, analytical and programming tasks.