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

• Analyze the computational complexity of basic algorithms
• Be familiar with basic and advanced data structures
• Be familiar with frequently used algorithms, such as sorting, searching, and selection
• Design appropriate data structures and algorithms for programming tasks

Prerequisites

• Computing III, Discrete Math I & II, Statistics for Scientists and Engineers, Calculus I-II

Textbook

• Required Textbook: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition, MIT Press.
• Optional Suppliment: Jon Kleinberg and Éva Tardos. Algorithm Design, Addison-Wesley, 2005.

Useful Links

Courseware, slides, homework, and other study materials will be shared at this link: click here, the access passcode has been emailed to the students, if you do not have the passcode please contact the instructor.

Grading

• The course will have 4 homework assignments, 1 midterm and 1 final exam (see syllabus for expected dates). Grades will be calculated approximately as follows:
• Homework 40%, 10 points for each homework assignment
• Midterm and Final exams, each accounts for 30 points

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

Last update: 12/08/2017