Course Description:
This course applies design and analysis techniques to numeric and nonnumeric algorithms which act on data structures. Design is emphasized so that the student will be able to develop new algorithms. Analysis of algorithms is concerned with the resources an algorithm must use to reach a solution. Only theoretical techniques of analysis are covered. Topics include introduction to algorithm, proof techniques, recurrence relation, asymptotic complexity, sorting and searching, divide and conquer, greedy graph algorithms, dynamic programming, data compression, backtracking, branch and bound.
Course Objectives:
The main objective of this course is to make the student familiar with subjects concerning algorithm complexity. By the end of the semester, the student should be able to:
· Recognize the use of several design techniques (greedy, divide-and-conquer, dynamic programming) and use these methods to solve simple Problems.
· Design effective, efficient, elegant, and readable algorithms for various classes of computing problems.
· Write and solve recurrence relations for recursive algorithms.
· Determine asymptotic growth rates for algorithms.
· Prove correctness of simple algorithms.
Course Components:
· Review of material from CS 211
· Introduction to algorithm analysis and design
· Mathematical Tools in Analysis
- Proof Techniques
- Recurrence Relation
· Basic Algorithmic Analysis
- Best, average, worst case behaviors
- Time and Memory Complexity
· Algorithmic Strategies
- Divide-and-Conquer strategies
- Backtracking
- Heuristics
- Greedy algorithms
- Brute Force algorithms
- Branch-and-bound
· Sorting and Searching
· Graph Algorithms
· Geometric Algorithms
· NP-Completeness
Text book:
Michael T. Goodrich, Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons Inc 0-471-38365-1, 2002.
In addition to the above, the students will be provided with handouts by the lecturer.
Learning Outcomes:
· Knowledge and understanding
· Cognitive skills (thinking and analysis)
· Communication skills (personal and academic)
· Practical and subject specific skills (Transferable Skills)
Assessment Instruments
Makeup Policy
No missed tests without prior excuse. Each case will be handled separately based on its own merits. Makeup tests will be much more difficult than regularly scheduled tests. Each student is responsible for what is covered and assigned in any classes which they miss. Abuse of this policy will result in a loss of leniency.
(Note that this syllabus may change as the course progresses.)