CS/ECE 374 Additional Resources
This page contains some useful resources as well as prerequisite
resources for this class. The useful resources are meant to strengthen
your understanding of the material and help you study. The prerequisite
resources are meant to strengthen your background and help you
revise stuff you already know.
Useful Resources
Illinois course materials
Lecture notes, lecture videos, slides, lab handouts, homeworks, and exams are available for several past semesters of algorithms classes at Illinois.
Course materials elsewhere
Over the last decade, it has sadly become much less common for instructors to preserve their course materials on the open web. Most instructors (or perhaps more accurately, most universities) either lock their course materials inside walled gardens ("learning management systems") or simply delete them when the course is over. Here are some useful exceptions.
-
Berkeley
(Fall 2014,
Fall 2016,
Fall 2017,
Fall 2018)
- homeworks (without solutions), lab problems (with solutions)
-
CMU
(Spring 2013,
Fall 2013,
Spring 2014,
Fall 2014,
Spring 2015,
Fall 2015,
Spring 2016,
Fall 2016,
Spring 2017,
Fall 2017,
Spring 2018,
current semester?) - notes/slides for all semesters, recitation worksheets for some semesters, homeworks only for the current semester
-
Maryland
(Spring 2012,
Fall 2012,
Fall 2013,
Fall 2015,
Spring 2016,
Fall 2017) - lecture notes for most semesters, homeworks for all
-
MIT
(Fall 2005,
Spring 2008,
Fall 2011) — notes, videos, and problem sets
-
Stanford (Summer 2013) — slides and problem sets
- UC Davis - videos on iTunes
-
Washington (several quarters) - notes/slides, sporadic problem sets. Primarily focuses on randomized algorithms, especially after about 2015.
MOOCs
Coursera, EdX and Udacity all offer complete algorithms courses, with videos, readings, and automatically graded exercises. By necessity, these courses tend to focus more on implementation and less on proofs and open-ended design than either CS 374 or CS 473.
- Udacity MOOCs are always freely available.
- EdX MOOCs are available only for enrolled students when the class is in session.
-
MicroMasters Program in Algorithms and Data Structures,
a series of eight MOOCs taught by Daniel Kane, Pavel Pevzner, and others,
loosely based on courses at UC San Diego
-
AlgorithmDesign and Analysis,
taught by Sampath Kannan at Penn
-
Advanced Algorithmics and Graph Theory with Python,
taught by Vincent Gripon, Patrick Meyer, Nicolas Farrugia,
Carlos Eduardo Rosar Kos Lassance,
and Ghouti Boukli Hacene at Institut Mines-Telecom
- Algorithms and Data Structures, taught by Sari Kulthm at Microsoft
- Algorithms , taught by Deepak Phatak, Nagesh Karmali, Ajit Diwan, and Ganesh Ramakrishnan at IIT Bombay
- Coursera MOOCs are also available only for enrolled students when the class is in session, and they are in session less often than EdX MOOCs.
- Algorithms Part 1 and Part 2, taught by Robert Sedgewick and Kevin Wayne, loosely based on algorithms classes at Princeton.
- Analysis of Algorithms, taught by Robert Sedgewick, loosely based on a more advanced class at Princeton.
- Coursera hosts several other algorithms “MOOCs”, but they all require a $49/month subscription to access, unless all you want are the videos. Pfft. Please.
- Khan Academy also hosts a free series of algorithms tutorials by Tom Cormen and Devin Balkcom.
Free Online Textbooks
Hopefully this list will continue to grow.
Dead Trees
For students who prefer an offline reference made of bleached and stained cellulose, we recommend the following textbooks. The campus bookstore probably doesn't have them, but you can find them cheaper online anyway. And they're all in the library. You remember that big brick building with the coffee shop and the study tables in it? Yeah, believe it or not, they have actual books in the basement!
-
You can buy paper copies of Jeff's book on Amazon, if you're into that sort of thing.
-
Recommended:
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani (McGraw-Hill, 2006). Based on the undergraduate algorithms course at Berkeley. Drafts of individual chapters (0,
1,
2,
3,
4,
5,
6,
7,
8,
9,
10) are freely available. (Thanks, Umesh!)
-
Introduction to Algorithms (3rd edition) by Tom Cormen, Charles Leiserson, Ron Rivest, and Cliff Stein (MIT Press/McGraw-Hill, 2009). Based on algorithms classes at MIT, and thick enough to stun an ox. A significant fraction of this book has been transcribed into Wikipedia.
-
Algorithms (5th edition) by Robert Sedgewick and Kevin Wayne (Addison-Wesley, 2011). Based on algorithms classes at Princeton. Focuses on more elementary material (taught in CS 225), with more emphasis on implementation and application than open-ended design and analysis. A crippled electronic version is available through the University library (if you have login credentials).
- There are several other relevant textbooks I'd love to recommend, but not at the outrageous prices that their publishers charge. Shame on you, Pearson; fuck you, Cengage.
Review
For review of prerequisite material, we strongly recommend the following online resources. (This stuff is also covered in several dead-tree textbooks, but really, why bother?)
Programming contests
...which (at least at the advanced levels) are really algorithm design contests where you also happen to write some code.
Other
We'll add more links here as we discover them. Suggestions are welcome!
Prerequisite Skills
Here, we list several basic mathematical concepts, data types, data structures, and algorithms that are typically covered in CS 173, CS 225, and earlier courses, with pointers to the corresponding Wikipedia entries. We assume you are already familiar with all of them. You can use any of these in your homework or exam solutions without providing further details or citing any source.
Because familiarity with these topics is crucial for success in 374, we are strictly enforcing the CS 173 and CS 225 prerequisites. Students who do not already have credit for both CS 173 and CS 225 (either from taking the course, passing the proficiency exam, or transferring credit from an equivalent course at another institution) cannot register for 374 without an override from the CS department. Instructors cannot offer prerequisite overrides.
For a detailed review of any of these topics, we strongly recommend using an actual textbook or one of the following online resources. (Beware that Wikipedia occasionally makes some very strange choices.)
Discrete Mathematics
-
Elementary algebra
-
Logarithm identities
-
Naive set theory
-
Binary relations, including functions, equivalence relations, and partial orders
-
Modular arithmetic
-
Asymptotic notation; comparing asymptotic growth rates
-
Evaluating simple summations (at least asymptotically)
-
Propositional logic and first-order predicate logic
-
Basic proof techniques: direct, indirect, exhaustive case analysis, contradiction
-
Induction (or equivalently, proof by minimal counterexample), especially strong induction and structural induction
-
Recurrences
-
Graphs (both undirected and directed),
trees,
directed acyclic graphs
Abstract data types
Elementary data structures
You may use any of these data structures in your homeworks and exams without providing further details or citing any source. If you use a small modification of one of these data structures, just describe your changes; don't regurgitate the original data structure details.
Elementary algorithms
You may use any of these algorithms in your homeworks and exams without providing further details or citing any source. If you use a small modification of one of these algorithms, just describe your changes; don't regurgitate the original algorithm details. We only care about worst-case running times in this class.
|