Everyone knows Moore’s Law, a prediction made in 1965 by Intel co-founder Gordon Moore that the density of transistors in integrated circuits would continue to double every 1 to 2 years. […] Even more remarkable — and even less widely understood — is that in many areas, performance gains due to improvements in algorithms have vastly exceeded even the dramatic performance gains due to increased processor speed.
Report to the President and Congress: Designing a Digital Future: Federally Funded R&D in Networking and IT
Covers the Design and implementation of fundamental data structures and algorithms, including: linked lists, hashing, sorting, trees, stacks, queues, sets and bags, and recursion. Application to problem solving and object-oriented design of moderate sized programs. Prerequisite: CS 501B.
The course is divided into five sections. See the syllabus for details.
The class meets on Mondays and Wednesdays in Howard Hall 316 (the CS conference room) from 6 p.m. to 7:50 p.m. Class starts on Wednesday, 19 January and ends on Monday, 2 May. There is no class Monday and Wednesday, 7 and 9 March, during Spring Break . Monday, 28 March, is the last day to withdraw from class with a W on your transcript.
All grades are kept with one digit of precision to the right of the decimal point and 0.05 rounded up. No grades are adjusted to a curve; that means, for example, that 89.9 is always a B+, never an A-.
95 ≤ A 90 ≤ A- < 95 86.6 ≤ B+ < 90 83.3 ≤ B < 86.6 80 ≤ B- < 83.3 76.6 ≤ C+ < 80 73.3 ≤ C < 76.6 70 ≤ C- < 73.3 F < 70
The final grade is the weighted sum of the quiz-grade average and the assignment-grade average with the weights
55% assignment grades 35% quiz grades 10% presentation grades
The quiz- and assignment-grade averages are straight, unweighted averages.
There are four quizzes, one quiz for each section after the first section; see the syllabus for the schedule. Quizzes are given in class, and are closed book with no notes; calculators and computers will not be necessary. The quizzes are cumulative, covering everything taught up to and including the class before the quiz. Quizzes should take no more than an hour to complete, and are given in the first hour of class. Quiz answers will be made available off the syllabus.
There are no midterms or final exams. Mid-term grades are computed from the straight, unweighted average of what ever grades have accrued by the day mid-term grades are due (Tuesday, 26 October).
There are many data structures and algorithms textbooks, all more or less the same. There’s no assigned textbook for this course; instead, pick a textbook or two you’re comfortable with. As a first cut, compare the book’s table of contents with the syllabus to make sure the topics mentioned in the syllabus appear in the table of contents. You can glean further advice from a small annotated bibliography of data structures and algorithms books.
Please do not interpret “There’s no assigned textbook for this course” to mean “Great! I don’t need a textbook.” Absorbing everything you need to know from lectures won’t be possible, not the least because there won’t be time to cover everything in lectures. Working it out over a textbook or two will give you the time and space to learn what you need to know. In addition, the tests are written assuming knowledge found in basic data structures and algorithms textbooks.
This is a programming course, and you’ll be programming in Java. In addition, the course will cover (possibly) new Java features in just enough detail to get by in data structures and algorithms. You should have at hand at least one Java programming language book to help you recover the old details and pursue further the new details. The book from CS 175 and 176 should be fine. Also recommended are Core Java 2, Vol. 1 — Fundamentals by Cay Horstmann and Gary Cornell, Sun Microsystems Press, 2008. and Java in a Nutshell by David Flanagan, O’Reilly Media, 2005.
Mail relevant to the class are stored in a hyper-mail archive. If your message is of general interest to the class, I’ll store it, suitably stripped of identification and along with my answer, in the archive.
http://tinyurl.com/mucs503s11h). I’ll make the class notes, assignments, and quizzes available off the syllabus (
http://tinyurl.com/mucs503s11s); you should get in the habit of checking the syllabus regularly.
http://identi.ca/mucs305) or twitter (
http://twitter.com/mucs305). The same messages appear on all services.
My attendance policy applies only to lecture attendance; it does not apply to other kinds of attendance which may be required for the course. Repeated failures to meet the attendance expectations set for tests, meetings, projects, labs or other forms of course work will have a bad influence on your grade.
First, the only complaint that matters is that something got marked wrong when it was actually right. When you come to complain, be prepared to present, in explicit detail, what it is you did and why you think it’s right.
Second, complaints about a particular test or assignment are only valid until the next test or assignment is due; after that point the book is permanently closed on all previous test or assignment grades.
A late assignment is penalized ten points a day for each day it’s late. I use a 24-hour clock running from midnight to midnight to measure days; note this means that an assignment handed in the day after it’s due is penalized ten points: five for the day it was due and five for the next day.
A make-up test must be scheduled to be taken by the date of the test following the missed test (or the final exam if you miss the last test). If a missed test is not made up by the time of the next test, you get a zero for the missed test.
There will be only one make up given per missed test. If more than one person misses the same test, those people will have to coordinate among themselves to pick a mutually agreeable date for the make up.
Learn data structures 'n' algorithms in the comfort of your home, courtesy of MIT. There’s also a more recent, non-video, advanced but still introductory version of the course. Or maybe you prefer Berkeley.
The NIST dictionary of algorithms and data structures.
FreeTechBooks' list of on-line data structures and algorithm books.
Softpanorama’s old but wide ranging link page for data structures and algorithms.
Algosort’s link page to algorithm pages.
The last time I taught this course.