What to teach students their first day/week/month studying CS

[07/08/11] Claire Mathieu: Hi Cora! Hi Val! Would you like to talk about what to teach students their first day/week/month studying CS? Any ideas on this?
[07/08/11] Glencora Borradaile: sadly, not really - other that they should see some algorithmic ideas early on. i liked Phil Klein's intro-cs course - that is really the only intro-cs class I've seen
[07/08/11] Glencora Borradaile: I've been handed a CS orientation class that needs work. 3 hrs/week for 10 weeks plus 1 hr of lab per week, but the labs are pretty set. we assume they know nothing and there is no requirement that they learn any programming
[07/08/11] Claire Mathieu: Really! So you're all free.
[07/08/11] Glencora Borradaile: Yes. Which is nice, but also too much freedom.
[07/08/11] Valerie King: There's an interesting course at CMU. It's "Great Ideas in Theory". It doesn't presume any previous knowledge
[07/08/11] Claire Mathieu: What kind of things do they teach? Computation? Godel's incompleteness theorem? Recursivity?
[07/08/11] Valerie King: some complexity some randomization, some algorithms. I think Rudich developed it
07/08/11] Glencora Borradaile: 15-251: Great Theoretical Ideas in Computer Science (Spring 2011)
This course is about how to use theoretical ideas to formulate and solve problems in computer science. It integrates mathematical material with general problem solving techniques and computer science applications. Examples are drawn from Algorithms, Complexity Theory, Game Theory, Probability Theory, Graph Theory, Automata Theory, Algebra, Cryptography, and Combinatorics. Assignments involve both mathematical proofs and programming. https://colormygraph.ugrad.cs.cmu.edu/
07/08/11] Claire Mathieu: But really, Cora's talking about, not just Theory, but all of CS I think.
[07/08/11] Glencora Borradaile: Yes.
[07/08/11] Claire Mathieu: At Orsay we used to have a mini-programming language with a mini-lab in which you could visualize an architecture and an execution step by step at the level of registers. You go from some basic-like piece of code to mini-assembly to a bunch of 0's and 1's, then we see it executed. It was an eye-opening experience for me to see how computers can actually do what they are told. Then Turing machines made a lot more sense. So we see the concept of programming and of computer. That, I thought, was brilliant.
[07/08/11] Glencora Borradaile: huh. I wonder if something like that is still available.
[07/08/11] Valerie King: In the old days we had a course like that, without programming but with a card board "computer" which had 10 instructions. I found it very interesting.
[07/08/11] Glencora Borradaile: So you think they should have some experience with seeing how a computer should work - computer architecture. (And they want *me* to teach it?) But is that computer science? Or just something that computer scientists should know?
07/08/11] Claire Mathieu: Well, it helps make sense of everything else for me. For example, what is an algorithm? Those formal definitions - sequence of instructions that you know how to do, etc. With a little bit of an intro to architecture, it's just so much more real.
[07/08/11] Valerie King: I think from our point of view it makes sense.
[07/08/11] Glencora Borradaile: one of the course learning objectives for this course is to be able to explain what computer science is.
[07/08/11] Valerie King: Well many people today would say it involves HCI, graphics, applications, etc.
[[07/08/11] Claire Mathieu: But those topics (HCI etc.), they are not core CS.
[07/08/11] Glencora Borradaile: what is core cs?
[07/08/11] Claire Mathieu: Computation
[07/08/11] Glencora Borradaile: That's difficult for me. It's a study of how to solve problems computationally. So, programming languages and algorithms are core. CA and OS - are they computer science or computer engineering? and then there are, perhaps topical areas - ML, graphics
[07/08/11] Valerie King: I looked at what others had written. There is something Jeanette Wing calls computational thinking. This includes algorithmic thinking. Which involves abstraction and recursion. There is also the ability to think about concurrency for example
[07/08/11] Valerie King: Ah, I've been writing up a description of that for our VPAC (Vice president Academic. that's standard Canadian.)
[07/08/11] Claire Mathieu: What is NOT CS? Prove the existence of an object by the probabilistic method, then ask students to find it. There is no algorithm. They are helpless. Then the difference between constructive and non-constructive problem-solving appears.
[07/08/11] Valerie King: CS is about what can be computed and what can't be. I'm not sure the probabilistic method is about computing, by itself.
[07/08/11] Claire Mathieu: Well, I mean precisely that the probabilitstic method enables you to prove things without giving you any handle on how to compute it, so it shows examples of what is NOT computer science.
[07/08/11] Valerie King: Here is my definition: Computer science is a relatively young, diverse and changing field, evolving as the use of computers evolve. Unlike electrical engineering, computer science deals not with the physical level of transistors and devices, but with a level of abstraction above this, where the computer's operations are idealized. Thus, on-off switches store information; information is manipulated by other information representing programs, programs are run by other programs known as systems, and so on. Understanding and designing for these complex processes requires skills which computer scientists sometimes call "computational thinking".
It includes ``algorithmic thinking," the ability to specify a step by step procedure by which the problem can be solved with the goal of minimizing time and computational resources. Algorithmic thinking also includes knowing which kinds of problems are infeasible for any computer to solve, how information can be communicated efficiently, and how it can be kept secret. Computational thinking also includes the ability to reason about large systems of interacting networks of computers and users, and large amounts of data, and how to represent this complexity to users. Computer scientists draw on diverse skills: mathematics and logic, psychology and sociology, engineering, linguistics, art and music.
In the last 20 years, scientists with large amounts of data, e.g., from the Hubble telescope or DNA sequences, have recognized the centraility of computation in their research. The analysis of the human genome was made possible by the development of speedier algorithms developed by computer scientists working with biologists. Today we are seeing researchers from the humanities. social sciences, and the arts working with computer scientists to analyze information and create knowledge in ways never considered before. New forms of electronic media, like Facebook, exhibit sociological connections between millions of people on a global level. The advent of online advertising and auctions have created a new subfield of computer science and economics.
An economist may be able to show a market equilibrium exists; a computational economist may show that it is computationally infeasible, in terms of computing resources, for anyone to determine the equilibrium point. Computational thinking is becoming ever more important, to a wider range of areas.
[07/08/11] Claire Mathieu: So what's different about CS? What makes it unique? Now it looks as though it's all over the map."in ways never considered before"?
[07/08/11] Valerie King: I believe it applies everywhere, but it's viewing everything through a particular lens, that of computation.
[07/08/11] Glencora Borradaile: math of the 21st century
[07/08/11] Valerie King: Re ways never considered before: I think of how we can now view millions of connections between people, we have all sorts of data we can analyse.
[07/08/11] Claire Mathieu: Kind of like statistics? (devil's advocate) Statistics apply everywhere: Analyzing data, huge amounts = statistics
[07/08/11] Valerie King: The question is whether CS gives a different view from statistics. Does data mining differ from statistics? I think CS has evolved some new perspectives, like the PAC learning model which can involve the notion of feasibly computation.
[07/08/11] Claire Mathieu: There is certainly a different flavor (emphasis on worst case vs. distribution assumptions for example), but in essence,...? I guess statistics is only trying to say things about data - analyze it and make observations, infer structure -- but we are solving problems involving data. That's a little bit different,m isn't it?
[07/08/11] Valerie King: I don't know, I think the difference is the notion of poly time computable, maybe

[07/08/11] Glencora Borradaile: what if you went backwards - what would a high school class learn about CS? my problem with (high school) cs classes - and math classes - is they don't reflect cs (or math). cs is "just programming"
[07/08/11] Claire Mathieu: "Just programming" is what they think after high school, and that is wrong.
[07/08/11] Glencora Borradaile: yes. maybe compare to physics or chemistry or biology
[07/08/11] Valerie King: They also have boring intro classes sometimes
[07/08/11] Glencora Borradaile: sure, you learn experimentation, but lab courses are a minority in what you study, from what I remember
[07/08/11] Claire Mathieu: Stil, I think that programming is central. Computability, undecidability, induction, abstraction etc. are best understood with some programming skills. You could have a course centered on problem-solving.
[07/08/11] Valerie King: Or some easy programming language.
[07/08/11] Glencora Borradaile: that's true - it is nice to see the ideas in action
[07/08/11] Claire Mathieu: One thing: I think that the notion of polynomial-time is probably too advanced for a first course. First they need to internalize the idea that we're dealing with asymptotics - large size data sets
[07/08/11] Glencora Borradaile: sure - that's fine
[07/08/11] Claire Mathieu: It might be good for them to see that (program Hanoi towers, say)
[07/08/11] Glencora Borradaile: but you could show them the difference between a bad design (exponential) and a good design (polynomial) for the same problem
[07/08/11] Valerie King: In our classes here, the other profs get the students to act out the algorithms. Like quicksort
[07/08/11] Glencora Borradaile: or median finding
[07/08/11] Claire Mathieu: What do you mean, act out? QS - I tried once to get them to sort themselves. That was rather awkward.
[07/08/11] Valerie King: I can't bring myself to do it.
[07/08/11] Glencora Borradaile: why not?
[07/08/11] Claire Mathieu: It's weird, and you need students who are good-natured
[07/08/11] Valerie King: It seems so silly. And if I were in the audience, it would have seemed so easy anyhow
[07/08/11] Claire Mathieu: When I was in elementary school we acted our computation in binary. Each student was 1 bit. Arm up (1), arm down (0).
[07/08/11] Glencora Borradaile: heh
[07/08/11] Valerie King: That's good. My daughter learned to count binary with her fingers
[07/08/11] Claire Mathieu: She has only 2 fingers?
[07/08/11] Valerie King: Each finger is a digit
[07/08/11] Glencora Borradaile: the number 4 is always amusing for kids
[07/08/11] Claire Mathieu: Oh, right. Some numbers had best be avoided though
[07/08/11] Claire Mathieu: jinx
[07/08/11] Valerie King: I guess games would be fun.
[07/08/11] Claire Mathieu: It can be fun, but what does it show? What concepts get taughts?
[07/08/11] Valerie King: Recursion maybe
[07/08/11] Glencora Borradaile: abstraction
[07/08/11] Claire Mathieu: Example of abstraction? Can you be more concrete?
[07/08/11] Valerie King: Cora, they tell us here when we design a class we should think of learning outcomes first
[07/08/11] Glencora Borradaile: yes, we have a similar thing here. the learning outcomes for this course are pretty minimal. i could do what I want, so long as I hit them
[07/08/11] Claire Mathieu: hit your students??
[07/08/11] Glencora Borradaile: very funny.
[07/08/11] Claire Mathieu: What are the "outcomes" for that course?
[07/08/11] Glencora Borradaile: "what is CS", "data representation", I think, I would have to find the list .... I remember them not being so ... specific or deep
[07/08/11] Claire Mathieu: "data representation": what would be good for that? In terms of what concepts to convey
[07/08/11] Glencora Borradaile: i think they have 'just' been doing binary representation. of course, you could go much deeper than that
[07/08/11] Valerie King: you could add huffman coding
[07/08/11] Claire Mathieu: Crypto. Code each letter with another letter. Ask students to decode a text that you have encoded.
[07/08/11] Glencora Borradaile: that's true. that would be good actually - hitting on some areas of cs
[07/08/11] Claire Mathieu: Manipulating data that's poorly represented: adding numbers written with Roman numerals -- the progress of mathematics with Al-Kowarizmi, thanks to symbol 0 and base 10 representation of numbers. Plus a little bit of implicit fighting anti-Moslem prejudices
[07/08/11] Valerie King: abacas
[07/08/11] Claire Mathieu: logarithms with those instruments that people used to have - they could ask their grandparents?
[07/08/11] Glencora Borradaile: slide rules?
[07/08/11] Claire Mathieu: yes. Except I don't even know how those work
[07/08/11] Valerie King: Didn't you have one? I did
[07/08/11] Claire Mathieu: no
[07/08/11] Glencora Borradaile: wow! Even I know how to use one, Claire! :) (or, at one point, I was shown and may be able to reproduce it)
[07/08/11] Valerie King: I'm the last of a time. Oh, my father was a chemist, very proud of his slide rule
[07/08/11] Claire Mathieu: Although maybe not such a good example because a lot of the difficulty is in the Math rather than in the computation itself, at least, that's my impression?
[07/08/11] Claire Mathieu: Do you thin slide rules are good for teaching data representation?
[07/08/11] Valerie King: I think an abacas might be more interesting.
[07/08/11] Claire Mathieu: How about the various representations of Catalan numbers? I don't know how to use an abacas either -- unlesss it's obvious
[07/08/11] Valerie King: I knew once, I forgot.
[07/08/11] Valerie King: You could go over the history of computation
[07/08/11] Claire Mathieu: That could be fun. Astronomy. The earth at the center of the world, or not. Copernicus. Religion. Taking square roots by hand
[07/08/11] Valerie King: Euclid's algorithm. methods for computing pi
[07/08/11] Claire Mathieu: Oh, pi, that is good! But they'd have to program something too
[07/08/11] Glencora Borradaile: do you think this would turn off a group of students? a group of students that probably are not fond of math (something I don't understand) (that people would major in CS when they 'hate' math)
[07/08/11] Claire Mathieu: They don't like math because they think it's purely symbolic
[07/08/11] Glencora Borradaile: you could have a competition to see who could compute the most digits of pi
[07/08/11] Valerie King: you can look it up
[07/08/11] Claire Mathieu: Teach them reasoning, problem-solving, puzzles, finding each other's mistakes in logical inferences and they'll love it, I think...?
[07/08/11] Valerie King: Most of what students do now is look up answers
[07/08/11] Claire Mathieu: Counter-intuitive answers are such fun. They destabilize the students. Make them unsure of previous certainties. It's a good way to start college
[07/08/11] Valerie King: Well there are those logic puzzle books. Like "what is the name of this book?"
[07/08/11] Claire Mathieu: Also, when the teacher teaches things that are wrong. You know, prove something, they nod, then tell them there's a mistake in your argument. Or write a program, tell them "find the error". Like Where's Waldo
[07/08/11] Glencora Borradaile: what can you ask students that they can't look up the answers to?
[07/08/11] Claire Mathieu: In class, in real time
[07/08/11] Glencora Borradaile: (a case for in-class tests and quizzes - I am thinking of not having any true assignments) without their laptops open
[07/08/11] Valerie King: Right, I give quizzes
[07/08/11] Claire Mathieu: Just thinking about the possibilities, though, it's exciting. Of course it's hard to make these concrete. And not lose sight of the goals.
[07/08/11] Claire Mathieu: I'm sorry but I have a meeting coming up
[07/08/11] Glencora Borradaile: thanks for all the ideas - this was really helpful for me
[07/08/11] Valerie King: Look at Rudich's course
[07/08/11] Valerie King: bye
[07/08/11] Claire Mathieu: bye
[07/08/11] Glencora Borradaile: later!