CSCI 235 / Fall 2021

Analysis of Algorithms

**Instructor
**

Ting Gu

Office: Haberlin 309

Extension: 3762

Email: tgu@holycross.edu

**Office Hours:**

**Lecture classroom and times
**

Swords 330, Tu/Th, 12:30 - 01:45 p.m.

The lecture may be switched to online session using Zoom ID:
980 0129 6417 when
in-person class is unable to carry on.

**Course description
**

Algorithms are recipes for solving computational problems. In this course
we will study fundamental algorithms for solving a variety of problems, including
sorting, searching and graph algorithms. More importantly, we will focus on
general design and analysis techniques that underlie these algorithms. For example,
we will examine divide-and-conquer, dynamic programming, greediness, and probabilistic
approaches. With an understanding of these techniques, you will be prepared to design
some of your own algorithms.

Algorithms are judged not only by how well they solve a problem, but also by how effectively they use resources like time and space. We will learn techniques for analyzing time and space complexity of algorithms and will use these to evaluate tradeoffs between different algorithms. We will also see that problems can be organized into a hierarchy that measures their inherent difficulty by the efficiency of the best possible algorithm for solving them.

Please check Canvas for the most updated course materials and schedule.

**Prerequisites
**

The prerequisite for this class is CSCI 132, Data Structures and 1 semester
of calculus.
You should feel comfortable with simple data structures (arrays, lists, trees,
stacks and queues) as well as recursion. You should also feel comfortable with
basic calculus concepts such as limits and derivatives.

In addition **you should be prepared to learn some new mathematical techniques**.
In order to analyze algorithms, we'll need to use some mathematical methods that may be
new to you. We will learn these methods in class, and they are also explained well
in the textbook.

The Notation we will use for algorithms is the pseudocode used in the textbook**.
**

**Textbook
***Introduction to Algorithms, 3rd edition *by Cormen, Leisersen, Rivest and Stein.
This excellent and comprehensive textbook is a "must" for any computer scientist.

It is recommended that Holy Cross students will have textbooks and other required class materials in order to achieve academic success. If you are unable to purchase course materials, please go to the Financial Aid office where a staff member will be happy to provide you with information and assistance.

**Homework Assignments**

There will be approximately eight to ten homework
assignments during the semester. These problem sets will be of the "paper and pencil"
variety. You are encouraged to use LaTeX to write your solutions. Extra points will be awarded for your effort in writing with LaTeX. Homework assignments will be posted and submitted through Canvas.

**Quizzes**

There will be approximately eight to ten short quizzes during the semester.
Quizzies will be posted and submitted through Canvas.

Ting Gu--tgu@holycross.edu

Computer Science 235--Analysis of Algorithms