CPSC 221
Basic Algorithms and Data Structures
Summer Session 2014/2015
Course Information
(created on May 6, 2015; expect revisions)
Instructor:
Kurt Eiselt
[email protected]
Teaching Assistants:
To be announced
Office Hours:
For Kurt, anytime immediately after class on Monday, Wednesday, and Friday, in the classroom, for as long as you have questions. Send me email if you
feel the need to talk privately, and we'll set up an appointment.
For the TAs, our schedule is here.
Official Calendar Description:
Design and analysis of basic algorithms and data structures; algorithm analysis methods, searching and sorting algorithms, basic data structures,
graphs and concurrency.
Textbooks:
Objects, Abstraction, Data Structures and Design Using C++, Elliott B. Koffman and Paul A.T. Wolfgang, Wiley and Sons, 2006.
Discrete Mathematics with Applications (Fourth Edition), Susanna S. Epp, Brooks/Cole, 2011.
Programming Language:
For labs and assignments, you will be programming in C++. For the homework assignments, you may use any development environment you wish,
but all your C++ code must compile and run correctly on the Linux ugrad.cs.ubc.ca servers (such as galiano.ugrad.cs.ubc.ca) using GNU C++.
We do not teach C++ programming in CPSC 221. You are expected to learn the syntax and concepts of C++ on your own. We strongly recommend
that you read Chapters P and 1 of Objects, Abstraction, Data Structures and Design Using C++ before your first lab. We will provide pointers to other C++
resources on UBC Connect, and there is plenty of C++ programming information on the Internet, in the Computer Science Reading Room and in the UBC Library.
Your best resource for C++ help may be your teaching assistants, all of whom will know far more about C++ than your intrepid instructor does.
Tentative Grading Scheme:
Labs 10%
Assignments 10%
Midterm exam 30%
Final exam* 50%
* You must earn at least 50% of the possible marks on the final examination in order to pass the course, regardless of the marks you have received
for other evaluated components.
Very Tentative Schedule based on other instructors' offerings of this course (this schedule could change significantly once I figure out how deep a hole I have dug myself into):
Kurt Eiselt
[email protected]
Teaching Assistants:
To be announced
Office Hours:
For Kurt, anytime immediately after class on Monday, Wednesday, and Friday, in the classroom, for as long as you have questions. Send me email if you
feel the need to talk privately, and we'll set up an appointment.
For the TAs, our schedule is here.
Official Calendar Description:
Design and analysis of basic algorithms and data structures; algorithm analysis methods, searching and sorting algorithms, basic data structures,
graphs and concurrency.
Textbooks:
Objects, Abstraction, Data Structures and Design Using C++, Elliott B. Koffman and Paul A.T. Wolfgang, Wiley and Sons, 2006.
Discrete Mathematics with Applications (Fourth Edition), Susanna S. Epp, Brooks/Cole, 2011.
Programming Language:
For labs and assignments, you will be programming in C++. For the homework assignments, you may use any development environment you wish,
but all your C++ code must compile and run correctly on the Linux ugrad.cs.ubc.ca servers (such as galiano.ugrad.cs.ubc.ca) using GNU C++.
We do not teach C++ programming in CPSC 221. You are expected to learn the syntax and concepts of C++ on your own. We strongly recommend
that you read Chapters P and 1 of Objects, Abstraction, Data Structures and Design Using C++ before your first lab. We will provide pointers to other C++
resources on UBC Connect, and there is plenty of C++ programming information on the Internet, in the Computer Science Reading Room and in the UBC Library.
Your best resource for C++ help may be your teaching assistants, all of whom will know far more about C++ than your intrepid instructor does.
Tentative Grading Scheme:
Labs 10%
Assignments 10%
Midterm exam 30%
Final exam* 50%
* You must earn at least 50% of the possible marks on the final examination in order to pass the course, regardless of the marks you have received
for other evaluated components.
Very Tentative Schedule based on other instructors' offerings of this course (this schedule could change significantly once I figure out how deep a hole I have dug myself into):
|
Week 1 May 11 - 15 Week 2 May 18 - 22 Note: May 18 is a holiday -- no class Week 3 May 25 - 29 Week 4 June 1 - 5 Note: midterm exam in class on June 3 Week 5 June 8 - 12 Week 6 June 15 - 18 Note: classes end on June 18 -- there is no class on Friday, June 19 Week 7 June 22 - 26 |
Topics
Overview; Linked lists, stacks, and queues; Introduction to algorithm analysis Big O, Big Omega, Big Theta; Time and space complexity; Algorithmic analysis Induction and recursion; Loop invariants and program correctness; Sorting; Trees, tree traversal, and binary search trees Review; Tree rotation and B-trees; Priority queues and heaps; Hashing; Graphs Counting; Review Final exam is yet to be scheduled |
Readings from the Koffman text
Ch. 4.5 - 4.7, 5, 6 Ch. 2.6 Ch. 2.6 Ch. 7 Ch. 10.1, 10.4, 10.7 - 10.10 Ch. 8.1 - 8.4 Ch. 11.1, 11.2, 11.4, 11.5 Ch. 8.5 Ch. 9 Ch. 12.1 - 12.4 |
Readings from the Epp text (3rd edition in white, 4th edition in blue)
Ch. 9.2 / Ch. 11.2 Ch. 9.3 / Ch. 11.3 Ch. 5.1, 5.2, 7.1, 7.2, 4.2, 4.3, 4.5 / Ch. 6.1, 6.2, 7.1, 7.2, 5.2, 5.3, 5.5 Ch. 9.5 / Ch. 11.5 Ch. 11.5 / Ch. 10.5 Ch. 7.3 / Ch. 9.4 Ch. 11.1 - 11.4 / Ch. 10.1 - 10.4 Ch. 6.1 - 6.5 / Ch. 9.1 - 9.6 |
