Description: Design and analysis of basic algorithms and data structures; algorithm analysis methods, searching and sorting algorithms, basic data structures, graphs.

For information on prerquisites, corequisites, and the like, please see the UBC calendar entry for CPSC 221.

Texts:

• Epp, Susanna. Discrete Mathematics with Applications, 3rd or 4th edition, Thomson Learning Inc., 2004, ISBN 0-534-35935-0.
• Koffman, Elliot B. and Wolfgang, Paul A. T. Objects, Abstraction, Data Structures, and Design Using C++, John Wiley & Sons, Inc., 2006, ISBN 978-0-471-46755-7.
• Alternatively: find resources or readings that are a better fit for you, but we likely cannot support your use (e.g., indicating appropriate sections).

Office hours: See schedule

Labs: Labs are required and marked. Lab writeups may contain a "Pre-Lab" section, which you must complete before the lab! You should aim to finish your lab and get it marked by the end of your registered lab session, but if necessary, you may continue to work on it afterwards. To get credit for the lab, though, you must get it marked by the beginning of the next lab session in the lab section in which you are registered. You may not make-up missed labs by attending a lab section in which you are not enrolled.

Labs will introduce C++; however, as 2nd year students, much of the responsibility of learning the new language will fall on you. If you need C++ programming resources, check the textbook section of the website.

Evaluation:
Your final course mark will be based roughly on the following breakdown. The staff reserves the right to change this scheme (but do not anticipate using that right).

Labs		10%
"Assignments"		10%	Computed as max(assignments, midterm, final)
"Midterm"		30%	Computed as max(midterm, final)
Final Exam		50%

To pass the course, you must obtain a 50% overall mark and, in addition, you must pass the final exam. Students who fail the final exam will receive as their course grade the minimum of their normally computed grade and 45%.

Approximate Topic Schedule:

	Topics	Readings from the Koffman text	Readings from the Epp text (4th edition)
Background that you're supposed to already know			Basics: Ch 1 Functions: 7.1, 7.2, 7.3, 11.1 Induction: 5.2, 5.3, 5.4 Logic: Ch 2 Proofs: Ch 4 Quantifiers: Ch 3 Sets: 1.2, 6.1, 6.2, 6.3
Week 1 May 12-16	Overview; Linked lists, stacks, and queues; Introduction to algorithm analysis	Lists: 4.5 Stacks: 5 Queues: 6.1-6.3 Big-O: Ch 2.6 Optional: Iterators 4.6-4.7	Analysis of algorithms: 4.8, 11.3 Big-O Notation: 11.2 Summations: 5.2
Week 2 May 19-23	Big O, Big Omega, Big Theta; Summations; Induction; Recursion; Recurrence Relations	Big-O: Ch 2.6 Recursion: 7	Analysis of Binary Search: 11.4, 11.5 Big-O Notation: 11.2 Recurrence Relations: 5.7 Recursion: 5.6 Summations: 5.2
Week 3 May 26-30	Runtime Analysis; Recursion; Correctness of Recursive Algorithms; Loop invariants Trees, tree traversal, and binary search trees	Recursion: 7 Insertion Sort: 10.4 Trees: 8.1-8.4 AVL Trees: 11.1-11.2	Correctness of Algorithms: 5.5 InsertionSort: 11.3 Logs: 7.1, 7.2, 11.4 Trees: 10.5, 10.6
Week 4 June 2-6 Note: midterm in class June 4	Review Dictionaries: Successor, FindClosest, RangeQuery Priority Queues: Implemented with arrays or AVL trees PQSort	Priority Queues: pp. 489-490 Dictionaries (=Maps): 9.2, 9.6
Week 5 June 9-14	B-Trees Sorting: Select, Insert, Merge, Quick Hashing	B-Trees: 11.4-11.5 Sorting: 10.2, 10.4, 10.7, 10.9 Hashing: 9.3-9.5
Week 6 June 16-20	Graphs Counting Review	Graphs: Ch 12	Graphs: Ch 10 Counting: 9.1-9.6
Week 7 June 23-27	Exam, Thursday June 26

