Dr. David W. Matula (Last update August 19 2000)
Download 24.23 Kb.
|
- Navigate this page:
- Prerequisites: CSE3353 and CSE 3358
- Reference
- II. Data Type Specification and Data Structure Implementation
- III. Algorithm Design Paradigms
- IV. Algorithm Implementation Project
- V. Computation Models and Introduction to Complexity
- Schedule: The following indicates the general schedule over 15 weeks. The specific times of the exams and due dates of the homeworks will be announced in the class.
- Topics Text Readings by Chapters or Sections Homework Set Number
- Fall 2000 Information: Class location: 0125C Day and Time: TTH 05:00PM-06:20 Tentative Exam Times
- FINAL EXAM Tuesday December 12 2000. (8:00AM to 11:00AM)
| Algorithm Engineering
Fall 2000 [Continually under revision] Dr. David W. Matula (Last update August 19 2000) 
Catalog Description: Methods for evaluating algorithm efficiency, data type specification, numeric representation and data structure implementation, algorithm design paradigms, fundamental algorithm case studies in sorting and searching, arithmetic and matrix computation, graphs and networks, computational geometry, introduction to problem complexity, survey of NP-complete problems. Reduction to practice: term project to design, test and validate, illustrate/animate and display results, and measure efficiency of an algorithm implementation. Prerequisites: CSE3353 and CSE 3358 (For non-majors: fluency in discrete mathematics and data structures) Current Textbooks: Introduction to Algorithms by Cormen, Leiserson and Rivest, McGraw-Hill, 1991, Computers and Intractability, by Garey and Johnson, Freeman, 1979 Reference: The Algorithm Design Manual by S.S.Skiena, Springer Telos, 1998 Instructor: David W. Matula Course Topics: I. Measuring Algorithm Efficiency (6 classroom hours): Implementation independent measurement of algorithm efficiency, time and space resources, growth in terms of input size, polynomial vs exponential growth algorithms, worst and average case efficiency, big Oh notation, algorithm efficiency vs inherent problem (any algorithm) complexity, decision trees, table lookup, popular algorithm notations, algorithm animation, deterministic and nondeterministic algorithms, algorithm analysis techniques, induction, recurrence equations, amortization, standards and implementation dependent resource measurement. II. Data Type Specification and Data Structure Implementation (9 classroom hours): Tools for algorithm design, abstract data types, selecting data structures, stacks, queues, priority queues, trees, heaps, hash tables, numeric representation, arrays and linked structures, data structure conversion and compression, data structure search and traversal, binary search, balanced data structures. III. Algorithm Design Paradigms (18 classroom hours): Characterization of algorithm design paradigms, greedy, dived-and-conquer, dynamic programming, backtracking, branch-and-bound, utilization of design paradigms for problems across application areas of sorting, selection, computer arithmetic and algebraic computation, graphs and networks, computational geometry. IV. Algorithm Implementation Project (6 classroom hours): Project description, specifying computational environments, data structure and algorithm selection, test problem design, illustration and algorithm animation, implementation validation, measuring implementation efficiency, result display. V. Computation Models and Introduction to Complexity (6 classroom hours): Topics from: Random access machines, parallel machines and algorithms, single-instruction multiple-data, multiple-instruction multiple-data, parallel sorting procedures, randomized algorithms, nondeterministic machines, the classes P and NP, NP-hard and NP-complete problems, reducibility, survey of NP-complete problems, parallel computation and NC.
Schedule: The following indicates the general schedule over 15 weeks. The specific times of the exams and due dates of the homeworks will be announced in the class. The following outlines text readings from Introduction to Algorithms that should accompany the topics covered in the course. There is considerable additional material in the text that can not be covered in class, so in many cases the readings are recommended simply to acquaint you with the material, and a light reading is all that is suggested. The classroom discussions and homework assignments will indicate the specific material to cover in more depth.
Fall 2000 Information: Class location: 0125C Day and Time: TTH 05:00PM-06:20 Tentative Exam Times: QUIZ (Background) Tuesday August 29 2000. EXAM I Thursday October 19 2000. FINAL EXAM Tuesday December 12 2000. (8:00AM to 11:00AM) Directory: cse cse -> Algorithms for Register Allocation Andrew Pardoe cse -> Fine-grained minimal overhead value-based core power gating on gpgpu cse -> Caroline M. Eastman cse -> Child sexual exploitation cse -> Applying the 12 Principles to 3d computer Animation The twelve principles of animation cse -> The History of Computer Gaming Osama Mazahir cse -> How to Jailbreak and Unlock Your iPhone by Dan Schointuch cse -> In 2013 / 2014 – Student Interns of Co-op Programme and Sandwich Programme for University Students cse -> Social Work Program Center for Student Excellence Advising Manual Table of Contents Information: Pages cse -> Bui,/Fernandez,/Tran pp 190: The History of Computing Download 24.23 Kb. Share with your friends:
|