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:

  1. Analysis of the complexity of algorithms;
  2. Sorting and searching;
  3. Algorithms for networks and graphs;
  4. 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.

Meeting:

  • Mohler 453, Mon/Wed/Fri, 9:10am-10:00am.
  • Mohler 444, Tuesday, 1:10pm-4:00pm

Lecture calendar

Note: much of the lecture material is adapted from slides by Jeff Linderoth for IE170. Thanks Jeff!

  1. 01/18/2010: Introduction;
  2. 01/20/2010: Induction, big-O notation;
  3. 01/22/2010: Recurrences and the Master Theorem;
  4. 01/25/2010: Correctness and complexity of the insertion sort;
  5. 01/27/2010: Divide and conquer; Merge Sort;
  6. 01/29/2010: Examples with the Master Theorem; Heaps;
  7. 02/01/2010: Binary Search Trees;
  8. 02/03/2010: Quicksort;
  9. 02/05/2010: Quicksort and stack issues;
  10. 02/08/2010: Red-black trees;
  11. 02/12/2010: Hash tables;
  12. 02/15/2010: Open addressing in hash tables;
  13. 02/17/2010: Open addressing in hash tables;
  14. 02/19/2010: Graphs;
  15. 02/22/2010: Breadth-first search;
  16. 02/24/2010: Depth-first search;
  17. 02/26/2010: Midterm practice (solutions);
  18. 03/01/2010: DFS on undirected graph, topological sort;
  19. 03/03/2010: Midterm exam;
  20. 03/05/2010: Strongly connected components; minimum spanning trees;
  21. 03/15/2010: Strongly connected components; minimum spanning trees (see lecture notes of 03/05);
  22. 03/17/2010: Minimum spanning trees: Kruskal’s and Prim’s algorithms;
  23. 03/19/2010: Shortest paths problems; Bellman/Ford’s and Dijkstra’s algorithm;
  24. 03/24/2010: All-pair shortest paths;
  25. 03/26/2010: APSP2; (see notes of 03/24);
  26. 03/29/2010: Floyd-Warshall’s algorithm (see notes of 03/24);
  27. 03/31/2010: Transitive closures;
  28. 04/02/2010: Flows in networks (see notes of 03/31);
  29. 04/05/2010: The maximum flow problem;
  30. 04/07/2010: Ford and Fulkerson’s algorithm (see notes of 04/05);
  31. 04/09/2010: Dynamic programming;
  32. 04/16/2010: Dynamic programming: the assembly line problem (see notes of 04/09);
  33. 04/19/2010: Dynamic programming: the lot sizing problem;
  34. 04/20/2010: Representation of matrices (in lab);
  35. 04/21/2010: Solving linear systems;
  36. 04/23/2010: the LUP decomposition;
  37. 04/26/2010: example of the LUP decomposition;
  38. 04/28/2010: Positive Definite matrices (see notes of 04/23);
  39. 04/30/2010: Least squares approximation (see notes of 04/23);

Lab calendar

Note: some of the material used in the lab is from code written by Ted Ralphs and colleagues for previous IE170 courses. Thanks Ted!

  1. 01/19/2010: Use of Eclipse, examples on Fibonacci Numbers and Euclid’s algorithm (package);
  2. 01/26/2010: Quick refresher of C++; Click here for the lab assignment;
  3. 02/02/2010: Bubblesort and Heapsort;
  4. 02/09/2010: Quicksort;
  5. 02/16/2010: Binary search trees;
  6. 02/23/2010: Hash tables;
  7. 03/02/2010: Breadth-first Search;
  8. 03/16/2010: Strongly connected components;
  9. 03/23/2010: Shortest path algorithms;
  10. 03/30/2010: All pairs Shortest paths;
  11. 04/06/2010: The maximum flow problem;
  12. 04/13/2010: Dynamic Programming;
  13. 04/20/2010: Matrix multiplication;
  14. 04/27/2010: LUP decomposition;

Course material

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).

Links

Randomly placed stuff for a better understanding of how algorithms are created and implemented.

These links show you how not to write code:

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.