SCS Curriculum Reinvention Committee: Difference between revisions

From Soma-notes
← Older edit
Mould (talk | contribs)
6 edits
 
(135 intermediate revisions by 5 users not shown)
Line 1: Line 1:
This page contains notes and discussions related to the 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.
=Requests for more data=


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.
*Why are students leaving SCS?
**What are the grades in SCS-related courses for students who change majors out of SCS?
**What majors do they switch to? After how many terms?
*DFW and A/B rates for 2009/2010 versus past years in 1405, 1406, 1805?


=COMP 1405/1406 Redesign=
=Courses to be examined=


==Topic Brainstorming==
Introductory Programming
*COMP 1405 - Introduction to Object-Oriented Programming
*COMP 1406 - Design and Implementation of Computer Applications


Add topics here at the end of the section.  Please ''don't'' '''remove''' anything!
Theory
*COMP 1805 - Discrete Structures
*COMP 2805 - Introduction to Theory of Computation
*COMP 2402 - Abstract Data Types and Algorithms
*COMP 3804 - Design and Analysis of Algorithms I


* WHAT IS COMPUTER SCIENCE
Intermediate Programming
** problem solving
*COMP 1402 - Introduction to Systems Programming
** algorithms
*COMP 2404 - Programming in C++
** 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
Other Core-ish Courses
*COMP 2003 - Computer Organization
*COMP 2405 - Internet Application Programming
*COMP 3000 - Operating Systems
*COMP 3002 - Compiler Construction
*COMP 3004 - Object-Oriented Software Engineering
*COMP 3005 - Database Management Systems
*COMP 3007 - Programming Paradigms
*COMP 3008 - User Interface Architecture
*COMP 3203 - Principles of Computer Networks
*STAT 2507
*STAT 2605


Should we copy the [http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2008/CourseHome/  MIT 6.00 outline] here?
=Detailed Discussions=


===Sub categories?===
*[[CR: COMP 1405/1406 Redesign|COMP 1405/1406 Redesign]]
Yes, we can add sub categories here.
*[[CR: Theory course redesign|Theory course redesign]]
 
*[[CR: Other CS approaches to Math/Theory]]
==COMP1405 LIST OF TOPICS (UNORDERED) FOR WEEKLY OUTLINE (Mark's Opinion)==
*[[CR: New course descriptions and rationale|New course descriptions and rationale]]
 
*[[CR: Survey of theory requirements in other Canadian Honours programs|Theory requirements survey]]
* WHAT IS COMPUTER SCIENCE
*[[CR: Reducing the Core Size|Reducing the Core Size]]
** problem solving
*[[CR: Learning Objectives]]
** algorithms
*[[CR: Proposal to Faculty May 2011]]
** abstraction and problem decomposition
*[[CR: stream changes]]
** divide and conquer
*[[CR: Proposal to Faculty September 2011]]
** efficiency (just an intro to the ideas behind it)
*[[CR: Third and Fourth Year]]
* PSEUDO-CODE
*[[CR: Attracting advanced students]]
* SEQUENCING INSTRUCTIONS
*[[CR: Curriculum Changes April 2012]]
** top down coding in sequence (e.g., draw a house)
*[[CR: to do list]]
* VARIABLES
*[[CR: Notes Fall 2012]]
** declaring vs. assigning
*[[CR: New 3rd year courses]]
** memory usage (how memory is affected)
*[[CR: Curriculum Changes for 2015/2016]]
** constants
*[[CR: Winter 2014]]
** examples:
*[[CR: Summer 2014]]
*** 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)
* COMMENTING / CODE FORMATTING GUIDELINES
* ARRAYS (1D and 2D)
** initializing and memory usage
** simple 1D (sum.avg/max/min)
** insert/remove
** copy/growing array
* 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
* EVENT-DRIVEN PROGRAMMING (if using Processing)
* GRAPHICS (if using Processing)
** drawing with lines/shapes
** grabbing/selecting/moving graphical objects
* USER INTERACTION
* 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
* SORTING
* SEARCH
** linear
** binary
** exhaustive
* SIMULATION
** virus clearing
** Roomba
* HOW TO READ CODE ???
 
==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, [http://www.cs.princeton.edu/introcs/home/ Introduction to Programming in Java]
 
==Assigned Problems (processing and other)==
Draw a face, draw a house, draw a robot. (basic straight-line code)
 
Logical drawing (draw simple forms based on mouse position)
[[File:Example.jpg]]
 
Using for loops to augment drawing.
 
Grass:
 
[[File:Example.jpg]]
 
Stars:
 
[[File:Example.jpg]]
- 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
[[File:Example.jpg]]
 
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
 
[[File:Example.jpg]]
 
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
 
==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.)
 
Write pseudocode for an algorithm that gets numbers from a user
until the user asks to stop, then computes the average of all the
numbers entered.
 
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 Dalmation 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.

Latest revision as of 20:46, 28 April 2014

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

Requests for more data

  • Why are students leaving SCS?
    • What are the grades in SCS-related courses for students who change majors out of SCS?
    • What majors do they switch to? After how many terms?
  • DFW and A/B rates for 2009/2010 versus past years in 1405, 1406, 1805?

Courses to be examined

Introductory Programming

  • COMP 1405 - Introduction to Object-Oriented Programming
  • COMP 1406 - Design and Implementation of Computer Applications

Theory

  • COMP 1805 - Discrete Structures
  • COMP 2805 - Introduction to Theory of Computation
  • COMP 2402 - Abstract Data Types and Algorithms
  • COMP 3804 - Design and Analysis of Algorithms I

Intermediate Programming

  • COMP 1402 - Introduction to Systems Programming
  • COMP 2404 - Programming in C++

Other Core-ish Courses

  • COMP 2003 - Computer Organization
  • COMP 2405 - Internet Application Programming
  • COMP 3000 - Operating Systems
  • COMP 3002 - Compiler Construction
  • COMP 3004 - Object-Oriented Software Engineering
  • COMP 3005 - Database Management Systems
  • COMP 3007 - Programming Paradigms
  • COMP 3008 - User Interface Architecture
  • COMP 3203 - Principles of Computer Networks
  • STAT 2507
  • STAT 2605

Detailed Discussions

Retrieved from "https://homeostasis.scs.carleton.ca/wiki/index.php?title=SCS_Curriculum_Reinvention_Committee&oldid=19100"