CSC 320 - Algorithms
2007 Spring Semester

A systematic study of algorithms and their complexity, including searching and sorting algorithms, mathematical algorithms, scheduling algorithms, tree and graph traversal algorithms, P, NP, NP-complete and intractable problems. This course satisfies both the critical thinking and the quantitative reasoning requirements.

Essential Information:

Instructor: 

Noel Petit

E-mail: 

petit@augsburg.edu

Office: 

Sverdrup 203D

Phone: 

(612) 330-1061

Class: 

MWF 1:20 – 2:20 PM Sverdrup 202

Dates: 

Beginning 17 Jan 2007 ending 27 April 2007

Text: 

Introduction to Algorithms (2nd Edition); Cormen, Leiserson, Rivest & Stein

FTP site for book's disk and other material is ftp://xspace.augsburg.edu/CSC/CSC320

Office Hours: 

TBA

 

Syllabus

Date               Topic                                       Chapter             Problems (P)

                                                                                                Exercises (E)

17 Jan            Intro                                        1                                                                      

19 Jan            Heapsort                                  6                       (P) 1-1

22 Jan            Quicksort                                7                       (E) 6.1-1 thru 6.1-5

24 Jan            Getting Started                        2                       Java Heap and Quick Sort

26 Jan            Still Starting                            2                       (P) 2-1                                                

29 Jan            Growth of Functions               3                       (P) 2-2, 2-3

31 Jan            More Growth                          3                       (P) 3-1 , Java Insertion Sort

2 Feb              Recurrences                             4                       (P) 3-2 and 3-3

5 Feb              Reccurences again                   4                       (E) 4.1-1 and 4.1-2

7 Feb              Quicksort continued                7                       (E) 4.2-1 and 4.2-2

9 Feb              Linear Time Sorts                    8                       (E) 7.1-3 and 7.4-2

12 Feb           Quiz I                                                               1-8                                                                  

14 Feb            Data Structures                        10                     (E) 8.2-1, 8.3-1

16 Feb            Data Structures                        10                     (E) 10.1-4

19 Feb            Hash Tables                            11                     (E) 10.2-2 and 10.2-3

21 Feb            Hash Tables                            11                     (E) 11.2-2

23 Feb            Binary Search Trees                12                     (E) 11. 3-1

26 Feb            Binary Search Trees                12                     (E) 12.1-3, 12.2-2

28 Feb            Dynamic Programming           15                     (E) 12.3-1

2 Mar             Dynamic Programming           15                     (E) 15.1-1

5 Mar             Greedy Algorithms                 16                     (E) 15.3-2

7 Mar             Greedy Algorithms                 16                     (E) 16.1-1, 16.2-2

9 Mar             B Trees                                    18                     (E) 16.3-2, (P) 16-1               

12 Mar           Binomial Heaps                       19                     (P) 18-1

14 Mar          Quiz II

16 Mar           Intro to Graphs                        22                    

17 -  25 Mar – Mid Term Break

26 Mar           Elementary Graphs                  22                     (E) 22.1-2, 22.2-1

28 Mar           Minimum Spanning Tree        23                     (E) 22.3-1, 22.3-2

30 Mar           Shortest Path                           24                     Bellman-Ford Shortest Path in Java

2 Apr             Shortest Path                           24                     Dykstra Shortest Path in Java

4 Apr             Shortest Path Max Flow         25, 26               (E) 25.1-1 in Java

6 Apr             Sorting Networks                    27                     (E) 25.2-1 in Java

9 Apr             Matrix Operations                   28                     Ford-Fulkerson Flow in Java on Fig 26.3a

11 Apr           Linear Programming               29                     1) Strassen Algorithm in Java

                                                                                                2) Linear Equation Solution in Java

                                                                                                3) Matrix Inversion in Java    

13 Apr           Fast Fourier Transform           30                     (E) 29.3-4 or 5 or 6 in Java

16 Apr           Number Theory                       31                     (E) 30.3-1 in Java

18 Apr           String Matching                      32                     RSA Key Generation in Java

20 Apr           Computational Geometry        33                     KMP String Matcher in Java

23 Apr           NP Completeness                    34                     Convex Hull by Graham or Jarvis in Java

25 Apr           NP Completeness                    34                     Circuit Satisfiability, Clique or Hamiltonian Cycle in Java

27 Apr           Approximations                      35                     Traveling Salesman (Brute and Approximate) in Java

30 Apr – 4 May – Finals Week