BCDEF
1
CS POGIL Activity Writing Program 2022
2
These 58 classroom-ready activities were developed as part of the CS POGIL Activity Writing Program in January–August 2022.
3
4
5
Note: Some of these actvities have not yet been used with students. We encourage you to review the activities, try them out in your classes, and provide feedback to the authors. More activities are available at http://cspogil.org
6
This program was funded by the National Science Foundation under IUSE award DUE-1626765.
7
Author NameCourse / Content AreaActivity TitleTopics CoveredLearning Objectives
8
Jingsai LiangAlgorithmsAnalysis of Recursive Algorithmsrecursion, algorithm analysis, factorial, Fibonacci number
Students will solve recurrence relation and analyze the time complexity for recursive algorithms.
Students will compare the efficiency between iterative and recursive implementations of computing Fibonacci numbers.
9
Pam SmallwoodComputer ArchitectureMIPS Machine Language - Part 1
Architecture, Computer Architecture, MIPS machine language, MIPS R-type instructions, MIPS I-type immediate instructions
Identify the fields of the three MIPS machine language formats.
Convert MIPS R-type instructions from assembly language to machine language.
Convert MIPS I-type immediate math/logic instructions from assembly language to machine language.
10
Pam SmallwoodComputer ArchitecturePipeline Diagrams and Pipeline Timing
pipeline, MIPS pipeline, CPU pipeline, pipeline clock cycles, pipeline timing, pipeline diagrams
Explain each part of a pipeline diagram.
Use a pipeline diagram to determine how many cycles are necessary to complete a set of LW instructions.
Apply a formula to determine the number of cycles required to complete any number of instructions in a pipeline.
11
Pam SmallwoodComputer Architecture
Building a MIPS Single Cycle Datapath - Part 1: R-type Instructions
datapath, single cycle, MIPS single cycle datapath, R-type instruction datapath
Identify all hardware units that will be used within the CPU, when executing MIPS R-type instructions.
Describe the datapath that the bits of a MIPS R-type instruction will follow when executing on a single cycle CPU, identifying the inputs and outputs of each hardware unit along the way.
Identify some MIPS instructions that will not be supported by this datapath.
12
Pam SmallwoodComputer ArchitectureMIPS machine language - Part 2
Architecture, Computer Architecture, MIPS machine language, MIPS I-type instructions, MIPS J-type instructions
Convert MIPS I-type LW and SW data transfer instructions from assembly language to machine language.
Convert MIPS I-type BEQ and BNE branch instructions from assembly language to machine language.
Convert MIPS J-type J jump instruction from assembly language to machine language.
13
Pam SmallwoodComputer ArchitectureData Hazards and Forwarding Solutions
data hazards, MIPS data hazards, pipeline data hazards, forwarding, pipeline forwarding
Explain what a data hazard is.
Analyze R-type instructions running on a MIPS pipelined processor to determine where data hazards exist.
Describe the concept of forwarding and how it can be used to solve problems caused by these data hazards.
14
Pam SmallwoodComputer ArchitectureData Hazard Detection and Handling – Part 1
data hazards, MIPS pipeline data hazards, data hazard detection, data hazard detection rules, forwarding unit
Explain how and when forwarding can be used to handle MIPS data hazards.
Describe the additional Forwarding Unit hardware, pipeline register data input, and control signal output lines that are needed to support forwarding within a MIPS pipelined datapath.
Evaluate data hazard detection rules to identify and handle data hazards for MIPS R-type instructions.
15
Pam SmallwoodComputer Architecture
Building a MIPS Single Cycle Datapath - Part 2: Adding I-type Memory Access Instructions
datapath, single cycle, MIPS, memory, R-type
Modify the R-type datapath with additional hardware and paths to support executing MIPS I-type LW and SW memory access instructions.
Describe the datapath that the bits of the MIPS LW and SW instructions will follow when executing on a single cycle CPU, identifying the inputs and outputs of each hardware unit along the way.
Determine whether MIPS immediate math/logic instructions and MIPS branch instructions can be supported by the modified datapath.
16
Pam SmallwoodComputer ArchitectureBooth's Algorithm
Booth’s algorithm, binary multiplication, 2’s complement multiplication
Apply Booth’s algorithm to multiply signed 2’s complement binary integers
○ Identify the multiplicand and multiplier for multiplication.
○ Identify the least significant bit (LSB) and previous least significant bit (previous LSB) at the start of the algorithm and after each pass.
○ Know and apply the correct operation for the algorithm, based on the LSB and previous LSB.
○ Know when to stop the algorithm and check the results.
17
Pam SmallwoodComputer ArchitectureIEEE Format for Binary Floating Point Numbersfloat data type, IEEE 754 standard, IEEE 754 binary format
Convert the fractional part of a decimal number to a binary number
Normalize decimal and binary floating point numbers
Identify the three parts of the IEEE standard for Single Precision Floating Point numbers and explain how each part is stored within the 32 bits
18
Mark GondreeComputer OrganizationData Reps IV – Layout of Data in Memorymulti-byte objects, endianness, struct padding, memory
Sketch the byte layout of objects (e.g., integers, shorts) in either big-endian or little-endian architectures.
Sketch the layout of structs in memory, including members and padding.
Describe the relative location of data held in arrays, including calculating the starting address of some particular element of an array.
19
Mark GondreeCryptographySymmetric Encryptioncryptosystem, key space, message space, ciphertext spaceList the three algorithms that must be defined for a cryptosystem, and express the relationships among these.
Characterize the size of the keyspace and the average cost of a brute force attack.
20
Mark GondreeCryptographyPerfect SecrecyBayes' theorem, conditional probability, cryptosystem, cipherApply rules about conditional probability to argue if a potential cipher may or may not be perfectly secure.
Recognize which features of a cryptosystem lead us to claim it achieves perfect secrecy.
21
Ben SchaferCS0Exploring the Use of Events in StorytellingScratch, eventsUnderstand how to use broadcast events to coordinate multiple sprites.
Read existing code to determine what it does.
Modify existing code to expand its function.
22
Ben SchaferCS0Conditionals in ScratchScratch, conditionals
Write a Scratch program to use a conditional (IF or IF/ELSE) to respond appropriately based on the value stored in a variable.
Combine multiple conditionals to address situations with more than two options.
Oral and Written Communication.
23
Ben SchaferCS0Understanding Animations in ScratchScratch, animation, loopsExplain the coordinate system in Scratch and relate this system to the coordinate system used in their math courses.
Explain the direction system in Scratch and relate this system to the direction system used in their math courses.
Consider programs with loops and evaluate the final outcome of a program with loops.
Oral and Written Communication.
24
Ben SchaferCS0Coordinating Sprites to Tell StoriesScratch, animation, events, timingCoordinate the actions of multiple sprites to tell a story by using timing.
Coordinate the actions of multiple sprites to tell a story by using events
Oral and Written Communication
25
James VanderhydeCS0The Halting ProblemAlgorithms, decidability, halting problemUse an algorithm as input to an algorithm.
Recognize an infinite loop.
Explain why the Halting Problem cannot be solved.
Critical thinking.
26
Ben SchaferCS0Text based I/O and Variables in ScratchScratch, text-based I/O, variables
Use programmer defined VARIABLES to store multiple user inputs for later use and explain why these blocks are normally preferred to using the ANSWER block.
Create customized output using the SAY, JOIN and ANSWER or VARIABLE blocks.
Oral and Written Communication.
27
Donna Gavin CS1Selection Sortsorting, selection sort, performance, linear searchDescribe the performance of a linear search on an unsorted list versus a sorted list.
Identify the key parts of a selection sort algorithm.
Describe and apply the selection sort algorithm, in either ascending or descending order.
Gain insight about why sorting is so important in computer science.
28
Shawn KennerCS1Booleans 2logical equivalence, negation, compound expressionsJust like we simplify mathematical expressions we can simplify boolean expressions.
DeMorgan’s Law can be used to simplify compound expresions involving negation.
Teamwork
Oral and written communication
29
Wei JinCS1Advantages of Object-Oriented Programmingobject-oriented programming, reference variable, implicit parameterIdentify the advantages of using the OO approach in data representation / storage.
Identify the advantages of using the OO approach in information passing.
Information Processing
30
Wei JinCS1 / JavaJava Exception Propagation and HandlingException Propagation, Exception Handling, Try-Catch StatementDescribe the flow of exception propagation.
Describe how try and catch statement works and how it can be used to handle user input errors.
Interpret the information contained in images and given code samples, make references, and extract patterns.
31
Wei JinCS1 / JavaScaffolding for Problem Solving with Loopswhile loop, problem-solving using loopsIdentify the advantages of solving a problem using loops.
Apply a scaffolding strategy that starts with a sequential code and then transforms it into a loop-based solution.
Interpret the information contained in diagrams and given code samples, make references, and extract patterns.
32
Wei JinCS1 / JavaStructure Decision for If Statementif statement
Identify the differences between a solution using a multi-branch if statement and a solution using a sequence of multiple single-branch statements.
Determine the most proper if statement structure for a given problem in terms of both correctness and code efficiency.
Interpret the information contained in flow charts and code samples, extract patterns, and identify critical decisions that a programmer needs to make when using if statements.
33
Nicole SebekCS1 / JavaCompareTostring methodsAccurately predict the output of two strings using compareTo being either 0,
positive, or negative.
Critical Thinking
Information Processing
34
Nicole SebekCS1 / JavaCreating and modifying objectscreating objects, modifying objectsCreate all the types of Objects they have constructors for.
Access public methods from a different class.
Explain what happens when an object is printed with or without a toString.
Critical Thinking
Information Processing
35
Kevin WortmanCS2 / C++Pointers and Memory Leakspointers, variables, objects, memory management, memory leaks
Trace the execution of C++ code and draw a sketch of the pointers and objects created by the code.
Diagnose and communicate whether code contains a memory leak error, double delete error, or is free of memory management errors.
Drawing precise sketches of objects and pointers (Written Communication).
Analyzing code to determine whether it obeys a rule (Assessment).
36
Victor NormanCS2 / C++Array Addressing and Pointers in C++array, element, pointer, argument, function
Explain how consecutive items in an array are in consecutive locations in memory and how one can compute the location of the i-th item in an array.
Explain how you can access items in arrays using pointers and use pointer arithmetic to iterate through an array.
Explain how you can use two different styles when writing the type of an array (int arr[] and int *arr).
Accurately interpreting information to determine meaning and to extract relevant evidence (Critical Thinking)
37
Victor NormanCS2 / C++C++ Class Inheritanceparent/child, base/derived, explicit-value base constructor
Define a parent/child (base/derived) class relationship in C++
Explain when C++ defines and calls constructors automatically.
Write code to call explicit-value base class constructors.
Interpret C++ code to determine meaning and to extract relevant evidence supporting when C++ automatically creates and/or calls constructors, when classes have or do not have explicit-value constructors (Critical Thinking)
38
Kevin WortmanCS2 / C++Stacksstack, LIFO order, push, pop, singly-linked listExplain LIFO order.
Sketch the result of push and pop operations on a stack.
State whether an arrayed stack is more efficient with the top at the first or last index.
Use evidence to compare alternative data structures and determine which is more efficient (Critical Thinking).
39
Kevin WortmanCS2 / C++Binary Search Tree Structurebinary search tree, BST, node, parent, child, BST order invariantIdentify, sketch, and define binary search tree concepts: node, parent, child, root, leaf, and the order invariant.
Search a binary search tree, identify the nodes that are visited, and state whether the search succeeds or fails.
Explain why the binary search tree search algorithm is correct despite not visiting all nodes.
Analyze how a data structure invariant supports the correctness and efficiency of an algorithm (Assessment).
40
Kevin WortmanCS2 / C++Multiplicative Hashinghash table, collision, chaining, adversarial analysisIdentify the structure, keys, and collisions of a hash table, and sketch the result of adding keys to a hash table.
Evaluate, generate, and analyze multiplicative hash functions.
Explain why hash table collisions are unavoidadable in practice.
Identify, evaluate, generate, and analyze multiplicative hash functions (Information Processing).
41
Victor NormanCS2 / C++Parameter Passing in C++C++, parameter passing, data structures
Discover the properties of pass-by-value parameters, pass-by-reference parameters, and pass-by-constant-reference parameters.
Identify which parameter passing modes can be used for in parameters, out parameters, and in/out parameters.
Critical thinking
Information Processing
42
Kate HoldenerCS2 / JavaPolymorphism with Inheritanceinheritance, polymorphismExplain the concept of polymorphism
Understand how polymorphism can be achieved with inheritance
Override superclass methods
Teamwork
43
Kate HoldenerCS2 / JavaPolymorphism with Abstract Interfacesinterfaces, polymorphismExplain the concept of an interface in Java
Use abstract interfaces to achieve polymorphism
Written Communication - Explain code changes in written sentences (without using code)
44
Kate HoldenerCS2 / JavaJava Exception Handlingexception handlingWrite Java code to prevent abnormal program execution with exceptions
Explain how polymorphism is utilized in the Java exception handling mechanism
Critical Thinking: Argue which ordering of the exception catch blocks is most appropriate.
The argument will be formed by stating their conclusion, providing evidence, and linking evidence to the conclusion.
45
Kate HoldenerCS2 / JavaJava Compiler and Runtime Errorscompiler errors, runtime errors, debuggingRead and interpret errors generated by the Java compiler.
Fix compiler errors.
Explain the difference between a compiler and a runtime error.
Critical thinking - forming arguments
46
Kate HoldenerCS2 / JavaBeautiful Code
naming variables & methods, code indentation, class organization, duplicate code
Describe the rules for writing readable code.
Identify opportunities for improving code readability.
Explain the dangers of code duplication.
Teamwork
Management
47
memory layout, stack, stack frame, buffer overflow, command-line parameters
Determine when and at what position function data is added to and removed from the stack corresponding to the execution of functions within a program.
Describe the purpose, relative positions, growth directions and limits of the code, data, heap and stack segments within the main memory of a computer.
Determine the layout and values of a function’s stack frame based on its parameters, local variables and its invocation within a program.
48
Kathryn LenthDatabase Referential IntegrityReferential integrity, foreign key constraints, referential actionsDefine referential integrity and explain why it is important.
Identify row operations that could violate referential integrity.
49
Kathryn LenthDatabase Foreign key constraints and referential actions
Define what a foreign key constraint is and explain why it is helpful.
List the referential actions available for foreign key constraints and explain what they do.
Decide which referential action is most appropriate for a foreign key constraint based on the database business rules.
50
Kathryn LenthDatabase Foreign Keys and Inner Joinsrelationship, foreign key, inner joinExplain what a foreign key is and how it allows tables to be related.
Use an inner join to show data from related rows in multiple tables.
51
Caroline BudwellDiscrete MathematicsPermutations and Combinationspermutations, combinationsClassify counting problems as either combination or permutation problems.
Apply the formula for the combination of objects to a variety of different situations.
Critical thinking skills to develop formulas for combinations.
52
Mark GondreeDiscrete MathematicsFirst Order Logic - Quantifierspropositional logic, first-order logic, quantifiers
Employ quantifiers to express ideas like "anyone who is a tiger is also a cat."
Assess the truth value of quantified expressions and apply De Morgan's Law in the presence of quantifiers.
Information Processing: students will be able to interpret diagrammatic models and make inferences based on models
Critical Thinking: students will be able to identify patterns and draw conclusions
53
Caroline BudwellDiscrete MathematicsIntroductions to Counting and Permutationscounting, permutations, product rule, sum ruleDetermine when to use the product rule versus the sum rule when counting.
Apply the formula for the permutation of objects to a variety of different situations.
Explore the two different permutation formulas and be able to apply them to permutation problems.
Critical thinking skills to develop formulas for counting.
54
James VanderhydeGame DevelopmentEvent-driven programming Events, GUI, JavaFX
Trace the flow of control of key presses in an event-driven computer program.
Use an anonymous inner class to simplify code.
Write Java code to implement handling a mouse movement event.
Reflect on their own learning to become aware of points of confusion that can occur when developing event-driven applications.
55
James VanderhydeGame DevelopmentMotion BehaviorsAI, Game development, UnityClassify motion behaviors into three levels.
Calculate steering forces and draw a projected path for the “seek” steering behavior .
Plan an implementation of the “pursue” steering behavior.
Coordinate their efforts to accomplish the goals of the activity.
56
James VanderhydeGame DevelopmentEntity-Component-SystemGame development, Software architectureDistinguish between object-oriented and data-oriented programming.
Decompose a solution into entities, components, and systems.
Implement a new system.
Evaluate and interpret information from class diagrams.
57
Jingsai LiangMachine LearningKNN (K Nearest Neighbors)nearest neighbors, classification, regressionBuild a KNN binary classification model to predict the shapes of unknown points on a two-dimensional plane.
Build a KNN simple regression model to predict response values.
58
Jingsai LiangMachine LearningConfusion Matrixmodel evaluation, confusion matrix, precision, recall, accuracy, FPRCalculate the table of confusion to analyze the prediction results of classification models.
Evaluate the binary classification models using precision, recall, accuracy, FPR, and two types of errors.
59
Mark GondreeOperating SystemsIntro to Queuing Theoryqueuing theory, scheduleing, Little’s LawState the goals of a queuing system in terms of utilization, throughput, and turnaround time.
Calculate response time, service time, and queuing delay in the context of a simple queuing system.
Interpret Little's Law under various arrival rates and service rates.
60
Paul Salvador InventadoProgramming / KotlinNull Safety and FunctionsKotlin, nullable variable, functionsWrite code that uses nullable variables to store and retrieve data.
Design and implement functions.
Information processing. Extract syntactical and structural patterns from sample code.
Critical thinking. Analyze code to generalize and apply knowledge in new contexts.
61
Paul Salvador InventadoProgramming / KotlinLambda and Higher order functions lambda function, higher order functions, Kotlin, mobile developmentDesign, implement, and use lambda functions.
Design, implement, and use higher-order functions.
Critical thinking. Analyze code to generalize and apply knowledge in new contexts.
Oral and written communication. Explain a concept in written form.
62
mutable/immutable variables, conditional statements, mutable/immutable lists, arrays
Explain the difference between mutable and immutable variables.
Recommend the appropriate conditional statement for a programming problem.
Explain the difference between mutable and immutable lists.
Explain the difference between arrays and lists.
Recommend the appropriate for-loop variation to solve a programming problem.
Use an elvis operator to assign a default value to a nullable variable.
Extract syntactical and structural patterns from sample code.
Compare and contrast different solutions.
63
Jessica JohnstonScientific ComputingVisualizing Functions that Change with TimeVisualizing Functions that Change with Time
Students will use the linspace function to create an array of evenly spaced values.
Students will plot a position-dependent function with differing variable values to determine the effect of each variable on the function.
Students will create an animation for a time-dependent function with differing variable values to determine the effect of each variable on the function.
Critical Thinking
Information Processing
64
Kate HoldenerSoftware DesignDependency Inversion Principledependency inversion principle (DIP)Explain how the dependency is inverted in the Dependency Inversion Principle (DIP).
Explain the benefits of applying DIP.
Apply DIP to software design.
Teamwork
Communication
65
Kate HoldenerSoftware DesignSingle Responsibility Principlesingle responsibility principle (SRP)Define Single Responsibility Principle (SRP)
Explain the benefits of SRP
Apply SRP to software design
Critical thinking
Problem solving