King Khalid University

College of Computer Science

Department of Computer Science

http://www.kku.edu.sa

REVISED MAY 31st 2013 BY

Dr.Radhakrishnan
 Kingdom of Saudi Arabia
The National Commission for Academic Accreditation & Assessment

COURSE SPECIFICATION

CS474: Design and Analysis of Algorithms

Revised 2013-06-01 by Dr. Radhakrishnan

Course Specification

Institution : College of Computer Science , King Khalid University, Abha, KSA

College/ Department : College of Computer Science/Dept .of Computer Science

A Course Identification and General Information

1. Course title and code: Design and Analysis of algorithms (CS 474)

2. Credit hours: 3 hrs

3. Program(s) in which the course is offered. Computer Science

4. Name of faculty member responsible for the course: one + one instructor
Dr. Radhakrishnan Palanikumar

5. Level/year at which this course is offered: level 10 / year 5

6. Pre-requisites for this course (if any)
Algorithms and data structure II ( CS 216)
7. Co-requisites for this course (if any)
One must be familiar with the following mathematical pre-requisites:-Elementary
calculus, especially basic differentiation and integration. Concepts of Limits and
asymptotic graphs, L'Hospital's rule. Arithmetic, Geometric & Harmonic Progressions,
their summations, of progressions involving both Arithmetic and Geometric series,
summation using Integration
8. Location if not on main campus

B Objectives
 1. Summary of the main learning outcomes for students enrolled in the course.
The aim of the course is a survey of concepts, principles, and techniques related to
designing and analysing algorithms. The main objective of the course is to teach the
students how to select and design algorithms that are appropriate for problems that they
might encounter. Students will become acquainted with both the strengths and
limitations of various techniques like Greedy Approach, Divide and Conquer, Dynamic
Programming, Branch and Bound. Lower bounds on the efficiency of solving are also
address, especially the notion of NP-completeness. This course offers the students a
mixture of theoretical knowledge and practical experience.
Upon completion of this course the student should be able to:
1. Apply the algorithm analysis and algorithm design techniques to solve problems;
2. Have a sense of the complexities of various problems in different domains

2. Briefly describe any plans for developing and improving the course that are being
implemented. (eg increased use of IT or web based reference material, changes in
content as a result of new research in the field)
Design and analysis of algorithms is a heavily researched discipline. We will try to
incorporate latest developments in the area of subject by referring research papers
while teaching the course.

C. Course Description (Note: General description in the form to be used for the Bulletin or
Handbook should be attached)
1 Topics to be Covered

Topic No of Contact
Weeks hours
Introduction to Analysis of Algorithm 2 4
Design and analysis fundamentals, performance analysis, space
and time complexity, Growth of function – Big-Oh, Omega,
Theta notation, Mathematical background for algorithm analysis,
randomized and recursive algorithm.
Divide and Conquer 2 4
General method, Binary Search, finding the min and max, Merge
sort analysis, Quick sort, Performance measurement,
Randomized version of quick sort and analysis, Partitioned
algorithm selection sort, radix Sort Efficiency considerations,
Strassen’s matrix multiplication.

Greedy Method 3 6
General method, Knapsack problem, Minimum cost spanning
tree Kruskal and primal algo performance analysis, Single
source shorted path, Job sequencing with deadlines, optimal
storage on tapes.
Dynamic Programming 2 4
The General method, Multistage graphs, All pair shortest paths,
single source, shortest paths, Optimal BST, 0/1 knapsack, TSP,
flow shop scheduling.

Backtracking and Graph Algorithm 3 6

The general method, 8 queen problem, sum of subsets, graph
coloring, hamltonian cycles, Knapsack problem. Graph
traversals- connected components – spanning trees- Bi-
connected components.

Revision 1 2

2 Course components (total contact hours per semester):

Lecture: 32 Tutorial: 4 Practical/Field Other: -25 hours net

work/Internship: 28 surfing for research
papers

3. Additional private study/learning hours expected for students per week. (This
should be an average: for the semester not a specific requirement in each week)

4 hr's + programming hours depending upon individual competence.

4. Development of Learning Outcomes in Domains of Learning

The course objectives are to:

 Present the concept of algorithm analysis
 Study of Asymptotic Notations
 Solution of Recurrence Relations
 Comprehensive survey of sorting and Searching algorithms
 Illustrate the idea of design methods, Divide and conquer, Dynamic
programming, Greedy method
 Treatment of graph algorithms
 Understanding of NP complete problems and approximation algorithms

