[go: up one dir, main page]
Scribd
Upload
57 views2 pages

Algorithms Course Outline BCS 4J

This document outlines the course information for CS302 - Design and Analysis of Algorithms being offered in the Spring 2023 semester at National University of Computer & Emerging Sciences, Lahore. The course is a 3 credit core course with prerequisites of Data Structures. It will be taught on Tuesdays and Thursdays from 4-5:20pm in room BCS-4J. The objective is to teach algorithm design techniques like brute force, divide and conquer, dynamic programming and greedy algorithms. Students will analyze time and space complexity and evaluate algorithm correctness. The textbook is Introduction to Algorithms and the weekly schedule outlines the topics to be covered over 14 weeks including sorting, dynamic programming, graphs and approximation algorithms. Students will

Uploaded by

Pakeeza Qaisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
57 views2 pages

Algorithms Course Outline BCS 4J

This document outlines the course information for CS302 - Design and Analysis of Algorithms being offered in the Spring 2023 semester at National University of Computer & Emerging Sciences, Lahore. The course is a 3 credit core course with prerequisites of Data Structures. It will be taught on Tuesdays and Thursdays from 4-5:20pm in room BCS-4J. The objective is to teach algorithm design techniques like brute force, divide and conquer, dynamic programming and greedy algorithms. Students will analyze time and space complexity and evaluate algorithm correctness. The textbook is Introduction to Algorithms and the weekly schedule outlines the topics to be covered over 14 weeks including sorting, dynamic programming, graphs and approximation algorithms. Students will

Uploaded by

Pakeeza Qaisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

NATIONAL UNIVERSITY

of Computer & Emerging Sciences, Lahore

Department of Computer Science


CS302 – Design and Analysis of Algorithms
SPRING 2023
Instructor Name: Aamina Batool
Email address: aamina.batool@lhr.nu.edu.pk
Office Loca on/Number: tbd
Office Hours: tbd

Course Informa on
Program: BSCS Credit Hours: 3 Type: Core
Pre-requisites: Data Structures
Class Mee ng Time: BCS-4J Tuesdays, Thursdays 04:00 PM to 05:20 PM

Class Venue:
BCS-4J E&M - 4

Course Descrip on:


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. Design algorithms using different algorithms design techniques
i.e., Brute Force, Divide and Conquer, Dynamic Programming, Greedy
Algorithms and apply them to solve problems in the domain of the
program
2. Analyze the me and space complexity of different algorithms by
using standard asympto c nota ons for recursive and non-recursive
algorithms
3. Evaluate the correctness of algorithms by using theorem proving
or execu ng test cases

Course Textbook
● Introduc on to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd Ed., MIT Press, 2001.
Addi onal 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 Educa on
● Algorithms in C++ by Robert Sedgewick, Addison-Wesley, 1992.
● Data Structures and Algorithms by Aho, Hopcro , and Ullman.
Weekly Schedule

Lectures Descrip on Chapters of Text

Week -1 The role of algorithms in computers, Asympto c func ons and 1, 2, 3


nota ons (Big-oh, big-omega, theta) best and worst case me
complexity

Week – 2, 3, Divide and Conquer (maximum subarray sum, coun ng 2, 3, 6


4 inversions, quicksort, merge sort) + Solving recurrences

Week – 5 Lower bound for comparison based sor ng, Sor ng in linear 8
me: Count Sort, radix sort

Midterm – I

Week – 6,7 Dynamic Programming ( maximum subarray, rod cu ng, 15


longest common subsequence, binary knapsack)

Week – 8, 9 Greedy Algorithms (Ac vity selec on, frac onal knapsack and 16
Huffman codes)

Week – 10 Introduc on to graphs (revision of BFS, DFS) and their 22


applica on (topological sort, strongly connected components)

Midterm – II

Week – 11 Minimum Spanning Trees (MST)(Prim's Algorithm and 23


Kruskal's Algorithm)

Week – 12, Shortest Path Algorithms (Dijkstra's Algorithm, Bellman-Ford 24


13 and Floyd Warshall Algorithm

Week 14 Approxima on Algorithms/ NP Hard Problems

Final Exam Comprehensive

Grading Criteria
1. Quizzes (10%)
2. Assignments (15%)
3. Midterm Exams (30%)
4. Final Exam (45%)

Grading Policy
Absolute Grading

Course Policies
1. Quizzes will be announced.
2. No makeup for missed quizzes and assignments.

Academic Integrity: All work MUST be done individually. Any copying of work from other person(s)
or source(s) (e.g., the Internet) will automa cally result in at least an F grade in the course. It does
not ma er whether the copying is done in an assignment, quiz, midterm exam, or final exam, it will
be considered equally significant.

You might also like