- Time: MWF 9:05 - 10:00
- Place: Merritt 100
- Instructor: John Lasseter
- Office: Lansing 300
- Office Hours:Wed 1:30 - 2:30, Th 10- 1:30, or by appointment (or just drop by)
- Phone: (315) 781-4652
- E-mail: firstname.lastname@example.org
In one sense, an algorithm is merely a language-independent specification of a set of instructions for performing some computational task: an abstract version of the real programs that are written in real languages. Yet the idea is much deeper than this, for the study of algorithms cuts to the core of what it means to solve a problem by computation. The ability to develop algorithms, analyse their important properties, and apply them to various problems is therefore crucial to becoming effective, both as a programmer and as a computer scientist.
On completion of the course, you will be able to adopt existing algorithms, or develop new ones, which solve previously unfamiliar computational problems correctly and, if possible, efficiently. You will be able to realize these new algorithmic solutions as real programs, in a variety of programming languages. More broadly, you will develop maturity in many of the mathematically-informed techniques that are essential to nearly all sub-disciplines of computer science.
In addition to a solid foundation in programming, CS 343 assumes a basic knowledge of data structures and algorithms, and recursive programming techniques, equivalent to the material taught in CS 241. Further, the analysis techniques we will use are drawn from discrete mathematics. Although prior experience is helpful here, the material is a subset of that covered in MATH 251 (a co-requisite), and we will cover it as needed.
- Introduction to the The Design and Analysis of Algorithms (2nd. Ed.), by Anany Levitin (Addison-Wesley, 2007).
- Additional readings will be posted as needed. Check the Announcements page for updates.
Format of the Course (IMPORTANT: READ ME)
This course will be taught in a seminar style, with a heavy emphasis on your active participation during each class. There will be much less emphasis on lecture, if any. Specifically, class time will consist first of initial discussion and clarification of material that you have prepared beforehand, with the bulk of class time devoted to individual and group problem-solving.
Participation and Preparation
In advance of each class, you will be assigned reading and occasionally also problem sets. You will be expected to have completed this reading by the following class, in order to participate effectively. See also "Prepared Problem Sets", below
Prepared Problem Sets
At the end of every week, there will be a few small problems assigned. These problems are to be solved individually, and they are due at the beginning of class: no late work will be accepted. At the end of class that week, you are to bring a neatly-formatted copy of your solutions to class, along with two photocopies, which will be given out to other groups for peer critique and discussion.
The standard for these problems is one of demonstrated engagement rather than correctness. What this means is that you should write up problems that you can solve, in a manner that teaches your solution to the reader. If you can't solve a problem, do your best: write what progress you made and where you got stuck.
We will spend some of each end-of-week class engaged in discussion and critique of each others' work on these problems. Because the timing of class depends on your efforts, no late work will receive credit.
In addition to class preparation exercises, there will be a few, larger take-home assignments, given as appropriate (roughly, every two weeks or so).
There will be two mid-term exams. We will discuss the format in class.
Per the schedule, there will be a final exam. We will discuss the format in class.
See the departmental policies page for the default behaviors. The following are changes local to this course:
Naturally, your prompt attendance is required at every class, for the entire class. You may take a total of 2 excused absences for the semester. Each absence beyond that (unless explicitly arranged with me) will cost 2 points from your final grade, up to the maximum participation component.
All homework comes with a due date, but if I haven't started grading the assignment yet, I'll still accept late work. Once graded and returned, I won't accept it.
One exception is work whose submission and presentation is a part of class time (and therefore vital to the class). Such assignments will be clearly identified, and late submissions (defined as after the start of class) will receive no credit.
That being said, do not get behind on the assignments. The material in this course is challenging, and the pace is intense: if you let yourself get behind, you will be overwhelmed. If you are having trouble, please ask for my help, as early as possible.
Students with Disabilities
Students with documented disabilities who may need accomodations, who have any emergency medical information an instructor should know of, or who require special arrangements in the event of an evacuation, should contact me as early as possible, preferably no later than the first week of classes.
If you are a student with a disability for which you may need accommodations, you should self-identify and register for services with the Coordinator of Disability Services at the Center for Teaching and Learning (CTL), and provide documentation of your disability. Disability related accommodations and services generally will not be provided until the registration and documentation process is complete. The guidelines for documenting disabilities can be found at the following website: http://www.hws.edu/disabilities
Please direct questions about this process or Disability Services at HWS to David Silver, Coordinator of Disability Services, at email@example.com or x3351.
I take this very seriously: a breach of academic honor will result in a failing grade for the course, and may be subject to further college sanctions. These standards are clearly laid out in the HWS Catalogue
and for the most part, they're pretty straightforward: your work must be yours and yours alone (or your working groups, if that applies), and your exams can only be discussed with me. Basically, you know already know the difference. Don't cheat.
Collaboration: Most assigned work is intended to be collaborative. Where individual efforts are required, you are still permitted -- indeed, encouraged -- to discuss course material with each other, to evaluate, trace, debug, refute, validate, or otherwise compare each others' work, and to adjust your own work if this collaboration results in new understanding.
However, you are not free to simply mail or print identical copies of the same work, and claim that it is the work of two separate individuals/groups. This is plagiarism, and is a breach of academic honor standards (it is also extremely easy to spot, especially in a class this small). While I encourage you to learn from each other, at the end of the day, the work you submit for a grade must be yours and yours alone.
If you find yourself unsure whether a form of collaboration or borrowing is acceptable, please ask me, in advance.
Code from outside class (texts, the Internet, etc.): As with collaboration, study of other approaches is acceptable, but you are expressly forbidden from copying such code and claiming it as your own. In the event that you cannot complete your own work without such a resource, you must clearly identify the original author and the resource from which you acquired it. Credit will be given for that portion of the work that is yours.
Relative weights for your final grade are as follows
- Participation and Preparation: 10%
- Homework: 30%
- In-class problem setst (20%)
- Midterm Exams: 10%, each
- Final Exam: 20%
Me, outside of class: The best way by far to get in touch with me is in person, during office hours. Any kind of class-related discussion is encouraged, whether it be a specific question about a homework problem, a request for encouragement and help getting started on an assignment, a point of confusion about the reading, or just plain curiousity about some of the further scientific directions that are possible. I am often available outside of office hours to answer questions, offer further explanation, or just to shoot the breeze. I am always available during posted hours. I encourage you to drop by.
Please note that my office (on the third floor of Lansing) is not wheelchair accessible. If this or another physical disability prevents your from reaching me there, please let me know, and I will happily arrange an alternative meeting place with you.
In Writing: Barring that, your best bet is by email, which I check late, early, and often. In fact, email is very often the most effective way for you to ask a question, as the effort involved in articulating what you want to ask can help clarify many things. It also makes it easier for me to give succinct replies to which you can refer later. I'm a pretty early riser, though, so don't assume I'll answer anything after 9 pm or so.
By Phone: Phone calls are, frankly, lousy. You're certainly invited to call (315-781-4652), but it's difficult to communicate technical questions and answers clearly without reading or writing down anything. Phone messages are generally a poor choice: you might wait as much as 24 hours before I get any voice mail message you leave.