Click here to get a copy of the syllabus.
The focus of this course is on algorithms. Students will learn how to model certain problems in systems engineering and how to design algorithms (and data structures) to solve them. The main subjects of the course are:
- Analysis of the complexity of algorithms;
- Sorting and searching;
- Algorithms for networks and graphs;
- Numerical algorithms.
Final exam: Tuesday, May 4, 8am to 11am in Mohler 110. Closed books, closed notes, no calculators. Chapters 2, 3, 4, 6, 7, 11, 12 (before the midterm); 16, 22, 23, 24, 25, 26, and 28 of the textbook. Midterm 2009 solutions, Final 2009, Midterm 2010.
- Mohler 453, Mon/Wed/Fri, 9:10am-10:00am.
- Mohler 444, Tuesday, 1:10pm-4:00pm
Note: much of the lecture material is adapted from slides by Jeff Linderoth for IE170. Thanks Jeff!
- 01/18/2010: Introduction;
- 01/20/2010: Induction, big-O notation;
- 01/22/2010: Recurrences and the Master Theorem;
- 01/25/2010: Correctness and complexity of the insertion sort;
- 01/27/2010: Divide and conquer; Merge Sort;
- 01/29/2010: Examples with the Master Theorem; Heaps;
- 02/01/2010: Binary Search Trees;
- 02/03/2010: Quicksort;
- 02/05/2010: Quicksort and stack issues;
- 02/08/2010: Red-black trees;
- 02/12/2010: Hash tables;
- 02/15/2010: Open addressing in hash tables;
- 02/17/2010: Open addressing in hash tables;
- 02/19/2010: Graphs;
- 02/22/2010: Breadth-first search;
- 02/24/2010: Depth-first search;
- 02/26/2010: Midterm practice (solutions);
- 03/01/2010: DFS on undirected graph, topological sort;
- 03/03/2010: Midterm exam;
- 03/05/2010: Strongly connected components; minimum spanning trees;
- 03/15/2010: Strongly connected components; minimum spanning trees (see lecture notes of 03/05);
- 03/17/2010: Minimum spanning trees: Kruskal’s and Prim’s algorithms;
- 03/19/2010: Shortest paths problems; Bellman/Ford’s and Dijkstra’s algorithm;
- 03/24/2010: All-pair shortest paths;
- 03/26/2010: APSP2; (see notes of 03/24);
- 03/29/2010: Floyd-Warshall’s algorithm (see notes of 03/24);
- 03/31/2010: Transitive closures;
- 04/02/2010: Flows in networks (see notes of 03/31);
- 04/05/2010: The maximum flow problem;
- 04/07/2010: Ford and Fulkerson’s algorithm (see notes of 04/05);
- 04/09/2010: Dynamic programming;
- 04/16/2010: Dynamic programming: the assembly line problem (see notes of 04/09);
- 04/19/2010: Dynamic programming: the lot sizing problem;
- 04/20/2010: Representation of matrices (in lab);
- 04/21/2010: Solving linear systems;
- 04/23/2010: the LUP decomposition;
- 04/26/2010: example of the LUP decomposition;
- 04/28/2010: Positive Definite matrices (see notes of 04/23);
- 04/30/2010: Least squares approximation (see notes of 04/23);
Note: some of the material used in the lab is from code written by Ted Ralphs and colleagues for previous IE170 courses. Thanks Ted!
- 01/19/2010: Use of Eclipse, examples on Fibonacci Numbers and Euclid’s algorithm (package);
- 01/26/2010: Quick refresher of C++; Click here for the lab assignment;
- 02/02/2010: Bubblesort and Heapsort;
- 02/09/2010: Quicksort;
- 02/16/2010: Binary search trees;
- 02/23/2010: Hash tables;
- 03/02/2010: Breadth-first Search;
- 03/16/2010: Strongly connected components;
- 03/23/2010: Shortest path algorithms;
- 03/30/2010: All pairs Shortest paths;
- 04/06/2010: The maximum flow problem;
- 04/13/2010: Dynamic Programming;
- 04/20/2010: Matrix multiplication;
- 04/27/2010: LUP decomposition;
First, you may want to have a look at the 2009 version of this course. Second, the textbook is:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Second Edition (McGraw-Hill, 2003).
Each lecture of the course will focus on one or more chapters of this textbook.
Three other very interesting books, although not required for the course, provide examples and insights. They are the following:
- Donald Knuth. The Art of Computer Programming (Addison-Wesley);
- Robert Sedgewick. Algorithms in C++ (Addison-Wesley);
- David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing (Addison-Wesley).
Randomly placed stuff for a better understanding of how algorithms are created and implemented.
- Sorting Algorithms Animations;
- The Tao of programming (from textfiles.com);
- C++ tutorials and info;
- The Standard Template Library;
- Code Kata: (programming) practice makes perfect;
- Project Euler, challenging mathematical/computational programming problems;
- A beginners’ guide to the Big O notation;
- The efficient version of the Fibonacci procedure is linear… or maybe not; see if you can catch the errors in the comments (hint: there are quite a few);
- Fractions and Fibonacci numbers;
- Pointers and arrays;
- Recursion, by Brian W. Kernighan, Dennis M. Ritchie, and HP Lovecraft;
- Animation of sorting algorithms;
- Explaining sorting algorithms with Folk dances;
- Stand-alone code for numerical computing;
- Visualizing (classical and user written!) sorting algorithms: http://visualsort.appspot.com.
These links show you how not to write code:
- The International Obfuscated C Code Contest
- Unmaintainable code
- Stack and Heap in C++
- The Daily WTF (obviously meaning “Worse Than Failure”): shocking, hilarious, appalling, weird coding solutions to otherwise trivial problems;
But if you really can’t resist writing bad code, please consider buying bad code offsets.
Accommodations for Students with Disabilities
If you have a disability for which you are or may be requesting accommodations, please contact both your instructor and the Office of Academic Support Services, University Center C212 (610-758-4152) as early as possible in the semester. You must have documentation from the Academic Support Services office before accommodations can be granted. For more information, please visit the student support services website: http://www.lehigh.edu/~inacsup/disabilities.