Tag Info

10

I regularly have to explain what computer science is to parents, and I have lately settled into this explanation: Technology keeps changing all the time. You get used to the menus in Microsoft Word, and then they change it to the Ribbon. You learn to program buttons in Java using Applets, and then Applets get removed from every major browser as a security ...

8

I think induction should be taught first, and then loop invariants, since you usually need induction to prove that the loop invariant is really an invariant, and also because you need induction for other purposes than just proving that a loop invariant is really an invariant. In fact, in most curricula for Computer Science at university will have some math ...

7

The Dutch National Flag problem is linear in running time. Essentially sort an array with only 3 distinct values each of which may appear 0 or more times. (not length 3). You are allowed only one pass over the array, so the solution is a single while loop with some prior initialization. It was probably originally posed by Dijkstra. It is mentioned in David ...

7

A variant on the ENIGMA machine encryption works well in a single loop, and is sufficiently complex to give students a real challenge. The core idea of the ENIGMA machine for this assignment is that (1) a number is given as an initial key, and (2) every prior letter used influences how the next letter will be encrypted. So, use a modular circle of ...

6

Maybe a bit of an orthogonal answer, but let me try to refocus your thinking. I don't think that teaching a lot of languages, especially if they are similar to one another in some way is a big advantage for students. Giving them experience with different paradigms (ways of thinking) on the other hand is a big advantage. While I prefer Java (for its libraries)...

6

Let's start with the term "Loop Invariance". It is a property of a loop that is true before and after each iteration, thus in-variant, non-changing. So then, what is the purpose of the loop invariance in proving algorithm correctness? That is, it is a predicate about what the loop is supposed to do. Thus with proof by induction on this predicate shows the ...

6

I'll attempt a self-answer here, based on hindsight and a few previous experiences where I went in knowing I wanted to do this. I've found that starting off with an analogy helps a lot of the time. Friends and co-workers have reported similar results in my super unscientific poll. The one we use is along the lines of Computer science has as much to do with ...

5

I would explain it like this: In reality, you have to solve problems on your daily basis. It may be a time problem, like "how do I get these five tasks done it just 1 hour?" or "how can I stack these boxes so that they all fit into the cupboard?". Computer science is in many ways equal to solving these problems, only that the problems are of a little more ...

5

Based on the comments, the minimum for theory and technical is how the nomenclature of MS Access relates to Excel. If they've been doing everything in Excel anyway, they've developed habits for, or against, normalization that you're not going to break in a couple days, intensive or not. If they haven't discovered the pitfalls of redundant data in Excel, ...

4

To give an explanation of this requires a problem in which to frame the discussion. I propose the Dutch National Flag problem, likely first proposed by Dijkstra, but I'm not positive. I'll pose the problem first and discuss the solution using invariants. The Problem Taken from The Science of Programming. You have an array of n elements. Each element ...

4

