Course Description

In this course, we will study algorithm analysis and design; explore algorithm paradigms and advanced data structures; and uncover classes of apparently hard problems.

The topics we hope to cover are:

  • Overview and Complexity as a metric for resources (time and space) consumed by algorithms; lower, upper bounds and decision trees; Analysis of algorithms: iterative and recursive;
  • Use of loop invariant for proving algorithm correctness
  • Techniques for Design and Analysis: Amoritized Analysis and Dynamic Programming;
  • Search algorithms using Binomial Heaps, Interval Trees, and B-Trees; String Search (Knuth-Morris-Pratt);
  • Graph Algorithms: Breadth-first Search, Depth-first Search, Minimum Spanning Trees, Single-source shortest path, All-pairs shortest paths, etc.;
  • P and NP: Introduction to the notion of complexity classes; and
  • (time permitting) Other topics: Matrix Multiplication and Inversion, Solving Linear Equations, Computational Geometry.

The aim of this course is to enable a student to:

  • use complexity as a metric for resources consumed by algorithms;
  • understand paradigms of algorithm design and techniques for analysis;
  • appreciate advanced data structures, combinatorial and graph algorithms;
  • prove the correctness of algorithms; and
  • grasp the theory of NP-completeness.

Course Materials

The following materials are required for this course.

Textbook

Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. McGraw Hill. Second Edition. 2001.

Lectures

You are advised to attend all lectures. Computer-generated slides used in the lecture will generally be made available to students with an account on the TCC. Login to one of the TCC machines running Linux. Once you are logged in, type:

  1. cd ~mazumdar/cs344
  2. ls -l
Alternatively, use a SCP client to securely copy to files to your own computer. After logging into a TCC machine (e.g., rainbow.nmt.edu), change the directory to /u/mazumdar/cs344. You may then copy lectures to your local computer.

You may view, print, or download these files, but do NOT make the publicly accessibly on the Web.

Course Policies

You are responsible for knowing and understanding the following policies for this course.

Grades

Your letter grade will be assigned based on your performance in various components weighted (tentatively) as follows:

  • 40% for class work, homework, and pop quizzes;
  • 60% for in-class exams; and

Additionally:

  • Only in certain, rare, **DOCUMENTED** emergencies can you make up for an exam (not pop quizzes) and only provided you get the consent of the instructor before the exam.
  • No assignment or homework will be accepted after its due date.

Homework

  • Handwritten homeworks will not be accepted. Type your answers. However, you may fill in by hand symbols such as greek alphabets for which you cannot find a font.
  • By writing your name on your homework, you are certifying that every answer is the result of your own work; do not share your answers.
  • Do not send your homework with another student. If you are unable to come to class to submit your homework, hand it over to the department secretary.
  • Copying a solution from a webpage on the Internet is cheating.

Academic Honesty

You are required to do homeworks and assignments by yourself. Group work requires permission from the instructor. You may discuss ideas, the questions in homeworks, and the reasons why certain strategies do or do not work; but you may not share solutions or drafts of solutions, or even attempts at solutions.

Make absolutely sure that you understand NMT's plagiarism policy (in the catalog) and the TCC Usage Policy. Also, please review http://infohost.nmt.edu/~nmtlib/INFO/ORef/plagiarism.html. If you have any questions, please speak with the instructor.

Miscellaneous

  • Check your email regularly and keep a close watch on the course website.
  • Sign all email messages with your name. Include 'CS 344' in the subject of the message.
  • During class, do not let mobile devices (yours or others) distract you or others from the lecture.
  • Pay careful attention to the lecture.
  • You are responsible for keeping track of all in-class announcements whether or not you are present.