---
tags: year2-2
---

# Algorithm Design

## Introduction

### Goal

- Formulate computational problem into a clear requirement
- Design algorithm to solve the problem correctly and efficiently

### Topics

- Complexity Analysis
- NP-Completeness (Can the problem be solved in reasonable time)
- Sythesis of algorithm
- Divide and Conquer
- Dynamic Programming
- Greedy
- Graph Algorithm
- State Space Search

### Example Problems

Problem Statement in this course contains

- Precise constraint of the input
- Required properties of the output

#### GCD

Find the greatest divisor of the number a and b

#### Fibonacci

Find n-th fibonacci number

**Solutions**

- Recursive (exponential time)
- Matrix + Divide and conquer (logarithmic time)
- Homogenous Recurrent RElation
- Eigen Vector

### Course Material

- MyCourseVille: Homework & Quiz
- Discord: Discussion
- Grader: Homework
- Zoom: Online Class
- Youtube: Lecture video

For official matter or direct message, Contact Prof. using email.

### Scoring

- 15% Activity
- 5% Small Quiz
- 20% HW