January 13 (Tue), 2004 HW1 assigned: exercises 1.1.1, 1.1.4, 1.1.5, 1.1.6, 1.1.7, 1.1.8. Questionnaire, with discussion; syllabus and grading policy handed out. Informal definition of algorithm. A little history: Al-Khawarizmi. Computing the greatest common divisor. Euclid's algorithm for computing the GCD. The sieve of Erathostenes.
January 15 (Thu), 2004 NOTE: HW1 due date changed to Thursday, January 23. Termination and correctness of Euclid's algorithm (proved), with several variations. Algorithm design techniques: list. Sorting. Insertion sorting. Efficiency of insertion sorting (briefly).
January 20 (Tue), 2004 HW2 assigned: exercises 1.2.1, 1.2.2, 1.3.1, 1.3.4, 1.3.7, 1.4.4, 1.4.6, due Thursday, January 29. Good Q&A on HW1 issues, especially related to Euclid's algorithm. Discussion of issues related to HW2: sorting, graphs.
January 22 (Thu), 2004 HW1 collected. Free trees, rooted trees, binary trees. Geometric progressions. Exercise 1.4.6 done in class (bounds on height w.r.t. number of nodes). Induction, Peano's first-order induction schema, and strong induction.
January 27 (Tue), 2004 Lesson canceled due to University closing, due to inclement weather.
January 29 (Thu), 2004 HW2 collected. Several questions on exercises, especially 1.3.7. Correctness of recursive programs by using induction. Examples: factorial and binary search.
February 3 (Tue), 2004 Correctness of iterative programs: the method of loop invariants. Example: multiplication by repeated sums. Another example of proof of correctness of recursive programs: computation of a power function.
February 5 (Thu), 2004 HW1 returned. HW3 assigned: all 10 exercises from section 2.1 of the textbook, due Thursday, February 12, 2004. Example of proof of correctness of an iterative algorithm: the linear algorithm for computing the maximum contiguous subvector (MCG). Introduction to (time) complexity analysis: cubic, quadratic, nlogn, and linear algorithms for MCG. Dependence of input size on available time to run.
February 10 (Tue), 2004 More on the MCG algorithms. General issues related to analysis of algorithms: correctness and complexity; characteristic (basic) operations, with examples; problems and problem instances; lower bounds (of the complexity of problems) and upper bounds (of the complexity of algorithms), as a function of problem input (parameter(s)).
February 12 (Thu), 2004 Lower bounds. Lower bounds for finding the minimum in an unsorted list (using comparison as a characteristic operation and the size of the list as input size) and for MCG (using array access as characteristic operation and the size of the array as input size). Observation that lower bound matches upper bound for MCG. Example of problem for which lower and upper bound do not match: matrix multiplication. Analysis of correctness and time complexity of selection sort, including setting up a recurrence relation, attempting its solution by forward substitution, and solving it by backwards substitution, and checking the solution (inductively) by direct replacement.
February 17 (Tue), 2004 HW3 collected. Q&A concerning exam. Proof of correctness of iterative linear search algorithm.
February 19 (Thu), 2004 MT1.
February 24 (Tue), 2004 MT1 post-mortem. HW4 assigned, due Thursday.
February 26 (Thu), 2004 HW5 assigned: all exercises in section 2.2, due on Thursday, March 4. Big-Oh notation.
March 2 (Tue), 2004 More on complexity. Fibonacci numbers.
March 4 (Thu), 2004 HW5 delayed to Tuesday, March 16 HW6 assigned, due Tuesday, March 23: Exercises 2.3.1, 2.3.2, 2.3.3, 2.4.1, 2.4.3, 2.4.4, 2.4.5, 2.5.2, 2.5.3, 2.5.4. Average-case complexity. Example: sequential search.
March 16 (Tue), 2004 HW5 collected. Towers of Hanoi: state-space representation; problem reduction representation and algorithm. BinRec algorithm. Smoothness rule. Master theorem for some divide-and-conquer recurrences.
March 18 (Thu), 2004 Introduction to divide-and-conquer. Master theorem, again. Summing n numbers by divide-and-conquer. Mergesort.
March 23 (Tue), 2004 HW6 collected. Mergesort recurrence. Quicksort.
March 25 (Thu), 2004 Quicksort: average case.
March 30 (Tue), 2004 HW7 assigned, due April 6 (in one week): Exercises 4.1.5, 4.1.6, 4.1.9, 4.2.1, 4.2.3, 4.2.5, 4.2.6, 4.2.8. Correction of parts of HW5. Quicksort: improvements: median of three, use of insertion sort for small subfiles, elimination (or: programmer-based control) of recursion, processing small subfiles first. Quickhull. Strassen's method: basics.
April 1 (Thu), 2004 HW5 returned. Correction of (most of) HW5. Some Q&A. This took longer than planned. See http://www.cse.sc.edu/~mgv/csce350sp04/hw/hw7Notes for some comments on HW7, which is due on Tuesday, April 6. (An email was sent to the csce350-001 mailing list.)
April 6 (Tue), 2004 Class canceled due to medical emergency. HW7 will be collected on Thursday.
April 8 (Thu), 2004 HW7 collected. Strassen's algorithm in detail, with analysis for multiplications and additions/subtractions. Linear time selection, in broad outline.
April 13 (Tue), 2004 MT2 will be on Tuesday, April 20. Heaps.
April 15 (Thu), 2004 More heaps, with analysis.
April 20 (Tue), 2004 MT2.
April 22 (Thu), 2004 HW8 assigned, due Wednesday, April 28, at midnight: 6.4.6, 9.1.1, 9.1.6, 9.3.2. Heapsort, Prim's algorithm for minimum spanning trees.
April 20 (Tue), 2004 HW8 due date changed to Thursday, April 30, at 9:30am. Review session will be Thursday, April 30, at 9:30am in 2A21 (the classroom). Dijkstra's algorithm for the (single source) shortest path problem (handout). Argument that any such algorithm must expand every node that is closer to the source node than the goal node is. Kruskal's algorithm for the MST problem. Evaluation.