CSE5311 Design and
Analysis of Algorithms
Dr. Mohan Kumar
FALL 2009
Course Syllabus
and Details
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. ALGORITHMS ARE FUN; ALGORITHM ANALYSIS is a NECESSARY TOOL; Students
are encouraged to solve homework problems and discuss/solve problems in the
class. Each student will be given one specific algorithm or problem to carry
out an in-depth study. Typically, this course should be
taken in the very first semester of your graduate study because algorithms are
used in Networks, Operating Systems, Databases, and other (including advanced)
courses.
The
objective of this course is to build a solid foundation of the most important
fundamental subject in computer science. Creative thinking is essential to
algorithm design. Algorithm analysis and verification demands sound
mathematical acumen and programming skills.
Data
Structures (CSE 2320) and Theoretical Concepts in Computer Science and
Engineering (CSE 3315) OR Equivalent.
The
class meets twice a week (Mondays and Wednesdays
The course on Algorithms is 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 that will be available and updated from time to time on the course
page.
Instructor: Mohan Kumar, 333 NH Email: mkumar@uta.edu
Phone: (817) 272-3610
Class:
Mon/Wed - 1:00 to 2:20 PM Office Hours:
Mon/Wed -
Course site: http://crystal.uta.edu/~kumar/cse5311_09FLDAA GTA:
TBA
·
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
There is no specified text book for this course. The students are however
expected to refer to the books in the reference list.
·
Algorithm Design
o
Jon Kleinberg
and Éva Tardos, Pearson
Addison-Wesley, ISBN
·
Class Notes, Power point slides, and Exercise Problems
·
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
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, 2009
Quiz 2 (10%): September 23, 2009
Quiz 3 (10%): October 07, 2009
Quiz 4 (10%):
Final Exam (25 %):
Quizzes 1 thru 4 are
of duration 30 minutes and the Final Exam is of duration 2 hours.
Lab Assignment:
Assignment problems
will be handed out by
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.
Do NOT ask for make
up exams or other components if you missed an exam or a project due to travel
(except when you are required to travel to represent the university or the
department). Meet with the instructor if you miss an exam or quiz due to
unavoidable circumstances (e.g., health).
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.