Saint Mary’s University

Department of Mathematics and Computing Science

CSC 451.1: Topics in Theoretical Computing Science I

FALL 1998-99

Instructor: Dr. Pawan Lingras

Class time: Tuesday and Thursday 4:00-5:15 p.m.

Room: L269 (Loyola Academic Complex)

Link to Calendar Description

Brief Description

In conjunction with CSC 452.2, this class is designed to provide a detailed introduction to various topics in theoretical computing science. The first part deals with the analysis of algorithms. This course will build on the concepts of analysis of algorithms introduced in data structures (CSC 341). The course will include mathematical background necessary for the analysis, detailed analysis of some of the key algorithms, as well as the notions of lower bounds and NP-completeness. In addition to the theoretical analysis of algorithms, students are expected to implement some of the algorithms in C++ and analyze their run-time performance. The hands on experimentation will be achieved through assignments as well as a project of student’s choice (determined in consultation with the instructor).

Textbook

Purdom, P. W. and Brown, C. A. (1985). The Analysis of Algorithms, Holt, Rinehart and Winston, Toronto.

 Topics

Week

Topics

Chapter

1

 Introduction

1

2

 Analysis of loops

1

3

 Summing Series

2

4

 Summing Series, Project Proposal discussion

2

5

 Products and Binomials

3

6

 Simple Linear Recurrence

5

7

 Recurrence (contd.), Midterm

5

8

 Nonlinear recurrence

7

9

 Global Techniques

9

10

 Lower bounds

10

11

 NP completeness

10

12

 Student Presentations

NA

 

Evaluation scheme

Method of Evaluation

Marks
Assignments

15
Project

20
Midterm

25
Final

40

Total

100

 

Assignments

Project

The project consists of three phases:

  1. Proposal (Due Date: October 21, 1998)
  2. Presentation (November 25 and 30, 1998)
  3. Paper (Due Date: December 4, 1998)

Midterm

The midterm examination will be held on Monday, October 19, 1998. A link to the guide for the midterm will be available here.

Final Examination

The final examination will be scheduled by the Registrar’s office during the examination period from December 2-17, 1998. A link to the guide for the final examination will be available here.