CS1101S: Programming Methodology

A Freshmen Module in the Department of Computer Science

School of Computing

National University of Singapore

by Martin Henz, Low Kok Lim, and Boyd Anderson.

CS1101S is a module taught in the Department of Computer Science at the NUS School of Computing. It is designed to give Computer Science majors 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. The module uses Structure and Interpretation of Computer Programs, JavaScript adaptation (SICP JS), see textbook. Since the its introduction at NUS as IC1101S in 1997, the module underwent substantial revisions and additions. As of 2020, CS1101S is characterized by a constructivist didactic approach, an immersive learning environment and a considerable wealth of application domains covered in examples to stimulate student interest in computing, while retaining Abelson's and Sussman's didactic approach.

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 four modular credits. The module offers opportunities for additional exercises and challenges that intensify the learning experience and broaden the students' foundation in programming methodology. Successful completion of these exercises is awarded one further modular credit, which means that the module has a maximum of five attainable modular credits.

Since Academic Year 2018/19, CS1101S is the mandatory freshman programming module for freshmen in the 4-year Bachelor in Computing (Computer Science) of the School of Computing at the National University of Singapore (NUS). The module is the most rigorous introduction to programming offered by NUS.

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 lecture per week that bring the class 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.)
Reflections: 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 reflection sheet]
Studios: The main vehicle for the constructivist teaching approach are studios that comprise 8 students and a facilitator called "Avenger". These studios meet physically in a 2-hour session every week to discuss the current material based on studio sheets that are handed out a few days prior to the meetings. [example studio exercises]
Online Discussions: The module uses the online Q&A system piazza to host semester-long forums for students to discuss their progress, questions and difficulties with each other and the module staff.
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]
Solving and grading missions 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.
Quests: 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 quests, typically aligned with the missions, and the quest schedule is given below. [example 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 Studios let students enter their personal Zones of Proximal Development, both during the studio 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 immersive. 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 features syntax highlighting, error reporting, Avenger/lecturer/student comments and custom support for runes, curves and lists.; The publicly available playground of the Source Academy serves as IDE for the textbook.
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 four versions of The Source, starting with a very small language called Source §1 (corresponding to Chapter 1 of the textbook) and ending in a fairly comprehensive subset of JavaScript called Source §4. For each student task, the IDE is configured to accept only programs written in the respective Source version. This provides the teaching team with rigorous control over the programming language constructs to be used by the students. [example description of Source (Source §2)] The choice of features of JavaScript to be included in Source is inspired by Douglas Crockford's JavaScript: The Good Parts.
Textbook: The module uses Structure and Interpretation of Computer Programs, JavaScript adaptation, a JavaScript version of the original Scheme-based SICP.
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 (reflection sheet)
Lecture 8B: Memoization (glimpses into data structures and algorithms)
Lecture 9A: Object-oriented Programming I (studio 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 quests, grouped into seven themes.

Runes (graphics based on tiling 2D and 3D space)

Mission 1: Understanding the Force
Mission 2: Rune Reading
Quest 2.1: Runic Carpets
Mission 3: Beyond the Second Dimension
Quest 3.1: Force Efficiency

Curves (graphics based on drawing lines on a 2D canvas)

Mission 4: Curve Introduction (mission description)
Quest 4.1: Defend Yourself (quest description)
Mission 5: Curve Manipulation
Quest 5.1: Wizard
Mission 6: Gosperize
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
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
Quest 15.1: Ship Arming - The Grand Laser
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
Quest: Back to Basics
Quest: Back to Basics! - Part 2

Streams

Mission 20: Stream Manipulation
Quest: Multiple Headaches
Mission 21: Force Calculus
Mission 22: Extreme Streams
Quest: Force Regeneration
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"

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: be able to implement bubble sort and insertion sort be able to implement linear search and binary search (both iterative and recursive versions): These outcomes are covered by with new lectures and exercises.

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

Assessment

The student assessment is distributed approximately as follows:

22%: Continuous assessment: The completion of programming assignments ("missions") is assessed using visual inspection of the programs and test cases. Timely submission and tidy programming style is incentivized through a game.
6%: Reflection attendance: Attendance of Reflection sessions is necessary for proper assimilation of the lecture material.
6%: Studio attendance and participation: Active participation in studios is essential for achieving the learning objectives and therefore incentivized in the assessment.
12%: Reading Assessments: Two reading assessments test a thorough understanding of the static and dynamic aspects of computer programs.
12%: Midterm Assessment: The midterm test is a 95-minute written test, comprising a mix of comprehension, analytical and programming tasks.
12%: Practical Assessment: The practical test assesses student's programming skills with time constraints. It is conducted online 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.

The exact weightage of the assessment components will be announced at the beginning of the semester.