NATIONAL UNIVERSITY
of Computer & Emerging Sciences, Lahore
Department of Computer Science
CS302 – Design and Analysis of Algorithms
Spring 2022
Instructor Name: Maryam Bashir
Email address:
[email protected]Office Location/Number: C142
Office Hours: Monday, Wednesday 10:00 AM to 11:30 AM, Tuesday, Thursday 11:30 AM to 12:30 PM
Course Information
Program: BSCS Credit Hours: 3 Type: Core
Pre-requisites: Data Structures
Class Meeting Time: Tuesday and Thursday: Section BCS-4A 10:00 AM to 11:20 AM, Section BCS-4B
1:00 PM to 2:20PM
Class Venue: Section 4A CS 11, Section 4B CS 15
Course Description:
The objective of this course is not to fill your brains with every algorithm that you would ever need.
One of the aims of this course is to teach you to reason about algorithms and describe them. In
addition, many known algorithms to solve known problems will be taught. At the end of the course,
you should be able to choose an appropriate algorithm from a set of algorithms for a given problem.
Course Learning Outcomes (CLOs):
1. Explain what is meant by “best”, “expected”, and “worst” case
behavior of an algorithm
2. Identify the characteristics of data and/or other conditions or
assumptions that lead to different behaviors.
3. Determine informally the time and space complexity of simple
algorithms
4. List and contrast standard complexity classes
5. Use big O, Omega, Theta notation formally to give asymptotic
upper bounds on time and space complexity of algorithms
6. Use of the strategies(brute-force, greedy, divide-and-conquer, and
dynamic programming) to solve an appropriate problem
7. Solve problems using graph algorithms, including single-source
and all-pairs shortest paths, and at least one minimum spanning tree
algorithm
Course Textbook
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd Ed., MIT Press, 2001.
Additional references and books related to the course:
Jon Kleinberg, Éva Tardos, Algorithm Design, Pearson/Addison-Wesley
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms, McGraw-Hill Education
Algorithms in C++ by Robert Sedgewick, Addison-Wesley, 1992.
Data Structures and Algorithms by Aho, Hopcroft, and Ullman
Weekly Schedule
Lectures Description Chapters of Text
Week -1 The role of algorithms in computers, Asymptotic 1, 2, 3
functions and notations (Bid-oh, big-omega,
theeta) best and worst case time complexity
Week – 2, 3, 4 Divide and Conquer (maximum subarray sum, 2, 3, 6
counting inversions, quicksort, merge sort)
+ Solving recurrences
Week – 5 Lower bound for comparison based sorting, Sorting 8
in linear time: Count Sort
Midterm – I
Week – 6,7 Dynamic Programming ( maximum subarray, rod 15
cutting, longest common subsequence, binary
knapsack)
Week – 8, 9 Greedy Algorithms (Activity selection, fractional 16
knapsack and Huffman codes)
Week – 10 Introduction to graphs (revision of BFS, DFS) and 22
their application (Cycle Detection, shortest paths,
connected components etc.)
Midterm – II
Week – 11 Applications of DFS (topological sort, strongly 22
connected components)
Week – 12 Minimum Spanning Trees (MST)(Prim's Algorithm 23
and Kruskal's Algorithm)
Week 13, 14 Shortest Path Algorithms (dijkstra's Algorithm, 24
BellmanFord and Floyd Warshall Algorithm
Final Exam Comprehensive
Tentative Grading Criteria
1. 4 Assignments (15%)
2. 4 Quizzes (15%) (3 best out of 4)
3. 2 Midterm Exam (12.5% each)
4. Final Exam (45%)
Grading Policy
Absolute Grading
Course Policies
1. Quizzes will be announced.
2. No makeup for missed quiz or assignment.
Plagiarism in Assignments
In writing up your assignments and in answering questions in exams, be as clear, precise, and
concise as you can. Understandability will be an important factor in grading.
Academic Integrity: All work MUST be done individually. Any copying of work from other person(s) or
source(s) (e.g. the Internet) will automatically result in at least an F grade in the course. It does not
matter whether the copying is done in an assignment, quiz, midterm exam, or final exam,
it will be considered equally significant.
