SCS Curriculum Reinvention Committee

This page contains notes and discussions related to the SCS Curriculum Reinvention Committee.

The content below has gratuitous markup so as to make it obvious how to add more stuff.

To edit this page, you first need to create an account - click the link in the top-right of the page. Then click on the edit tab just about the page headline. Or, you can edit individual sections.

COMP 1405/1406 Redesign

Topic Brainstorming

Add topics here at the end of the section. Please don't remove anything!

• WHAT IS COMPUTER SCIENCE
  • problem solving
  • algorithms
  • abstraction and problem decomposition
  • efficiency ??
• PSEUDO-CODE ??
• SEQUENCING INSTRUCTIONS
  • top down coding in sequence (e.g., draw a house)
• VARIABLES
  • declaring vs. assigning
  • memory usage ??
  • constants
  • examples:
    • compute simple math formulas
    • interactive input (e.g., use mouse position)
    • motion (if doing graphics)
• Numbers
  • integers
  • floats
• CONDITIONALS
  • simple IF/ELSE
  • nested IF
  • booleans(AND/OR)
  • examples:
    • make choices based on runtime input
    • basic state machine
    • edge cases / error checking
• ITERATION
  • repeating X times (REPEAT)
  • counting (FOR)
  • repeating until condition (WHILE)
  • nested loops
  • examples
    • sum/avg/max/min
    • counting matches
    • MonteCarlo approximation
    • loop until user input
    • searching (find first match)
• ARRAYS (1D and 2D)
  • initializing and memory usage
  • simple 1D (sum.avg/max/min)
  • insert/remove
  • copy/growing array
• Optimization
  • e.g., knapsack
  • greedy
• Simulation
  • virus clearing
  • Roomba
• Abstract data types
• Sorting
• Search
  • linear
  • binary
  • exhaustive
• Divide and conquer
• Dynamic programming
• FORMATTING
  • string manipulation
  • display in columns (i.e., tabbing)
  • display dates/times
• Data structures
  • lists
  • structures
  • tuples
  • binary trees
  • dictionaries
  • sets
  • stacks, queues
• Complexity analysis
  • informal
• OBJECTS
  • instance variables
  • initialization (constructors)
  • shared references
  • static vs. instance
• FUNCTIONS and PROCEDURES
  • simple computations and return values
  • passing parameters
  • passing arrays as parameters
  • helper methods
• RECURSION (likely 1406 material?)
  • inductive definitions of data and associated recursion patterns.
  • direct vs. indirect
  • tail recursion
  • examples:
    • math problems (factorial/sum/avg)
    • searching mazes
    • iterate a non recursive data structure (array)
    • iterate a recursive data structure (e.g., tree)
• PERSISTENCE (likely 1406 material?)
  • writing files
  • reading files
  • parsing files
• WINDOWING
  • display text output
  • get textfield input
  • buttons
  • design and layout
  • handling events
  • menus
  • dialog boxes
• GRAPHICS
  • drawing with lines/shapes
  • grabbing/selecting/moving graphical objects
• User interaction
• PROPER CODING STYLE
  • encapsulation
  • polymorphism
  • private/public/protected data
• INHERITANCE
  • class hierarchies
  • abstract vs. concrete classes ?
  • overriding/inheriting methods
  • type-casting (needed if JAVA used) ?
• NETWORKING ?? (1406 ... as interesting examples)
  • read internet page
  • two applications talk over network
• Event-driven programming
• Model-View-Controller (more for 1406)
• Database APIs
  • Allow use of key/value stores as used by standard websites
• Testing and debugging
  • design vs. implementation errors
  • basic test cases, regression testing?
  • basic debugger usage
  • strategies for identifying and fixing programming problems
• Software licenses
  • open source and commercial
  • restrictions on reuse
• How to read code
• editing and building software
  • basic IDE usage
• commenting, code formatting guidelines
• revision control
  • have students grab class code from this, pull updates
  • make commits/push to submit?
• Understanding APIs
  • basic idea of contract, side effects
• Concurrency/parallel code
  • maybe not standard locking but some clean parallel constructs?
• Relative costs of operations
  • memory vs. I/O vs. computation
  • very basic benchmarking
  • main idea: know that you can't predict what is going to be fast in practice w/o tests

