C455 - Analysis of Algorithms I

Document last modified: 

Date

Notes, Readings, Activities

Jan
9

Chapters 1 & 2
Answers

16

23

Chapter 3 Answers

30

Chapter 4 Answers
Substitution Activity Solution

6

Recursion Tree Activity Solution
Master Method Activity Solution

Chapter 6 Answers
 

15

Chapters 1-4

22

6

Review B-Tree
Insert Activity Solution
Delete Activity Solution

8

Chapters 6, 11, 12, 18

22

5

12

Backtracking and Best-First Answers
Backtracking Activity Solution
Best-First Activity Solution
Chapter 23 - Minimum Spanning Trees

Chapter 34 Answers
Activity Solution

Models, algorithms, recurrences, summations, growth rates. Probabilistic tools, upper and lower bounds; worst-case and average-case analysis, amortized analysis, dynamization. Comparison-based algorithms: search, selection, sorting, hashing. Information extraction algorithms (graphs, databases). Graphs algorithms: spanning trees, shortest paths, connectivity, depth-first search, breadth-first search. General methods: dynamic programming, backtracking, best-first, greedy algorithms.

Click for 
Grade Book:

Learning requires a partnership between the instructor, authors, researchers and students; therefore students are encouraged to use any and all resources available to solve homework problems and complete programming assignments. However, students must:

1. clearly cite any contributing source; a text, another student, the Internet, etc.
2. create their own solutions

For example, students may work in groups to solve homework problems provided each student creates their own (not copies) solutions  and clearly lists all group members or other sources such as authors of texts or on the Internet. Likewise, software that performs assigned functionality may not be directly used but the source code may be consulted provided it is subsequently cited. Changing the spelling of algorithm identifiers does not constitute creating an original solution. It is absolutely essential to note that failure to cite any contributing source will be considered cheating regardless of the reason for the omission. Likewise, verbatim duplication of any source, whether from another student, a text, etc. will always be considered plagiarism.

Violation of any aspect of this policy will result in a failing grade for the course.