**CSE5311 Design and Analysis of Algorithms**

*Dr. Mohan Kumar*

**SPRING 2013**

__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 including 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 5:00 am to 6:20pm). Power
point slides and other lecture material will be available on Blackboard. Whiteboard
will be used in all classes. At the end of each topic, students must attempt to
solve exercise problems. Solutions to exercise and homework problems will be
discussed in class. Solutions may not be provided in electronic form. The
instructor will provide comprehensive notes and references to relevant
material. Exercise problems can be found on the course web page, in the text
book and in reference books. Solutions to problems will be discussed in class
or in meetings with the instructor/GTA. All students are expected to work on
these problems and participate in the class discussions. The Midterm and final
exams will be ** open-notes**; all notes MUST be handwritten by the individual
student. Exceptions will be made for persons with special abilities and
requirements (please contact the instructor for more details).

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; 559 ERB;**Email**:
mkumar@uta.edu;**Phone**: (817) 272-3610

**Class**: TBA; Tue/Thu - 5:00 PM - 6:20 PM;**Office**** Hours: **Thursdays 2:00 to 4:30 PM;

**Course site**: http://ranger.uta.edu/~kumar/CSE5311_SP13

**GTA**:
TBA

**Course
Syllabus****:**

o Review of Asymptotic Analysis
and Growth of Functions; Trees, Heaps, and Graphs; and Recurrences.

o Greedy Algorithms: Minimum
spanning tree, Union-Find algorithms, Kruskal's
Algorithm, Clustering, Huffman Codes, and Multiphase greedy algorithms.

o Dynamic Programming: Shortest
paths, negative cycles, matrix chain multiplications, sequence alignment, RNA
secondary structure, application examples.

o Network Flow: Maximum flow
problem, Ford-Fulkerson algorithm, augmenting paths, Bipartite matching
problem, disjoint paths and application problems.

o NP and Computational tractability:
Polynomial time reductions; The Satisfiability
problem; NP-Complete problems; and Extending limits of tractability.

o Approximation Algorithms,
Local Search and Randomized Algorithms

o Applications of Algorithms,
sample examples

**Text book
**

o Algorithm Design

o Jon Kleinberg and Eva Tardos,
Pearson Addison-Wesley, 2004 or Later Edition

**References
**

- Class Notes, Power point
slides, and Exercise Problems
- The Design and Analysis
of Algorithms 1974
- AV Aho,
JE Hopcroft and JD Ullman, Addison-Wesley
Publishing Company
- Introduction to
Algorithms: A Creative Approach, Reprinted 1989
- Udi Manber,
Addison-Wesley Publishing Company
- Introduction to
Algorithms, Second Edition, 2001
- T Cormen,
C E Leiserson, R L Rivest
and C Stein McGraw Hill and MIT Press
- Graph Algorithms, 1979
- Shimon Even, Computer
Science Press
- Introduction to the
Theory of Computation, 1992
- Michael Sipser, PWS Publishing Company
- The Art of Computer
Programming, Vols. 1 and 3
- Knuth, Addison Wesley
Publishing Company

**Assessment**

Midterm exams: 30%

The structure of the
quizzes will be discussed in class, at least one week prior to the quiz.

o **Midterm**** Exam 1**** (15%): February 21,
2013**

o **Midterm**** Exam 2**** (15%): April 11, 2013**

**Final Exam : **(30%): May 02, 2013.

Midterm exams are **80** minutes and the Final Exam is of **2 **hours duration.

**Homework and Quizzes : **10 %

**Lab Assignment**: 30%

Assignment problems
will be handed out by February 05, 2013 and the expected date of completion is
9 am May06, 2013. The students will be required to write programs and run
experiments.* *

**Homework
Assignments**:

**Class participation**: ACTIVE Participation will prepare you well for the
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 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 'Homework and Quizzes' component.

Please visit course
page for details on **Americans with Disabilities
Act, Academic Dishonesty and Student Support Services. **