This was the syllabus in Spring 2006 and has been superceded by the CourseSyllabus, to which it bears more than a passing resemblance....
Contents
Contents
Clearly this page needs to be split into pieces and made more functional. Feel free to do so, but please don't lose information.
Who/What/Where etc.
This course is Foundations of Computer Science. It is a 6 credit course offered Fall 2004 at the Franklin W. Olin College of Engineering. A 4 credit option is also available; students enrolled in the 4 credit version are excused from certain specified portions of the assignments and from certain specified sessions.
The course is taught by Professor Lynn Andrea Stein. Lynn can often be found in her lab (AC312) or office (OC358); at x2525; online at las@olin; or on AIM (screen name available on request or ask around the dorms; I'd rather it not be posted to the web, please!)
We meet Mondays and Thursdays 10-11:50 in AC318.
This syllabus is way more bureaucratic and official-sounding (not to mention officious) than the rest of the class will be. I thought I'd get it all out of my system at once....
- === Disclaimer === This course is an experimental one. It has been offered once previously, but is likely to change significantly from that prior offering. It is not a direct derivative of any previously existing course. It borrows learning objectives from several traditional mid-level computer science courses. It is being taught to a group twice the size of the originally anticipated enrollment. And anyway, this is Olin College.
In short, expect things to be a little bit unsettled this semester. You will be a major part of helping to determine how this course goes. We will try many things. Hopefully, most of them will be outstanding successes. Inevitably, some of them will be resounding failures. (If there are no failures, it will mean that we're not being ambitious enough!) Please be prepared to provide feedback on how things are or aren't working for you and to provide constructive suggestions on what might help to improve situations. Please also be prepared to be patient when things don't improve as quickly as you wish they would or when you find yourself in a frustrating situation. Hopefully, this won't happen very often....
In theory, there is no difference between theory and practice. In practice, however, ... [TheoryPracticeNote] === Acknowledgements === Allen Downey sat through innumerable sessions of my wrestling with this material and still managed to provide invariably sage advice. Katie Rivard did everything I asked of her and then did three times as much. Anything that actually works in this course is to her credit; anything that's broken is in spite of her best efforts to manage me and entirely my fault. A lot of Olin students lived through a first version of the course. Some of them even enjoyed it. All of them gave valuable feedback.
Sean McBride and Rob Quimby tried to help me patch it up after the semester was over. The entire CS education community has developed a wealth of resources on top of and out of which this course is built. Olin provides an incredible opportunity for experiments such as this one. Its students keep it real. Thanks to everyone.
Course and Learning Objectives
This section covers some of the things you should expect to get out of this course. It's going to start out as a hodgepodge of Olin Competencies, CS "standard" topics (drawn from CC2001 and ABET's CAC, among other places), and my own personal ideas about what's important and what we'll be doing this semester. Eventually, it will be nicely sorted and coherent. Or not.
- === A Stab at Objectives === A successful student completing this course should be able to:
- Analyze a problem description and select an appropriate algorithm, simple language, or abstract machine to solve the problem (for the major classes of language and of computational complexity, for the most fundamental data structures and algorithms in computer science).
- Articulate tradeoffs in algorithm and language selection
- Identify tractable, intractable-but-computable, and non-computable problems, explain what these mean and identify sources of intractability and undecidability.
Qualitative Understanding and Quantitative Understanding: Absolutely. This course focuses on understanding what's needed and how problems are solved, on understanding how to measure solutions, on selecting among alternatives, etc. This course is substantially about the theory behind computation and how that relates to implementation.
Life-long Learning: Oh, yes. This course will be underdeveloped, the resources won't be adequate or adequately fine tuned, and the entire semester will be an exercise in figuring out how to learn what you need to know. OK, hopefully it won't be that bad, but at least the first time through this competency will definitely be a theme of the course. Taught a little -- as we share strategies -- and measured mostly implicitly by whether you learn the ostensible content of the course.
Diagnosis: There will be some design-debugging and it's hard to do anything computational without this, but this skill probably plays a smaller role here than in, say, Software Design.
Opportunity: Only insofar as you will learn what kinds of problems are amenable to which kinds of solutions.
Teamwork: Probably some, in that all work at Olin seems to involve collaboration, but this is not a big focus of the course. It won't really be taught and it won't really be measured except insofar as there are study group and/or peer grading components to the course.
Communication: Measured implicitly in problem sets, lab reports, and class and on-line participation (including notetaking), but again not a major focus.
Design: Implicitly, in that we'll be learning the tools by which designs are measured and using them to do some simple designs, but again this is not a major focus of this particular course.
Context: Not so much. Although there is a contextual aspect to deciding how to make tradeoffs, most of these will be more technical tradeoffs rather than social, ethical, or otherwise. (See lots of other courses I teach or plan for plenty of context, though.)
- === "Traditional" CS curricular objectives ===
- Hits main points of:
- algorithm analysis
- algorithm design
- complexity theory
- automata theory
- computability theory
- programming language paradigms
- language design
- Includes:
- basic logic (both predicate and propositional forms)
- graphs and trees
- algorithms and problem solving
- fundamental data structures
- recursion
- basic algorithmic analysis
- algorithmic strategies
- fundamental computing algorithms
- basic computability
- the complexity classes P and NP
- automata theory
- language interpretation (and translation)
- programming language paradigms
- declarations and types
- abstraction mechanisms
- functional programming
- issues in programming language design
- search and constraint satisfaction
- knowledge representation
- basics of information management
- fundamental data structures and associated algorithms, including:
- linear data structures
- graph structures and algorithms
- trees
- fundamental N : log N depth relationship (inverse of power set)
- algorithmic strategies including:
- brute force
- greedy
- divide and conquer
- backtracking
- asymptotic analysis of algorithms
- recognize basic patterns (sub-linear, linear, n log n, polynomial, exponential)
- understand best/worst/average case concepts
- appreciate amortization
- language and automata hierarchy and equivalences:
- finite state automata
- regular expressions
- push-down automata
- context free languages
- Turing machine
- recursive/recursive enumerability
- determinism/nondeterminism
- incompleteness and non-computability
- universal machine
- halting problem
- diagonalization as a strategy
- Church/Turing
- Godel
- propositional (boolean) logic
- truth tables
- Karnaugh maps
- universality of nand
- SAT
- predicate logic
- knowledge representation
- NP
- hardness
- completeness
- short certificate
- reductions
- also PTime ? PSpace? ?NC?
- Lisp
- list processing (incrementally and map/filter)
- recursion and stack
- tail recursion
- functional programming/no mutation
- interpreter
- ? Constraint programming/logic programming
- ? Machine learning
- ? Information Retrieval
- ? Databases, relational algebra
- Hits main points of:
Course Expectations
These are the rules. Know them. Don't break them. If you have a problem with them, discuss it with me. They are here to protect both of us. If they're not doing that job, we need to rethink them, but don't ignore them and expect that it will all be OK.
- === Time Commitment === This is a 6 credit course. That means that you should expect to spend 18 hours a week on this course. (If you are taking the course for 4 credits, you should expect to spend 12 hours a week on it. You will be excused from certain specific activities that should bring your time commitment down to 12 hours.)
The number of hours per week is meant as a guideline. It is my intention that (a) you will be provided with enough things to profitably spend approximately this number of hours per week on the course and (b) you should not need to spend appreciably more than this number of hours per week on the course. This assumes that you are keeping up with the work (and in particular that you are doing reading or other independent-learning things outside of class and on schedule, generally in advance of class sessions). If you fall behind, you should expect that it will take extra effort to catch up. This also assumes that the specified number of hours is spent working reasonably efficiently; if you haven't slept in a week or are studying during the 12-measure rests in a concerto you're playing, please discount appropriately. As much as possible, I will provide time estimates for how long I think each component of the coursework should take. You will need to help me to learn whether these estimates are reasonable.
If you find that you are regularly spending more than the indicated number of hours on this course, please let me know ASAP. This means either that I am doing a bad job of estimating how much work I'm asking you to do or that you're struggling more with the material or working less efficiently than you might be. These are all fixable problems, but they're better fixed earlier than later. In addition, do not spend unlimited time working until you finally solve a problem. Know when you've hit the limit of productive work on something and it is time to give up (or let me know so I can redirect you to a more efficient way of using your time). If you find that you are regularly spending substantially less time than expected on this course -- or if the time that you are spending feels like it's not being used well -- please let me know that as well. There is an enormous amount of interesting material that we're not going to have time to cover and I would be happy to point you towards some of the advanced aspects of the material we're covering. It is not in any of our interests for you to be bored or for your time to be poorly used by the course.
NB: This course is not using time-based grading. There is no requirement that you spend exactly a certain amount of time on the course each week. Rather, the time is a guideline that lets each of us know whether the course is meeting our needs and expectations. === Attendance ===
Unlike some of the classes that I have taught at Olin, FOCS attendance is expected. This course does not have a textbook. It does not even have a fixed syllabus. What happens in the classroom will not be entirely predictable nor will the critical points necessarily be replicated elsewhere. If you miss class, you will be missing something that cannot be made up. At the same time, your participation in class provides me with critical feedback; the course as a whole will suffer if you are not there. Please note that attendance means mentally as well as physically. If you get yourself into a position where you will simply not be able to absorb the content of the class, it may be better not to come. If this happens once, I will likely overlook it. If it happens regularly, I will feel entitled to conclude that you are not taking the participation requirement seriously. I do understand that conflicts arise. I expect that you will let me know substantially in advance of any class session that you will unavoidably miss. ("Substantially in advance" means as soon as you know it yourself. Email is the best way to let me know as it also creates a record.) I further expect that you will make arrangements to obtain as full a report as possible from a classmate and that you will take complete responsibility for any missed content.
The only exceptions to this policy are emergencies. Hospitalization is an emergency. Play rehearsal is not. Neither is an airplane ticket for noon on March 16.
You will, of course, need to make your own decisions and tradeoffs in this as in all of your life. Please please understand that these decisions will have consequences. In particular, unexcused absences (or excessive "excused" absences) may substantially affect your course grade. === Missed Work === Homeworks, projects, examinations, in-class and online participation are all required components of this class. Missing any component of the coursework will have consequences for your course grade. The consequence for missing an assignment may, at my discretion, exceed the weight of that assignment (had it been completed) in your course grade. If you believe that we need to discuss an exception to this policy, please let me know.
As a reminder, only students who have had an unanticipated disruption in their academic terms are eligible for a grade of incomplete. That grade must be requested (of the registrar) by the student prior to the last day of classes. Under Olin's policies, I cannot give a grade of incomplete, an extension beyond the end of term, or other hold-over grade. === Collaboration Policy ===
You are strongly encouraged to collaborate with your classmates as a means of learning the course material. Some aspects of course assignments are also intended primarily as educational rather than for assessment. In these cases, peers can be an invaluable resource. However, it is also important to determine what you understand on your own, both for your own callibration and for formal assessment purposes. Therefore, collaboration is encouraged except as specified in particular assignments. In general:
- Studying together is strongly encouraged. There is no better way to learn material than to teach it to someone else.
- Problem sets and projects may be discussed with others (except where indicated), but the write-up (including formulae, etc.) that you turn in must be entirely your own.
- Peer grading will play a role in this course. As a result, you may sometimes be asked not to collaborate with specific individuals on a particular assignment.
- Written solutions to various problems and projects may exist. Unless otherwise specified, you should not consult these until after you have completed your work.
- Any written solutions or other references or resources that you consult should be explicitly acknowledged in your collaboration statement (see below). Even if your consultation is inadvertent, please indicate it in the collaboration statement.
- Collaboration of any kind on examinations is explicitly forbidden.
- These are the general collaboration policies for this course. An individual assignment may specify different policies that pertain only to that particular assignment.
All collaboration must be acknowledged. This includes anyone you've discussed the assignment with at all and any resources that you may have consulted in order to complete this assignment. Unacknowledged collaboration is ilicit collaboration and may have consequences ranging from grade penalty to honor board action. If you have not collaborated on a particular assignment, you must indicate this on that assignment. Assignments without a collaboration declaration will not be accepted. === Readings ===
We will discuss course reading information on the first day of class. The are two textbooks that you are responsible for obtaining (access to): Cormen, Leiserson, and Rivest's Introduction to Algorithms (2e) and Sipser's Introduction to the Theory of Computation (1e). Other editions of these texts are fine. The Olin Library also has copies on reserve, though obviously not enough for everyone in the class. === Course Grade === Except under extenuating circumstances, you will receive only one grade in this course whether you are taking the course for 4 credits or 6 credits. Students taking the course for 6 credits will be expected to participate in certain activities from which 4 credit students are excused; however, there will not be a separate grade for these activities, which are meant primarily to enhance and deepen your understanding of the material covered in this class. A substantial fraction of this class is about the formal mechanisms underlying computation (and their implications for actual computer programs). In some senses, it's like a math class. It is very different from a class like Software Design (aka PI), which is fundamentally project-based and involves internalizing the ability to build (certain kinds of) things. As a result, your grade in this course will be based primarily on your ability to use formal analytical tools. This will be measured largely through examinations and through written problem sets. Because this is Olin, you will also put these analytical skills to use in building things. Because this class is being built by all of us as we go along, you will also communicate your understanding through class participation and online participation. All of these things will factor into your grade, but in most cases the bulk of your grade will be based on examinations and, to a lesser extent, on problem sets. Some notes:
- If all data are in agreement, this will indicate the grade that you should receive.
- Where some data disagree, I will work to understand why and use my best judgement to reconcile them to obtain an accurate understanding of your ability to use formal analytical tools as demonstrated by work in this course. In particular, if you have difficulty with written exams, we may consider oral exams or other means to evaluate what you actually know.
- Missed work or obvious lack of effort may be taken into account out of proportion to that work's contribution to my assessment of your abilities. In other words, some of the work in this course will only affect your grade significantly if you blow it off.
- Peer graded work will be used as confirmatory data or to trigger a further review, but will not form the primary basis for a final grade.
I will make every attempt to give solid mid-term feedback on or before the 33d day of instruction (March 10).
Assignments
- You are expected to keep up with assignments in this course. Late work will not be accepted. (If you believe that there's a really good reason for me to reconsider this, please let me know as soon as the reason becomes apparent. Given the nature of this course, I'm disinclined to accept late work.) === Reading === Some reading will be assigned. Other reading will be recommended. You should use your own judgement as to how you learn best; however, you will be expected to make adequate use of texts to support your learning. The Olin College Library has several texts on each of the topics that we will be covering in this class. You may find that you prefer someone else's coverage to the books we are officially using. === Class Participation === The enrollment in this class means that I will probably run in a very interactive seminar style. I expect you to come to class prepared to contribute. If you don't contribute, I will notice and I will let you know. If you do conribute, please bear in mind that there are a large number of students in the class and make room for them to contribute as well. === Notetaking/Wiki Participation === During the course of this semester, we will be building a web site containing the material that we've covered. This web site will be built by you. (OK, I'll help too....) Each student will be expected to take notes during certain assigned class sessions (three times during the semester) and to put those notes on the wiki (or other web-accessible place with suitable links). In addition, you may be assigned to critique/edit/augment notes up to three times during the semester. The gold standard is notes that provide adequate coverage of the class so that someone who misses that session -- which won't happen in actual practice, of course -- would be able to learn all of the material missed. This is an opportunity to demonstrate your understanding of the material in this class and to teach it to your peers. NB scanned paper notes are acceptable. There will likely be additional on-line participation required at various points during the semester. A mailing list and the existing wiki will be possible venues, but we may also add blogging, threaded discussion, or other facilities as appropriate. === Written Assignments/Problem Sets === The bulk of the ongoing work in this class will be in the form of regular problem sets. These will be due approximately every two weeks -- there should be six of them -- but the timing will vary to fit the topics presented. There will also be problems assigned between (some) class sessions; some of these may be part of the problem sets while others will be for class preparation only. You may be asked to assist in evaluating your peers' work. This provides an opportunity for you to see other solutions to problems and for you to enrich your own understanding (even if it means by figuring out why an incorrect answer is wrong). It also leverages the class numbers to increase the feedback and assessment available. (Instructor grading will also occur, just not always....unless you don't mind getting your problem sets back the week after graduation...) Time spent in evaluating peer work will be included in estimates of time spent on total coursework, of course. === Programming Assignments/Projects === For those taking the full 6 credit version of FOCS, regular weekly programming assignments will also be included. The actual due dates for these assignments will vary and will be announced as the semester progresses. As with written work, you will be asked to provide feedback on peer programming/project assignments. In this course, projects and programming exist to reinforce and deepen your understanding of the fundamental course material. They are not a course goal in and of themselves. You should, of course, expect others to read only elegant, well-written, and adequately documented code; however, code cleverness will not be a major assessment factor in this course. === Examinations === Regular examinations will provide the bulk of your evaluation this semester except in unusual cases. At present, three exams are planned. These are tentatively scheduled for:
- Thursday 23 February (covering sessions and assignments through 21 February)
- Monday 3 April (covering sessions and assignments through 30 March
- During finals week, TBD by the registrar