I have been teaching theoretical CS to math teachers (don't ask why...). I assumed that they were comfortable with numerical induction and therefore the transition to structural induction (on a computation as in proving invariants) wouldn't be difficult. I was wrong on both counts. It seemed to me that this is partly because they encountered induction in a ...

4

Dealing with (my) parents who are not particularly aware of computers or the difference between a server and a database, I believe I have a fairly simple answer for this question. Computer science is the theory and study of how computers work, algorithms (in layman's terms, a process to solve a problem), and how to think like a computer in order to ...

3

You could use introduce elementary (one-dimensional) cellular automata. Basically, you represent a single row of cells as a simple array. Then you write a function that takes an array and applies the rules of the cellular automata to each cell (usually based on the old value of the cell and its two neighbors) to return a new array representing the next ...

3

Computer science is a discipline of problem solving. I use this phrase from CS50 often (mainly because I teach an adaption of it): inputs -> algorithms -> outputs From the official CS50 notes from last year's Week 0 lecture, the following three bullets explain what this phrase means: At the end of the day, computer science is about problem ...

3

I don't know if I have a solid answer to the main thrust of your question, but I do have some one-off suggestions that may or may not be helpful. First, something you could try integrating into your lessons is some kind of meta-narrative about why proofs are useful in the first place. This seems to be a very common concern from students in the discrete ...

3

I've found a lot of success giving real world (often times very silly) examples of boolean algebra to give them a more intuitive understanding in addition to the pure algebraic laws. An example would be "If it rains tomorrow, I will bring an umbrella so I will stay dry". This is a simple A -> B: If it rains tomorrow then I will bring an umbrella, I will ...

3

One big struggle is getting CS students to care about induction. Proving correctness doesn't really count as motivation, when "passing the tests" seems so much approachable and the extra benefits from proving correctness just don't seem worth the extra effort. On the other hand, if induction could be practically useful in designing algorithms in the first ...

3

Firstly, I believe that if the thought process is clear to you, then going through that process with your students, out loud, clearly and slowly, can help them understand what it is that you are trying to convey. Go through that process for a number of various examples, which show how you decide on a loop invariant in the varying situations (yes, that pun ...

2

A great resource for the instructor to learn the max about invariants is to go to the master. David Gries, The Science of Programming It isn't a book for novice learners, though. But understanding what is in this book will help you a lot in teaching programming via invariants. He reveals all. He and his son have an undergrad text book also, that might ...

2

At the CS1 level that I teach, I focus a lot on the role and the precise meaning of variables and encourage comments at the point of declaration that attempt to make these clear, especially variables that are involved in loops. Since the meaning of a variable changes as the loop body is executed, we "agree" to use the entry point as the standard point of ...

2

A couple of ideas: 1st day Start by getting everybody up and moving. Have people form sets - say, a set of colors, with everybody wearing a different color, or a set of ages - but remind them that they can't have two people representing the same color in the set. Perform different operations with the human sets - intersections, unions, etc. After a couple ...

2

I don't know if this will help you, but I often find myself in the position of explaining the difference between CS and IT to students / prospective students / parents, and I use the experience of being a one-time emergency medical technician to help. I compare the difference between CS and IT to the difference between medical doctors and EMTs. As an EMT, ...

2

I recommend to check out <algorithm>, <numeric>, and related C++ headers. There are literally tons of linear algorithms of utter significance. From the top of my head, copy, reverse, find, lower_bound, accumulate, iota, partial_sum, adjacent_difference, inner_product are well deserving much attention.

2

Grades. Works especially well around final exam time. You can find the average. Find the highest and lowest. Find the average with the lowest dropped. Find the most common grade. Count how many are in the range 90-100%. Given an array of grades assigned for each class, calculate GPA. Given 3 arrays that represent labs, quizzes, and tests calculate the ...

2

Markov Chains are great for putting out nonsense based on statistical data. However, a predictive keyboard that outputs nonsense isn't very useful. It needs much more context than a Markov Chain can produce. Such a program would base its next output entirely on the most recent entry. That said, a project to do something like the Mark V. Shaney program ...

2

All programming languages are tools. Whether one is a programmer, a computer scientist, a student, or an instructor, the tool status of programming languages remains constant. Selecting the right tool for the job, out of those which are available at the time, becomes an exercise in itself. The second half of the exercise is how to use the tools you do have ...

2

One idea which might be a bit too trade-schooly but which I offer in case you disagree: the practice of software engineering. One big difference between Java and JavaScript is that Java has enormous standard libraries, and JavaScript has very little. In consequence, JS forces you to either reinvent the wheel or learn to use a package management system. Use ...

2

I agree that Introduction to the Theory of Computation by Sipser is good text, but I also recommend taking a look at the Stanford CS103 course page archive, which has a lot of great supplementary resources, including handouts, problem sets, and lecture notes.

1

I was wondering the other day. Who would I hire? Someone with good theory knowledge, that used educational languages (Eiffel for OO, scheme for functional, both for simple and creating DSLs). Or Someone with some knowledge of the languages that we use here. I think I would hire the people that learnt the educational languages, and so have a better ...

1

One small, but significant, algorithm is to find Euler's Number. The irrational number $e$, also called Euler’s number, is approximately 2.71828. The number is significant both to the culture of computing and has a role in such functions as computing continually compounding interest. Euler proved that this number was irrational by showing that it was ...

Only top voted, non community-wiki answers of a minimum length are eligible