Design and Analysis of Algorithms Chapter 1

Course Overview

• The course aims to teach students to think algorithmically, familiarize themselves with core algorithms, and learn various design techniques and analysis.
• The course covers Divide & Conquer, Greedy Algorithms, Randomization, and Dynamic Programming.

Student Assessment Criteria

• Attendance & Participation: 5 points
• Assignments: 5 points
• Quizzes: 10 points
• Mid-Term Exam: 20 points
• Practical / Project: 20 points
• Final Exam: 40 points

Importance of Algorithms

• Studying algorithms enhances problem-solving skills and provides approaches to tackle complex problems.
• Learning about algorithms helps develop more efficient solutions, saving time and resources in various applications.
• Algorithms are applicable in various disciplines such as mathematics, engineering, and natural sciences.

Algorithm Definition

• An algorithm is a sequence of steps to accomplish a particular task.
• A good algorithm should use resources like CPU time and memory judiciously.
• The output produced by an algorithm lies in a set called range, and the input is taken from a set called domain.

Characteristics of an Algorithm

• An algorithm can have zero or more inputs.
• An algorithm must have at least one output.
• An algorithm should be efficient in terms of memory and time.
• An algorithm should be finite.
• Every statement in an algorithm should be unambiguous.

Ways of Writing an Algorithm

• English-like Algorithm: can be written in simple English, but lacks the characteristic of being definite.
• Flowcharts: graphical representations of processes or workflows, consisting of symbols and connectors that depict the sequence of steps, decisions, and actions involved in a process.

Importance of Algorithms in Real-World Applications

• Google's Search Engine uses the PageRank (PR) algorithm to order search results.
• Google Maps uses the shortest path algorithm to provide driving directions.
• Algorithms are important in biological endeavors, such as searching and sorting algorithms used to extract information from billions of DNAs.