Design and Analysis of Algorithms Course Outline - University of Sargodha

Course Title: Design and Analysis of Algorithms

Course Code: CS-3143

Course Structure: Lectures: 3 / Labs: 0

Credit Hours: 3

Prerequisites: CMP-2111 (Discrete Structure)

Course Objectives:

The course introduces students with the basic notions of the design of algorithms and the
underlying data structures. Students will learn about several measures regarding the structure,
complexity, and efficiency of algorithms.

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.

Course Outline:

1.     Role of Algorithms in Computing, Analysing Algorithms, Designing Algorithms, Growth
of Functions, Asymptotic Notation, Standard Notations and Common Functions. [TB:
Ch1,2,3]

2.      Divide-and-Conquer, Strassen's Algorithm for Matrix Multiplication, Recursion. [TB:
Ch. 4]

3.      Recurrences: Substitution Method for Solving Recurrences, Recursion-Tree Method for
Solving Recurrences, Master Method for Solving Recurrences. [TB: Ch. 4]

4.      Sorting and Order Statistics: Heapsort Algorithm, Priority Ques, Quicksort Algorithm,
Analysis of Quicksort. [TB: Ch. 6, 7]

5.      Sorting in Linear Time: Lower Bounds for Sorting, Counting Sort, Radix Sort, Bucket
Sort. [TB: Ch. 8]

6.      Medians and Order Statistics, Binary Search Trees, Querying a Binary Search Tree,
Insertion and Deletion. [TB: Ch. 9, 12]

7.      Red-Black Trees: Properties of Red-Black Trees, Rotations, Insertion, Deletion;
Minimum Spanning Trees: Introduction, Growing a Minimum Spanning Tree. [TB: Ch.
12]

8.      Dynamic Programming: Elements of Dynamic Programming, Longest Common
Subsequence, Optimal Binary Search Trees [TB: Ch. 15]

9.      Greedy Algorithms: Elements of The Greedy Strategy, Huffman Codes, Matroids and
Greedy Methods, Task-Scheduling Problem. [TB: Ch. 16]

10. Elementary Graph Algorithms, Representations of Graphs, Breadth-First Search, Depth-
First Search, Topological Sort. [TB: Ch. 22]

11.  Single-Source Shortest Paths: The Bellman-Ford Algorithm, Single-Source Shortest
Paths in Directed Acyclic Graphs, Dijkstra's Algorithm. [TB: Ch. 24]

12.  All-Pairs Shortest Paths: Floyd-Warshall Algorithm, Johnson's Algorithm for Sparse
Graphs. [TB: Ch. 25]

13. Maximum Flow: Flow Networks, Ford-Fulkerson Method, Push-Relabel Algorithms,
Relabel-to-Front Algorithm. [TB: Ch. 26]

14.  String Matching: Naive String-Matching Algorithm, Rabin-Karp Algorithm, String

Matching with Finite Automata, Knuth-Morris-Pratt Algorithm. [TB: Ch. 32]

Text Book(s):

•        Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest and Clifford Stein, The MIT Press; 3^rdEdition (2009). ISBN-10: 0262033844

Reference Material:

•        Introduction to the Design and Analysis of Algorithms by Anany Levitin, Addison
Wesley; 2^ndEdition (2006). ISBN-10: 0321358287

•          Algorithms in C++ by Robert Sedgewick (1999). ASIN: B006UR4BJS

•          Algorithms in Java by Robert Sedgewick, Addison-Wesley Professional;
3^rdEdition(2002). ISBN-10: 0201361205

Note: This content is obtained from official documents of University of Sargodha and applied on BS Computer Science for Main Campus, Sub Campuses, and Affiliated Colleges.