<div class="statcounter"><a title="real time web analytics" href="http://statcounter.com/" target="_blank"><img class="statcounter" src="//c.statcounter.com/11209578/0/b9fc2e7e/1/" alt="real time web analytics"></a></div>

COMP.4040: Analysis of Algorithms (Fall, 2017)

Time: Thu, 5:30pm - 8:15pm

Location: Olsen 103


Yongfeng Zhang (yongfeng_zhang@uml.edu)

Office: Olsen 216

Office hour: Fri, 2:30pm - 5:00pm, or by appointmnet

Course Description

This is a required course for Computer Science majors. It builds on the introduction to data types and data structures that students receive in Computing II (COMP 1020).

In this course (COMP 4040) we distinguish between an abstract data type (such as a list, stack, queue, tree, or hash table) and a data structure that represents how the abstract data type is represented and stored in the computer's memory. We learn about algorithms for manipulating information in a variety of fundamental abstract data types and data structures.

Information tasks such as searching, retrieving, inserting, updating, sorting and deleting arise frequently in Computer Science problems that are central to many computer applications. We focus on algorithms to correctly and efficiently accomplish these types of core tasks.

What do we mean by "efficiently?" We measure efficiency in terms of speed and space (storage) usage. We use techniques from theoretical computer science and discrete mathematics for our analyses.

Why does efficiency matter in computing environments in which processors are very fast and storage space is abundant? Here are two reasons that have significant practical impact: 1) The amount of information continues to explode quickly, and for large amounts of information the differences in speed and storage requirements across different algorithm/data structure combinations can be huge; 2) Some types of problems are inherently difficult and we cannot expect to solve them as efficiently as we can solve easier ones. It is important to learn to recognize such problems and be familiar with ways to tackle them.

The algorithms we study represent a variety of important Computer Science problem-solving strategies, or algorithmic paradigms. We examine major characteristics of several algorithmic paradigms.


Algorithms, Data Structures, Time and Space Complexity Analysis

Course Goals

Upon finishing this course, the students should be able to:



Useful Links


Homework Assignments

We have 4 homework assignments, 10 credits for each assignment. Assignments are posted on Fridays, you have two weeks to finish the homework, homeworks are due on the second Friday (14 days later) at 11:59pm.

Tentative Schedule

Class# Date Topic Reading Slides
1 9/7 Algorithmic Analysis, Divide and Conquer I Ch2, 3 Lecture 1
2 9/14 Divide and Conquer II, Solving Recurrences Ch 3, 4.3-4.6 Lecture 2
3 9/21 Sorting Lower Bounds, Linear Sorting Algorithms Ch8, 9 Lecture 3
4 9/28 Binary Search Trees, Red-Black Trees Ch12, 13 Lecture 4
5 10/5 Randomized Algorithms I, Quick sort Ch5, 7 Lecture 5
6 10/12 Randomized Algorithms II, Hashing Ch11 Lecture 6
7 10/19 Graph Algorithms I, DFS/BFS/Dijkstra's Ch22, 24.3 Lecture 7
8 & Midterm 10/26 5:30pm – 7:00pm, Olsen 311; Graph Algorithms II - Lecture 8
9 11/2 Greedy Algorithms I, Proof of Correctness Ch16.1, 16.2, 16.3 Lecture 9
10 11/9 Greedy Algorithms II, Minimum Spanning Tree Ch23 Lecture 10
11 11/16 Dynamic Programming I, Bellman-Ford/Floyd-Warshall Ch25.2, 15.1 Lecture 11
- 11/23 - No class, Thanks giving day -
12 11/30 Dynamic Programming II, LCS/Knapsack Ch15.4 Lecture 12
13 12/7 Maxflow/mincut, Final review - Lecture 13
- 12/14 - Reading Day, QA
Final Exam 12/15 Time: 6:30PM - 9:30PM, Location: Olsen 311 - -

Last update: 12/08/2017