CS 4306 Algorithm Analysis

Purpose:

The goal of this assignment is to help you to apply knowledge of computing advanced algorithm analysis including the introduction of formal techniques and the underlying mathematical theory such as Fibonacci number and dynamic-programming algorithm are defined by recurrence using current techniques, skills, tools that affect in your future career in Data Analysts, Artificial Intelligence and Machine Learning.

Specifically, you will learn the following topics:

• Dynamic Programming Techniques

- Recursions - Solve the sub-problems recursively

• Image Compression

Skills: This assignment will help you to practice the following skills by applying tools that you learn

in this course, role of Algorithms and its complexity, conquer recurrence relations, inserting sort,
dynamic programming language.

Upon successfully completing this course, students will be able to “do something useful with Python”.

• Demonstrate basic understanding of the design concepts and analysis methods of algorithms
• Branch-and-bound, divide-and-conquer, dynamic programming, greedy method, search and traversal.
• Compare the computational complexity of different algorithms and analyze the time and space efficiency of algorithms.
• Demonstrate knowledge of P-FIB complete problems
• Implement the algorithms in a high-level language

Knowledge:

This assignment will also help you to become familiar with the following important content knowledge
in this disciple are as follow:

1. Be fluent in the use of dynamic programming algorithms — assignments, reinforces the recurrence relation of the Fibonacci sequence with a comparison to the dynamic programming algorithm.
2. Knowledge of basic searching and sorting algorithms.

Tasks:

Part 1 15.1- 5

 The Fibonacci number are defined by recurrence (3.22). Given an O(n) – time dynamic-

programming algorithm to compute the nth Fibonacci number. Draw the subproblem graph.

How many vertices and edges are in the graphs?

Part 2

The purpose of this assignment is to reinforce dynamic programming algorithms. Specifically, the assignment is to do problem 15-8 on page 409 of the text. In addition, implement the algorithm that you construct. You may write your program in any modern language. I suggest Python because the output can be put in a visual representation

Part 1 reinforces the recurrence relation of the Fibonacci sequence with a comparison to the dynamic programming algorithm. (goals 1, 3, 4)

Using the same algorithm in different ways illustrates the efficiency achieved by different algorithmic methods.

Part 2 reinforce the use of algorithms using a modern language.

Criteria for Success:

Please see criteria and specifications for assignments listed and example below. Apply the specification of your skills knowledge on assignment as is listed.

Resources/ Example:

1) Fibonacci Sequences - https://www.mathsisfun.com/numbers/fibonacci-sequence.html
2) Dynamic Programming Tutorial with Fibonacci Sequence -
https://www.youtube.com/watch?v=e0CAbRVYAWg
3) Image compression: https://adityashrm21.github.io/Image-Compression/

Deliverable

Submit your assignment via d2l dropbox on or before due date. Assignment will be graded and provided

a feedback within a few days.