Description:
The study and analysis of algorithms, their complexity and supporting data structures. Topics include searching, sorting, mathematical algorithms, tree and graph algorithms, the classes of P and NP, NP-complete and intractable problems, and parallel algorithms.

This course has a CW designation as a writing course.

Prerequisites:    CS 240, MA 160, and MA 210 or MA 116

Class Times and Locations:
TuTh     1:00pm - 2:20pm     C-210 Brumbaugh Academic Center
M          4:00pm - 4:55pm     C-102 Brumbaugh Academic Center

Instructor:    Dr. Gerald Kruse

Phone:          641-3595

Office:          C-205A Brumbaugh Academic Center

E-mail:         kruse@juniata.edu

Office Hours:  For the most up-to-date, see http://faculty.juniata.edu/kruse/office.htm

Textbook:        Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest, and Stein. ISBN: 978-0262-03384-8
Any CD's containing the implementation of algorithms from the text is optional.

Grading (Dates tenative):
Exam 01, Thurs 18.Mar 100 pts.
Exam 02, Tues 04.May100 pts.
Writing Assignments, approx 150 pts.
Homework Assignments, approx 150 pts.
Class Attendance, Participation, and Professionalism 25 pts.
                       

Participation:
Each student will be expected to present at least one homework problem to the rest of the class over the course of the semester. Volunteers will be solicited before students are randomly chosen. Additionally, you may earn a bonus point for asking a good, insightful question during discussion section. Students are expected to attend and participate in each class, and act with their peers and instructor in a professional manner.

Homework: (as always, show your work or include your Maple worksheet, where appropriate)
HW01 due 01/25 (upload in Moodle): Read Chap. 1, E 1.1 - 4,  E 1.2 - 2,  E 1.2 - 3,  P 1-1(only thru one day)
HW02 due 02/01 (upload in Moodle): Read Chap. 2, A.1-1(pg. 1149), A.2-1(pg. 1156), C.1-9(pg. 1188), E 2.2 - 1, E 2.2 - 2, E 2.2 - 4, E 2.3 - 1, E 2.3 - 3, P 2-3 (parts a and b only)
HW03 due 02/08 (upload in Moodle): Read Chap. 3, Chap. 4 (read Chap 28 Sec. 2 if you have the 2nd edition), P 2-2 (part d only, be sure to clearly identify the worst-case, though), E 3.1 - 3, E 3.1 - 4, E 4.4-6 (if you have the 2nd edition this problem is E 4.2 - 2)
HW04 due 02/15 due 02/22 (upload in Moodle): Read Chap. 7, E 4.2-1 (if you have the 2nd edition this problem is E 28.2 - 1), E 4.2-2 (this problem is not in the 2nd edition ), E 7.1 - 1 array of <13, 19, 9, 5, 12, 8> only , E 7.1 - 2, E 7.2 - 2, E 7.2 -3
HW05 due 02/21: Read Chap. 6, E 6.1 - 1 , E 6.1 - 2, E 6.1 - 6, E 6.2 -1
HW06 due 03/01 due 03/04: Read Chap. 9 and 8,E 6.2 - 3 , E 6.2 - 4, E 6.3 - 2, E 6.5 -1, E 6.5 -2, P 9-1, E 8.2 - 3, E 8.3 - 4
HW07 due 03/17: Read Chap. 12, E 12.1 - 1, E 12.1 - 2, E 12.2 - 1, E 12.2 - 5, P12 - 2

Writing Assignments:
Writing Assignment 01 (upload in Moodle)
Writing Assignment 02 (upload in Moodle) due Mon, 15.Feb
Writing Assignment 03 (upload in Moodle) first draft due Fri, 26.Feb at 5:00pm Mon, 01.Mar at 4:30pm, final draft due Fri, 05.Mar at 5:00pm


Code:
Sorts.java

Additional links:    Partition Worksheet     Google's Ranking Changes      Timing in Java and C++      Excel Tips      Running Visual C++      An Interesting Discussion of Euler's Sums      Sum of the squares of inverses      Running of the Squirrels      Herding Cats     Bambi Meets Godzilla

Content:
Growth of Functions / Summations, Recurrence Relations, O( ) sorts, Heapsort, Quicksort, other O( ) sorts, sorting in linear time, Medians and Order Statistics, Hash Tables, Binary Search Trees, Red-Black Trees, Augmenting Data Structures, Elementary Graph Algorithms, Pattern Matching, Internet Algorithms, NP-Completeness

Sorting Animations

The home of Zestful Algorithms.

Standard Course Policies: For the most up-to-date, see http://faculty.juniata.edu/kruse/policies.htm