CS 315 - Algorithm Design and Analysis

 

Credits: 3

 

Course 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.

 

Prereqs: CS-215, CS-275, and engineering standing.

 

Needed Skills

 

The student is expected to be familiar with basic concepts of programming in a general purpose programming language, and with a variety of mathematical tools for modeling and analyzing discrete structures. More specifically, the student should be familiar with programming features such as variables, control flow, iteration, and recursion, and structures such as arrays, records, lists, queues, stacks, trees, and graphs. The student should have some rudimentary understanding of time as a measure of program complexity and of basic ideas of program correctness. The student should be familiar with mathematical areas such as college algebra (especially polynomial, logarithmic, and exponential functions); calculus including differentiation and integration of basic functions; basic concepts of logic, set theory, and proof construction; counting techniques; and basic graph theory.

 

Learning Outcomes

 

The student will develop a knowledge of intermediate level algorithms and data structures, techniques for the analysis of their complexity and correctness and some of the fundamental limitations on what can and cannot be computed efficiently. The student will be expected to learn models for asymptotic analysis of algorithms; techniques for searching and sorting lists, including binary search, and various sorts such as insertion, selection, merge, quick, heap, tree, bin and radix sorts; lower bounds on the complexity of sorting; advanced structures for data storage such as balanced trees and hashing; algorithms for performing a variety of operations on graphs, such as traversals, shortest path finding, and spanning trees; a sampling of algorithms from other areas such as numerical and string algorithms; and the concepts of tractability and intractability of problems (including notions of polynomial time and NP-completeness).


Specifically, students will:

1. Understand the limiting factors of resources such as time and space in algorithmic solutions.

2. Understand how to approach the algorithm design and analysis

3. Understand basic algorithms and data structures and how to compare their quality.

4. Understand how to experimentally analyze the performance of programs.


Measures:

These specific outcomes will be evaluated on the basis of student work (homeworks, programming assignments, and exams) that contain problems specifically addressing these outcomes and on the basis of student self-assessment of their mastery of the outcomes at the end of the semester evaluation forms.


CAC Categories:

 


Topic

Core

Advanced

Math Fundamentals

3

2

Data Structures

2

2

Algorithms & Software Design

24

8

Computer Organization and Architecture

1

0

Concepts of Programming Languages

1

1

Social and ethical issues

1

0

Total

32

13

 

Math Fundamentals (5): Core (3): Basic recurrences and asymptotic estimations (1); Basic formulas used in algorithm analysis (1); Mathematical induction (1)

Advanced (2): Program correctness with invariants (2)

 

Data structures (4): Core (2): Sets, Graph, trees, heaps (2)

Advanced (2): Balanced trees, Union-Find, Abstract Data Types (2)

 

Algorithms and Software (32): Core (24): Searching and sorting (6); Order statistics (2); Elementary Graph algorithms (5); Algorithm design techniques (5); Recursion (4); Experimental running-time analysis (2)

Advanced(8): Graph algorithms (4); Algebraic algorithms (2); String algorithms (2).

 

Computer Organization and Architecture (1): Core (2): Memory layout, computer speed (1)

 

Concepts of Programming Languages (2): Core (1): Implementation of recursive algorithms (1)

Advanced (2): Implementations of Abstract Data Types (1)

 

Social and ethical issues (1): Responsible usage of computers, social impact of incorrect algorithms and faulty software (1)

 

Oral Communication (presentations)

 

none

 

Written Communication

 

7-10 homework assignments, 2-4 fuly documented programming projects.

 

Coverage

 

Theoretical content: 40%

· Asymptotic estimates

· Abstract Data Types

· Graphs

· Basic algebraic properties

· Strings and their properties

· Algorithm design paradigms

· Fundamental computational problems and their algorithmic solutions

· Proof by invariant

· Lower bounds

· Intractability and NP completeness.

 

Problem analysis: 30%

· Analyze algorithmic problems and discover, formulate and analyze their properties

· Formulate problem abstractions.

 

Solution design: 30%

· Design algorithms and data structures

· Construct proofs of properties of algorithms

· Translate algorithmic solutions into programs

· Solve recurrences

· Asymptotic estimation problems

 

Student evaluation and feedback

 

Students are evaluated on their work (homeworks, projects, exams). Graded students' papers are marked to indicate problems, to point out correct or better solutions, and to improve the quality of presentation. Sample solutions and typical errors are discussed in class.

 

Grading

 

Grade is determined by performance on homeworks (30%), programming assignments (30%), and exams (40%)..Final grades will be assigned according to the following scale: A=90-100%, B=80-89%, C=70-79%, D=60-69%, E=0-59%. (Categories and weights for assignments and scales are examples only; actual categories, weights and scales used may vary with instructor.)

 

NOTE: 100% lecture - 0% recitations

 

Course Evaluation Questions

 

Do you agree that course has helped you to:

37. Understand the limiting factors of resources such as time and space in algorithmic solutions.

38. Understand how to approach the algorithm design and analysis

39. Understand basic algorithms and data structures and how to compare their quality.

40. Understand how to experimentally analyze the performance of programs.

 

Possible Textbook

 

Compared to What? An Introduction to the Analysis of Algorithms,
G.J.E Rawlins,
W. H. Freeman, 1992

 

Data Structures and Algorithm Analysis in C++ ( or in Java),
Mark A. Weiss
Addison-Wesley.