Description

The course introduces the student to the classical techniques and paradigms used in the design and analysis of algorithms and data structures. Some of the covered techniques are recursion, divide and conquer, dynamic programming, greedy approach, and randomization. Students will be able to practice their skills on many well-known algorithms and data structures designed to solve real-life problems. Here is the course syllabus.

Prerequisites

ICS 202 and ICS 253 are the only official prerequisite for this course. In particular, some programming skills and a good background in discrete mathematics, data structures, and probability will be very helpful.

Course Objectives

1.       To know the importance of studying the complexity of a given algorithm.

2.       To study various algorithmic design techniques.

3.       To utilize data structures and/or algorithmic design techniques in solving new problems.

4.       To know and understand basic computability concepts and the complexity classes P, NP, and NP-Complete.

5.       To study some techniques for solving hard problems.

Course Learning Outcomes

After completion of this course, the student shall be able to:

1.      Describe, apply and analyze the complexity of certain divide and conquer, greedy, and dynamic programming algorithms.

2.       Identify and analyze criteria and specifications appropriate to new problems, and choose the appropriate algorithmic design technique for their solution.

3.       Describe the classes P, NP, and NP-Complete and be able to prove that a certain problem is NP-Complete.

4.       Explain and apply backtracking and branch and bound techniques to deal with some hard problems.

Evaluation

Textbook

Other References