CS3851 -- Algorithms

This course extends the study of algorithms introduced in CS-2851. Topics covered include searching, sorting, selection, graph structures, traversal algorithms, and P/NP complete problems. Applications such as data compression, optimization problems and database indexing are also discussed. Laboratory activities include the implementation and comparison of problem-specific algorithms. (prereq: CS-2851, SE-280, MA-230) (3-2-4)

Outcomes

Upon successful completion of this course, the student will:

  • apply asymptotic time complexity analysis to choose among competing algorithms.
  • construct and solve recurrence equations describing the asymptotic time complexity of a given algorithm.
  • implement sorting algorithms such as heapsort and quicksort.
  • describe how graph and tree structures are implemented.
  • describe similarities and differences between breadth-first and depth-first search techniques.
  • compare and contrast at least two minimum spanning tree alogrithms.
  • identify the use of dynamic programming techniques in algorithmic design.
  • describe the implications of demonstrating that a particular algorithm is NP complete.
  • list at least three engineering applications of algorithmic design and analysis.

The above course description and goals were taken from the official course description.

General Course Policies

Please review the general course policies webpage.

Textbook

Introduction to Algorithms e/2, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press and McGraw-Hill, 2001. (errata list)

Presentation

Each student will be responsible for a 12 minute oral presentation of an algorithm or concept related to this course. The topic should be unique and not covered in class. A one page abstract describing the topic is due by the end of week 6. Presentations will be scheduled for weeks 9 and 10. Students are advised to take this assignment seriously as it is worth more than a lab grade. A typical student should plan to allocate 0.5-2 hours selecting a topic, 4 hours researching the topic, 4 hours developing a presentation, and 1 hour practicing.

Homework

Homework assignments will be given throughout the quarter. You are encouraged to work on the homework in groups, but you should not turn in any solutions that you do not understand completely (I may quiz you on what you submit). At least 25% of the midterm and final will be problems from the homework or directly related to homework problems.

Each problem will be graded on the following scale:

  • -3 points: substantially incorrect
  • 0 points: minor mistakes, unorganized, or unclear
  • 3 points: Clearly presented and correct
When calculating your final grade, I will add your average homework problem score to your lab/exam grade. For example, suppose your grade for all exams and lab assignments is 86.3%. If you do not turn in any homework, your final grade will be 83.3% (BC). If you submit correct and clearly presented solutions to all of the problems, your final grade will be 89.3% (AB).

Laboratory

Unless stated otherwise, all laboratory assignments will be completed in teams of two. One lab report should be submitted for each team. All Lab assignments are worth 50 points per week (i.e., a two week lab assignment is worth 100 points).

My Schedule

Time Mon Tue Wed Thu Fri
11:00     Dr. Uphoff
Dr. Sebern
Lunch w/
Students*
XX
12:00 Mentor Meal Dr. Durant SE1020-L3
S362
SE1020 Plan
1:00 Dept Mtg SE1020
S362
SE1020
S362
2:00 Office Hour CE2800-2L
S314
Office Hour CS3851-2L
S362
3:00 CS3851
L104
CS3851
L104
CS3851
L104
4:00 CE2800
L104
CE2800
L104
CE2800
L104
 

* I would like to have lunch with you individually or as a group to get to know you better. If we eat in RWJ, housing will pick up my lunch bill. If you would prefer to eat elsewhere, we will each be responsible for our own bill. Feel free to suggest another time if the time above does not work for you.

Grading

Presentation: 15%
Lab Projects: 40%
Midterm Exam: 20%
Final Exam: 25%
Total: 100%
Note: your exam scores must average above 50% in order to pass this course.

  • © 2001-2015 Dr. Christopher C. Taylor •
  • Office: L-343 •
  • Phone: 277-7339 •
  • npǝ˙ǝosɯ@ɹolʎɐʇ