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: 

  1. Introduction
  2. Analysis of Algorithms (sets O, Ω, Θ)
  3. Brute Force and Exhaustive Search
  4. Divide-and-Conquer
  5. Fast Fourier Transform
  6. Decrease-and-Conquer
  7. Transformations
  8. Greedy Algorithms
  9. Dynamic Programming
  10. Iterative Improvement (Linear Programming)
  11. Decision Trees
  12. 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. 
  • Method 2:
    • Mid term exam: 40% (Tentative date October 6, 2023)
    • Final exam: 60%
    • Important Note: A student should get at least 50% in all lab assignments in order to be eligible to take the final exam.
For the lab assignments, students can work in groups. Each group should send a report via email to the course Teaching Assistant (TA) before the given deadline. The group will be examined according to the schedule that will be posted on the course website. During the examination, all group members should be present. Each group can submit up to one (1) delayed assignment but should be examined at a later date which will not exceed two weeks from the assigned deadline. Any other assignment submitted late will have a 10% per (late) day penalty.
 
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.