CSE5311 Design and Analysis of Algorithms
Dr. Mohan Kumar
FALL 2010
Course Syllabus and Details
Course Description
Design and Analysis
of Algorithms is THE most important basic course in any graduate computer
science and engineering curriculum. It is vital for every computer science
student to be fluent with algorithms and their analysis. Typically, this course should be taken in the very first
semester of graduate study because algorithms are used in Networks, Operating
Systems, Databases, and other (including advanced) courses.
Course
Objectives
The principal
objective of this course is to build a solid foundation in algorithms and their
applications. Students completing this course are expected
to appreciate the importance of algorithms in other areas – for example routing
in networks, query processing in databases, collaboration in distributed
computing, efficient caching in operating systems etc.
Course
Prerequisites
Data
Structures (CSE 2320) and Theoretical Concepts in Computer Science and
Engineering (CSE 3315) OR Equivalent. Creative thinking, sound mathematical insight
and programming skills.
Mode of
Teaching
The
class meets twice a week (Tuesdays and Thursdays 3:30 to 4:50pm). Power point
slides and other lecture material will be used. At the end of each topic,
students must attempt to solve exercise problems. There will be no specific
text book for the class – the instructor will provide comprehensive notes and
references to relevant material. Exercise problems can be found on the course
web page and in reference books. All students are expected to work on these
problems and participate in the class discussions.
Algorithms are critical to your development as a
computer scientist, a researcher, a creative thinker and/or a problem solver.
This is a fundamental course - algorithms are extensively used in databases,
networks, artificial intelligence, bioinformatics, pervasive and mobile
computing, robotics, security, architecture, all engineering and science
disciplines, finance, management, music, biology and indeed in everyday life.
In this course you will be encouraged to think on your own and to discuss
solutions with your peers. The course is not limited to any programming
language. Students are strongly encouraged to use reference books and course
material provided by the professor.
Professor: Mohan Kumar, 335 ELB Email: mkumar@uta.edu Phone: (817) 272-3610
Class: NH 202; Tue/Thu - 7:00 – 8:20 PM; Office Hours: Thu - 2:00 to 5:00 PM;
Course site: http://crystal.uta.edu/~kumar/cse5311_10FLDAA GTA:
TBA
Course
Syllabus:
·
Review of Asymptotic Analysis and
Growth of Functions; Trees, Heaps, and Graphs; and Recurrences.
·
Greedy Algorithms: Minimum spanning
tree, Union-Find algorithms, Kruskal's Algorithm,
Clustering, Huffman Codes, and Multiphase greedy algorithms.
·
Dynamic Programming: Shortest paths, negative
cycles, matrix chain multiplications, sequence alignment, RNA secondary
structure, application examples.
·
Network Flow: Maximum flow problem,
Ford-Fulkerson algorithm, augmenting paths, Bipartite matching problem,
disjoint paths and application problems.
·
NP and Computational tractability:
Polynomial time reductions; The Satisfiability problem;
NP-Complete problems; and Extending limits of tractability.
·
Approximation Algorithms, Local
Search and Randomized Algorithms
·
Applications of Algorithms, sample
examples
Text book
There is no specified text book for this course. There are several good quality
books. However, the recommended reference book for a graduate course in
algorithms is “Algorithm Design by Kleinberg and Tardos”.
Detailed course material and exercises will be available on the course page
before the beginning of Fall semester. Students are also expected to refer books
from the list below.
References
·
Class Notes, Power point slides, and
Exercise Problems
·
Algorithm Design
o Jon Kleinberg and Éva Tardos, Pearson Addison-Wesley, 2004.
·
The Design and Analysis of Algorithms
1974
o AV Aho, JE Hopcroft and JD Ullman, Addison-Wesley Publishing Company
·
Introduction to Algorithms: A
Creative Approach, Reprinted 1989
o Udi Manber, Addison-Wesley Publishing Company
·
Introduction to Algorithms, Second
Edition, 2001
o T Cormen, C
·
Graph Algorithms, 1979
o Shimon
Even, Computer Science Press
·
Introduction to the Theory of
Computation, 1992
o Michael
Sipser, PWS Publishing Company
·
The Art of Computer Programming,
Vols. 1 and 3
o Knuth,
Addison Wesley Publishing Company
Assessment
Quizzes and class
participation: 40%
The structure of the
quizzes will be discussed in class, at least one week prior to the quiz.
Quiz 1 (10%): September 9, 2010
Quiz 2 (10%): September 23, 2010
Quiz 3 (10%): October 07, 2010
Quiz 4 (10%): October 28, 2010
Final Exam (30%): December 02, 2010.
Lab Assignment: 30%
Quizzes are of 60 minutes and the Final Exam is of 2 hours duration.
Lab
Assignment:
Assignment problems
will be handed out by September 15, 2010 and the expected date of Completion is
November 30, 2010. The students will be required to write programs and run
experiments.
Homework
Assignments: No
Grades awarded directly!
Class participation: ACTIVE Participation will prepare you well for
Quizzes and Exams Students are expected to interact actively during lectures.
All students are expected to solve homework problems and discuss solutions in
the class.
Missed
Exams, Quizzes, and Makeup Work
Talk to the
instructor if you miss an exam or quiz due to unavoidable circumstances (e.g.,
health).
Attendance
and Drop Policy
Attendance though
not mandatory, is HIGHLY encouraged. Class participation is important to your
grade in the 'Quizzes and Class Participation' component.
Please visit course
page for details on Americans with Disabilities
Act, Academic Dishonesty and Student Support Services.