| Course Description | The course begins with a short review of basic analysis techniques: approximating functions asymptotically, bounding sums, and solving recurrences. We will study problems that are efficiently solvable, focusing on design techniques such as divide-and-conquer, dynamic programming, amortization and greedy algorithms. Algorithms for sorting, graph algorithms, computational geometry, and string matching algorithms will serve to illustrate these concepts. The emphasis of this class will be on learning algorithm design: developing the intuition that helps us find the right approach, the ability to formalize an appropriate procedure, and the skills to analyze its correctness and efficiency. | ||||
| Prerequisites | CSc 342 and CSc345 | ||||
| Time & Place | MW 10:30 - 11:45am GS906 |
||||
| Textbook | Cormen, Leiserson, Rivest, and Stein Introduction to Algorithms, Second Edition MIT Press, Boston, 2001. (Note that used copies of CLRS can be bought for as little as $12 online, e.g., abebooks.com) | ||||
| Instructor |
Stephen G. Kobourov Gould-Simpson 723 Office Hours: MW 1:00-3:00pm and open door policy Phone: 621-4324 kobourov AT cs.arizona.edu | ||||
| Teaching Assistants |
| ||||
| Exams and Grading |
A midterm exam, a final exam, and homework assignments will all contribute to the final grade. Your final grade will be based on the percentage of all available
points that you receive. Homework assignments account for 42% of the grade, and the midterm and final exams account for 25% and 33%, respectively. To give you an idea of how percentages might
translate into letter grades, here is a typical example: A (85-100), B (70-85), C (60-70), D (50-60), E (0-50).
I do not claim that the grade cutoffs for this class will be the same. These cutoffs are merely to give you an idea of how I have graded in the past. I reserve the right to fail any student who has failed any component of this course.
The midterm and the final will be in-class exams. Written makeup exams will not be offered. If you have a very good reason to miss an exam (hospital stays, athletic competition, etc.) you must schedule an oral exam within one week of the written exam. Instructor review of the grading for an exam must be requested no later than one week after the graded exam is returned to you. Be aware that as a result of such a review your grade is just as likely to go down as it is to go up. |
||||
| Homework Assignments |
There will be 6 homework assignments of equal weight. Assignments
will be posted every other Monday and due the following Monday at
the start of class. TA review of the grading for a homework assignment must be
requested no later than one week after the graded assignment is
returned to you.
Homework Assignment 1 Due 10:30am, February 4, 2008; Solutions
Late homework will not be graded for credit. Failure to turn in
a homework on time will result in a zero for that assignment. Yes,
this lateness policy is harsh. Why? Because in the past, those who
have fallen behind have had a devil of a time catching up. So we are
trying to prevent you falling behind. In the past, I have had students
complain that they could have handed in something substandard on time
and gotten more points than if they had handed in something really
good a little late. Too bad. It is up to you to plan your time
carefully and get your work in on time! You have been warned. I will
not entertain complaints. If you have extenuating circumstances, tell
me as early as possible. If you do so well before the due
date, requests will be considered reasonably. The closer to the due
date it gets, the less likely I am to give you extra time. As a writing proficiency course, 10% of your grade will be based on clarity of exposition of the solutions. In other words, a problem solution that is technically perfect, but which is presented in a difficult-to-understand manner, might lose 10% of the available points. Neat and concise solutions are required in order to receive full credit. If you cannot solve a particular problem, state this clearly in your write-up, and write down only what you know to be correct; rambling at length about ideas that don't quite work may cause additional points to be deducted. Further guidelines for the written presentation of solutions are given here.
Extra credit:
Sometimes the homework assignments will suggest extra credit work. Extra credit
in this course will be tallied separately from regular scores. If you
end up on the borderline between two grades at the end of the course,
extra credit will count in your favor. However, failure to do extra
credit will never be counted against you, as grades are assigned on
the basis of regular scores. You should do extra credit work if you find it
interesting and think that it might teach you something. On the other
hand, it is not wise to skimp on the regular assignment in order to do
extra credit. |
||||
| Attendance | Attendance will be expected, but not recorded. Needless to say, attendance is strongly recommended. There will be no pre-canned slides or lecture notes for this course. Students are fully responsible for all material presented or assigned in class. | ||||
| Academic Integrity |
Any work that is submitted by a student for credit is expected to be
that student's, and that student's alone. You may discuss your
homework assignments with your classmates, your instructor and your TAs. In fact, I recommend discussing ideas and
approaches to problems with others. However, you should
write your own written homework solutions and should not read or
copy the solutions written by others. For
more details, see the Computer
Science Departmental Course Policy on Collaboration and the University of
Arizona Code of Academic Integrity.
Any attempt to pass off someone else's work as one's own is considered to be cheating. Using material from a textbook, journal, or other such ``external'' source without proper acknowledgment, is considered to be cheating. Plagiarism is the incorporation of someone else's words or ideas without proper attribution, regardless of where these ideas came from (e.g., another student, the instructor's published solutions, the Internet). Plagiarism constitutes theft of intellectual property, and those who engage in it will receive the failing grade of ``E''. These and other provisions are governed by the University's Code of Academic Integrity which applies to all in this course. |
||||
| Students with Disabilities | I encourage students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss with me any appropriate accommodations that I might make on their behalf. | ||||
| Honors Students |
Honors students (and other interested students) will work on
a research project. Several projects will be offered and small groups
of 2-3 students will work on them. The projects typically involve
designing, implementing, and testing an algorithm. The one unifying
feature of the projects is that they are different than standard course-work.
Participating in a research project could also be useful in other ways: it will look good on your applications to grad school (should you
decide to pursue a graduate degree) and maybe it will give you some
idea of what to do for an honors thesis, independent study, etc.
I will expect 2 progress reports (one 2 weeks in the semester and another 8 weeks in the semester). In addition, you will have to write a 10 page report of the work (last day of classes). Each of these projects should lead to a conference/journal publication and the report is a close-to-final draft of this publication. All of the projects are part of various research efforts with faculty, graduate and undergraduate students working on them. Thus help on your part of the work will be readily available throughout the semester. To compensate for the significant amount of time you will spend on these projects, you can drop the lowest homework grade (which means that you can skip a homework, but I don't recommend that you do). More importantly, 20% of your final grade will be based on the project. That is, if you have a 100% in all class work and 50% on the final, you will receive a 90% for the class. | ||||
| Newsgroup |
The instructor and the TAs will post various kinds of information by way of the cs.course445 newsgroup. Please check the newsgroup frequently, especially when you have questions about the homework. We will assume that when a message is posted to the newsgroup, you have read it. You can also post questions (regarding an assignment, an exam, etc.). We will do our best to answer within 24 hours. | ||||
| Help |
Questions regarding the class, homework, exams, etc. can be addressed to the newsgroup so that all students can benefit from the answer. If you have questions about your grades, or for similar topics, you should email cs445s08@cs.arizona.edu. We will try to respond within 24 hours. Please do not email to individuals (the instructor or a particular TA) but rather mail all of us via the cs445s08 alias. |