Course Code: CS-3811

Credit Hours:3

Prerequisites:  CMP-2111(Discrete Structures)

Introduction:

Introduction of Design & Analysis of Algorithm: An Algorithm is a sequence of steps to solve a problem. Design and Analysis of Algorithm is very important for designing algorithm to solve different types of problems in the branch of computer science and information technology.The course introduces students with the basic notions of the design of algorithms and the underlying data structures. The. fundamental concepts of Designing Strategies, Complexity analysis of Algorithms, followed by problems on Graph Theory and Sorting methods. This tutorial also includes the basic concepts on Complexity theory. Students will learn about several measures regarding the structure, complexity, and efficiency of algorithms.

Learning Outcomes

• Able to argue the correctness of algorithms using inductive proofs and invariants.
• Analyze worst-case running times of algorithms using asymptotic analysis.
• Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it
• Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it.
• Describe the greedy paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm.
• Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate. Synthesize new graph algorithms and algorithms that employ graph computations as key components, and analyze them.
• Explain the different ways to analyze randomized algorithms (expected running time, probability of error). Recite algorithms that employ randomization. Explain the difference between a randomized algorithm and an algorithm with probabilistic inputs.
• Analyze randomized algorithms. Employ indicator random variables and linearity of expectation to perform the analyses. Recite analyses of algorithms that employ this method of analysis.
• Course Syllabus: Algorithms in Computing, Divide-and-Conquer, Recurrences, Sorting and Order Statistics, Sorting in Linear Time, Binary Trees, Red-Black Trees, Dynamic Programming, Greedy Algorithms, Elementary Graph Algorithms, Single-Source Shortest Paths, All-Pairs Shortest Paths, Maximum Flow, String Matching.
• Text Book(s):  Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, The MIT Press; 3rdEdition (2009). ISBN-10: 0262033844 

• Reference Material:

  Artificial Intelligence: A Systems Approach by M. Tim Jones, Jones and Bartlett
  Publishers, Inc; 1stEdition (December 26, 2008). ISBN-10: 0763773379
  · Artificial Intelligence in the 21st Century by Stephen Lucci , Danny Kopec, Mercury
  Learning and Information (May 18, 2012). ISBN-10: 1936420236
• Grading Scheme:
• Mid Term:     30 Marks
• Final Term:     50 Marks

Assignment & Quizzes:       20 Marks

Quiz: 10

assignments: 10

Design &analysis of Algorithms

EX-PPP BSCS 6th-C
Monday 03:30-05:00

Tuesday 3:30-05:00

EX-PPP BSCS 6th-D
Monday 12:30-02:00

Wednesday 12:30-02:00

EX-PPP BSIT 6th-C
Thursday 03:30-05:00

Friday 02:00-3:30

 BSSE 6th- Self
Tuesday 12:30-02:00

Thursday 11:00-12:30