Queen's School of Computing CISC-235* - Winter 2018 Title and Photo Table

CISC-235*

Data Structures

Winter 2018


 

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

Urgent Notices
Internal LinksAnnouncements

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
Robin Dawes
Goodwin 537 
dawes AT cs DOT queensu DOT ca
http://sites.cs.queensu.ca/dawes/
533-6061 (but e-mail is a much better idea)
Office Hours: Until further notice, my office hours will be :
    Monday 2:00 - 4:00
    Thursday 9:30 - 11:30

TAs
Name
Email  
Office Hours
Picture

Katherine Baillie



Ian Chew



Sharleen Fisher



Daniel Hughes



Grace Pigeau



Filipe Roseiro Cogo



Marshall Ruse


Simon Ungar





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.  

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




Monday 10:30 - 11:20
Biosciences Auditorium
Wednesday 9:30 - 10:20 Biosciences Auditorium
Friday 8:30 - 9:20 Biosciences Auditorium

Assignment and Test Schedule


Date
Location
Test 1
January 31

Test 2 February 28

Test 3 March 19

Test 4 April 4

Assignment 1
January 24
submit on onQ
Assignment 2
February 19
submit on onQ
Assignment 3
March 16
submit on onQ
Assignment 4
April 9
submit on onQ



Return to top



Course Plan and Record

Record Table
Week 1
Complexity Analysis
Monday, January 8
Plan: Intro
20180108 Notes
Wednesday, January 10
Plan: Complexity
Friday, January 12
Plan: Complexity
20180110+20180112 Notes
Week 2
Stacks and Queues
Monday, January 15
Plan:
Wednesday, January 17
Plan:
Friday, January 19
Plan:
Notes for the week
Week 3
Binary Search Trees
Monday, January 22
Plan:
Wednesday, January 24
Assignment 1 due on January 24
Plan:
Friday, January 26
Plan:
Notes for the week
Week 4
Red-Black Trees
Monday, January 29
Plan: Binary Tree Deletion

Balanced Trees
Wednesday, January 31
TEST 1

Solutions
Friday, February 2
Plan: First Look at Red-Black Trees

Notes for the week

Week 5
Hashing
Monday, February 5
Plan:Well, we're still doing Red-Black Trees
Wednesday, February 7
Plan:

Notes for Monday and Wednesday

Friday, February 9
Plan: But we've finished them now

Notes for Friday
Week 6
More Hashing
Monday, February 12
Plan: Hashing
Wednesday, February 14
Plan: Chaining
Friday, February 16
Assignment 2 due on February 24
Plan: Linear Probing and Quadratic Probing


Notes on Hashing (so far)
*** Reading Week ***
Week 7
B-Trees (Actually, more hashing)
Monday, February 26
Plan: Double Hashing

Hashtag?  Hash browns?
Wednesday, February 28
TEST 2

Solutions
Friday, March 2
Plan: Choosing a Good Hashing Function

SNAHU
Week 8
Heaps
Monday, March 5
Plan: Heaps
Wednesday, March 7
Plan: Heaps

Friday, March 9
Plan: More Heaps!

Notes for the week, plus partial material for Monday March 12

Week 9
Graphs
Monday, March 12

Plan: Finishing Heaps (see March 9)
Wednesday, March 14

Plan: REALLY Finishing Heaps (see March 9)
Friday, March 16
Assignment 3 due on March 16


Plan:  Graph Theory

Introduction of BFS, Adjacency Matrices, Adjacency Lists
Week 10
MST
Monday, March 19
TEST 3

Solutions
Wednesday, March 21
Plan:  Depth-First Search

But what is it for?
Friday, March 23
Plan: Prim's Algorithm for finding a Minimum Weight Spanning Tree

A practical problem and a flexible solution
Week 11
MST Algorithms and
Dijkstra's Algorithm
Monday, March 26
Plan: Finish Prim
Wednesday, March 28
Plan: Really Finish Prim's MST Algorithm
Friday, March 30
Good Friday - no class
Week 12
Bloom Filters

Monday, April 2
Plan: Disjoint Set Trees

Kruskal and Disjoint Set Trees
Wednesday, April 4
TEST 4

Solutions
Friday, April 6
Plan: ... wooo, it's a mystery ...
Assignment 4 due on April 9

Bloom Filters

Demo Code


Return to top



Assignments

CISC-235 Assignments

Due Date
Assignment Instructions
Marking Scheme
11:59 PM, January 24 Search Party

11:59 PM, February 19 Arboriculture

11:59 PM, March 16
HOTNCU instructions

HOTNCU data file

11:59 PM, April 9
Choosing Connections at HOTNCU

Test_Cases.txt

Instructions and data, zipped for faster download




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 from 2017
Solutions
Test 2 from 2017
Solutions
Test 3 from 2017
Solutions
Test 4 from 2017
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
20180109
Updated due dates for assignments.
Assignment 1 posted.
20180114
Complete notes for Week 1 posted
20180121
Complete notes for Week 2 posted
20180122
Sample Test 1 posted
20180126
Sample Test 1 solutions posted
20180127
Complete notes for Week 3 posted
20180204
Complete notes for Week 4 posted
20180211
Notes for Week 5 posted
20180222
Notes for Week 6 posted
Solutions for Test 1 posted






















































































Return to top