CSE5311 Design and
Analysis of Algorithms
Dr.
Mohan Kumar
FALL
2009
Course
Syllabus and Details
Class
Notes
Exercise
Samples
Project. Click Here ! |
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. 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. Course Objectives
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. Course Prerequisites
Data Structures (CSE 2320) and Theoretical Concepts in
Computer Science and Engineering (CSE 3315) OR Equivalent. Mode of Teaching
The class meets twice a week (Mondays and Wednesdays 1:00 to
2:20pm). 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
sdiscussions. 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, 335 ELB Email: mkumar@uta.edu
Phone: (817) 272-3610 Class: Mon/Wed - 1:00 to 2:20 PM Office Hours: Mon/Wed - 2:30 to 4:00 PM
Course site: http://crystal.uta.edu/~kumar/cse5311_09FLDAA GTA: Arjun Dasgupta Office Hours: Tuesday
10:00 AM to 12:30 PM Email:: arjun
(dot) dasgupta (at) mavs (dot) uta (dot) edu 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. The students are
expected to refer to the books in the reference list, in addition to class
notes and posted material on the course page. References
ˇ 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 E Leiserson, R L Rivest and C Stein McGraw
Hill and MIT Press ˇ
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 16, 2009 Quiz 2 (10%): October 7, 2009 Quiz 3 (10%): October 26, 2009 Quiz 4 (10%): TBA Final Exam (25 %): December 07, 2009. Time : 11 am – 1 :30 pm. 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 September 15,
2009 and the expected date of Completion is November 30, 2009. 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
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
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. Statement
of Ethics
Please sign and submit the ethics form |