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

Tentative Grading:

• Biweekly assignments (40%)
• Midterm Exam (25%)
• Final Exam (35%)

Policies:

Assignments will normally be given out on Thursdays every two weeks. You are given two weeks to finish them unless for special notice. Hand in hard copies in class.

One late submission (up to one week past the due date) per person per semester is permitted. Send an email to the TA when you plan to use it.

Please note that all coursework is to be done independently. Plagiarizing the homework will be penalized by maximum negative credit and cheating on the exam will earn you an F in the course. See the GMU Honor Code System and Policies at http://www.gmu.edu/catalog/acadpol.html and http://www.cs.gmu.edu/honor-code.html. You are encouraged to discuss the material BEFORE you do the assignment. As a part of the interaction you can discuss a meaning of the question or possible ways of approaching the solution. The homework should be written strictly by yourself. In case your solution is based on the important idea of someone else please acknowledge that in your solution, to avoid any accusations.

You are allowed to take two pages of notes to the midterm and final exams, which will be handed in with the exam.