CS502 Handouts, Assignments, Mid & Final Term Past Papers - Scholarships | Fellowships

CS502 Handouts, Assignments, Mid & Final Term Past Papers are given below. The goal of this course is to help students grasp the concepts and methods underlying algorithm design and analysis. Programming is not required for this mostly theoretical course, although comprehending the idea of a mathematical proof and a basic comprehension of discrete mathematics are. We will discuss and examine a number of data structures and algorithms that have been picked for their significance and their ability to illustrate key ideas. We will place a focus on examining an algorithm’s worst-case running time as a function of input size.

Assuming that viable calculations are those that can be completed in polynomial time, we will also spend some time examining the boundary between feasible and infeasible computations. The name of the Muslim author Abu Jaffar Mohammad ibn Musa al-Khwarizmi is where the word “algorithm” originates. He was born in the eighth century in the modern Uzbekistani province of Khwarazm (Keva), south of the Oxus River. Since more than a thousand years ago, Uzbekistan has been a Muslim nation. In 1873, the Russians seized control.

CS502 Handouts, Assignments, Mid & Final Term Past Papers

His precise birth year is unknown. When he was a child, the parents of Al-Khwarizmi relocated to a region south of Baghdad. His contributions have demonstrated that he flourished in Baghdad from 813 to 833 CE under Khalifa Al-Mamun. Around 840 C.E., Al-Khwarizmi passed away. Al-Khwarizmi produced a large amount of work, which was published in the book al Kitab al-mukhatasar fi hisab al-jabr wa’l-muqabalah (The Compendious Book on Calculation by Completion and Balancing). The words algebra and algorithm are taken from the titles of these books and his name. Al-Khwarizmi is recognized as the most accomplished mathematician of all time as a result of his work.

Any clearly defined computing process that accepts a value or set of values as input and outputs a value or set of values is referred to as an algorithm. Thus, an algorithm is a series of computations that convert input into output. Why do algorithm design studies? A good program’s design has numerous components. One (and a crucial one) of them is good algorithm design. A truly complete algorithm designer should be knowledgeable about both machine and programming difficulties. There are two main categories of problems in every significant programming project: macro difficulties and micro issues.

The coordination of numerous programmers working on a single piece of software and how to verify that a complicated programming system fits its many needs are two examples of macro problems. The main focus of software engineering courses is these macro concerns. The majority of sophisticated software systems’ programming effort is spent on pieces whose programming is (Input and output, data conversion, error checking, and report generation) Fairly routine. However, there is frequently a small, crucial section of the software that requires only a few tens to hundreds of lines of code but consumes the vast bulk of the processing time.

Table of Contents

Lesson Learning Objectives:

After completing this course, you ought to be able to:

Analyze how an algorithm’s worst-case execution time changes with the size of the input.
Recurrence connections puzzle
Recognize and use the Divide and Conquer technique.
Recognize the principles of dynamic programming.
Recognize the principles of the greedy algorithm.
Recognize the fundamentals of graph traversing.
Recognize and explain the fundamentals of complexity theory.

We will attempt to explore algorithms as purely mathematical objects in this course, ignoring factors like the programming language, computer, and operating system. This has the benefit of eliminating the confusing details that have an impact on implementation. But these specifics can be crucial. For instance, the locality of reference is a key aspect of modern CPU technology. Data that is often accessed can be kept in registers or cache memory. Usually, we’ll ignore these problems in our mathematical analysis. However, an effective algorithm designer can operate inside the field of mathematics while still maintaining.

Keep an open mind about future implementation difficulties that are crucial for successful implementation. For instance, this semester, we will study the heap-sort, merge-sort, and quick-sort fast sorting algorithms. All have equal running times, according to our mathematical research. On almost all modern machines, quick sort is the fastest of the three (barring any other factors). Why? From the standpoint of the location of reference, it is the best. However, the difference is often negligible (the running time difference may be between 10% and 20%).

(Or, as the saying goes, 20% of the code accounts for 80% of execution time.) How to handle these tiny, crucial portions of code the best is one of the micro problems in programming. It might be crucial for the entire project’s success that these code sections are written as efficiently as feasible. A regrettably common approach to this issue is to first design an ineffective algorithm and data structure to address the issue, and then use this subpar design to try to improve performance by using clever coding techniques or by implementing it on the most expensive and powerful machines available to boost performance as much as possible. The issue is that, in many cases, no amount of fine-tuning will make a significant difference if the basic design is flawed.