ICS 311 Algorithms (3 credits) Design and correctness of algorithms, including divide-and-conquer, greedy and dynamic programming methods. Complexity analyses using recurrence relations, probabilistic methods, and NP- completeness. Applications to order statistics, disjoint sets, B-trees and balanced trees, graphs, network flows, and string matching. Pre: 211 and 241, or consent.
Comment: On the fall 2013 final exam one student wrote about a problem:
“This question is too hard! We shouldn’t have to know implementations we have not used before!”
I wrote back to thank the student for concisely expressing (the negation of) exactly what this course _ is_ intended to teach! You may not “know” an implementation you have not encountered before, but this course should prepare you with the tools to analyze and make informed decisions about new implementations.
Do not approach this course solely as a memorization task, where you can only do algorithms you are trained to do, like a circus animal. We do want you to learn a “catalog” of algorithms, but you should be understanding their analyses as examples that enable you to analyze unexpected algorithms in the future. This is essential for being successful in a fast changing field where you are expected to figure out whether a new idea will work, as _ you _ are the computer scientist hired to do this.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009.
Students are advised to purchase the textbook, as this book will serve as a lifelong reference (it is the second most cited publication in computer science). Also, the exams will be open book but with no electronics permitted, so the PDF version of the book won’t help you there.
Students are also advised to keep their ICS 241 (Discrete Mathematics for Computer Science) textbooks for reference.
Daniel D. Suthers
Professor of ICS
Robert Ward
M.S./Ph.D. Student in ICS
Anthony Sarria
ICS Undergrad and ICS 311 Survivor
Questions about Course Content: In general, questions about course content such as concepts, clarifications of assignments, etc. should be posted to the Laulima discussion forum of the week. This is because (1) other students can see our responses there, and thus also benefit; and (2) other students may notice the question and answer before the instructor or TA notices it (though we will check daily). If you email us a question, we will post the reply in Laulima unless personal information is involved.
Personal Topics: For topics that are not of interest to other students or are personal, you may email us, or stop by office hours. (Of course you may also use office hours for course content questions.) If using email, put “ICS 311” in the subject line.
Communication with other students (e.g., group members): You can send email to other students in the course using the Laulima “Mailtool”. You don’t need to know their real email address to do this.
We use the course website www2.hawaii.edu/~suthers/courses/ics311s14/ for posting schedules and notes.
We use **Laulima** for all other online required course functions such as podcasts, quizzes, discussions and submitting assignments. Please see this document on everything Laulima users should know.
We will use Google Docs for in-class problem solving, as it supports simultaneous editing.
Screencasts (videos) of lectures are available on YouTube and iTunesU as well as Laulima (your choice). They are linked from the individual Notes pages (Topic-XX.html).