CS
583 Fall 2013
Analysis of Algorithms I
Lecture time: Wednesday 7:20 pm - 10:00 pm
Location: Robinson Hall B203
Course webpage: http://www.cs.gmu.edu/~lifei/teaching/cs583-fall13
Credit: 3
Instructor: Fei Li, Room 5326, Engineering Building, email:
mailto:lifei@cs.gmu.edu
Office hours: Wednesday 5:00pm – 7:00pm
Teaching assistant: Yue Ning, Engineering Building, email: mailto:yning@gmu.edu
Office hours: Fridays 1:00pm – 3:00pm
News:
Course overview:
In
this course, a thorough examination of several well-known techniques that are
used for the design and analysis of algorithms will be covered. Topics to be
covered include theoretical measures of algorithm complexity, sorting and
selection algorithms, greedy algorithms, divide and conquer techniques, dynamic
programming, graph algorithms, search strategies, and an introduction to the
theory of NP-completeness. Additional topics may be covered if time permits.
Students are expected to have taken prior undergraduate courses in data
structures, as well as calculus and discrete mathematics.
Prerequisites:
CS 310 and CS 330
Calculus (MATH 113, 114, 213) and MATH 125. Please contact with the instructor if you are not
sure.
Textbook:
Introduction
to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C.
Stein, 3rd Edition (2009)
Course materials:
Lecture
|
Date
|
Topic
|
Lecture notes
|
Scope
|
Assignments
|
Note
|
1
|
August
28
|
Introduction
|
Introduction
|
Appendix
A
Chapter
10 (read it by yourself)
|
|
|
2
|
September
4
|
Divide
and Conquer
|
|
|
|
|
3
|
September
11
|
Probabilistic
Analysis
|
|
|
|
|
4
|
September
18
|
Sorting
|
|
|
|
|
5
|
September
25
|
Search
|
|
|
|
|
6
|
October
2
|
Review
|
|
|
|
|
7
Midterm Exam
|
October
9
|
|
|
|
|
|
8
|
October
16
|
Dynamic
Programming
|
|
|
|
|
9
|
October
23
|
Dynamic Programming
|
|
|
|
|
10
|
October
30
|
Greedy
Algorithms
|
|
|
|
|
11
|
November
6
|
Amortized
Analysis
|
|
|
|
|
12
|
November
13
|
Graph
Traversals
Minimum
Spanning Tree
|
|
|
|
|
13
|
November
20
|
Shortest
Path
|
|
|
|
|
Thanksgiving recess
|
November
27
|
|
|
|
|
|
14
|
December
4
|
Maximum
Flow
Review
|
|
|
|
|
Final exam
|
December
11
7:30pm
– 10:15pm
|
|
|
|
|
|
Topics:
In this course, we will consider the algorithm
design and analysis techniques of various problems coming from the
following areas:
·
Function growth: O, theta, omega notation
(CLRS 3)
·
Recurrence relations (CLRS 4)
·
Probabilistic analysis; randomized algorithms
(CLRS 5)
·
Amortized analysis (CLRS 17)
·
Dynamic programming (CLRS 15)
·
Greedy algorithms (CLRS 16.1-3)
·
Sorting: heapsort,
quicksort, mergesort (CLRS 2, 6, 7)
·
Non-comparison-based (CLRS 8)
·
Selection/order statistics (CLRS 9)
·
Data structures balanced binary search trees
(CLRS 12, 13)
·
Graph algorithms: BFS/DFS (CLRS 22)
·
Minimum spanning tree (CLRS 23)
·
Shortest paths (CLRS 24, 25)
· Maximum
flow (CLRS 26.1-3)
· Time
complexity, NP-Complete (CLRS 34)
Course outcomes:
·
An understanding of classical problems in Computer
Science
·
An understanding of classical algorithm design and
analysis strategies
·
An ability to analyze the computability of a problem
·
Be able to design and analyze new algorithms to
solve a computational problem
·
An ability to reason algorithmically
Tentative grading:
·
Midterm Exam
(30%)
·
Final Exam (40%)
·
Assignments
(30%)
·
No make-up exams
for missed tests.
·
No late
assignments graded.
Policies:
Hand in hard copies of assignments in class. 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.
Academic honesty:
The integrity of the University community is
affected by the individual choices made by each of us. GMU has an Honor Code
with clear guidelines regarding academic integrity. Three fundamental and
rather simple principles to follow at all times are that: (1) all work
submitted be your own; (2) when using the work or ideas of others, including
fellow students, give full credit through accurate citations; and (3) if you
are uncertain about the ground rules on a particular assignment, ask for
clarification. No grade is important enough to justify academic
misconduct.
Plagiarism means using the exact words, opinions, or factual information from
another person without giving the person credit. Writers give credit through
accepted documentation styles, such as parenthetical citation, footnotes, or
endnotes. Paraphrased material must also be cited, using MLA or APA format. A
simple listing of books or articles is not sufficient. Plagiarism is the
equivalent of intellectual robbery and cannot be tolerated in the academic
setting. If you have any doubts about what constitutes plagiarism, please see
me.
Disability statement:
If you have a learning or physical difference that
may affect your academic work, you will need to furnish appropriate
documentation to the Disability Resource Center. If you qualify for
accommodation, the DRC staff will give you a form detailing appropriate
accommodations for your instructor.
In addition to providing
your professors with the appropriate form, please take the initiative to
discuss accommodation with them at the beginning of the semester and as needed
during the term. Because of the range of learning differences, faculty members
need to learn from you the most effective ways to assist you. If you have
contacted the Disability Resource Center and are waiting to hear from a
counselor, please tell me.