CS421 - Advanced Data Structures and Algorithm Development SYLLABUS

Number and Title of Course:CS421 - Advanced Data Structures and Algorithm Development

Instructor(s): Dr. Wayne Summers
Office: SCA207B Office phone: (505) 454-3230 Department phone: (505) 454-3295
Office Hours: MWF 1:00-1:50 TR 4-4:50; via e-mail, net-meetings and by appointment
e-mail address: summers_wayne@ColumbusState.edu
homepage:http://csc.ColumbusState.edu/summers

Catalog Description of Course: The investigation of computer data structures with an emphasis on the design and development of efficient algorithms for solving a wide variety of common computing problems. The course also covers the analysis and measurement of the performance of algorithms.

Course Prerequisite: Grade of at least a "C" in CS345 and CS350 and Math 317.

Required Textbook(s):

1) Compared to What? An Introduction to the Analysis of Algorithms by Gregory Rawlins, Computer Science Press, 1992, ISBN 0-7167-8243-X.

Educational Outcomes

Students should be able to analyze algorithms, in terms of time and space complexity.
Students should understand and be able to use sorting, selection, and searching algorithms.
Students should be able to able to apply problem solving techniques, such as divide-and-conquer, the greedy algorithm, and dynamic programming.
Students should understand several advanced data structures and their algorithms including graphs and trees.
Students should understand parallel algorithms.
Students should understand the unfeasibility of some problems (NP-complete & NP-hard).
Students should be able to apply analytic skills to solve new algorithmic problems.
Students should be able to compare algorithms that solve the same problem.
Students should be able to determine inefficiencies in algorithms and how to optimize them.
Students should be able to determine whether a problem has an algorithmic solution.

Major Topics

Solving Problems
Searching Algorithms
Selecting Algorithms
Sorting Algorithms
Graphs
Numbers
Infeasibility

Instructional Methods and Techniques

Students and the instructor will share their experiences of creating and solving new algorithms. Some of these will be developed by the class as a whole and students will be expected to present an analysis of the solutions. Class participation is necessary.

Assignments for Course

Readings from the book and outside materials including the WWW.
Homework exercises and problems from the textbook and outside readings.
Exams cover material from the text. The lectures may not cover all the material in the textbooks and may be supplemented by additional materials. Late assignments will be subject to up to a 25% deduction in points per day. No credit will be given for assignments that are more than one week late.

Evaluation

Homework Exercises and Problems - 200 - 300 pts.
Class participation - 50 pts.
3 Tests (100 pts. each) - 300 pts.
Final Exam - 200 pts.

Grading Scale (Approximate):

A 90 - 100%

B 80 - 89%

C 70 - 79%

D 60 - 69%

F 0 - 59%

SCHEDULE

	Lecture Topic	Homework
Week 1:	Appendix A - Mathematical Background 1.1 - Problems 1.2 - Models 1.3 - Algorithms 1.4 - Analysis	Week 1 Assignment
Week 2:	1.5 - Now What? 1.6 - Napkin Mathematics Appendix B - Manipulating Order Notation 1.7 - Growth Rates	Week 2 Assignment
Week 3:	1.8 - Back to Reality 1.9 - Hard Problems 1.10 - Coda - The Continent of Analysis	Week 3 Assignment
Week 4:	2.1 - Linear Search 2.2 - Jump Search Appendix C - Recurrences 2.3 - Binary Search 2.4 - Changing the Model
Week 5:	2.5 - Coda - Apples and Oranges Review Test I 3.1 - Rankings 3.2 - Finding the Best
Week 6:	3.3 - Finding the Second Best 3.4 - Finding the Best and the Worst 3.5 - Finding the ith Best 3.6 - The Partition Problem
Week 7:	3.7 - Changing the Model 3.8 - Coda - Artists and Artisans 4.1 - Strategies 4.2 - Swap Sorts 4.3 - Insert Sorts 4.4 - Select Sorts
Week 8:	4.5 - Merge Sorts 4.6 - Split Sorts 4.7 - Lower Bound on Sorting 4.8 - Optimal Sorting 4.9 - Changing the Model 4.10 - Coda - Sorting Out
SPRING BREAK	HAVE FUN
Week 9:	Review Test II 5.1 - Structures
Week 10:	5.2 - Queues and Partitions 5.3 - Connecting Telephones 5.4 - Partially Sorted 5.5 - Exploring Graphs 5.6 - Broadcasting Information
Week 11:	5.7 - Distributing Flow 5.8 - Coda -- Graph Therapy 6.1 - Exponential Numbers 6.2 - Common Numbers Good Friday
Week 12:	Easter Monday 6.3 - Prime Numbers 6.4 - Secret Numbers 6.5 - Authentic Numbers
Week 13:	6.6 - Random Numbers 6.8 - Coda -- Straight On Till Morning Review Test III
Week 14:	7.1 - Remembrance of Times Past 7.2 - Models of Computation 7.3 - Turing Machines 7.4 - Birth of NP-Completeness 7.5 - Working out the Hierarchy
Week 15:	7.6 - Solving Hard Problems 7.7 - What is an Algorithm? 7.8 - What is a Proof? 7.9 - Coda -- The End of the Beginning Review
Week 16:	FINAL EXAMS	Monday, May 3, 1999 - 6 p.m.