Pietro Belotti

Click here to get a copy of the syllabus.

The focus of this course is on data structures and algorithms. Students will learn how to model certain problems in systems engineering and how to design data structures and algorithms to solve them. The main subjects of the course are:

1. Sorting and searching;
2. Algorithms for networks and graphs;
3. Numerical algorithms.

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!), and Lecture 38 from Ted Ralphs (thanks Ted!).

1. 01/12/2009: Introduction (notes).
2. 01/14/2009: Induction, complexity (notes).
3. 01/16/2009: Recurrences, the Master theorem (notes).
4. 01/19/2009: Insertion sort: correctness and complexity. Data structures: lists (notes).
5. 01/21/2009: A quick tour of pointers in C++.
6. 01/23/2009: C++: classes, constructors, dynamic memory allocation (notes).
7. 01/26/2009: C++: passing by value/reference, iterators, STL (notes).
8. 01/28/2009: Divide & Conquer. The towers of Hanoi. Merge Sort (notes).
9. 01/30/2009: Binary trees. Heaps. Heapsort (notes).
10. 02/02/2009: Heapsort (cont.). Quicksort. The call stack (notes).
11. 02/04/2009: Quicksort: average case analysis. The call stack. Red-black trees (notes).
12. 02/06/2009: Red-black trees (notes).
13. 02/09/2009: Hash tables. Direct addressing (notes).
14. 02/11/2009: Open addressing (notes).
15. 02/13/2009: Graphs and their representation (notes).
16. 02/16/2009: Breadth-first search (notes).
17. 02/18/2009: Depth-first search (notes).
18. 02/20/2009: Midterm practice (no notes).
19. 02/23/2009: Midterm exam (solution). Grades are out – check Blackboard.
20. 02/25/2009: DFS on undirected graphs. Topological sorting (notes).
21. 02/27/2009: Connectivity in graphs. Strongly Connected Components. (notes).
22. 03/09/2009: Exercises on SCCs (notes).
23. 03/11/2009: The Minimum Spanning Tree (MST) (notes).
24. 03/13/2009: Kruskal’s and Prim’s algorithms for MST (notes).
25. 03/16/2009: Shortest paths. Bellman-Ford’s and Dijkstra’s algorithms (notes).
26. 03/18/2009: All-pairs shortest paths (notes).
27. 03/20/2009: The Floyd-Warshall algorithm. Transitive closure (notes).
28. 03/23/2009: Transitive closure. Flows in networks (notes).
29. 03/25/2009: An application of APSP1 and Floyd-Warshall algorithm (no notes).
30. 03/27/2009: The Maximum Flow problem (notes).
31. 03/30/2009: Max flow: Ford-Fulkerson method. Bipartite Matching (notes).
32. 04/01/2009: Bipartite Matching. Dynamic Programming (notes).
33. 04/03/2009: Dynamic Programming: Capital budgeting, assembly line (notes).
34. 04/06/2009: Dynamic Programming: assembly line, lot sizing (notes).
35. 04/08/2009: Dynamic Programming: lot sizing. Greedy algorithms (notes).
36. 04/10/2009: Vectors and matrices: definitions. (notes).
37. 04/13/2009: Representation of matrices (notes).
38. 04/15/2009: Permutation matrices. Solving systems of linear equations (we’ll use the same notes as last time).
39. 04/17/2009: LUP decomposition (notes).
40. 04/20/2009: Positive definite matrices. Least squares (notes).
41. 04/22/2009: Cryptography: an overview (notes).
42. 04/24/2009: Practice for the final exam (notes; you can also use Ted Ralphs’ final practice).
43. 04/29/2009: Final, Mohler 110, 4pm-7pm. Closed books, closed notes.

Lab calendar

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

1. 01/13/2009: Use of MS Visual Studio. Recursive and Direct Fibonacci method. The Greatest Common Divisor problem (notes).
2. 01/20/2009: Linked lists and arrays. Insertion sort (notes).
3. 01/27/2009: Bubblesort. Debugging with Visual Studio (notes).
4. 02/03/2009: Heapsort (package).
5. 02/10/2009: Binary Search Trees (package).
6. 02/17/2009: Hash tables (package).
7. 02/24/2009: Graphs (package).
8. 03/10/2009: Strongly connected components (package).
9. 03/17/2009: Shortest paths (package).
10. 03/24/2009: All-pairs shortest paths (package).
11. 03/31/2009: Max flow (package).
12. 04/07/2009: Dynamic Programming: the capital budgeting problem (package).
13. 04/14/2009: Matrices (package).
14. 04/21/2009: Systems of linear equations (package, available soon).

Note: In order to specify arguments within Visual Studio, select menu Project, item Settings…. The second tab of the window is the Debug tab, and you can set the arguments to your program by putting them in the “Program Arguments” field, separated by a space. Also, the field “Working Directory” below allows you to set a directory alternative to where the executable file is located.

For instance, if your program Lab05.exe is located in the folder H:MyprogramsLab05 and the input file input.100.txt is located in another folder, say H:DataTestFilesinput.100.txt, you may want to set the “Working Directory” field to H:DataTestFiles. From then on, you can specify the argument to your program as input.100.txt (from within Visual Studio only!) or open the file in the program (with ifstream file ("input.100.txt");) without having to specify the whole path.

Course material

Midterm practice.

The textbook for this course 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.

• 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;

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.

Miscellaneous

See the page on Opportunities for students.