CPSC 5115            Algorithm Analysis and Design
Topics Covered                                        Fall 2007

1.    Thursday, August 16
        Introduction to the Course
        Overview of Computational Complexity        HTML Version MS-Word Version
        Audio of Lecture        WMA File

2.    Tuesday, August 21
        Chapter 1:   Introduction to Algorithms
        Lecture slides by the textbook author:        PowerPoint Slides
        Sudoku puzzle that was discussed:            HTML Version MS-Word Version
        Audio of Lecture        WMA File    (I forgot to turn off the recorder -
                                                  some "empty space" at the end).

3.    Thursday, August 23
        Chapter 2:    Analysis of Algorithm Efficiency
        Lecture slides by the textbook author        PowerPoint Slides
        Audio of the Lecture    WMA File
        Homework set 1 is assigned and due 8/30    HTML Version MS-Word Version

4.    Tuesday, August 28
        Chapter 2: Analysis of Algorithm Efficiency (continued)
        Lecture slides by the textbook author           PowerPoint Slides
        Audio of the Lecture        WMA File

5.    Thursday, August 30
        Chapter 3: Brute Force as a Design Strategy
        Lecture slides by the textbook author        PowerPoint Slides
        Audio of the Lecture    WMA File        NOTE: It terminates abruptly, but is essentially complete.
        Homework set 2 is assigned and due 9/13        HTML Version MS-Word Version

6.    Tuesday, September 4
        Chapter 3: Brute Force (Continued)
        This lecture covers two standard problems (TSP and Knapsack)
            as well as two others (an Alphametic and "Dogs, Cats, and Mice")
        Audio of the Lecture    WMA File

7.    Thursday, September 6
        Chapter 4: Divide and Conquer: Mergesort, Quicksort, etc.
        Lecture slides - by the textbook author    PowerPoint Slides
        Audio of the Lecture        WMA File

8.     Tuesday, September 11
        Chapter 5: Review of Graph Theory
           Audio of the Lecture        WMA File

9.     Thursday, September 13
Chapter 5: Decrease and Conquer
          Lecture slides by the textbook author        PowerPoint Slides
         Audio of the Lecture        WMA File

10.    Tuesday, September 18
        Chapter 5: Depth-First Search
        Lecture slides by the textbook author        PowerPoint Slides
        Audio of the Lecture        WMA File

11.    Thursday, September 20
        Chapter 5: Breadth-First Search
        Lecture slides by the textbook author     PowerPoint Slides
        Audio of the Lecture        WMA File

12.    Tuesday, September 25
          Review for the Mid-Term Exam
          The Mid-Term Exam is handed out:   
          Audio of the Lecture    WMA File

13.    Thursday, September 27
          Directed Graphs and Topological Sort
          Audio of the Lecture    WMA File

14.    Tuesday, October 2
          The mid-term exam must be returned to me by 9:30 PM this day.
           Matrix Mathematics and Solutions to Linear Equations
           Lecture slides by the textbook author    PowerPoint Slides
        Audio of the Lecture        WMA File

15.     Thursday, October 4
           Discuss the mid-term exam. 
            Audio of the Lecture     WMA File

16.    Tuesday, October 9
            Presorting as a Design Strategy
            Audio of the Lecture    WMA File

            Thursday, October 11   NO CLASS.  THIS IS FALL BREAK.

17.    Tuesday, October 16
          Heaps and Heapsort
          Lecture slides by the textbook author    PowerPoint Slides
         Audio of the Lecture        WMA File

18.    Thursday, October 18
        String Matching: Horspool's Algorithm
        Lecture Slides by the textbook author    PowerPoint Slides
        Audio of the Lecture        WMA File

19.    Tuesday, October 23
         Hashing: Open and Closed
          Lecture slides by the textbook author    PowerPoint Slides
        Audio of the Lecture        WMA File

20.    Thursday, October 25
        B Trees and B+ Trees
        Computation of Fibonacci Numbers
        Audio of the Lecture        WMA File

21.    Tuesday, October 30
Warshall's Algorithm and Transitive Closure
        Lecture Slides by the Textbook Author        PowerPoint Slides
        Audio of the Lecture        WMA File

22.    Thursday, November 1
        Floyd's Algorithm
        Lecture Slides by the Textbook Author    PowerPoint Slides
        Audio of the Lecture        WMA File

23.   Tuesday, November 6
        An Introduction to the Greedy Method
        Prim's Algorithm for Generating a MST
        Lecture Slides by the Textbook Author    PowerPoint Slides
        Audio of the Lecture        WMA File

24.    Thursday, November 8
         Backtracking and the Knapsack Problem
        Audio of the Lecture        WMA File
        Homework set 4 is assigned and due on November 16        HTML Version  MS-Word Version

25.    Tuesday, November 13
        Backtracking and the N-Queens Problem
        Audio of the Lecture    WMA File

26.    Thursday, November 15
        Branch and Bound and the Assignment Problem
        Audio of the Lecture    WMA File

27.    Tuesday, November 20
          Lower Bound Theory
          Audio of the Lecture        WMA File    DVF File MP3 File

            Thursday, November 22    NO CLASS. It is Thanksgiving Day!

28.    Tuesday, November 27
          Solution of Non-Linear Equations
         Audio of the Lecture        WMA File

29.    Thursday, November 29
         Introduction to Finite Automata
        Audio of the Lecture        WMA File

30.    Tuesday, December 4
        Finite Automata and Grammars
        Audio of the Lecture        WMA File