Class Notes (1,100,000)
CA (620,000)
Queen's (10,000)
CISC (500)
Lecture 1

CISC235 Lecture 1: Week 1


Department
Computing
Course Code
CISC 235
Professor
Robin W Dawes
Lecture
1

This preview shows half of the first page. to view the full 2 pages of the document.
We considered a few problems:
1. How would you organize a dictionary to facilitate auto-
complete and/or spell-checking?
2. How would you represent the structure of the Internet so as to
efficiently determine good routes for email?
3. How would you segment an image file so as to minimize the
file size?
4. How would you efficiently store a list of "forbidden" words, so
that any word could be quickly tested for membership in the list, if
you were willing to have a small percentage of "acceptable" words
falsely reported as being in the list? Equivalently, how would you
store a list of existing user-names, so that when a new user selects
a user-name you can quickly determine if it has already been taken
- again, a small number of "false positive" results is acceptable.
5. How would you create a secure login system with usernames
and passwords in which the passwords are not stored, even in an
encrypted form, anywhere?
These problems all have two things in common: each one
- involves organizing information
- has a specific goal
This illustrates the first and crucial point about choosing a data
structure to organize a set of information - we need to know what
we want to do with it. Some data structures are particularly suited
for searching the set, while others are optimal for adding and
deleting members of the set, or finding subsets, etc. Thus we need
to think about the types of operations we may need to implement
for a data set, since these will definitely influence our decision.
You're Reading a Preview

Unlock to view full version