ECE 325- Iterative Methods

Course Details

**Objectives of the course:**

This course covers a broad spectrum of techniques for solving problems using iterative methods. During the course we will study various problems (search, decision, optimization) and we will investigate various algorithmic approaches for solving them. Emphasis will be given to the problem formulation, the precise description of the algorithm that solves the problem, as well as to the analysis of the correctness and efficiency of the algorithms. The objective of the course is to introduce problem solving strategies, mainly through the design of iterative algorithms. The course will introduce specific algorithm design techniques and will provide the tools for analyzing the efficiency of each algorithm.

**Prerequisite:**

Students must have completed at least a programming course and a course in data structures (CS 034 and CS 035 or equivalent).

**Course Syllabus: **

- Introduction
- Analysis of Algorithms (sets O, Ω, Θ)
- Brute Force and Exhaustive Search
- Divide-and-Conquer
- Fast Fourier Transform
- Decrease-and-Conquer
- Transformations
- Greedy Algorithms
- Dynamic Programming
- Iterative Improvement (Linear Programming)
- Decision Trees
*P*,*NP*, and*NP*-Complete Problems – If time permits

**Grading:**

**Method 1:**- Laboratory Assignments: 15
**%**

- Mid term exam: 35
**%**(Tentative date**October 6, 2023**) - Final exam:
**50%**. **Important Note:**To pass the class, students should get at least**50%**in the exams and**50%**in the lab assignments.

- Laboratory Assignments: 15

**Method 2:**- Mid term exam: 40
**%**(Tentative date**October 6, 2023**) - Final exam: 6
**0%** **Important Note:**A student should get at least 50% in all lab assignments in order to be eligible to take the final exam.

- Mid term exam: 40

**Important Note**: All students who wish to use Method 2 for their grading should send an email to the course instructor with the title “

**[ECE 325] Method 2**” and should include the name and ID number of the student.

**Textbook**: Anany Levitin, “Introduction to The Design and Analysis of Algorithms”, 2nd Edition, Prentice Hall, 2007.

**Bibliography**

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, “Introduction to Algorithms”, 2003.

S. Dasgupta, C. Papadimitriou, and U. Vazirani, “Algorithms”, 2008.

R. Johnsonbaugh, M. Schaefer, “Algorithms”, 2004

J. Kleinberg and E. Tardos, “Algorithm Design”, 2005

S. Baase, “Computer Algorithms: Introduction and Design Analysis”, 1988.

G. Brassard and P. Bratley, “Fundamentals of Algorithmics”, 1996.

**Academic Honesty: **It is acceptable to work together in small groups for study, homework, and laboratory assignments. However, the work that you turn in under your name **must be your own**. Cheating will not be tolerated; neither during homework nor during exams.