Syllabus
From CS 531 Design and Analysis of Algorithms
Contents |
Instructor Information
| Name: | Alden Wright |
| Office: | 407 Social Science |
| Telephone: | (406) 243-4790 |
| Fax: | (406) 243-5139 |
| Email: | alden.wright@umontana.edu |
| CAS Webpage: | CAS Web Page |
| CS Webpage: | Web Page |
| Office Hours: | MWF 10:00--12:00 or just stop in. However, I will not have much time just before class (11 am to 2 pm Tuesdays and Thursdays) since I will usually be preparing for class. |
Online Tools
As you have no doubt noticed, the course will make heavy use of this wiki.
Textbooks
Primary Text Note: this book is required despite not being ordered at the bookstore. I thought that it would be considerably cheaper for students to buy this book online.
| Title: | Introduction to Algorithms |
| Author: | Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein |
| Edition: | Second Edition |
| Publisher: | 2001 McGraw Hill |
Supplemental Text: A more intuitive apprach to algorithms
| Title: | How to Think About Algorithms |
| Author: | Jeff Edmonds |
| Edition: | First Edition |
| Publisher: | 2008 Cambridge University Press |
| Online URL: | http://www.cse.yorku.ca/~jeff/notes/3101/TheNotes.pdf |
Resources
Most class material will be posted on this wiki. Blackboard is enabled, and will be used primarily for the digital drop box and for reporting grades.
Prerequisites
- Discrete math such as Math 225. We will be doing proofs in this course, including induction proofs.
- Two semesters of calculus such as Math 152-153. We will use limits and do limit proofs, and we will use l'Hopital's rule.
- Data structures such as CS 241.
- A willingness to work.
Course Objectives
After taking this course, students will be able to;
- Prove the correctness of simple algorithms
- Understand asymptotic notation
- Analyze simple iterative and recursive algorthms
- Use the divide-and-conquer, greedy, and dynamic programming paradigms to design algorithms
- Learn a variety of useful algorithms
Meeting Times/Place
| Time: | Monday, Wednesday, Friday 2:10 - 3:00 |
| Place: | Social Science room 254 |
Final Exam Time and Place
| Time: | Tuesday, May 12, 3:20-5:20 |
| Place: | Social Science room 254 |
Grading Policy
Grading Breakdown
Grades of A-F will be assigned based on a percentage of the total possible points earned. The break points are as follows.
| A | 94-100 |
| A- | 90-93 |
| B+ | 87-89 |
| B | 83-86 |
| B- | 80-82 |
| C+ | 77-79 |
| C | 73-76 |
| C- | 70-82 |
| D+ | 67-69 |
| D | 63-76 |
| D- | 60-62 |
| F | 0-59 |
Assessment
Grades will be based upon the following forms of evaluation.
| Component | Description of Component | Percent of Grade |
|---|---|---|
| Group Assignments | These are assignments that will be completed in a group. They will be done partly out of class and partly in class. Normally, the entire group will receive the same grade for these assignments. However, I reserve the right to lower the grade of an individual who did not adequately participate in the solution to be problem. | 30% |
| Problem Sets | Individually prepared, these will be answers to assigned problems. Mostly they will be from the Cormen text. Some collaboration is allowed (see below), but each student must write up his/her own solution. | 30% |
| Exams | Traditional closed-book exams. There will be 2 midterms and 1 final. | 40% |
Other Issues Related to Grades
Flexibility of Grading Breakdown
I reserve the right to make changes to the grading policy that will be favorable to students grades.
Pass Fail
Students taking the course pass/no pass are required to earn a grade of C or better in order to pass.
Attendance Policy
The learner centered design of the course will make attendance neccessary. If you know in advance that you will need to miss class, I encourage you to come speak to me. Acknowledging that everyone misses class occasionally, at least one of the in class assignments will be discarded before grades are computed.
Late Assignments
Other than in in exceptional circumstances, such as family emergencies, late homework will not be accepted. If you do have an emergency that causes you to miss an important classroom activity or an assignment, let me know by e-mail as soon as possible.
Academic Integrity
As a student of the University of Montana, you are responsible for upholding all rules in the student conduct code. There are aspects of that code that are of particular importance in Computer Science courses. The electronic nature of the many assignments facilitates their dissemination. To be clear, from the student conduct code:
- 1. Plagiarism: Representing another person's words, ideas, data, or materials
- as one's own.
- 2. Submitting work previously presented in another course: Knowingly making
- such submission in violation of stated course requirements.
Of course, all other aspects of the student conduct code will be enforced as well. These are just the two that are commonly violated.
I will interpret these guidelines to the letter. Students found in violation will be penalized with the maximum punishment permitted in the student conduct code. That is to say, the matter will be handed over to the Academic Dean and academic misconduct proceedings will take place. In order to reconcile encouraged interaction between students and the academic misconduct policies, you must credit other students in your work. If, for example, you worked with others to develop some algorithm, or solve some homework problem, specifically mention those that you have worked with in the assignment that is handed in. Similarly, you must properly document and credit any online resources that you use.
If you collaborate with others, the instructor has the right to question you about the material turned in. If it is evident that your understanding of what you turn in is weak, your grade will be lowered.
Students are to uphold a level of conduct becoming of adults. The use of profanity and abusive speech is not permitted under the student conduct code, and will not be tolerated in this course.
Disabilities
Students with disabilities are encouraged to meet with me at the beginning of the semester to discuss any accommodations they require. Please let me know early.
Other Issues
- Turn off your cellphone, or set it to vibrate in class. Take the call outside the classroom.
- Do not talk in the classroom during lecture. Take it outside.
Course Schedule
Since this will be the first time that I have taught the course in this learner-center fashion, I don't know how much we will cover. However, we should cover most of the following chapters of the Cormen textbook:
1. The role of algorithms in computing 2. Getting started 3. Growth of functions 4. Recurrences 7. Quicksort 15. Dynamic programming 16. Greedy algorithms 34. NP-completeness.
If time, we may also cover parts of the following algorithms:
5.Probabilistic analysis and randomized algorithms. 17. Amortized analysis 22. Elementary graph algorithms. 23. Minimum spanning trees. 35. Approximation algorithms.
Instructor's Rubric
Completed by the instructor, about each group.
| Grade | 100 | 85 | 70 | 50 |
|---|---|---|---|---|
| Content | Solution was both correct and complete. | The solution had a few minor errors or missing components. The idea is correct. | The solution has generally the right idea, but there are substantial errors in the implementation. | The solution has serious errors, but the team or the individual made a good effort. |
Cross assessment rubric
To be completed by each member of each group, about each other member of the group.
| Points | 3 | 2 | 1 | 0 |
|---|---|---|---|---|
| Participation | Participates actively. Helps direct the group in setting goals. Helps direct group in meeting goals. Thoroughly completes assigned tasks. Actively participates in helping the group work together better. | Participates in group. Shows concern for goals. Participates in goal setting. Participates in meeting goals. Completes assigned tasks. Demonstrates effort to help the group work together. | Sometimes participates in group. Shows concern for some goals. Participates marginally in goal setting. Participates in meeting goals. Completes some assigned tasks. | Chooses not to participate. Shows no concern for goals. Impedes goal setting process. Impedes group from meeting goals. Does not complete assigned task.Promotes fragmentation of group |
| Communication | Shares many ideas related to the goals. Encourages all group members to share their ideas. Listens attentively to others. Respectful of other people's ideas. | Freely shares ideas.Listens to others. Considers other people's feelings and ideas. | Shares ideas when encouraged. Allows sharing by all group members. Listens to others. Considers other people's feelings and ideas. | Discourages sharing. Does not participate in group discussions. Does not listen to others. Inconsiderate of others. |
Acknowledgements
I would like to thank Dr. Jesse Johnson who had the idea of using a Wikimedia server to support a class. I also borrowed part of the wording of this syllabus from his CS 477/577 syllabus.
