CES 512   Theory of Software Systems

              MS-CES Program, Spring 2008

Sonoma State University

Instructor:

B.Ravikumar. Office:116 I Darwin Hall

Office phone: 664 3335. Email: ravi@cs.sonoma.edu.

             Office hours:  TBA

 

Class Time:

W 6 to 8:45 PM, Room 2008 Salazar Hall

     

Background Expected:
       

  • Background in data structures and a high-level programming language, preferably c++ or Java.
  • Basics of Discrete Mathematics (basics of probability and counting, proofs, induction, graphs and trees etc.)

 

Goals:

 

  • This course is intended to provide the mathematical and quantitative tools for understanding the design and implementation of software systems. Specifically, given a software design task, we will address the issues such as:
    • the best choice of algorithms and data structures to solve the problem
    • the time and storage requirements for solving the problem
    • comparison of two or more competing techniques
    • validating the correctness of the solution etc.

            

  • However, we will not discuss some of the issues such as software management, team work and other topics typically covered under “Software Engineering”.

 

  •  Standard algorithm design techniques (such as dynamic programming, greedy method and linear programming) as well as core problems (such as shortest path, sorting and searching) will be discussed. One of the key concepts that we would emphasize is to design algorithms by relating the problem to a known problem whenever possible.

 

  • The course project is intended to provide experience in reading research papers and in converting algorithms into computer programs. A black-box approach to problem solving will be emphasized in the project based on code reuse.

   

Text and References:

 

 Introduction to Algorithms, Second Edition by Cormen, Leiserson and Rivest, published by MIT Press and McGraw Hill. 2002

 

Some other useful books/lecture notes/web sites are:

  • J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley Inc 2005.
  • R. Ahuja et al. et  al Network Flow: Theory and Applications, Prentice-Hall Inc.
  • V. Chvatal, Linear Programming, W.H.Freeman and Co.
  • R. Ladner, Applied algorithms – Course offered at the University of Washington,Seattle.

Course Work:


 Course work will consist of some of the following:

  1. short quizzes (in class)
  2. home-work assignments

·         some home work problems will involve programming.

·         others will involve describing algorithms and analyzing their performance.

  1. one mid-semester test
  2. a semester-long course project and
  3. a final examination

 

Details regarding the course work will be finalized after a discussion in the class.
 

Grading: (tentative and approximate)

 

Short quizzes – 5 points

Home work assignments – 20 to 25 points

Mid-Semester Test – 15 to 20 points

Project  – 20 to 25 points

Final examination – 25 to 35 points.

  

The weights indicated above are approximate and are subject to change. Home Work assignments will be due at the beginning of class on the due date. Late submissions may be marked down significantly. The course project shall be chosen from a list of problems given at the beginning of the semester and should be worked on throughout the semester. At the end of the semester, you may be required to give a presentation on the project.

 

Topics covered:

         

The following is a tentative list of topics to be covered and is subject to minor/major revisions as the semester progresses.

 

Algorithms and Data Structures

 

·         Goals of the course 

·         Algorithm design and analysis framework

·         Insertion sorting

 

Chapters 1 to 3
  • Heap
  • Hash table
  • Some applications of priority queues and hash tables

Chapters 6 and 11
  • Binary search trees
  • Some applications

 

     Chapter 12
  • Divide and conquer
  • Greedy method 

Chapters 4 and 16
  • Dynamic programming and applications

Chapter 15
  • Dynamic programming and applications

Chapter 15

Advanced topics

 

  • Graph algorithms -  DFS, BFS

Chapter 22
  • shortest paths and spanning trees
  • applications of path problems

Chapters 23 and 24
  • matching and network flow

Chapter 26
  • Linear programming

 

Chapter 29

       Applications
  • String matching and applications
  • Data and image compression
  • FFT and applications

 

 

 

 

Expected Time Commitment:

 

You will be required to spend about 10 hours per week on this course beyond the three hour class meeting. This includes reading the text as well as working on the home-work problems.