CS395 - Analysis of Algorithms

Frequent Links

Class News

May 5
Study List:

from text: chapters: 1, 2, 3, sections: 4.1, 4.2, 5.1, 5.2, 5.3, 6.4, 7.3, 8.1
anything that was homework
the first exam
anything discussed in class
all the algorithms in the algorithms section on the class web page that we discussed in class
the class notes on the class web page

More information coming. Also check the updated class notes.

Mar 20
The due date for assignment 4 has been delayed two days to Wed the 27th because of the exam. Some new extra information has been put into the class notes.

Mar 18
Exam 1 will cover the class notes (see this side bar); chapters 1, 2, 3, 4, 5.2, 5.3; anything from assignments 1, 2, 3, and 4 (this is a good source of problems from the material above); anything in the lecture (a good review for this includes understanding all of the algorithms except string compare algorithms in the algorithms section below).

Mar 7
Assignment 4 has been posted. assignment 4 pdf. assignment 4 tex.

Mar 7
Exam 1 is on Fri Mar 22. Exam Review will be in class on the Wed Mar 20.

Mar 3
I am starting to put class notes in this file: notes.pdf.

Mar 3
HINT: For assignment 3 problem 3 you might want to remember that big-O notation is an upperbound. That is, you only need to bound the function for all values larger than some number. So that computing the sum of a sqrt of a variable index might be bounded above by a convenient constant that makes the sum easy to express as a function. Answers I am NOT looking for include one of harmonic numbers, sums, or powers of max that are poor upperbounds.

Feb 26
Assignment 3 has been posted. Here is: assignment 3 pdf and here is the tex file: assignment 3 tex. Download tex as download link. Note it has a "tex" file extension.

Feb 3
Assignment 2 has been posted. Here is: assignment 2 pdf and here is the tex file: assignment 2 tex. Download tex as download link. Note it has a "tex" file extension. Great LaTeX references are below. Expand your horizons and give it a shot.

Jan 23
NO CLASS ON WED JAN 23 DUE TO ILLNESS. See you Friday.

Jan 21
Assignment 1 has been posted.

Jan 9
All CS395 students should take this survey to help me understand the skill mix of the class. Thanks!

Jan 9
Welcome to Analysis of Algorithms! Be sure to read the material in the Service section below. You are responsible for everything that appears on the class web pages. Many links will be dead links until we talk about them in class so I can update them for each semester. Have fun!

Class Description

This class is about lots of cool algorithms and how to analyze and improve their performance. My approach will be one of not just mathematics but of coding.

[This page is under construction]

Time: MWF 12:30-1:30 Final: Yes Location: EP 216
Text: Introduction to the Design and Analysis of Algorithms by Anany Levitin

Estimated Syllabus

This syllabus is an estimate of what we might cover this semester. This is the first time I have taught this course so expect the syllabus to be very fluid.

Wk#	Monday of that Week	Topics/Links	Assignments	Comments
1	Jan 7	Class intro, Definition and features of an algorithm, Example of some simple algorithms, Tractability, Euclid's algorithms done many ways	Read Chapter 1	NO CLASS ON MONDAY
2	Jan 14	Algorithm metrics, how do we compare algorithms, efficiency classes, tractable	Read Chapter 2
3	Jan 21	O, Omega, and Theta, how to compare efficiency classes	Assignment 1	NO CLASS ON MONDAY
4	Jan 28	Simple algorithm analysis techniques	assignment 2 pdf, assignment 2 tex
5	Feb 4	Brute force approaches, sorting and the tower of Hanoi
6	Feb 11	depth first search/breadth first search
7	Feb 18	more search based graph algorithms
8	Feb 25	insert sort, some magic of analysis and the Shell sort	assignment 3 pdf, assignment 3 tex
9	Mar 4	partitions and quick sort, trivial traversals	assignment 4 pdf, assignment 4 tex
10	Mar 11			SPRING RECESS. NO CLASSES THIS WEEK
11	Mar 18	Review for exam	EXAM 1 on Friday
12	Mar 25
13	Apr 1
xx	Apr 8
14	Apr 15			NO CLASS: at conference Apr 17 and 19
15	Apr 22
16	Apr 29
17	May 6			FINAL EXAM 12:30-2:30 Wed May 8

References and Resources

Algorithms

Algorithms, most of which we showed in class.
Ineffective sorts from the xkcd comic.
The sounds of a quicksort and the sounds of other sorts. Pretty cool.

Python References

The Python Library Reference
The Python Language Reference
A Python Tutorial
examples-py.tar are some python examples I covered in another class

LaTeX References

AMS math guide
LaTeX for Computer Scientists
The Giant Book of Symbols
Cool tool that lets you draw a latex symbol and it will do pattern matching to look it up. Try it! Don't always pick the first symbol it picks.
The Source for all things TeX and LaTeX
examples-tex.tar are the notes I used when I talked about LaTeX in one of my classes
A weird LaTeX example just doing lots of things. It requires the files: latexGraph.png, latexHyenaBib.bib, latexStripedHyena.jpg

Services

Homework submission page. This is not just for final homework submission. This is not to be confused with other submission tools used in the CS department.
Submitting homework without a browser