The College of New Jersey
Computer Science Department
CMSC 410: Advanced Algorithms
Fall 2001

Class Time:
 
Monday, Thursday 12:30-1:50  Holman Hall 252.
Monday, Thursday 2:00-3:20  Holman Hall 252.

Textbook:
 
"Algorithms in C++: Fundamentals, Data Structures, Sorting, 
Searching"
by Robert Sedgewick
published by :
Addison-Wesley Pub. Co.
ISBN: 0201350882

Instructor:
 
          Dr. Miroslav Martinovic.

E-mail Address :
 
          mmmartin@tcnj.edu

Telephone :
 
          (609) 771-2789.

Office :
 
          Rm. 243, Holman Hall

Office Hours:
 
Monday :
8:30-9:30
10:50 – 11:50
Wednesday :
8:30-9:30
10:50-11:50
3:25 - 4:25 (by appointment)
 		 Thursday :
10:50-11:50
3:25 - 4:25 (by appointment)

Grading Policy:
 
Homeworks, Class Participation and Effort
10%
Project Assignments
20%
Midterm 
25%
Final Exam
45%
*         Homeworks are regularly due on the next class period. No late homework will be accepted.
**       The lowest homework grade will be replaced by the average of other homework grades.
****   There will be no make up exam for this course.

 
 
 


 
 
CS 601
Tentative Schedule


 
 Week of 8/28 
Fundamentals of Algorithms and 
Their Complexity
Analysis of Algorithms
Implementation of Algorithms
Time and Space Complexity of Algorithms
 Evaluating Complexity of a Given Program
 Computational Complexity Measures for Algorithms
O(f(n))
W(f(n))
Q(f(n))

Class Notes

Homework 1
 


 
 Weeks of 9/28 and 9/4 
More on Complexity Measures 
for Algorithms
Recursive Methods
       Fibonacci Numbers
            Deriving Time Complexity Using Recurrent Equations

Class Notes

Homework 2
Homework 2a
 
 Weeks of 9/4 and 9/10
Abstract Data Structures
Abstract Data Structres and Their Operations
        Lists
             Implementation Using Arrays
             Implementation Using Reference Structures
        Stacks
             Implementation Using Arrays
             Implementation Using Reference Structures
        Queues
             Implementation Using Arrays
             Implementation Using Reference Structures

Class Notes
Dynamic Memory Organization
Homework 3
 


 
 Weeks of 9/10 and 9/17 
Sorting Algorithms I
Elementary Sorting Methods
       Bubble Sort
       Selection Sort
       Insertion Sort

       Performance Characteristics

Quick Sort

Class Notes

Homework 4
 


 
Weeks of 9/17 and 9/24 
Sorting Algorithms II
Quick Sort
       Performance Characteristics
       Optimized Implementations
Quick Sort Time Complexity Analysis

Merge Sort
       Performance Characteristics
       Optimized Implementations

Merge Sort Time Complexity Analysis
Class Notes
MultipleSorting.java
MultipleSortingPhases.java

Midterm Info

Homework 5
 


 
Weeks of 9/24 and 10/1 
Sorting Algorithms III
Heap Sort
       Priority Queues
       Heap Data Structure

       Performance Characteristics
       Optimized Implementations

Review for the Midterm Exam

Homework :
 


 
MIDTERM EXAM October 10 , 2001 


 
Midterm Exam Solutions Discussion Week of 10/11 
MT Exam I Solution
MT Exam II Solution
MT Exam III Solution
MT Exam IV Solution
Quick Sort Time Complexity Analysis
Class Notes
Homework 6
Weeks of 10/15 and 10/25 
Sorting Algorithms IV
Bin Sort
       Performance Characteristics
       Optimized Implementations

Class Notes
Class Notes - Appendix
Homework 7
 


 
Week of 10/29 
Searching Algorithms I
Elementary Searching Methods
       Sequential Search
       Binary Search
       Binary Tree Search

       Performance Characteristics

Balanced Trees
       2-3-4 Trees
       AVL Trees

       Performance Characteristics
       Optimized Implementations

Homework :
    Binary Tree Traversals Homework

 


 
Week of 11/5 and 11/12 
Searching Algorithms II
External Searching
       B Trees

       Performance Characteristics
       Optimized Implementations

Hashing
      Hash Functions
      Collision Problem
           Open Hashing
           Closed Hashing

       Performance Characteristics
       Optimized Implementations

Class Notes
Homework 8
 


 
Weeks of 11/12, 11/19 and 11/26 
Graph Algorithms I
Fundamentals of Graph Theory

Elementary Graph Algorithms
        Depth-First Search
        Breadth-First Search

       Performance Characteristics
       Optimized Implementations

Connectivity and Weghted Graphs
       Connected Components
       Biconnectivity
       Minimum Spanning Tree (MST)
              Prim's and Kruskal's Methods for Finding MST
                    Performance Characteristics
                    Optimized Implementations

Class Notes
Graph Algorithms
Homework 9
Project 2
Project 3
Project 4
Homework 10
More Projects

 


 
Weeks of 11/26 and 12/2 
Graph Algorithms II
Shortest Path in a Graph
          Dijkstra's Algorithm
                   Performance Characteristics
                    Optimized Implementations

Directed Graphs
          Transitive Closure Algorithm

Homework :
    Homework 11
    Practice Exercise 12
    Homework 12
    Homework 13
 
Weeks 12/2 and 12/9 
String Processing Algorithms (optional)
String Searching
Pattern Matching
Parsing
File Compression
Cryptology
          Performance Characteristics
          Optimized Implementations

Homework :
 
Final Exam Review
Week of 12/9 
FINAL EXAM HINTS

 
Final Exam