rpastel@mtu.edu
204 Rekhi
office hours
Course information and policies at www.csl.mtu.edu/cs4321/www/
Prerequisites are CS
2311 and CS
2321. I will assume that you are familiar with the data structures and
algorithms taught in that these courses.
You may discuss the homework problems and solution in groups, but you
must write up your own solutions.
The two exams (midterm and final) are closed books and notes.
Grades will be based on achievements on the homework and exams. The weight of the homework and exams:
|
Homework (6 assignments, equal weight) |
40 |
|
Midterm exam |
20 |
|
Final exam |
40 |
|
Total |
100 |
Introduction to the Design and Analysis of Algorithms, 2nd edition, by Anany Levitin, Addison Wesley
The preface explains that introductory algorithms textbooks can introduce the material in one of two approaches:
1. Problem types
2. Algorithm types
Because the textbook stress algorithm design, it prefers to introduce the material by categorizing algorithms:
Brute Force
Divide and Conquer
Decrease and Conquer
Transform and Conquer
Space - Time Tradeoffs
Dynamic Programming
Greedy Algorithms
Iterative Improvements
In addition we will discuss problem complexity and
algorithms for NP problems
Nevertheless, problem classification is also important. Identifying the problem type may give you ideas about how to solve the problem. The introduction proposes the problem classification
Sorting
Stable sorting
In place sorting
Searching
Search key
String Processing
A string
string matching problem
Graph Problems
Graphs
Traveling salesman problem
Graph-coloring problem
Combinatorial Problems
Generating combinatorial objects: permutations
Geometric Problem
Ancient Greeks used ruler and compass, today we use the computer
Closest pair problem
Convex-hull problem
Numerical Problems
e.g. solving linear systems, optimizations of continuous functions
Course by itself, we'll not cover much
The book proposes the sequence for developing algorithms
Details
The procedure is generally iterative
Recognize the problem or reduce the problem to another
Problem inputs, problem instances, boundary conditions and special cases
Space and time constraints
Sequential Algorithms or parallel algorithms
In CS generally we want exact solutions and/or all solutions
but numerical algorithm cannot give exact solutions, so must decide accuracy.
If the problem is NP then we may not be able to generate the exact solution in reasonable time.
Algorithm + Data Structure = Programs
Study the algorithm categories
Pseudocode
Flow charts
Verbal description
Check that the algorithm really works. This not code debugging
Check boundary problem instances. I have been bitten many times
Time and space efficiency
Simplicity
Generality - refractoring
Choose the language
Debugging
Check inputs
I have added
Document and comment
Arrays
Index
Problem the most important
Computational machines are design to facilitate arrays
Minimum space
Fast random access by index
Problems growing -
amortized growth?
Link List
Nodes and pointers, header
No growth problem
Problems
Random access
Space concerns and caching
Stacks and Queues
Vertices and Edges (endpoints)
Adjacent vertices
Undirected and Directed Graphs, DAG
Sparse and dense graph
Representations: Adjacency Matrix or List
Weighted graphs
Paths and cycles
Connectivity
Acyclicity
Simple
Length
Nodes and edges
Free trees and Forests
Rooted trees
Children and parents
Ordered Trees
right and left children
elements and sometimes keys
Universal set and bit vectors
Multiset or bag
Set operations