Syllabus      CS463    Algorithms              Spring 2006

INSTRUCTOR

Dr. Irena Pevac,  Associate Professor

OFFICE

Maria Sanford 219

PHONE

832-2721

e-mail

pevac  @   ccsu.edu

WEB

members.cox.net/pevac

 

 OFFICE HOURS

 

Monday,  Wednesday, Tuesday,  Thursday

PM   4:00-5:15 

 

CREDIT LOAD

3 credit hour

PREREQUISITE

CS 253 and Math 218

TEXTBOOK

Levitin Intro to the Design & Analysis of Algorithms, Addison Wesley, 2003.

Pevac Recursive Examples in Java XanEdu OriginalWorks , 2006

http://xanedu.proquest.com/originalworks/Prevac

Additional Reading

Cormen, Leiserson, Rivest Intro To Algorithms McGraw Hill , MIT Press, 2000.

Baase, Gelder: Computer Algorithms, 3rd ed., Addison Wesley, 2000

Sedgewick: Algorithms in JAVA, 3rd ed, Addison Wesley, 2003.

Harel: Algorithmics, 2nd ed, Addison Wesley, 1997.

OVERVIEW: This is a theoretical course covering design and analysis of algorithms for solving real problems that arise frequently in computer applications. The emphasis is on fundamental concepts of studying design techniques and not on specific software and implementation.  The computational complexity such as time performance worst case, average behavior, and space usage and lower bounds on the complexity of a problem will be discussed. Various types of advanced algorithms and NP-completeness will be introduced.

COURSE TOPICS - Read the topic before it is covered in the class.

Notion of Algorithm, Examples

Analyzing algorithms O, W, q, w, o

Analysis of nonrecursive algorithms

Analysis of recursive algorithms

Brute force algorithms

Exhaustive search

Divide-and-conquer: mergesort, quicksort, binary search

Other divide-and-conquer algorithms: binary tree traversal, Multiplication of large integers, Strassen matrix multiplication, closest-pair and convex hull problems

Decrease-by-one: insertion sort, DFS, BFS, topological sorting

Decrease-by-a-constant factor, Josephus problem

Instance simplification presorting, Gaussian Elimination, balanced search trees

Representation change: heap and heapsort

Representation change: Horner’s rule, binary exponentiation

Problem reduction

Space-time tradeoffs: string matching, hashing, B-trees

Dynamic programming algorithms: Fibonacci, longest common subsequence, binomial coefficients, Warshal’s algorithm for transitive closure

Greedy algorithms: Prim’s, and  Kruskal’s for connected components Dijkstra’s for shortest path

Decision trees

P, NP, and NP-complete algorithms

COURSE ASSIGNMENTS:

  • Group research paper should have 10-20 pages.  An oral presentation of the paper with PowerPoint slides  should be presented in front of the class. Each group (2 students) will select a topic related to materials covered in the course to write a research paper.
  • Three projects

  CS463 TEST DATES

  PROJECTS DUE

  T1  03-01-06           T2    04-12-06

P1   02 - 27 - 06          P2   03 - 29 - 06          P3   04 - 26 - 06

 Final Exam   5-15-06

 

LATE PROJECTS: Projects are due as mentioned. You may submit a project at most one class after the due date in which case a penalty of two points will occur. After that projects are unacceptable.

GRADE EVALUATION

Quantity

 Points

 Percentage

TESTS

2

20 points each

40% of Final Grade

PROJECTS

3

10 points each

30%

PAPER AND ORAL

1

10 points

10%

FINAL EXAM

1

20

20%

Thus, the Final Grade consists of approximately 60% on testing, 40% on projects and academic class-work. 

ATTENDANCE POLICY: You are supposed to attend classes regularly. In case of absence it is your responsibility to cover the topics done in the class. In case of missing a test date your final exam score will be used to replace the missing test score.

SPECIAL NEEDS: If you need special adaptations or accommodations because of a disability or if you need special arrangements in case the building must be evacuated, please notify me as soon as possible during my office hours.