Based upon above objectives the course goals / learning outcomes are defined
below:
1 Define key concepts and key notations: Concept of algorithm analysis, O notation, Ө
notation, Solution of divide and conquer recurrence relation using Master theorem,
Solution of recurrence relation using generating function technique
2 Decent coverage of Searching : Sequential search, Quick Sequential search, Binary
Search, Interpolation Search, Worst case and average case analysis of above mentioned
algorithms
3 Comprehensive Coverage of Sorting: Divide and conquer strategy, Merge Sort,
Quick Sort
Heap sort, Insertion Sort, Selection Sort, Bubble Sort, Shell Sort, Analysis of above
mentioned algorithms
4 Understand Design Strategies: Dynamic Programming Methodology(Fibonacci
numbers, Knapsack problem, Longest integer subsequence, Longest common
subsequence ,Weighted interval scheduling
5 Fundamental ideas of Greedy method: Greedy method, Comparison with dynamic
programming, Knapsack problem, Coin Problem, (more examples to come later in
graph algorithms)
6 Basics of Graph Algorithms: Breadth first search, Depth first search, Topological
sorting, Minimum weight spanning trees, Prim algorithm, Kruskal algorithm, Dijkstra
algorithm, Bellman Ford algorithm
7 Idea of different problem classes: Class P, Class NP, NP hard problems, NP
complete problems, Deterministic and non deterministic polynomial time algorithms,
Approximation algorithms for some NP-complete problems for example approximation
algorithms for vertex cover problem and Set cover problem
8 Advanced Topic: Concept of Parallel Algorithms

a. Knowledge

(i) Description of the knowledge to be acquired

1. Student will become familiar with algorithm design
2. Student will become expert of algorithm analysis

(ii) Teaching strategies to be used to develop that knowledge

Lectures, tutorials, programming assignments, theory assignments and mini projects
will be given to the students. One group project will be given. These assignments will
help the students to understand working of Algorithms. Theory assignments require use
of library reference material and web sites to identify information to complete tasks.

(iii) Methods of assessment of knowledge acquired

The learning of knowledge part will be evaluated through two tests each one focuses on
certain learning outcomes based on assignment and exercises, and final exam.

b. Cognitive Skills
 (i) Cognitive skills to be developed:

The student will be able to develop the design and analytical skills.

(ii) Teaching strategies to be used to develop these cognitive skills

At least two examples will be given on each topic in the lecture. Also the students will
be given some exercise on each topic to solve in the class itself. So that students can
have better understanding of the topic.

(iii) Methods of assessment of students cognitive skills

The assignments are identified in such a manner that solving them will lead to
development of the skills and assessing them will give idea about the development of
these skills. Also few cases will be used and their independent analysis shall help
understanding of the development of these skills.

d. Communication, Information Technology and Numerical Skills

(i) Description of the skills to be developed in this domain.

These skills are important component of this course, where they should be able to
analyse and communicate both in oral as well as in written form.

(ii) Teaching strategies to be used to develop these skills

Team work: Division of work, group discussion on the various topics of computer
networks. Preparing group for seminars on any latest topic in data communication
technology and finally presenting it. Every project team is required to submit at least
one written report of typically 45-50 pages and will make many presentations.

(iii) Methods of assessment of students numerical and communication skills

Communication skill will be assessed on the basis of explanation of tutorial problems
in the class.

e. Psychomotor Skills (if applicable)

(i) Description of the psychomotor skills to be developed and the level of performance
required NA

(ii) Teaching strategies to be used to develop these skills NA

(iii) Methods of assessment of students psychomotor skills NA

 5. Schedule of Assessment Tasks for Students During the Semester

Assess Assessment task (eg. essay, test, group project, Week due Proportion
ment examination etc.) of Final
Assessme
nt
1 Test1 6 10
2 Test2 12 10
3 Assignments & project 13 10
4 Lab & project Viva 8 &15 20
5 Final Exam 17 or 18 50

D. Student Support
1. Arrangements for availability of faculty for individual student consultations and
academic advice. (include amount of time faculty are available each week)

1. Numbers of Faculty and Staff Required

Additional Number of Faculty and Staff Required
Equivale
Minimu

Category of Faculty if Student numbers Increase

nt Full

and Staff ___ to ___ ___ to ___ ___ to ___ ___ to ___
m

Students Students Students Students

Faculty 1 1 all

Laboratory 1 all
Assistants

Other (Specify)

E Learning Resources

 Design And Analysis Of Algorithms, A.A.Puntambekar, Publisher Technical

Publications, 2010, ISBN 8184317786, 9788184317787
 Cormen, Leiserson, and Rivest. Algorithms, MIT Press 2001
 Essential References: Robert Sedgewick, ALGORITHMS IN C++, Pearson
education, 2008.
 Ellis Horowitz and Sartaj Sahni, "Fundamentals of Computer Algorithms",
Galgotia Publication 1998.
 Sara Baase and Allen Van Gelder, "Computer Algorithms Introduction to
Design & Analysis", Pearson Education 1999.
 4-. Electronic Materials, Web Sites etc

Course site on blackboard http://bbapp.kku.edu.sa/,

http://www.acm.org/, http://www.ieeexplore.ieee.org/Xplore/dynhome.jsp
5- Other learning material such as computer-based programs/CD, professional
standards/regulations

F. Facilities Required

Indicate requirements for the course including size of classrooms and laboratories (i.e.
number of seats in classrooms and laboratories, extent of computer access etc.)
1. Accommodation (Lecture rooms, laboratories, etc.)
1 Lecture rooms with data show and smart board.
1 Lab
2. Computing resources
20 Computers with internet connection.
3. Other resources (specify --eg. If specific laboratory equipment is required, list
requirements or attach list)

G Course Evaluation and Improvement Processes

1 Strategies for Obtaining Student Feedback on Effectiveness of Teaching

A well-designed feedback form is used by the faculty, which has both qualitative and
quantitative components. The form covers the feedback on instructor’s approach to
teaching, his preparation for teaching and student perspective about him. It also details
out the student’s background
2 Other Strategies for Evaluation of Teaching
There is ample openness in the department, and students have direct access to head of
the department and verbal communication is also used
3 Processes for Improvement of Teaching
The students answer qualitatively few questions in the feedback form, where they can
suggest learning problems and can give suggestions. Further, instructor also will carry
out his own analysis from the results of evaluation, and will make judgments about
what can be done better and how. The list of suggestions as an improvement for next
time teaching will be used either by him or the other faculty teaching the course. A
one-day workshop was organized to share the teaching experiences and share the
feedback among the faculty to strengthen the process of improvement. This exercise is
undertaken every semester.
4. Processes for Verifying Standards of Student Achievement (e.g. check marking by
an independent faculty member of a sample of student work, periodic exchange and
remarking of a sample of assignments with a faculty member in another institution)
At present it is not being done, may be at little later stage we can do this on maturity of
assessment system
5 Action planning arrangements for periodically reviewing course effectiveness and
planning for improvement.
Based upon the results of evaluation planned and the feedback obtained, a course self-
assessment report will be prepared. The format suggested for assessment will be used It
will also summarize to what extent the subject learning objectives are achieved, do they
need improvement and what are the suggested ways and means for the same. The
instructor will list out the proposed changes, given chance to teach again the same
subject. And how the previously suggested changes have led towards improvement. A
one-day workshop was organized to share the teaching experiences and share the
feedback among the faculty to strengthen the process of improvement. This exercise is
undertaken every semester.

1 Strategies for Obtaining Student Feedback on Effectiveness of Teaching

 Course evaluation forms are filled by all students who attend the course

2 Other Strategies for Evaluation of Teaching

NA
3 Processes for Improvement of Teaching
 Training for solving more exercise sessions
 Workshops to facilitate the exchange of experiences amongst faculty members
 Regular meetings where problems are discussed and solutions given
 Attending professional development conferences
 Training more and more in Mathematica packege
4. Processes for Verifying Standards of Student Achievement (eg. check marking by an
independent faculty member of a sample of student work, periodic exchange and
remarking of a sample of assignments with a faculty member in another institution)
 Samples of students' assignments and exams are collected every semester and
reviewed from time to time as per IOP standards.

5 Action planning arrangements for periodically reviewing course effectiveness and

planning for improvement.
 Feed back mechanisms and evaluations are discussed in meetings with the
males section of Physics Department, and continuous improvement is being
implemented
1 Strategies for Obtaining Student Feedback on Effectiveness of Teaching
a. Lecture evaluation
b. Mid Term Evaluation
c. End of Year Evaluation
2 Other Strategies for Evaluation of Teaching
a. Weekly tutor meeting
 b. Educational meetings
3 Processes for Improvement of Teaching
a. Weekly tutor meeting
b. Faculty Development Programs
c. Educational Committee meetings
d. Follow-up of year and phase planners
4. Processes for Verifying Standards of Student Achievement (e.g. check marking by
an independent
faculty member of a sample of student work, periodic exchange and remarking of a
sample of
assignments with a faculty member in another institution)
a. Students Final Reports
b. Students’ final presentations
5 Action planning: arrangements for periodically reviewing Block effectiveness and
planning for improvement.
a. Academic Committee for Curriculum Development
b. End of Block Report.