Skip navigation
Brigham Young University
Login
Computer Science

Computer Science

CS 312 - Algorithm Analysis

Summary Analysis of algorithms including searching, sorting, graphs, and trees.
Prerequisites CS 240, CS 252
Credits 3  
Return to Course Listing

CS312 Objectives and Topics

This document is not a syllabus. Instead, for ALL offerings of this course, this document states the expected objectives and topics for the course and the approximate number of 50-minute lectures to be devoted to each topic. Faculty members teaching this course should adhere to these objectives and topics. Students taking this course can expect to achieve the objectives and cover the topics specified, and faculty members teaching follow-on courses can expect students to have been appropriately exposed to the prerequisite material as stated.


Objectives

Students should:


Students should:

1. Understand fundamental computer algorithms and how to analyze them. In particular, students should understand the five algorithmic paradigms: divide-and-conquer, greedy, dynamic programming, backtracking, and branch-and-bound.

2. Review and reinforce material encountered earlier in the curriculum on time and space analysis and complexity theory.

3. See how math supports CS and how CS concepts can be formalized in mathematics (beyond lectures and the text book, homework exercises plus thought questions related to programming projects should pull these ideas together);

4. Further their ability to program by writing five programs that illustrate the conflicts of time efficiency, recursive complexity, and space allocation associated with the five algorithmic paradigms.

Topics

Review                  (the equivalent of 2 lectures scattered throughout,
                         as concepts are encountered)
        Big Oh analysis
        recurrence relations
        P/NP/NP-complete

Divide-and-Conquer      (8 lectures)
        mergesort, binary search
        quicksort
        strassen matrix multiplication
        Deriving Big Oh bounds on Divide-and-Conquer algorithms

Greedy                  (8 lectures)
        job scheduling
        fractional knapsack
        heaps and disjoint sets
        minimal spanning trees- Kruskal, Prim
        deriving Big Oh bounds on greedy algorithms
        proving Greedy algorithms work
        proving Greedy algorithms fail

Dynamic Programming     (8 lectures)
        matrix chain multiplication
        longest common subsequence
        Traveling Salesperson 
        0-1 knapsack
        reduction of Big Oh bounds for some NP-complete problems

Backtracking            (8 lectures)
        Traveling Salesperson and kill rules
        colored block problem
        chess problems
        static/dynamic 0-1 knapsack backtracking
        applications to NP-complete problems

Branch-and-bound        (8 lectures)
        reduced matrices
        approximations to NP-complete problems
        memory management
        kill rules
        seed heuristics
        Big Oh bounds on heuristics

eStore