<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

Instructor

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.

Topics

Algorithms, Data Structures, Time and Space Complexity Analysis

Course Goals

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

Prerequisites

Textbook

Useful Links

Grading

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 Ch22, 24.3 Lecture 7
8 & Midterm 10/26 5:30pm – 7:00pm, location TBD; Graph Algorithms II - Lecture 8
9 11/2 Greedy Algorithms I Ch16.1, 16.2, 16.3 Lecture 9
10 11/9 Greedy Algorithms II Ch23 Lecture 10
11 11/16 Dynamic Programming I Ch25.2, 15.1 Lecture 11
- 11/23 - No class, Thanks giving day -
12 11/30 Dynamic Programming II Ch15.4 Lecture 12
13 12/7 Intractable Problems; Max-flow, min-cut, Final review - Lecture 13
- 12/14 - Reading Day, QA
Final 12/15 6:30PM - 9:30PM Time and Location TBD -

Last update: 10/06/2017