CSCI 235 / Fall 2021

Analysis of Algorithms


Instructor
Ting Gu
Office: Haberlin 309
Extension: 3762
Email: tgu@holycross.edu


Office Hours:

  • Wednesday (online Zoom ID: 926 2761 7816) 11:00 a.m. - 12:00 p.m. & 1:00 - 2:00 p.m.
  • Thursday (in-person Haberlin 309) 2:00 - 3:00 p.m., or By Appointment.

  • 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