• my first wiki entry ever! - djh

Should we copy the MIT 6.00 outline here?

Sub categories?

Yes, we can add sub categories here.

COMP1405 LIST OF TOPICS (UNORDERED) FOR WEEKLY OUTLINE (Mark's Opinion)

• WHAT IS COMPUTER SCIENCE
  • problem solving
  • algorithms
  • abstraction and problem decomposition
  • divide and conquer
  • efficiency (just an intro to the ideas behind it)
• PSEUDO-CODE
• SEQUENCING INSTRUCTIONS
  • top down coding in sequence (e.g., draw a house)
• VARIABLES
  • declaring vs. assigning
  • memory usage (how memory is affected) LATER
  • constants LATER
  • examples:
    • compute simple math formulas
    • interactive input (e.g., use mouse position)
    • motion (if doing graphics)
• Numbers
  • integers
  • floats MINIMAL HERE --- MAKE SURE THIS TOPIC IS TAUGHT SOMEWHERE IN CURRICULUM
• CONDITIONALS
  • simple IF/ELSE
  • nested IF
  • booleans(AND/OR)
  • examples:
    • make choices based on runtime input
    • basic state machine
    • edge cases / error checking
• ITERATION
  • repeating X times (REPEAT)
  • counting (FOR)
  • repeating until condition (WHILE)
  • nested loops
  • examples
    • sum/avg/max/min
    • counting matches
    • MonteCarlo approximation
    • loop until user input
    • searching (find first match)
    • Make sure to have examples with non-trivial loop invariants (e.g., gcd, searching)
• COMMENTING / CODE FORMATTING GUIDELINES
• ARRAYS (1D and 2D)
  • initializing
  • simple 1D (sum.avg/max/min)
  • insert/remove
  • copying as needed for examples
• OBJECTS TO BE DISCUSSED
  • instance variables
  • initialization (constructors)
  • shared references
  • static vs. instance
• FUNCTIONS and PROCEDURES
  • simple computations and return values
  • passing parameters
  • passing arrays as parameters
  • modular programming using functions and procedures
  • recursion
• USER INTERACTION
  • input and output interaction with environment (e.g. user)
• RELATIVE COSTS OF OPERATIONS
  • memory vs. I/O vs. computation
  • very basic benchmarking
  • often, but not always, you can't predict what is going to be fast in practice w/o tests
• SORTING
  • teach in context of indexing (e.g., search engines)?
  • illustration of: algorithms, complexity, recursion, divide-and-conquer
• SEARCH
  • linear
  • binary
  • exhaustive
• SIMULATION
  • possible examples: robots, Monte Carlo, virus clearing, Roomba
• Course work should include some code reading

COMP1406 LIST OF TOPICS (UNORDERED) FOR WEEKLY OUTLINE (Mark's Opinion)

• EDITING AND BUILDING SOFTWARE
  • basic IDE usage
• RECURSION
  • inductive definitions of data and associated recursion patterns.
  • direct vs. indirect
  • tail recursion
  • examples:
    • math problems (factorial/sum/avg)
    • searching mazes
    • iterate a non recursive data structure (array)
    • iterate a recursive data structure (e.g., tree)
• PERSISTENCE
  • writing files
  • reading files
  • parsing files
• WINDOWING
  • display text output
  • get textfield input
  • buttons
  • design and layout
  • handling events
  • menus
  • dialog boxes
• EVENT-DRIVEN PROGRAMMING (if not using Processing in 1405)
• MODEL/VIEW/CONTROLLER
• GRAPHICS (if not using Processing in 1405)
  • drawing with lines/shapes
  • grabbing/selecting/moving graphical objects
• PROPER CODING STYLE
  • encapsulation
  • polymorphism
  • private/public/protected data
• INHERITANCE
  • class hierarchies
  • abstract vs. concrete classes ?
  • overriding/inheriting methods
  • type-casting (needed if JAVA used) ?
• NETWORKING
  • read internet page
  • two applications talk over network
• FORMATTING output nicely
  • string manipulation
  • display in columns (i.e., tabbing)
  • display dates/times
• ABSTRACT DATA TYPES / DATA STRUCTURES
  • lists
  • structures
  • tuples
  • binary trees
  • dictionaries
  • sets
  • stacks, queues
• TESTING AND DEBUGGING
  • design vs. implementation errors
  • basic test cases, regression testing?
  • basic debugger usage
  • strategies for identifying and fixing programming problems
• OPTIMIZATION
  • e.g., knapsack
  • greedy
• DYNAMIC PROGRAMMING

EXTRA LIST OF TOPICS TO ADD IF TIME PERMITS (Mark's Opinion)

• UNDERSTANDING APIs
  • basic idea of contract, side effects
• DATABASE APIs ???
  • Allow use of key/value stores as used by standard websites
• SOFTWARE LICENSES
  • open source and commercial
  • restrictions on reuse
• REVISION CONTROL
  • have students grab class code from this, pull updates
  • make commits/push to submit?
• CONCURRENCY/PARALLEL CODE
  • maybe not standard locking but some clean parallel constructs?

Sample weekly outline (Fall 2006)

1. Introduction Sept 7-8

    - intro to CS
    - class stuff

2. Algorithms Sept 11-15

    - what are they
    - intro to problem solving
    - statements
    - pseudocode

3. Variables Sept 18-22

    - concept
    - identifiers
    - assignment
    - expressions, arithmetic

4. Conditionals Sept 25-29

    - Decision statements
    - boolean operators
    - if / then / else
    - case / switch
    - going from problem description to conditional statement

5. Iteration Oct 2-6

    - idea of looping
    - starting / stopping / stepping
    - loop bodies
    - top and bottom loops
    - for loops
    - while loops
    - going from problem to loop statements

6. Subprograms Oct 9-13

    - idea of modularization
    - functions and procedures
    - parameter passing
    - variable scope
    - when to modularize (problem solving)

7. Computer architecture Oct 16-20

    - basic von Neumann architecture
    - linear memory organization
    - possibly midterm post-mortem in this week

8. Data structures 1: Arrays Oct 23-27

    - idea of data structures & collections
    - arrays & linear memory
    - array operations, initialization
    - relation to loops
    - 2D arrays
    - going from problem to array specification

9. Data structures 2: Structs Oct 30-Nov 3

    - idea of user-defined structures
    - why and when to use
    - examples

10. Searching Nov 6-10

    - a larger problem domain
    - linear and binary search
    - 'putting it all together' (arrays, loops, variables, etc)
    - introduction to algorithm analysis (just the idea that different

algorithms can take different time)

11. Sorting Nov 13-17

    - same basic structure as searching week
    - bubble sort and selection sort

12. Recursion Nov 20-24

    - introduction to the idea
    - base cases & recursive cases
    - composition steps (returning a value)

13. Review Nov 27-Dec 4

    - lab exam postmortem
    - review for the final

Textbooks

• Sedgewick and Wayne, Introduction to Programming in Java

Assignment problems

Please list your ideas for assignment problems below in your own subsection. Note that we are currently focusing on smaller problems that can be assembled into weekly assignments.

David's Processing Problems

Draw a face, draw a house, draw a robot. (basic straight-line code)

Logical drawing (draw simple forms based on mouse position)

Using for loops to augment drawing.

Grass:

Stars:

- change the size, color distribution of stars - draw stars only above the horizon - draw stars only inside a circle (telescope view)

- add freckles to the face, hair

Skyscraper: - drawing location based on loop variable

variants: some windows dark, some lit

draw entire city (collection of buildings)

base sky color and window distribution on mouse pointer (windows get dark as it gets later)

Simple image processing:

Convert colored image to greyscale

Convert image to black and white; variant: base proportion of blackness on mouse position

Convert image to red and white -- only keep red pixels (problem: how to define?)

Robot behaviour:

Move small robot image or drawing primitive based on obstacles, mouse pointer - e.g., flee from mouse - e.g., attracted to mouse - e.g., want to maintain certain distance from mouse

David's Paper problem solving examples

• Suppose you have two jugs, one with a capacity of three liters and the other with a capacity of five liters. Write an algorithm that uses these two jugs, and no other measuring devices, to get exactly one liter of water in the five-gallon jug.

• The Greeks of classical Athens assemble to choose a new leader, and they vote by placing voting stones into an urn: a black stone, to vote for Castor, or a white stone, to vote for Pollux. You are put in charge of the election results. Write a specific algorithm for determining which of the candidates (Castor or Pollux) is the winner.

• You are the in charge of the Royal mint, which produces a single type coin, the grote. There are ten machines producing grotes. One machine is producing grotes weighing one gram less than they should (each coin should weigh 10 grams). You have a scale that can be used exactly once before it explodes (don't ask), but will give an accurate reading of the weight of whatever is on the scale. Using only this one weighing, identify the single faulty machine. (Note; no algorithm required, just solve the puzzle if you can).

• The Royal Mint has run out of exploding scales, and now has balances instead. (A balance will tell you whether the items in the left pan or the items in the right pan are heavier, but not how much heavier.) You have nine grote-minting machines, and one of them is producing grotes that are too light. Write an algorithm for using the balance to determine which machine's grotes are too light. (Challenge: do it with only two balance operations.)

• Four travellers are trying to cross an old, rickety bridge, so decrepit that only two can cross at once. They reached the bridge at night, and have only one flashlight among them; there are enough holes in the bridge that it can only be crossed safely by a group carrying a light. Now, the travellers have reached the bridge at different levels of exhaustion: one will take 1 minute to walk across; one will take 2 minutes; one will take 5 minutes to limp across; and one will take 10 minutes to crawl across. A group moves at the speed of its slowest member. Give a general algorithm for getting everyone safely to the far side of the bridge. Using your algorithm, how long does it take the travellers to cross? (There are no tricks, like throwing the flashlight back to the other side.) (Challenge: get the group across in under 20 minutes.) (Challenge #2: get the group across in under 18 minutes.)

• An old story has a grateful king granting a wish to a favored advisor, and the advisor describing the following process. A chess board is to be brought out, and one grain of rice placed on the first square, two grains on the second, four on the third, and so on, doubling for each square. There are 64 squares on the chessboard. Write pseudocode for an algorithm to determine how many pounds of rice the unlucky king has to give to the advisor, assuming 1000 grains per pound.

• Suppose you are trying to pay off credit card debt. You have an initial balance, and the credit card charges 1.5% additional interest each month. Write pseudocode for an algorithm that gets a monthly payment amount from the user and then reports (a) how long it will take to pay off the debt; (b) how much of the payment is for interest (total paid minus initial balance). Make sure not to allow infinite loops! (How would a bank avoid an infinite loop on a credit card?)

• You have a spaceship that runs on gold, consuming 1 ton of gold for each parsec traveled. It can carry a maximum of 1000 tons, but can also eject gold into space and pick it up later. You have 3000 tons of gold and want to get as much as possible to your destination 1000 parsecs away (just at the limits of what you could reach, arriving empty). Describe a general algorithm for getting to your destination with as much gold as you can. (Challenge: reach the destination with more than 425 tons.)

• Consider the following exchange:
  • ``My dog is precisely one-third Dalmatian.
  • ``How can that be?
  • ``Well, his father was one-third Dalmatian, and his mother is one-third Dalmatian, and so he is too.

What is wrong with the reasoning in the last statement? (Note: this is a question about recursion, NOT genetics! Pretend that the amount of Dalmatian in the offspring is the average of the amounts in the parents.)

• The Greek hero Achilles has the ability to stride half the distance to his goal in just a single step. He also has the ability to take a normal step, which will take him at most 1 meter. Write pseudocode for a recursive function that takes a float argument (the initial distance to the goal) and returns the smallest number of steps Achilles has to take to reach his goal. Notice that Achilles's best strategy will be to take giant steps (halving the distance) until the distance remaining is one meter or less, which he can finish with one normal step.

Anil S's example problems

• Build an adventure game (2D graphics or text). This can turn into a huge assignment; however it can break down into a number of small tasks. Adventure games are a great way to teach about objects, persistence, conditionals, for example.
• draw fractals: recursion, numerical methods (limits of precision), basic graphics, complexity (fractals can take a while to render)
• find patterns in an image (squares, lines) - specific pixel patterns are easy, but scale and rotation invariant searches are much more challenging.
• spirograph
• file visualization - learn file I/O, basic data visualization, string processing, bit of recursion
• core wars? You just need arrays and a simple bytecode interpreter (bunch of conditionals)

Michiel's example problems

• Monte-Carlo estimation of pi: Throw N points randomly in the unit-square, and count how many of them are in the unit-circle. Do experiments with larger and larger values of N, and see how the result improves.

• Monte-Carlo estimation of integrals. Take some integrals that students learned in calculus (and that are not completely trivial). Choose random real numbers and count how many of them are underneath the function. Do experiments as for pi.

• Monty Hall problem. First let students guess what is the best strategy. Do a large number of experiments (put the prize behind a random door; choose a random door first, then follow the strategy) and count how many times you win the car. Based on this, students may be convinced that their initial strategy is not correct. In this case, revise the strategy and repeat the experiments.

• In all these problems, students may use different random number generators and see if they give the same results.

Mark's paper problem solving examples

• Part A - Mary Melody has an apartment building high up in the sky. On her balcony is a ledge with 10 flower pots on it. The ledge is so narrow that it only holds exactly 10 pots. Mary has named each of her 10 flowers by placing a piece of masking tape on the bottom of the pot with the name on it. One day Mary decided to have a maid come and clean. The maid was so thorough and she was a kind of "neat freak". The maid wants to sort the flowers by name from left to right so that the leftmost flower has the name which comes first alphabetically. Assume that the maid can pick up only 1 pot in each hand at a time and that the pots must either be in the maid's hand or on the ledge (that is, she cannot put them down anywhere else). Note that the maid may pick one pot up in her hand and slide another pot along the ledge with her free hand. Explain (i.e. give an algorithm) how the maid can sort the pots properly.
  • Part B - Assume now there are exactly two ledges and that the maid can make use of the second ledge to place the pots on. Can you describe a better way of sorting the pots ? Perhaps there is a quicker way or a way that involves the use of only one hand.

• Assume that you want a robot to follow along the walls of a building and that the walls have always 90 degree turns. Explain how to get the robot to follow the walls. Draw a picture of your robot and indicate any kinds of sensors that you would need. Make sure to explain how you use the sensors.

Mark's programming problems

• Write a program to compute how many balls can be packed into a box. This can be done 2D or 3D. In 2D, the user can draw a rectangle and a circle and then use their dimensions to compute the number of circles that fit into the rectangle and display them packed in there. It can be done in 3D as well without too much difficulty. (This will help students understand the differences between using floats and ints because only WHOLE balls are to be fit into the rectangle, not partial balls).

• Part A - Write a program that determines whether or not cell phone access is continuously available along a planned path between various cities. In this program, the user will click a set of arbitrary locations on the screen that represent city centers. Assume that a cell phone tower is placed at each city center and is represented as a circle with some radius. Assuming that the user then drives from one city center to the others in sequence, the user then needs to compute whether or not there is cell phone access along the whole path. The solution is to make sure that the circles intersect for each consecutive pair of cities.
  • Part B - Assume that internet access is available throughout the whole trip. If it costs $0.20 per minute to use the cellphone and the person traveled an average (non-stop) speed of 50km/h ... for the whole trip, staying connected to the internet the whole time ... what will be the maximum cell phone cost from this trip ? (They would calculate the distances between adjacent cities to compute the total distance and will need to determine how many minutes of travel time was made on the trip ... assuming constant speed of 50km/h to keep things simple).

• Simulate Cars parking in ParkingLots over time. Define Car and ParkingLot data structures, where cars maintain the time that they entered the parking lot (if they take a ticket stub) and perhaps whether or not they have a parking pass. As cars enter the lot, their entry time is stored in the Car data structure, based on the current time. When they leave, the cost is computed based on their entry time and current time at some fixed cost (e.g., $1.50 per hour). The ParkingLot maintains the total money made so far as well as its capacity and the number of cars parked there. (The students could draw the parking lot and grab cars with the mouse to place them in the lot (perhaps showing their entry time as well). The cars can then be clicked on to leave the lot (no need to animate it). We could then have two parking lots of different capacities and rates and then have the cars go into each one. This is a nice way to get them used to using data structures)