LE/EECS 3101 A
Design & Analysis of Algorithms
Course Information
- Term: Fall 2023
- Lectures:
Synchronous lectures are in person at 16:00 - 17:20 on Tuesdays (LSB 106) and Thursdays (LSB 103). These "content delivery" lectures introduce the concepts to be learned for the week. Lectures will be broadcast live on Zoom and also recorded via Zoom
https://yorku.zoom.us/j/96539986100?pwd=QUMvRmQweEVuYU82Vm9OOGc1TUxldz09
Given the classroom's limited recording support, Zoom live sessions and recordings come with no guarantee of video quality.
- Tutorials:
In-person tutorials are held on Fridays at 16:00-17:30 (LSB 106). In a typical week, the in-person tutorial serves as the "practice" lecture, where the students will practice the concepts and skills learned with real problem-solving exercises guided by the instructor. Tutorials will be broadcast live on Zoom and also recorded via Zoom
https://yorku.zoom.us/j/91082541032?pwd=RlFtdW9vcCtOaWIxK2VuLzdNbHdMQT09
Given the classroom's limited recording support, Zoom live sessions and recordings come with no guarantee of video quality.
- Instructor:
Shahin Kamali
kamalis@yorku.ca
Add "[EECS 3101]" in the subject line, and allow 24 hours for response.
- Office hours:
Thursdays 14:00 - 15:00 in person at LAS-3052A
and Friday 14:00 - 15:00 on Zoom
https://yorku.zoom.us/j/95142265810?pwd=Um1WclZsTkZyRi8wL0w1akhqTU03Zz09
- Info & Syllabus:
Find all details here
This course is intended to teach students the fundamental techniques in the design of algorithms and the analysis of their computational complexity. Each of these techniques is applied to several widely used and practical problems. At the end of this course, a student can choose algorithms appropriate for many common computational problems, exploit constraints and structure to design efficient algorithms and select appropriate trade-offs for speed and space. Topics covered may include a review of fundamental data structures, asymptotic notation, solving recurrences, sorting and order statistics, divide-and-conquer approaches, dynamic programming, greedy method, divide-and-conquer algorithms, amortization approaches, graph algorithms and the theory of NP-completeness..
- Piazza page:
https://piazza.com/yorku.ca/fall2023/eecs3101/home
Students are encouraged to post their questions on Piazza (this can be done anonymously).
- Course Goals and Intended
Learning Outcomes:
This course exposes students to fundamentals of algorithm design and analysis. By the end of this course, students are expected to be able to:
- Choose an appropriate algorithm to solve a given computational problem, and justify that choice
- Apply standard graph algorithms to a variety of problems
- Design new algorithms using a variety of techniques (recursion, greedy algorithm, dynamic programming, backtracking)
- Prove correctness of an algorithm using pre- and post-conditions and loop invariants
- Prove bounds on the running time of
an algorithm
- Textbooks:
All materials from the class will be posted in the course web-page. The slides will be the main source for assignments and exams.
The following book is the main reference for the materials covered in the class.
- Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, MIT Press.
- Course overview:
EECS3101 is a course on design and analysis of algorithms. Students will learn new techniques for solving fundamental algorithmic problems efficiently.
Topics to be covered include:
|
|
List of topics & course material
1. Introduction
Intended learning outcomes:
- Explain the difference between an ADT and a data structure, and the difference between an Algorithm and a Program
- Demonstrate an abstraction of a computational machine to a Random Access Machine
- Describe the meaning and application of asymptotic notations
- Describe the growth of a given function using asymptotic notation, using common techniques such as substitution and Master theorem
- Slides (Chapters 1, 2, and 3 of CLRS)
- Zoom links:
- September 7 (scroll to minute 18:00): here
- September 12 (scroll to minute 8:00): here
- September 14: here
- September 19: here
- Tutorial material:
- Assignment 1
- Assignment 1 solutions
- Unofficial online lectures from last year:
2. Recursion and Divide-and-Conquer Paradigm
Intended learning outcomes:
- Explain the difference between sequential and recursive algorithms
- Analyze the time complexity of a recursive algorithm using asymptotic notations
- Demonstrate the advantage of a divide-and-conquer algorithm over a brute force algorithm
- Slides (Chapter 4 of CLRS)
- Zoom link:
- Tutorial material:
- Assignment 2
- Assignment 2 Solutions
- Unofficial online lectures from last year:
3. Sorting
Intended learning outcomes:
- Explain the difference between various searching algorithms
- Analyze the running time and memory usage of different sorting algorithms and explain the advantages and disadvantages of each algorithm
- Describe the difference between worst-case, average-case, and best-case running times
- Differentiate between comparison-based sorting and non-comparison-based sorting algorithms
- Describe the lower bound for the running time of the comparison-based sorting
- Explain the applications and limitations of linear-time sorting algorithms
- Slides
- Zoom links:
- Tutorials
- Unofficial online lectures from last year:
- Sample Midterm
- Midterm Answers
- Tutorial (October 20)
4. Dynamic Programming
Intended learning outcomes:
- Apply the dynamic programming framework for solving optimization problems
- Utilize the bottom-up approach for filling dynamic programming tables
- Reconstruct an optimal solution for an optimization problem using dynamic-programming tables
- Explain the dynamic programming
algorithms for optimization problems such as Rod cutting and
Longest Common Subsequence problems
- Slides
- Zoom links:
- Tutorials
- Unofficial online lectures from last
year:
- Assignment 4
- Assignment
4 Solutions
5- Greedy Algorithms
Intended learning
outcomes:
- Apply the greedy programming framework for solving optimization problems.
- Recognize the difference and relationship between dynamic programming and greedy algorithms.
- Solve simple optimization problems using greedy programming techniques.
- Explain the greedy algorithms in the context of Huffman codes, Fractional Knapsack, and Activity selection problems.
- Slides
- Zoom links:
- Unofficial online lectures from last year:
- Tutorial (November 17th):
- Tutorial (November 24th):
6- Graph Algorithms
Intended learning
outcomes:
- Describe applications of graphs for modelling relationships in the real world.
- Explain various graph representations and exemplify their advantages and drawbacks.
- Apply Breadth-First and Depth-First Search algorithms on multiple graphs.
- Describe and Trace Prim's and Kruskal's Minimum Spanning Tree algorithms.
- Describe and Trace Dijisktra's Shortest Path algorithm
- Slides
- Zoom
links:
- Unofficial online lectures from last year:
- Assignment 5
- Assignment 5 Solutions
7- Remarks on Complexity
Intended learning outcomes:
- Contrast the difference between
polynomial-time algorithms and super-polynomial-time
algorithms.
- Explain the notion of polynomial-time
reduction and P≠NP conjecture.
- Describe the NP-complete complexity
class.
- Slides
- Zoom links:
- Unofficial online lectures from last year:
-