CISC-235*Data StructuresWinter 2020 |
Internal Links | Announcements | |
Personnel | ||
Course Information | ||
Schedule | ||
Course Plan and Record | ||
Assignments | ||
Practice Problems | ||
Recommended Readings | ||
Sample Tests | ||
Academic Integrity in CISC 235 | ||
Change Log | ||
Date | Subject | Text |
Instructor |
Dr. Robin W. Dawes |
|||||||||
Goodwin 537 |
||||||||||
dawes
AT cs DOT queensu DOT ca I typically receive more than 100 email messages each day. I cannot guarantee a response to any message - not even if you put "URGENT" in the subject line. During the COVID-19 outbreak the amount of email arriving in my inbox has escalated to the point at which email is effectively useless - the noise is totally swamping the signal. Please use the daily online office hours to communicate with me directly. |
||||||||||
http://sites.cs.queensu.ca/dawes/ |
||||||||||
533-6061 (but speaking to me in
person is a much better idea) - this phone line is not being
monitored during the COVID-19 outbreak. |
||||||||||
Office Hours: Office hours during the COVID-19 outbreak will be held online every day. The times of online office hours will be confirmed on a daily basis.
|
TAs |
Name |
Email |
Office
Hours |
Picture |
Shrey Anand |
sa201 |
|||
Katherine Baillie |
kb180 |
|||
Lea Cerron |
lc147 |
|||
Jonah Isen |
jdi1 |
|||
Maxwell Keleher |
mk191 |
|||
Benjamin Lammers |
bdl1 |
|||
Yueyang Liu |
yl77 |
|||
Jinghua Zhong |
jz61 |
Calendar
Description |
Design and implementation of advanced data structures and related algorithms, including correctness and complexity analysis. Efficient implementation of lists, sets, dictionaries, priority queues, trees, graphs, and networks using arrays, hash tables, heaps, and hierarchical linked structures. String and graph problems, such as string matching and shortest path. External storage and input-output complexity. |
Text |
Introduction to Algorithms, Third Edition, Cormen, Lieserson, Rivest, Stein |
Syllabus |
pretty much what the calendar says |
Marking Scheme |
4 Assignments - lowest counts 4%, the
other three count
8%
28% 4 Tests - lowest counts 12%, the other three count 20% 72% There are no make-up tests in CISC-235. If you miss a test due to valid extenuating circumstances (which do not include social activities or family gatherings) I will revise your marking scheme. You must have an overall passing grade on the tests (ie at least 36% out of the possible 72%) in order to pass the course. If you do not have a passing grade on the tests your final grade will be based on your test grades only.
Students with special needs are responsible for contacting the instructor at least a week before each test. Please see the Queen's Disability Services page for students for more information. |
Class
Schedule |
Tuesday 9:30 - 10:20 |
All classes are in Dupuis Auditorium |
Thursday 8:30 - 9:20 | ||
Friday 10:30 - 11:20 | ||
Assignment
and Test Schedule |
Date |
Location |
Test 1 |
January 24, 2020 |
Dupuis Aud and Ellis Aud |
Test 2 | February 14, 2020 |
Dupuis Aud and Ellis Aud |
Test 3 | March 13, 2020 |
Dupuis Aud and Ellis Aud |
Test 4 | April 3, 2020 |
online |
Assignment 1 |
January 19 |
submit on onQ |
Assignment 2 |
February 9 |
submit on onQ |
Assignment 3 |
March 8 |
submit on onQ |
Assignment 4 |
March 29 |
submit on onQ |
Week 1 Complexity Analysis |
Tuesday, January 7 Plan:
Introduction |
Thursday, January 9 Plan:
Notes: |
Friday,
January
10 Plan:
It's Big-O Time |
Week 2 Stacks, Queues and Trees |
Tuesday, January 14 Plan:
Notes: |
Thursday, January 16 Plan:
Notes: |
Friday,
January
17 Plan:
Notes: Finally, stacks |
Week 3 Binary Search Trees |
Tuesday, January 21 Plan:
Revised Plan:
Notes: |
Thursday, January 23 Plan:
Notes: |
Friday,
January 24 Plan:
|
Week 4 Red-Black Trees Revised Plan: Binary Search Trees |
Tuesday, January 28 Plan:
|
Thursday, January 30 Plan:
|
Friday,
January 31 Plan:
Notes: Full week's notes on Binary Search Trees |
Week 5 Red-Black Trees Revision: Still doing Binary Search Trees |
Tuesday, February 4 Plan:
|
Thursday, February 6 Plan:
|
Friday,
February 7 Plan:
Full week's notes on BST Deletion, AND Intro to Red-Black Trees Assignment 2 due on February 9 |
Week 6 B-Trees Revision: RB Trees |
Tuesday, February 11 Plan:
Revised Plan:
|
Thursday, February 13 Plan:
Revised Plan:
Notes: Complete notes on Red-Black tree insertion |
Friday,
February 14 Plan:
|
*** Reading Week *** | |||
Week 7 Hashing |
Tuesday, February 25 Plan:
Revision: Proof that Red-Black Trees have O(log n) height |
Thursday, February 27
|
Friday.
Feb 28 Plan:
Notes: Clarification of details of Assignment 3 |
Week 8 Hashing |
Tuesday, March 3 Plan:
|
Thursday, March 5 Plan:
Class cancelled due to illness |
Friday,
March 6 Plan:
Complete notes on hashing so far (plus a bit more) Assignment 3 due on March 8 |
Week 9 Heaps |
Tuesday, March 10 Plan:
Revised Plan:
Notes: Some more useful notes regarding hashing, in prep for the test. |
Thursday, March 12 Plan:
Revised Plan:
Notes: The beginning of the end of hashing
|
Friday,
March 13 Plan:
|
Week 10 Graphs Cancelled |
Tuesday, March 17 Plan:
Class Cancelled |
Thursday, March 19 Plan:
|
Friday,
March 20 Plan:
Class Cancelled |
Week 11 MST Algorithms Revised: Priority Queues, Heaps, Graphs |
Tuesday, March 24 Plan:
Revised:
Notes: |
Thursday, March 26 Plan:
Revised:
Notes: First
notes of Graphs, Adjacency Matrices and Adjacency Lists |
Friday,
March 27 Plan:
Assignment 4 due on March 29 - extended to April 3 Notes: Into the Depths |
Week 12 Dijkstra's Algorithm Revised: MST, Prim's Algorithm |
Tuesday, March 31 Plan:
Revised:
Notes: |
Thursday, April 2 Plan:
Revised:
|
Friday,
April 3 Plan:
Assignment 4 due on April 3 |
Due
Date |
Assignment
Instructions |
Marking Scheme | Sample Solutions |
January 19, 2020 | Search and Rescue? | Assignment 1 Marking Scheme |
|
February 9, 2020 |
Stack Attack |
Assignment 2 Marking Scheme |
My Pseudo-code Solutions with Explanation (as
provided to TAs) My Python 3 Solutions |
March 9, 2020 |
"Forests unclutter the mind" |
Assignment 3 Marking Scheme |
My
Python 3 Solution |
March 29, 2020 |
HOTNCU HOTNCU_project_names_2020.txt |
Assignment 4 Marking Scheme |
Source |
Exercises |
http://www.cs.wustl.edu/~sg/CS241_FL99/hw1-practice.html | 2, 3, 4 |
http://tinyurl.com/6pkjjdu | 3, 4, 5, 6, 8, 9, 13, 14 |
http://tinyurl.com/82sr5p5 | 1, 2, 3, 4, 5 |
Cormen, Leiserson, Rivest, Stein,
Chapter 6, Exercise Set 6.1 |
1, 3, 4, 5, 6, 7 |
CLRS, Chapter 6, Problems |
Problem 6-2 |
CLRS, Chapter 11, Exercise Set 11.2 |
2, 3 |
CLRS, Chapter 11, Exercise Set 11.4 |
1 |
CLRS, Chapter 22, Exercise Set 22.1 |
1, 2, 3, 5 |
CLRS, Chapter 22, Exercise Set 22.2 |
4, 5, 6, 7 |
CLRS, Chapter 22, Exercise Set 22.3 |
11, 12 (for these, use our definition of the DFS algorithm - much simpler) |
CLRS, Chapter 22, Problems |
Problem 22-1 |
CLRS, Chapter 23, Exercise Set 23.1 |
1, 5, 10 |
CLRS, Chapter 23, Exercise Set 23.2 |
2 |
Source |
Section |
Comments |
Learning
(Your
First Job) |
All |
Essential reading for all students |
Computer Science For Fun | Any | purely recreational |
Algorithms and Data Structures (Wirth) | Any - this book is an excellent resource for anyone studying data structures. | The link to the free PDF version is on Line 6 under "Oberon Books" |
The
Art of Computer Programming (Knuth) |
The four volumes of TAOCP will teach you more about Computer
Science than any other source. Knuth is a monster. |
This is just a link to the Wikipedia page - the books themselves
are available from Amazon (and "other sources"). |
Introduction to Algorithms (CLRS) | 2.2 | |
CLRS | 2.3.2 | |
CLRS | 3.1 | |
https://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29 | stacks | |
CLRS | 10.1 | stacks |
http://www.c4learn.com/data-structure/c-program-stack-convert-decimal-to-binary/ | example of using a stack | |
CLRS |
10.4 |
|
CLRS |
12.1 |
|
CLRS | 12.2 |
|
CLRS | 12.3 |
|
CLRS |
13.1 |
|
CLRS |
13.2 |
|
CLRS |
13.3 |
|
CLRS |
Problem 13-3 (Page 333) |
|
The Interwebs |
http://en.wikipedia.org/wiki/AVL_tree |
|
CLRS |
11.2 |
|
CLRS |
11.3 |
|
CLRS |
11.4 |
|
CLRS |
6.1 |
|
CLRS |
6.2 |
|
CLRS |
6.3 |
|
CLRS |
6.4 |
|
CLRS |
6.5 |
|
CLRS |
22.1 |
|
CLRS |
22.1 |
|
CLRS |
22.3 |
|
CLRS |
22.4 |
|
CLRS |
23.1 |
|
CLRS |
23.2 |
|
CLRS |
24.3 |
|
Wikipedia |
http://en.wikipedia.org/wiki/Trie |
|
Wikipedia |
http://en.wikipedia.org/wiki/Bloom_filter |
|
Numberphile |
https://curiosity.com/videos/rsa-129-numberphile-numberphile/ |
Numberphile videos are always good -
this one is about RSA cryptography |
Buzzfeed - Python Dicts and hashing | https://www.buzzfeed.com/andrewkelleher/deep-exploration-into-python-lets-review-the-dict-module?utm_term=.hxLOd7l1m2#.vjVykGAeRr | this link provided by a past CISC-235 student |
Atlantic - From Aristotle to Computers | https://www.theatlantic.com/technology/archive/2017/03/aristotle-computer/518697/ |
Test 1 | Test 1 from 2018 Solutions |
Note: this test was given later in the term in 2018, so more
material had been covered. Our test will not have any
questions on binary trees. |
Test 2 | ||
Test 3 | Sample
Questions The sample questions on binary trees that were distributed before Test 2 are still relevant |
|
Test 4 | Test
4 from 2018 Solutions |
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 on the Arts and Science website) and from the instructor of this course.
Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification. Falsification includes attempting to obtain, or accepting, a grade that is not solely and completely based on the graded work as submitted.
In CISC 235, academic integrity means that the work you hand in as your
own (tests and assignments) really is your own. You may ask other people
for general help in the course -- by which I mean general explanations and
help with practice problems that are not being handed in. You may talk in
general terms with other students about marked assignments, as in
discussing strategies ("how are you handling the case where the list is
empty?") or requirements ("are we supposed to print out all the data or
just the average?"). You may not share code or even pseudo-code with
anyone else.
CISC-235 has a zero-tolerance policy regarding departures from academic integrity. There will be no exceptions.
Given
the seriousness of these matters, actions which contravene the
regulation on academic integrity carry sanctions that can range from a
warning or the loss of grades on an assignment to the failure of a
course to a requirement to withdraw from the university.
The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.
Date | Log Entry |
20200104 |
2020W website initialized |
20200107 |
Assignment 1 posted |
20200110 |
Class schedule corrected |
20200111 |
|
20200112 |
Complete notes for Week 1 posted |
20200119 |
|
20200121 |
|
20200122 |
Assignment 2 posted |
20200126 |
Remaining notes for Week 3 posted |
20200202 |
Complete notes for Week 4 posted |
20200206 |
Assignment 2 Marking Scheme posted |
20200209 |
Complete notes for Week 5 posted |
20200211 |
Assignment 2 Solution posted |
20200212 |
Test 1 Solutions posted |
20200219 |
Assignment 3 posted |
20200303 |
Complete notes on Red-Black Trees posted |
20200304 |
Clarification notes for Assignment 3 posted (in the Course Record
section since this material was covered in class) |
20200305 |
Assignment 3 Marking Scheme posted |
20200306 |
Test 2 Solutions posted |
20200307 |
First set of Hashing notes posted |
20200308 |
Sample questions for Test 3 posted |
20200311 |
More hashing notes posted |
20200313 |
Assignment 4 posted |
20200314 |
|
20200323 |
|
20200326 | Notes on Depth-First Search posted |
20200330 |
|
20200331 |
|
|
|