CPSC 210_101_2016W

Course Title: 
Software Construction
Instructor(s): 
Course Info
Course Number: 
CPSC 210
Section: 
101
Term: 
Term 1
Location
Building: 
DMP
Room: 
310
Dates
Year: 
2016 Winter
Days: 
MWF
Time (start): 
12:00 PM
Time (end): 
1:00 PM
Date (start): 
Sep 06, 2016
Date (end): 
Dec 02, 2016

Design, development, and analysis of robust software components. Topics such as software design, computational models, data structures, debugging, and testing.

Extended Description: 

The topics that we will be discuss in this course fall into two main categories. First, we will look at techniques that we can use to design efficient data structures and algorithms. Second, we will learn tools that make it possible to prove the correctness and the efficiency of the algorithms and data structures that we designed. More specifically, we will look at the following broad topics (not necessarily in this order):

  • Searching and sorting;
  • Data structures, such as skip lists.
  • Mathematical tools, like O notation, recurrence relations, and amortized analysis;
  • Algorithm design techniques, for instance randomization, greediness and dynamic programming.

Much of the material is formal (mathematical) in nature, and hence proofs will constitute an important part of the course.

At the end of the course, you will be able to:

  1. Recognize which algorithm design technique(s), such as divide and conquer, prune and search, greedy strategies, or dynamic programming was used in a given algorithm.
  2. Select and judge several promising paradigms and/or data structures (possibly slightly modified) for a given problem by analyzing the problem's properties.
  3. Implement a solution to a problem using a specified algorithm design paradigm, given sufficient information about the form of that problem's solution.
  4. Select, judge and apply promising mathematical techniques (such as asymptotic notations, recurrence relations, amortized analysis and decision trees) to establish reasonably tight upper and lower bounds on the running time of algorithms.
  5. Recognize similarities between a new problem and some of the problems they have encountered, and judge whether or not these similarities can be leveraged towards designing an algorithm for the new problem.

a place of mind, The University of British Columbia

 

ICICS/CS Building 201-2366 Main Mall
Vancouver, B.C. V6T 1Z4 Canada
Tel: 604-822-3061 | Fax: 604-822-5485
General: help@cs.ubc.ca
Undergrad program: undergrad-info@cs.ubc.ca
Graduate program: grad-info@cs.ubc.ca

Emergency Procedures | Accessibility | Contact UBC | © Copyright The University of British Columbia