CS 315 Algorithm Design and Analysis

University of Kentucky
Department of Computer Science
CS 315 Algorithm Design and Analysis
 
 
1.  Course Number/Name:  CS 315, Algorithm Design and Analysis
 
2.  Credits and Contact Hours:  3 credit, 3 contact hours
 
3.   Instructor:  assigned by the department
 
4.   Textbook:   Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani; McGraw-Hill,  2008.

5.   a.  Catalog Description:  Introduction to the design and analysis of algorithms. Asymptotic analysis of time complexity. Proofs
            of correctness. Algorithms and advanced data structures for searching and sorting lists, graph algorithms, numeric
            algorithms, and string algorithms. Polynomial time computation and NP-completeness.

       b.  Prerequisites:  CS 215, CS 275, and engineering standing. 
 
c.  Required course:  Required
 
6.  a.   Outcomes of Instruction:  Students will demonstrate understanding of basic  concepts in algorithm design and analysis.  
 
           Specifically, students will:
 
1.     understand the limiting factors of resources such as time and space in algorithmic solutions;
2.     know how to approach the algorithm design and analysis;
3.     know basic algorithms and data structures and know how to compare their quality;
4.     know how to analyze experimentally the performance of algorithms.
 
b.   Contributions to Student Outcomes (ABET Criterion 3 for Computer Science)
           

Outcome

a

b

c

d

e

f

g

h

i

j

k

CS 315

3

3

3

 

 

 

 

 

 

3

 

3- Strongly supported   2 – Supported   1 – Minimally supported
 
 7.   List of Topics Covered:
 
1.     Introduction to algorithms --- correctness and efficiency
2.     Algorithms with numbers
3.     Divide-and-conquer algorithms
4.     Exploring graphs
5.     Paths in graphs
6.     Greedy algorithms
7.     Dynamic programming
8.     Sorting, searching, and search trees
9.     Algorithms on strings
10.   NP-completeness