Wolkite University
College of Computing and Informatics
Course Title: Design and Analysis of Algorithms Course Code: CoSc 3092 Credit Hrs.: 3
Prerequisite: Data Structure and Algorithms Course Category: Compulsory Year III Semester II
Course Description
The course focuses on the design and analysis of algorithms. Topics Include: Review of the basic data
structures; Design techniques: divide-and-conquer, dynamic programming, greedy algorithms, And graph
algorithms: Elementary graph algorithms, Breadth-first search (BFS), Depth-first search (DFS), Strongly-
connected components, Minimum spanning tree, Shortest paths.
Objectives
By the end of this course, students will be able to:
➢ Perform algorithm analysis using the different techniques;
➢ Demonstrate the use of algorithm design techniques; and
➢ Describe the basics of computational complexity
➢ Apply advanced searching and sorting algorithms
➢ Develop, and reason about the correctness and performance of algorithms, in particular for string
Searching and graph manipulation
Course Outline
Chapter 1: Introduction and Elementary Data Structures (6hr)
1.1. Introduction to Algorithm analysis
1.1.1. Asymptotic Notations
1.1.2. Analysis of Algorithm
1.2. Review of elementary Data Structures
1.2.1. Heaps
1.2.2. Hashing
1.2.3. Set Representation
1.2.3.1. UNION, FIND Operation
Chapter 2: Divide and Conquer (6hr)
2.1. The General Method of Divide and Conquer
2.2. Binary Search
2.3. Finding Maximum and Minimum
2.4. Merge Sort
2.5. Quick Sort
2.6. Selection Sort
Chapter 3: Greedy Algorithms (6hr)
3.1. General Characteristic of Greedy Algorithms
3.2. Graph Minimum Spanning Tree (MST) - Kruskal’s and Prims’s Algorithms
3.3. Shortest Paths
3.4. Scheduling
Chapter 4: Dynamic Programming (6hr)
4.1. Introduction to Dynamic Programming
4.2. All pairs Shortest Path - Floyd-Warshall Algorithm
4.3. Shortest Path - Dijkstra Algorithm
4.4. 0/1 Knapsack
4.5. Depth First Search
Chapter 5: Back Tracking (6hr)
5.1. 8 Queens Problem
5.2. Graph Coloring
5.3. Hamiltonian Cycle
5.4. Knapsack Problems
5.5. Traveling Salesman Problems
Chapter 6: Introduction to Probabilistic Algorithms - Parallel Algorithms (2hr)
Assessment method
Mid Exam 20%
Quiz 5%
Individual Assignment 5%
Project 20%
Final Exam 50%
Total 100%
Teaching materials
Reference books:
➢ Cormen, T.H. et al. (1990) Introduction to Algorithms. MIT Press and McGraw-Hill
➢ Manna, Z. (1974) Mathematical Theory of Computation McGraw-Hill.
➢ Baase, S. (1988) Computer Algorithms: Introduction to Design and Analysis, 2nd ed.
➢ T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction to Algorithms The MIT Press,
Cambridge,
