Main Navigation (Top Menu) Secondary Navigation (Side Menu) Page Content

CISC-235* - Winter 2020 Title and Photo Table

CISC-235*

Data Structures

Winter 2020

Image by Alexandre Duret-Lutz, used under Creative Commons licence https://creativecommons.org/licenses/by/2.0/

Urgent Notices

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

External_Links

External Links	Queen's School of Computing
	Computing Students' Association
	Class Photo Gallery
	Learning - Your First Job (Paper by Dr. R. Leamnson) - ESSENTIAL READING
	Academic Integrity Statement from Faculty of Arts and Science

Announcements

Announcements

Date	Subject	Text

Return to top

Personnel

Personnel

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.

Monday	TBA
Tuesday	TBA
Wednesday	TBA
Thursday	TBA
Friday	TBA

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

Return to top

Course Information

CISC-235 Course Information

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.

Return to top

Schedule

Schedule_Table

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

Return to top

Course Plan and Record

Record Table

Week 1

Complexity Analysis

Tuesday, January 7

Plan:

Intro

Notes:

Introduction

Thursday, January 9

Plan:

Complexity

Notes:

Basic Operations

Friday, January 10

Plan:

Complexity

Notes:

It's Big-O Time

Week 2

Stacks, Queues and Trees

Tuesday, January 14

Plan:

Stacks

Notes:

Complexity Continued

Thursday, January 16

Plan:

Queues

Notes:

Theta Classification

Friday, January 17

Plan:

Trees

Assignment 1 due on January 19

Notes:

Finally, stacks

Week 3

Binary Search Trees

Tuesday, January 21

Plan:

Binary Search Trees

Revised Plan:

Finish Stacks

Notes:

Stacks to the Max

Stack Exercises

Thursday, January 23

Plan:

Binary Search Trees

Notes:

A Fair Tree, A Rattling Tree

Friday, January 24

Plan:

TEST 1

Solutions

Week 4

Red-Black Trees

Revised Plan: Binary Search Trees

Tuesday, January 28

Plan:

Binary Search Trees

Thursday, January 30

Plan:

Friday, January 31

Plan:

Ditto

Notes:

Full week's notes on Binary Search Trees

Week 5

Red-Black Trees

Revision: Still doing Binary Search Trees

Tuesday, February 4

Plan:

Red-Black Trees

Revised: BST Deletion

Thursday, February 6

Plan:

Red-Black Trees

Revised: BST Deletion Continued

Friday, February 7

Plan:

FINALLY : Red-Black Trees

Notes:

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:

B-Trees

Revised Plan:

Red-Black Trees

Thursday, February 13

Plan:

B-Trees

Revised Plan:

Red-Black Trees

Notes:

Complete notes on Red-Black tree insertion

Friday, February 14

Plan:

TEST 2

Solutions

*** Reading Week ***

Week 7

Hashing

Tuesday, February 25

Plan:

Hashing

Revision:

Proof that Red-Black Trees have O(log n) height

Thursday, February 27

Plan:

Hashing

Friday. Feb 28

Plan:

Hashing

Notes:

Clarification of details of Assignment 3

Week 8

Hashing

Tuesday, March 3

Plan:

Hashing

Thursday, March 5

Plan:

Hashing

Class cancelled due to illness

Friday, March 6

Plan:

More Hashing!

Complete notes on hashing so far (plus a bit more)

Assignment 3 due on March 8

Week 9

Heaps

Tuesday, March 10

Plan:

Heaps

Revised Plan:

Hashtag: still hashing

Notes: Some more useful notes regarding hashing, in prep for the test.

Thursday, March 12

Plan:

Heapsort

Revised Plan:

Say goodbye to hashing

Notes:

The beginning of the end of hashing

The end of the end of hashing

Friday, March 13

Plan:

TEST 3

Solutions

Week 10

Graphs

Cancelled

Tuesday, March 17

Plan:

Adjacency Matrices
Adjacency Lists

Class Cancelled

Thursday, March 19

Plan:

Depth-First Search

Class Cancelled

Friday, March 20

Plan:

Prim's Algorithm

Class Cancelled

Week 11

MST Algorithms

Revised:

Priority Queues, Heaps, Graphs

Tuesday, March 24

Plan:

Prim's Algorithm

Revised:

Priority Queues
Heaps

Notes:

Full notes on Priority Queues and Heaps (including HeapSort, which is not part of our reduced syllabus)

Thursday, March 26

Plan:

Kruskal's Algorithm

Revised:

Heap Implementation
Graphs:

Adjacency Matrices
Adjacency Lists

Notes:

First notes of Graphs, Adjacency Matrices and Adjacency Lists

Friday, March 27

Plan:

Kruskal's Algorithm
Disjoint Set Trees

Revised:

Breadth First Search (in previous notes)
Depth First Search

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:

Dijkstra's Algorithm

Revised:

Prim's Algorithm

Notes:

Prim and proper

Thursday, April 2

Plan:

Mystery

Revised:

Extended online office hours

Friday, April 3

Plan:

TEST 4 (online)

Assignment 4 due on April 3

Return to top

Assignments

CISC-235 Assignments

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

Return to top

Practice Problems

Practice Problems

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

Return to top

Recommended Readings

Recommended Readings

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/

Return to top

Sample Tests

CISC-235 Sample Tests

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

Return to top

Academic Integrity in CISC 235

CISC-235 Academic Integrity Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

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.

Each student in CISC-235 is required to confirm that they have read this statement on academic integrity and that they understand the consequences of any departure from academic integrity. Your assignments and tests will not be evaluated unless you complete this confirmation through onQ.

The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.

Return to top

Change Log

Change Log

Date	Log Entry
20200104	2020W website initialized
20200107	Assignment 1 posted
20200110	Class schedule corrected
20200111	Assignment 1 Marking Scheme posted Office Hours updated TA names posted
20200112	Complete notes for Week 1 posted
20200119	Complete notes for Week 2 posted Practice Test 1 posted
20200121	Practice Test 1 solutions posted Notes for 20200121 posted Stack Exercises posted (with 20200121 notes)
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	Happy Pi Day! Final hashing notes posted
20200323	Link to final hashing notes included in Record Table Record Table revised to show new plan for course Test 3 solutions posted Full notes on Priority Queues and Heaps posted First notes on Graphs posted
20200326	Notes on Depth-First Search posted
20200330	Practice Test 4 posted Final notes on Graphs posted
20200331	Marking guide for Assignment 4 posted Assignment 3 solution posted Practice Test 4 solutions posted

Return to top