ECE-1762: Algorithms and
Data Structures
Instructor: Andreas Veneris, veneris@eecg.toronto.edu
Admin: Rosa Esteireiro, rosa.esteireiro@utoronto.ca
Teaching Assistant: Hratch Mangassarian, hratch(at)eecg(dot)toronto(dot)edu
Lecture: Tuesday 3-5pm, GB-221 and
Friday 3-6pm, BA-4164
This course covers fundamentals of computer algorithms and data
structures. The objective is to give the audience an introduction to
combinatorial modeling, algorithms and the underlying analysis. It also
aims to present a wide range of fundamental data structures and examine
their complexity in terms of space/time. In brief, the course will start
with a review of a number of basic combinatorial tools such as recurrences,
worst/best/average case analysis, probability, and discrete mathematics
(summations, principles of counting, induction). Next, it will present a
wide range of fundamental data structures and algorithms along with a
detailed analysis of their time/space behavior and real life use. Topics
include searching and sorting, dictionary operations, dynamic programming,
greedy methods, graph algorithms (shortest paths, maximum flow), intro
to NP-completeness, approximation algorithms and one advanced topic
of choice such as matrix multiplication, FFT or amortized analysis.
Algorithms and data structures along with an in-depth performance analysis
is an important subject and has numerous applications in different areas of
computer engineering such as software design, distributed computing, networking
and wireless computing, programming languages, compilers, operating systems,
multimedia and security, computer architecture, and digital circuit design.
This is a homework (problem solving) course and all topics are
exercised on paper for the student to gain expertise on the subject. Theory
is presented in class (lecture) and tutorial concentrates on
homework. No programming is required. Auditing is welcome but strongly not
recommended; a student will need to do homeworks and take the exams to
digest the ideas.
Requirements and Weight:
5 homeworks 30%, 90 min Midterm exam 30%,
120 min Final exam 40%. Exams are open book. Homeworks
can be done in groups of 1 or 2 students.
Textbook:
T.Cormen, C.Leiserson, R.Rivest, and C.Stein
``Introduction to Algorithms,''
McGraw Hill, 2001
Parenthesis contain the number of lectures, where every
lecture is equivalent to two hours approx:
* Introduction, summations, recurrences, asymptotic notation (3)
* Heapsort and analysis (1)
* Deterministic and randomized quicksort and analysis (2)
* Lower bounds for sorting, medians and order statistic (1)
* Hashing, Uniform Hashing and analysis (1)
* Binary Search Tree and Balanced Trees (1)
* Dynamic Programming (2)
* Greedy Algorithms (1)
* Amortized analysis and Splay trees (3)
* Disjoint sets (1)
* Intro to Graph Algorithms, BFS/DFS, Minimum
Spanning Trees (1)
* Single Source Shortest Paths and All-Pair
Shortest Paths (2)
* Maximum flow bipartite matching (3)
* NP Completeness (3)
* Approximation Algorithms (1)
Back to main