CS 483 Fall 2007
Data Structure and Analysis of Algorithms

Lecture Time: Tuesday and Thursday 3:00-4:15pm
Location: Robinson Hall B102
Course webpage:http://www.cs.gmu.edu/~lifei/teaching/cs483_fall07/
Credit:3

Instructor: Fei Li, Office 443 ST II, email: lifei@cs.gmu.edu
Office hours: Tuesday and Thursday 4:30-5:30pm

Teaching Assistant: Yanyan Lu, Room 365 ST II, email: ylu4@gmu.edu
Office hours: Wednesday and Friday 4:00-5:00pm

Course overview:
In this course, we will analyze computational resources for important problem types by alternative algorithms and their associated data structure; using mathematically rigorious techniques. We will analyze specific algorithms and their improvements. The course present the fundamentals about basic and useful algorithms. We will discuss how to design algorithms, how to prove their correctness, how to measure their performance (in terms of time and space), and how to improve their performance if possible.
Prerequisites:
CS 310 and CS 330 Calculus (MATH 113, 114, 213) and MATH 125. Please contact with the instructor if you are not sure.
Required Textbook:
Introduction to the Design and Analysis of Algorithms by Anany Levitin , Addison Wesley; 2nd edition (2007)
Topics:
In this course, we will consider the algorithm design and alaysis techniques of various problems coming from the following areas:

• Introduction fundamentals, problem types
• Analysis of Algorithm Efficiency asymptotic notation, recursive and non-recursive algorithms
• Brute Force sorting, searching, convex hull
• Divide (decrease) and Conquer merge sort, quicksort, binary search, convex hull, insertion sort, BFS and DFS, topological sorting
• Transform and Conquer balanced search trees, heapsort, problem reduction
• Greedy Techniques minimum spanning tree, shortest path, Huffman tree
• Dynamic Programming All-pairs shortest path, knapsack problem
• Iterative Improvement simplex method, matching
• Limitations of Algorithm Power and Coping with Limitations decision trees, P, NP, backtracking, branch-and-bound, approximation