Communication: Most electronic communication should go to the discussion area on Piazza. (You are expected to read the Announcements on Piazza daily! Personal questions or those that might violate academic conduct standards if posted should go to cs221@ugrad.cs.ubc.ca for response by any staff member or to the individual staff member you wish to contact (see the home page).

Assignments: There will be roughly three programming assignments and three written assignments during the term.

• Programming Environment: You may use any development environment you wish, but all programming assignments must compile and run correctly on the Linux ugrad.cs.ubc.ca servers (such as lulu.ugrad.cs.ubc.ca) using GNU C++. See the computing and programming guideline pages for tips.

Submission: Programming assignments will submitted with the "handin" tool. Check handin's acknowledgment of your submission to see if your submission proceeded correctly. Written assignments will be submitted in the hand-in box for CPSC 221 (location will be announced).

• Schedule: Programming assignments will normally be due at 9PM on the due date. Written assignments will normally be due at 5PM on the due date.

• Late Policy: Late work will receive no credit, but we can be flexible if you contact us promptly, well before the due date. So, tell us if you're having trouble!

• Collaboration: See the academic conduct guidelines.

Exams: There will be one midterm exam and one final exam.

• Scheduling: Dates for the exams are TBD.

• Resources: TBD.

• Concession (missing the exam): Do not write an exam if a medical factor might significantly impair your performance. If you are unable to write a midterm exam due to illness, inform your instructor immediately, detailing the period during which you were ill, but do not present a doctor's note. The instructor will establish and explain accommodation at that time. If you are unable to write the final due to illness, contact your Faculty's advising office (e.g., the Science Undergraduate Advising office) immediately.

Academic Conduct:

Collaboration enhances the learning experience. We encourage collaboration in various ways throughout the course, subject to the rules stated here:

• Assignments: You may work on assignments in groups of two, and we encourage you to do so. (Specific assignments may allow larger groups; any change will be stated in the assignment handout.) Groups are described below. Your group may also work with any other person or resource subject to five rules:
  • The group must spend at least 10 minutes working on each problem independently before collaborating with others.
  • Collaboration with others must be limited to discussion and brainstorming. No record of any sort (e.g., written or electronic material) may be exchanged or leave the brainstorming session.
  • Each group must write up their own solution independently, using their own words to prove that they understand the problem on their own.
  • Groups must acknowledge all collaborators or sources of assistance in their submission, although you need only name CPSC 221 course staff, handouts, and required textbooks if you quote or adapt directly from them. You are allowed (and expected!) to record the names of people in brainstorming sessions with you.

• Labs: You are required to work on labs in groups of two (or possibly one group of three). Groups are described below.

• Groups:
  • Must indicate they are working together in the appropriate venue (on the front page/README for assignments, to the lab TA for labs).
  • Must submit only one joint solution to the lab/assignment.
  • Will receive one grade for the lab/assignment that applies to every group member (except in extreme circumstances).

  In lab, we require that you collaborate rather than, for example, working on individual parts of the lab and stitching the result together. We recommend the same for assignments. For advice on group work, speak with the teaching staff and check out All I Need to Know About Pair Programming I Learned in Kindergarten for a lighthearted but well-researched perspective on pair work in Computer Science (for programming but applicable to written assignments).

• Exams will follow the University's Rules Governing Formal Examination, including disallowing any communication by any means with anyone besides the exam's invigilators except where specifically noted in exam instructions.

Violation of any of these rules constitutes academic misconduct and is subject to penalties ranging from a grade of zero on a particular assignment to indefinite suspension from the University. If you are uncertain as to what is or is not reasonable collaboration, please contact the instructor. If you are having problems understanding or keeping up with the material, please contact your instructor or TA to discuss how we can fix the problem. Don't cheat!