Course No: CSE 2201
Course title: Computer Algorithms
Prerequisite courses:
· CSE 1201
· CSE 2101
Contact hours/week: 3
Credits: 3.00
Course Description
Asymptotic Notations: Complexity Analysis of Algorithms, Worst Case, Best Case and Average Case.
Sorting Algorithms: Divide and Conquer Approach: Merge Sort and Quick Sort Algorithm (Complexity Analysis: Worst and Average Case Analysis), Heaps: Heap Construction Algorithm, Heap Sort, Application of Heap: Priority Queue, Sorting in Linear Time: Decision Tree Model and (Worst Case) Lower Bound on Sorting, - Radix Sort, Bucket Sort, Counting Sort, etc.
Graph Algorithms: Representation of Graphs, Breadth First Search, Depth First Search, Minimum Spanning Tree, Kruskal and Prims Algorithm, Shortest Path: Dijkstra’s Algorithm, Bellman-Ford Algorithm. Floyd Warshall Algorithm.
Searching Algorithms: Binary Search Trees, Balanced Binary Search Trees: AVL Trees, Red-Black Trees and B-Trees, Skip Lists, Hashing(Hash Table) Priority Queues, Heaps, Interval Trees.
Dynamic Programming: Longest Common Subsequence (LCS), Matrix Chain Multiplication (MCM), Knapsack Problem, Multistage Graphs.
Greedy Algorithm: Greedy Algorithm, Activity Selection Problem, Huffman Codes and its application, Knapsack problem, Tree Vertex Splitting.
Recurrences & Backtracking: Recurrences, NP-Hard and NP-Complete Problems, Backtracking, n-Queen Problem, Branch and Bounds.
Reducibility between Problems and NP-completeness: Lower Bound Theory, Discussion of Different NP-Complete Problems like Satisfiability, Clique, Vertex Cover, Independent Set, Hamiltonian Cycle, TSP, Knapsack, Set Cover, Bin Packing, etc.
Computational Geometry: Line Segment Properties, Convex Hull, Graham Scan Algorithm of Convex Hull.
Books:
B1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, "Introduction To Algorithms", Second Edition.
B2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithm”.
Course Objectives:
Computer algorithms are the building blocks in computer programming. This course will give students a comprehensive introduction of algorithm design and analysis. Unlike programs, algorithms are not dependent on a particular programming language, machine, system, or compiler. They are mathematical entities, which can be thought of as running on some sort of idealized computer with an infinite random-access memory and an unlimited word size. Algorithm design is all about the mathematical theory behind the design of good programs. It makes familiar with fundamental algorithms, algorithmic techniques and analyze the running time of a given algorithm.
Outline of the Course:
Course Content according to Books
B1:
Part – I:
Chapter: 2,3,4
Part – II
Chapter: 6,7,8
Part – III
Chapter: 11, 12, 13, 14 (sec: 14.3)
Part – IV
Chapter: 15 (sec: 15.2, 15.4), 16 (sec: 16.1, 16.3)
Part – V
Chapter: 18
Part – VI
Chapter: 22 (sec: 22.1, 22.2, 22.3), 23, 24 (sec: 24.1, 24.3), 25 (Sec: 25.2)
Part – VII
Chapter: 33 (sec: 33.1, 33.3), 34 (sec. 34.5)
B2:
Chapter: 1 (sec: 1.1, 1.2, 1.3)
Chapter: 2 (sec: 2.2, 2.3.1, 2.4, 2.6)
Chapter: 3 (sec: 3.1, 3.2, 3.3, 3.4, 3.5, 3.8)
Chapter: 4 (sec: 4.1, 4.2, 4.3, 4.4, 4.5)
Chapter: 5 (sec: 5.1, 5.2, 5.3, 5.4, 5.7)
Chapter: 6 (sec: 6.1, 6.2)
Chapter: 7 (sec: 7.1, 7.2, 7.3, 7.4, 7.5, 7.6)
Chapter: 8 (sec: 8.1, 8.2, 8.3)
Chapter: 10
Chapter: 11
Grading:
Quizzes/Class Test: 20 Marks* (3 best out of 4 quizzes/class tests may be taken for awarding grade)
Homework’s/Attendance: 8 Marks*
Semester Exam: 72 Marks
* - We reserve the right to change the above grading scheme.
Homework's
A new homework is released and is then due after 9 days. No grade will be given to homework submitted afterwards. Homework solutions should be written and submitted individually, but discussions among students are encouraged.
Notice
Class Test Marks - #1 - marks(C) - marks(B)
Class Test Marks - #2 – Marks(B) - Marks(C)
Class Test Marks - #3 and #4 – Marks(B)
Lab (B): Quiz(B), Attendance(B),
Class(B): Class Attendance(B)
Lab Quiz & Attendance - Section C
Class Attendance - Section(C)
Handouts
Sessional
Course No: CSE 2202
Course title: Sessional based on CSE 2201
Prerequisite courses: None
Contact hours/week: 3
Credits: 1.50
Course Description
Sessional based on the theory of course CSE 2201.
Grading
Quiz Test: 20 Marks*
Homework's/Attendance: 8 Marks*
Board Viva: 25
Others: 47 Marks*
Lab Report (Individual)* - 20
Lab Performance (Individual)* - 27
* - We reserve the right to change the above grading scheme.
Outline of the Course: