Course Title Design and Analysis of Algorithm
Operation Course
As Per Schedule Credits
3
Period
Class
Schedule
M-F Code CSEg2208
Target
Students’ computer science and Engineering Target
2rd year
Student Grade
Major
Prerequisite( Capacity
s) for Data Structure And Algorithm Max 55
(Maximum
enrollment Number)
Upon completion of this course, students should be able to:
o Express the art of computational problem solving.
o perform algorithm analysis using the different techniques;
Learning o demonstrate the use of algorithm design techniques; and
outcome o Describe the basics of computational complexity.
o apply advanced searching and sorting algorithms
o develop, and reason about the correctness and performance of algorithms, in
particular for string searching and graph manipulation
The course focuses on the design and analysis of algorithms. Topics Include:
Review of the basic data structures; Design techniques: divide-and-conquer,
Course
dynamic programming, greedy algorithms, And graph algorithms: Elementary
Description
graph algorithms, Breadth-first search (BFS), Depth-first search (DFS),
Strongly-connected components, Minimum spanning tree, Shortest paths.
Related 1. Data Structure and Analysis
research 2. Analysis existence Algorithm
3. Design and develop new Algorithm
areas
4. Analysis the complexity of the algorithm
Lecture Plan
Week Topic
Chapter 1: Introduction Review of Elementary Data
W1 Structures, Analysis of Algorithms, Sorting algorithms, Heaps
and Heap Sort, Hashing, Asymptotic notations, Examples.
Topics
Chapter 2: Divide and Conquer General method,
W2 applications-Binary search, Quick sort, Merge sort, Selection
Sort, finding maximum and minimum. Solving recurrence
relations using Masters Theorem, substitution method
Chapter 3: Tree Binary tree, Binary search tree, RB tree, B-
W3
Tree, B+ Tree basic operations and applications.
Chapter 4: Greedy Method General method, Examples of
Greedy Approach, Advantages and limitations.
W4-5
Applications-Job sequencing with deadlines, 0/1 knapsack
problem, Minimum cost spanning trees, Single source shortest
path problem.
Mid Exam
Chapter 5: Dynamic Programming
General method, Examples of Dynamic Programming,
Advantages and limitations, applications-Matrix chain
W5
multiplication, Optimal binary search trees, 0/1 knapsack
problem, All pairs shortest path problem, Travelling sales
person problem, Reliability design.
Chapter 6: Back Tracking General method, applications- 8
W6 queen problem, sum of subsets problem, graph coloring,
Hamiltonian cycles.
Chapter 7: Branch and Bound Branch and Bound: General
W6 method, applications - Travelling sales person problem,0/1
knapsack problem- LC Branch and Bound solution, FIFO Branch
and Bound solution.
Chapter 8: Graph Algorithms BFS, DFS, Minimum Spanning
W7 Tree, Single Source Shortest path, All pair shortest path,
Maximum flow Problem
W8 Chapter 9: NP-Hard and NP-Complete problems
Basic concepts, Non-deterministic algorithms, NP - Hard and
NP Complete classes, Cook’s theorem.
Parameter Weight Remark
5 but optional
Attendance
10
Quiz
Assignment / 10
Presentation
Assessment
5
Class Participation
10
Project /seminar
25
Mid exam
40
Final exam
100 %
Total
1. Introduction to the Design and Analysis of Algorithms, Anany Levitin :
Course Textbook
Pearson Education, 2013 (Text Book )
http://www. rabieramadan.org Design and Analysis of Algorithm
References in Algorithm Analysis
MOOC Introduction to Design and Analysis
MIT6.00 OCW and Harvard CS50x
Algorithm
Related
http://www.tutorialspoint.com/python/
references
Fundamentals of Computer Algorithms,Horowitz and Sahni, Galgothia
publications.
Introduction to Algorithms,Cormen, Leiserson and Rivest : Prentice Hall of
India.
