Computer Science 360 Detailed Information

Purpose

The first part develops and analyzes some standard techniques for algorithm development which are widely applicable to computer science problems. The second part analyzes several formal models of computers so that their capabilities are known.
Prerequisites: CMPT 260 and 280, 6 credit units in 200-level MATH or STAT (excluding MATH 213 and STAT 244)

 

Instructors

Texts

  • Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006.

References

  • Elements of the Theory of Computation by Harry Lewis and Christos Papadimitriou, Prentice-Hall, 1998.

Course Files and Discussion

  • http://moodle.cs.usask.ca/ and look up 360.

Description

  1. Algorithms
    • Graph Algorithms
    • Greedy Algorithms
    • Divide-and-Conquer
    • Dynamic Programming
    • NP-completeness and Computational Intractability
    • Handling Hard Problems
  2. Machines
    • Finite Automata
    • Nondeterministic Finite Automata
    • Regular Languages
    • Context-free Languages
    • Pushdown Automata
    • Turing Machines

Marking

  • Assignments - 30% in total
    • 5 or 6 assignments, no programming involved
  • Examinations - 70% in total
    • 1 midterm exam - 20%
    • final exam - 50%

 

IMPORTANT! Please read:
1) All students must be properly registered in order to attend lectures and receive credit for this course.
2) Failure to write the final exam will result in failure of the course.
3) Failure to complete required course work will result in failure of the course.

Honesty

Students are expected to be academically honest in all of their scholarly work, including course assignments and examinations. Academic honesty is defined and described in the Department of Computer Science Statement on Academic Honesty at the site
http://www.cs.usask.ca/content/academichonesty/
This site has other documents on honesty, and a Online Declaration of Honesty that every student is required to complete.

 

If an instructor has reason to suspect academic dishonesty on an assignment, the instructor will not return the original assignment to the student. Instead it will be forwarded along with all relevant evidence to the Department Academic Dishonesty Panel. The Departmental Academic Dishonesty Panel consists of two faculty members appointed by the Department Head and one student member appointed by the CSSS. The Panel will deliberate on the case, possibly requiring testimony from the student(s) involved. The Panel, in consultation with the instructor, will decide whether the case should be forwarded to the Arts and Science Student Academic Affairs Committee for a disciplinary hearing or whether the case should be handled locally within the Department. Should the Panel find no evidence of dishonesty, the case will be excused. In cases where dishonesty is determined, the Panel may decide to issue a warning and delete any mark associated with that assignment. In such cases, a formal warning letter will be sent to the student, copied to the instructor and the Arts and Science Student Academic Affairs Committee, and no other academic penalty will be applied. If the student or instructor is dissatisfied with the Panel's decision, either party may request that the case be reviewed by the Student Academic Affairs Committee.

The Student Academic Affairs Committee treats all cases according to the University Policy and has the right to apply strict academic penalties (see
http://www.usask.ca/university_secretary/council/reports_forms/reports/09-27-99.php)

Missed Examinations

1) "Students who have missed an exam or assignment must contact their instructor as soon as possible. Arrangements to make up the exam may be arranged with the instructor. Missed exams throughout the year are left up to the discretion of the instructor if a student may make up the exam or write at a different time. If a student knows prior to the exam that she/he will not be able to attend, they should let the instructor know before the exam."

2) "Final exams of a student who is absent from a final examination through no fault of his or her own, for medical or other valid reasons, may apply to the College of Arts and Science Dean's office. The application must be made within three days of the missed examination along with supporting documentary evidence. Deferred exams are written during the February mid-term break for Term 1 courses and in early June for Term 2 and full year courses."