Advanced concepts from data structures and general algorithms are discussed from both theoretical and applied viewpoints.   Topics covered include: multi-lists, graph theory, searching and sorting algorithms, and general n-way tree structures.   Techniques for analysis of algorithms for average and best/worst cases are presented.   Laboratory work may involve some programming in a high-level structured language.   Three lecture hours per week.   Not open to students who have received credit for CSC 385.
      Prerequisite:   CSC 260, MAT 220, and at least one of the following: CSC 311, CSC 320, CSC 325, CSC 340, CSC 390.

• CG1: to present a coherent view of the algorithms encountered in earlier courses;
• CG2: to introduce a selection of more advanced algorithms;
• CG3: to present the most common tools and techniques for assessing the costs and complexity of these algorithms.

• CO1: perform best case, worst case, and average case analysis of selected algorithms for managing lists, trees, heaps, and hash tables;
• CO2: explain and analyze examples of greedy algorithms, such as Huffman codes;
• CO3: explain and use the main ideas of probabilistic and amortized analysis;
• CO4: explain the analysis and use of breadth-first and depth-first search, minimum spanning trees, and shortest-path algorithms.

• brief review of course programming language (if any)
• mathematical tools for algorithm analysis
  • limits and big-O notation
  • summation formulas
  • recurrence relations
  • generating functions
• numeric algorithms (Fibonacci numbers, polynomial arithmetic, Fast Fourier Transform, etc.)
• analysis of searching and sorting algorithms
  • finding largest (or smallest), second largest, etc.
  • linear search, binary search
  • insertion sort, quicksort, merge sort, tree sort, heap sort
• multi-lists
• tree structures
  • general trees
  • n-way trees
  • balancing algorithms
  • traversal algorithms
  • expression trees
• review of basic hashing techniques
• advanced fast-access algorithms
• graphs, their representations, and traversal algorithms
• computational complexity, NP-completeness

      The primary emphasis of this course is on the understanding of a set of algorithms with wide-ranging applicability, together with their costs, advantages, and disadvantages.   Each algorithm is presented and discussed in detail, including classic analysis to determine best, average, and worst-case performance.   Implementation considerations will be touched on, along with proper solution development.   One or two algorithms may be assigned for implementation in programming projects, which will include analysis of time and space costs.   (Possible programming assignments: creation and evaluation of expression trees; balancing algorithms; breadth-first vs. depth-first graph traversal; hashing.)   There will be periodic written homework assignments on the major topics of the course.

The course grade will be determined using the following approximate weights: lab reports (if any) - 20%, written homework - 40%, final examination - 20%, other tests - 20%.

• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren.   Concrete Mathematics.   A Foundation for Computer Science.   Addison Wesley, 1989.

• Baase, Sara; Van Gelder, Allen.   Computer Algorithms. Introduction to Design and Analysis.   Third Edition.   Addison-Wesley, 2000.
• Berlioux, Pierre; Bizard, Philippe.   Algorithms: The Construction, Proof, and Analysis of Programs.   John Wiley, 1987.
• Knuth, Donald.   The Art of Computer Programming, Volume 1 (Third Edition) and Volume 3 (Second Edition)   Addison-Wesley,1997.
• Kronsjo, Lydia.   Algorithms: Their Complexity and Efficiency. Second Edition.   John Wiley, 1987.
• Manber, Udi.   Introduction to Algorithms:   A Creative Approach.   Addison-Wesley, 1989.
• Moret, B. M. E.; Shapiro, H. D.   Algorithms from P to NP.   Volume I: Design and Efficiency.   Benjamin/Cummings, 1991.
• Purdom, Paul Walton, Jr.; Brown, Cynthia A.   The Analysis of Algorithms.   Holt, Rinehart and Winston, 1985.
• Rawlins, Gregory J. E.   Compared to What?   An Introduction to the Analysis of Algorithms.   Computer Science Press [W. H. Freeman], 1992.
• Sedgewick, Robert.   Algorithms.   Second Edition.   Addison-Wesley, 1988.
• Sedgewick, Robert.   Algorithms in C.   Parts 1-4, Third Edition, 1998.   Part 5, Third Edition, 2001.   Addison Wesley.
• Smith, Jeffrey D.   Design and Analysis of Algorithms.   PWS-Kent, 1989.